PDF de programación - Introducción a LISP

Introducción a LISP

1. Sintaxis (Resumen)

LISP es un acrónimo de List Processing. El lenguaje está compuesto escencial-
mente de dos cosas:
• Átomos:

– Símbolos (Identificadores): comienzan con un carácter seguido de

cualquier otro caracter excepto espacios, comas, puntos o parentesis.

– Números: las reglas normales de escritura de números se aplican aquí.

LISP no es sensible al caso.
• Listas:

Lista ::= ‘‘()’’ | ‘‘NIL’’ |

‘‘(’’ <atomo1> [<atomo2>] ...

[<atomon>] ‘‘)’’

Los átomos en una lista deben estar separados por espacios.

Átomos especiales (palabras reservadas).
• Los átomos T y NIL están reservados para representar el valor de verdad
verdadero y falso, respectivamente.
• NIL es al mismo tiempo un átomo y una lista vacía.
• Los nombres de funciones predeterminadas de LISP también son palabras
reservadas y no deberían usarse como identificadores.

Ejemplos:
• Átomos: A, X, B, un-atomo, p+100, atomo*valido-
• Listas: (1 2 3 4), (a 3 b un-atomo-valido),
(p+100 no es una suma) (pero)
(+ p 100) (si lo es)

2. Semántica

LISP funciona a través de un intérprete. La misión del interprete es evaluar la
expresión que se introduce. La evaluación procede de la siguiente forma:

evalua( X ):

1. si X es un átomo, entonces devolver el valor de la variable X

2. si X es una lista y X1,...,Xn los elementos de X, hacer

(a) Yi = evalua( Xi ), para i = 2, .., n
(b) regresar X1(Y2, Y3,..., Y4), es decir, llamar a la función

especificada por X1 con los argumentos Y2,..,Yn.
(si X1 no es un átomo o la función especificada no existe, se
produce un error).

Todas las instrucciones en LISP son funciones y regresan un valor. Además,
por la forma como funciona el intérprete, LISP usa notación prefija.

Ejemplos:

Cómo declarar una variable global (el símbolo “>” es el prompt de LISP):
> X → ERROR
> (setf X 3) → 3
> X → 3

La función setf es una función predeterminada de LISP que crea una
nueva variable y le asigna un valor (si la variable ya existe, cambia su valor
anterior).
> (a b c) → ERROR (la función “a” no existe)
> (quote (a b c)) → (a b c)
> ’(a b c) → (a b c)

En los últimos dos ejemplos se hace uso de una función predeterminada
de LISP llamada quote o simplemente ’. Esta función es especial en el sen-
tido de que evita la evaluación de su único argumento y devuelve su argumento
al evaluarse.

Algunas funciones comunes de LISP:
• (FIRST <Lista>) ó (CAR <Lista>): Devuelve el primer ele-
mento de la lista.
• (REST <Lista>) ó (CDR <Lista>): Devuelve la lista menos el
primer elemento.
• (CONS <Elem> <Lista>): Genera una nueva lista con Elem al prin-
cipio de Lista.
• (APPEND <Lista1> <Lista2>): Pega las listas y regresa el resul-
tado.
• (MEMBER <Elem> <Lista>): Si Elem está en Lista, entonces re-
gresa la lista a partir de ese elemento, en caso contrario regresa NIL.
• (NULL <Lista>): Regresa T si la lista está vacía.
• (SETF <Variable> <Valor>): Asigna el valor a la variable (y la
crea si no existe). Regresa el valor asignado.
• (REVERSE <Lista>): Invierte la lista.

