PDF de programación - Introducción a LISP

2 INTRODUCCIÓN A LISP

El objetivo de este capítulo es que puedan programar en Lisp tan pronto como sea
posible. Al final de la misma, conocerán lo suficiente de Lisp como para comenzar a
escribir sus propios programas. Este material debe revisarse como un tutorial básico
sobre el lenguaje Lisp. Esta presentación se complementa con la revisión del capítulo
tres del libro de Seibel [22].

￿.￿ ￿￿￿￿￿￿￿￿￿￿￿

Es particularmente cierto que la mejor forma de aprender Lisp es usándolo, porque
se trata de un lenguaje interactivo. Cualquier sistema Lisp, incluye una interfaz in-
teractiva llamada top-level. Uno escribe expresiones Lisp en el top-level, y el siste-
ma despliega sus valores. El sistema normalmente despliega un indicador llamado
prompt (>) señalando que está esperando que una expresión sea escrita. Por ejemplo,
si escribímos el entero 1 después del prompt y tecleamos enter, tenemos:

> 1
1
>

el sistema despliega el valor de la expresión, seguida de un nuevo prompt, indicando
que está listo para evaluar una nueva expresión. En este caso, el sistema desplegó
lo mismo que tecleamos porque los números, como otras constantes, evalúan a si
mismos. Las cosas son más interesantes cuando una expresión necesita algo de trabajo
para ser evaluado, por ejemplo, sumar dos números:

> (+ 2 3)
5
>

En la expresión (+ 2 3) el símbolo + es llamado el operador y los números 3 y 4
son sus argumentos (o parámetros actuales, siguendo la notación introducida en el
capítulo anterior). Como el operador viene al principio de la expresión, esta notación
se conoce como prefija y aunque parezca extraña, veremos que es muy práctica. Por
ejemplo, si queremos sumar tres números en notación infija, necesitaríamos usar dos
veces el operador +: 2+3+4. En Lisp, las siguientes sumas son válidas:

> (+)
0
> (+ 2)
2
> (+ 2 3)
5

15

16

￿￿￿￿￿￿￿￿￿￿￿￿ ￿ ￿￿￿￿

> (+ 2 3 5)
10

Como los operadores pueden tomar un número variable de argumentos, es necesa-
rio utilizar los paréntesis para indicar donde inicia y donde termina una expresión.
Las expresiones pueden anidarse, esto es, el argumento de una expresión puede ser
otra expresión compleja. Ej.

> (/ (- 7 1)(- 4 2))
3

En español esto corresponde a siete menos uno, dividido por cuatro menos dos.
Estética minimalista, esto es todo lo que hay que decir sobre la notación en Lisp.
Toda expresión Lisp es un átomo, como 1, o bien es una lista que consiste de cero o
más expresiones delimitadas por paréntesis. Como veremos, código y datos usan la
misma notación en Lisp.

￿.￿ ￿￿￿￿￿￿￿￿￿￿

Veamos más en detalle como las expresiones son evaluadas para desplegar su valor en
el top-level. En Lisp, + es una función y (+ 2 3) es una llamada a la función. Cuando
Lisp evalúa una llamada a alguna función, lo hace en dos pasos:

1. Los argumentos de la llamada son evaluados de izquierda a derecha. En este

caso, los valores de los argumentos son 2 y 3, respectivamente.

2. Los valores de los argumentos son pasados a la función nombrada por el opera-

dor. En este caso la función + que regresa 5.

Si alguno de los argumentos es a su vez una llamada de función, será evaluado con

las mismas reglas. Ej. Al evaluar la expresión (/ (- 7 1) (- 4 2)) pasa lo siguiente.

1. Lisp evalúa el primer argumento de izquierda a derecha (- 7 1). 7 es evaluado

como 7 y 1 como 1. Estos valores son pasados a la función - que regresa 6.

2. El siguiente argumento (- 4 2) es evaluado. 4 es evaluado como 4 y 2 como 2.

Estos valores son pasados a la función - que regresa 2.

3. Los valores 6 y 2 son pasados a la función / que regresa 3.

No todos los operadores en Lisp son funciones, pero la mayoría lo son. Todas las
llamadas a función son evaluadas de esta forma, que se conoce como regla de evalua-
ción de Lisp. Los operadores que no siguen la regla de evaluación se conocen como
operadores especiales. Uno de estos operadores especiales es quote (’). La regla de
evaluación de quote es –No evalues nada, despliega lo que el usuario tecleo, verbatim.
Por ejemplo:

> (quote (+ 2 3))
(+ 2 3)
> ’(+ 2 3)
(+ 2 3)

Lisp provee el operador quote como una forma de evitar que una expresión sea

evaluada. En la siguiente sección veremos porque esta protección puede ser útil.

￿.￿￿￿￿￿￿

17

￿.￿ ￿￿￿￿￿

Lisp ofrece los tipos de datos que podemos encontrar en otros lenguajes de programa-
ción, y otros que no. Ya hemos usado enteros en los ejemplos precedentes. Lascadenas
de caracteres se delimita por comillas, por ejemplo, “Hola mundo”. Enteros y cadenas
evalúan a ellos mismos, como las constantes.

Dos tipos de datos propios de Lisp son los símbolos y las listas. Los símbolos
son palabras. Normalmente se evaluan como si estuvieran escritos en mayúsculas,
independientemente de como fueron tecleados:

> ’uno
UNO

Los símbolos por lo general no evaluan a si mismos, así que si es necesario referirse
a ellos, se debe usar quote, como en ejemplo anterior, de lo contrario, se producirá
un error ya que el símbolo uno no está acotado (no tiene ligado ningún valor en este
momento).