• (NTH <n> <Lista>): Regresa el n-ésimo elemento de Lista
(basado en 0).
• (NTHCDR <n> <Lista>): Elimina los primeros n elementos de Lista.
• (LENGTH <Lista>): Regresa la longitud de la lista.
• (LIST <Elem1> <Elem2> ... <Elemn>): Crea una nueva lista
cuyos elementos son Elem1...Elemn
• (RETURN <Expr>): Provoca que la función actual termine y regresa el
valor dado por Expr.
• (DOLIST (<Iterador> <Lista> [<Resultado>])
<Expr1> ...
las expresiones Expr1... Exprn. Regresa la expresión Resultado.
• (DOTIMES (<Iterador> <ValorFinal> [<Resultado>])
<Expr1> ...
0...ValorFinal-1 y para cada valor,
Expr1...Exprn). Regresa la expresión Resultado.

<Exprn>): Para cada elemento de Lista, se ejecutan

los
valores
instrucciones

iterador

toma
ejecuta las

<Exprn>):

El

• (DO ( (<X1> <ValInicial1> [<Incr1>]) ...

(<Xn> <ValInicialn> [<Incrn>])

) (<Cond> <Resultado>)

<Expr1> ... <Exprn> ) :

Iteración genérica. Los iteradores X1...Xn se inicializan e incrementan en
paralelo. El valor regresado es Resultado.
• (LET ( (<X1> <ValInicial1>) ...

(<Xn> <ValInicialn>)

) <Expr1> ... <Exprn> ) :

Secuenciación genérica, las variables son creadas e inicializadas en
paralelo. El valor regresado es Exprn.
• (PROG1 <Expr1> ... <Exprn>): Secuenciación genérica.
valor regresado es Expr1.
• (PROGN <Expr1> ... <Exprn>): Secuenciación genérica.
valor regresado es Exprn.

El

El

• (COND (<Cond1> <Expr1>) ...

(<Condn> <Exprn>)

) : Selección múltple. Si Condi es verdadera, entonces se ejecuta

Expri. El valor regresado es la expresión seleccionada.
• (DEFUN <Funcion> (<Arg1> ... <Argn>)

(<Expr1> ...

<Exprn>)

) : Define una nueva funcón llamada Funcion que recibe los

argumentos Arg1...Argn. El resultado que regresa la nueva función es
Exprn.
• Modificadores de argumentos de función:

– &KEY <Var1> ...

<Varn>: Declara argumentos por nombre
(argumentos clave). Para poner valores a estos argumentos hay que
escribir :<Vari> <Valori> al llamar a la función. Para inicializar
los argumentos se usa la sintaxis (<Vari> <Expri>).

– &AUX <Var1> ...

<Varn>: Declara variables locales nuevas.
Las nuevas variables se inicializan a NIL a menos que se use la sin-
taxis (<Vari> <Expri>).

• (IF <Cond> <Then> <Else>): Selección condicional sencilla. Re-
gresa la expresión que se haya ejecutado.
• LISP usa los operadores aritméticos normales: +, -, *, / y los com-
paradores aritméticos =,>,<,>=,<=. La desigualdad se hace con (NOT
(= <Expr1> <Expr2>)).
• La división puede dar números racionales. Para convertirlos a números
de punto flotante se usa la función float, para convertirlos a enteros se
puede usar floor o round.
• (EQ <S1> <S2>): Compara dos símbolos, pero no compara números
reales. EQL usa EQ y regresa T si sus argumentos son números del mismo
tipo y valor. EQUAL hace lo mismo que EQL pero también compara listas.
• AND, OR, NOT: Conjunción, disyunción y negaciones lógicas, respecti-
vamente. AND y OR pueden llevar más de un argumento.

Ejercicio: Programe la ordenación de listas por selección, inserción y quick-
sort.
• Seleccion(L): Se extrae el elemento más pequeño de L y se pone al
final de una lista temporal Lp. El algoritmo se repite hasta dejar L vacía,
en cuyo caso, Lp contiene la lista ordenada.
• Insercion(L): Se toma el siguiente elemento de L y se inserta de forma
ordenada en una lista temporal (ordenada) Lp. El algoritmo continúa hasta
que todos los elementos de L han sido insertados en Lp, en cuyo caso, Lp
contiene la lista ordenada.
• Quicksort(L): L se parte en dos listas L- y L+ de acuerdo a algún ele-
mento pivote p de L de forma que todos los elementos de L- son menores
(o iguales) que p y todos los elementos de L+ son mayores. Después se
ordenan L- y L+ usando Quicksort y se fusionan (el pivote debe de
ponerse en medio de ambas listas durante la fusión). ¿Cómo podría imple-
mentar este algoritmo para que corra en paralelo?

3. Breve nota sobre la programación funcional

La programación funcional está basada en usar las funciones matemáticas con
sus propiedades normales. Una de las propiedades clave es que la misma
expresión siempre tiene el mismo valor en el mismo contexto. A esto se le
llama transparencia referencial. Esto quiere decir que no se permiten efectos
secundarios (como paso de argumentos por referencia).

Por ejemplo, en la expresión f(sqrt(2), sqrt(2)), podemos hacer un
símbolo nuevo s = sqrt(2) y substituir la expresión anterior por f(s, s)
y tendremos el mismo resultado. Sin embargo, si hacemos f(getchar(),
getchar()), ya no podemos sustituir los argumentos por un sólo símbolo,
debido a que getchar() produce efectos secundarios.

Esta clase de efectos secundarios no son permitidos en lenguajes funcionales
puros. Sin embargo, LISP tiene varias funciones que permiten efectos secun-
darios (como el DEFUN). Pero, por otro lado no es absolutamente necesario
utilizar DEFUN para escribir un programa...

4. Metaprogramación

LISP permite que se genere código en tiempo de ejecución. Esto puede lograrse
con una variedad de métodos:
• (EVAL <Expr>): Esta función evaúa Expr y luego ejecuta el resultado.
• (APPLY <Apuntador-Funcion> <Lista-Argumentos>):
Esta función ejecuta la función “apuntada por” Apuntador-Funcion
con la lista de argumentos proporcionada. Ejemplo:
> (APPLY #’+ ’(3 2)) → 5.

Note que el operador #’ se usa para obtener la “dirección” de la función
predefinida +.
• (LAMBDA (<Arg1> ...
<Argn>) <Expr1> ... <Exprm>):
Crea una función anónima in situ para poder ser usada por funciones como
APPLY. La nueva función regresa el valor de Exprm.

Sabiendo que existe la siguiente función de LISP:

(MIN <Valor1> ...

<Valorn>)

Que regresa el mínimo de los valores dados, ¿cómo podría haber usado la
metaprogramación y la función MIN para programar la ordenación por se-
lección?

Análisis del lenguaje natural

Otro uso posible de la metaprogramación es para el análisis del lenguaje
natural. Se puede hacer un programa que reciba como entrada las reglas de
producción de alguna oración y luego, en tiempo de ejecución, genere el código
que acepta tales oraciones y lo incluya en su programa. Es decir, tendríamos un
programa que se modifica y actualiza a sí mismo durante su ejecución. Esto es
posible puesto que en LISP, el código y los datos tienen el mismo formato.

¿Cómo podría implementarse esto con lenguajes de programación tradi-
cionales?

Tarea (1): Conversión a notación prefija

Haga un programa que reciba una expresión algebraica en notación infija
y la convierta a notación prefija. Ejemplos:

> (parse ’(a + b / 2 - (4 * a * c - 8) / (8 * x + 4)))
(+ A (- (/ B 2) (/ (- (* 4 (* A C)) 8) (+ (* 8 X) 4))))

> (parse ’(- 3 * 4 / - 8 + (7 - 15) * 4))
(+ (* (- 3) (/ 4 (- 8))) (* (- 7 15) 4))

> (+ (* (- 3) (/ 4 (- 8))) (* (- 7 15) 4))
-61/2

Los operadores aceptados deben ser: +, - (binario y unario), *, y /. Además,
no