Las listas se representan como cero o más elementos entre paréntesis. Los elementos
pueden ser de cualquier tipo, incluidas las listas. Se debe usar quote con las listas, ya
que de otra forma Lisp las tomaría como una llamada a función. Veamos algunos
ejemplos:

> ’(Mis 2 "ciudades")
(MIS 2 "CIUDADES")
> ’(La lista (a b c) tiene 3 elementos)
(LA LISTA (A B C) TIENE 3 ELEMENTOS)

Observen que quote protege a toda la expresión, incluidas las sub-expresiones en
ella. La lista (a b c), tampoco fue evaluada. También es posible construir listas usan-
do la función list:

> (list ’mis (+ 4 2) "colegas")
(MIS 6 COLEGAS)

Estética minimalista y pragmática, observen que los programas Lisp se representan
como listas. Si el argumento estético no bastará para defender la notación de Lisp,
esto debe bastar –Un programa Lisp puede generar código Lisp! Por eso es necesario
quote. Si una lista es precedida por el operador quote, la evaluación regresa la misma
lista, en otro caso, la lista es evaluada como si fuese código. Por ejemplo:

> (list ’(+ 2 3) (+ 2 3))
((+ 2 3) 5)

En Lisp hay dos formas de representar la lista vacia, como un par de paréntesis o

con el símbolo nil. Ej.

18

￿￿￿￿￿￿￿￿￿￿￿￿ ￿ ￿￿￿￿

> ()
NIL
> NIL
NIL

￿.￿ ￿￿￿￿￿￿￿￿￿￿￿ ￿￿￿￿￿￿￿ ￿￿￿ ￿￿￿￿￿￿

La función cons construye listas. Si su segundo argumento es una lista, regresa una
nueva lista con el primer argumento agregado en el frente. Ej.

> (cons ’a ’(b c d))
(A B C D)
> (cons ’a (cons ’b nil))
(A B)

Las funciones primitivas para accesar los elementos de una lista son car y cdr. El
car de una lista es su primer elemento (el más a la izquierda) y el cdr es el resto de
la lista (menos el primer elemento). Ej.

> (car ’(a b c))
A
> (cdr ’(a b c))
(B C)

Se pueden usar combinaciones de car y cdr para accesar cualquier elemento de la

lista. Ej.

> (car (cdr (cdr ’(a b c d))))
C
> (caddr ’(a b c d))
C
> (third ’(a b c d))
C

￿.￿ ￿￿￿￿￿￿￿ ￿￿ ￿￿￿￿￿￿

En Lisp, el símbolo t es la representación por default para verdadero. La represen-
tación por default de falso es nil. Ambos evaluan a si mismos. Ej. La función listp
regresa verdadero si su argumento es una lista:

> (listp ’(a b c))
T
> (listp 34)
NIL

Una función cuyo valor de regreseo se intérpreta como un valor de verdad (ver-
dadero o falso) se conoce como predicado. En lisp es común que el símbolo de un
predicado termine en p.

￿.￿￿￿￿￿￿￿￿ ￿￿ ￿￿￿￿￿￿

Como nil juega dos roles en Lisp, las funciones null (lista vacía) y not (negación)

hacen exactamente lo mismo:

19

> (null nil)
T
> (not nil)
T

El condicional (estructura de control) más simple en Lisp es if. Normalmente toma
tres argumentos: una expresión test, una expresión then y una expresión else. La
expresión test es evaluada, si su valor es verdadero, la expresión then es evaluada; si
su valor es falso, la expresión else es evaluada. Ej.

> (if (listp ’(a b c d))

(+ 1 2)
(+ 3 4))

3
> (if (listp 34)

(+ 1 2)
(+ 3 4))

7

Como quote, if es un operador especial. No puede implementarse como una fun-
ción, porque los argumentos de una función siempre se evaluan, y la idea al usar if
es que sólo uno de sus argumentos sea evaluado.

Si bien el default para representar verdadero es t, todo excepto nil cuenta como

verdadero en un contexto lógico. Ej.

> (if 27 1 2)
1
> (if nil 1 2)
2

Los operadores lógicos and y or parecen condicionales. Ambos toman cualquier nú-
mero de argumentos, pero solo evaluan los necesarios para decidir que valor regresar.
Si todos los argumentos son verdaderos (diferentes de nil), entonces and regresa el
valor del último argumento. Ej.

> (and t (+ 1 2))
3

Pero si uno de los argumentos de and resulta falso, ninguno de los argumentos
posteriores es evaluado y el operador regresa nil. De manera similar, or se detiene
en cuanto encuentra un elemento verdadero.

> (or nil nil (+ 1 2) nil)
3

20

￿￿￿￿￿￿￿￿￿￿￿￿ ￿ ￿￿￿￿

Observen que los operadores lógicos son operadores especiales, en este caso defini-

dos como macros.

￿.￿ ￿￿￿￿￿￿￿￿￿

Es posible definir nuevas funciones con defun que toma normalmente tres argumen-
tos: un nombre, una lista de parámetros y una o más expresiones que conforman el
cuerpo de la función. Ej. Así definiríamos third:

> (defun tercero (lst)

(caddr lst))

TERCERO

El primer argumento de defun indica que el nombre de nuestra función definida
será tercero. El segundo argumento (lst) indica que la función tiene un sólo argu-
mento, lst. Un símbolo usado de esta forma se conoce como variable. Cuando la
variable representa el argumento de una función, se conoce como parámetro. El resto
de la definición indica lo que se debe hacer para calcular el valor de la función, en
este caso, para cualquier lst, se calculará el primer elemento, del resto, del resto del
parámetro (caddr lst). Ej.

> (tercero ’(a b c d e))
C

Ahora que hemos introducido el concepto de variable, es más sencillo entender lo
que es un símbolo. Los símbolos son nombres de variables, que existen con derechos
propios en el lenguaje Lisp