1 El lenguaje LISP

2 Introducción Origen: 1959 Uso habitual en Inteligencia ArtificialLISt Processing Lenguaje Interpretado También posible compilado Todas las variables son punteros Liberación automática de memoria (automatic garbage collection) Eficiencia menor que otros lenguajes (causas: es interpretado, liberación automática de memoria, ...). Adecuado para prototipados y cálculo simbólico. Datos ~ Programas

3 Datos Expresiones LISP: Átomos Listas Símbolos:simbolo, simbolo3,ejemplo-de-simbolo Especiales: nil, t Keywords: :ejemplo, :keyword Strings (distinción minúsculas-mayúsculas) “abc”, “ABC”, “string” Números: enteros: 33, 4, -5 racionales: -3/5, 4/8 reales: 3.23, -4.78, 3.33E45 Listas Colecciones de expresiones (a b (c (d)) e), (), (3 “abc”)

4 Evaluación Evaluación de una expresión LISP Ejemplos de evaluacionesÁtomos Símbolos: Su evaluación es su valor como variable T y NIL se evalúan a sí mismos Números, Strings y Keywords Se evalúan a sí mismos Listas () se evalúa a NIL Una lista no vacía evaluable debe tener como primer elemento un símbolo (+ 3 (+ 2 5)) (quote (a b c)) (setf variable (+ 3 4)) Forma LISP: expresión evaluable

5 Operadores QUOTE y SETFFunciones: evalúan todos sus argumentos Macros: no evalúan todos los argumentos QUOTE Macro: no evalúa su argumento (quote (a b c)) >>> (A B C) ‘(a b c) equivale a (quote (a b c)) SETF Macro: sólo evalúa el segundo argumento (setf x ‘(a b c)) >>> (A B C) Representación en memoria T, NIL son símbolos reservados

6 Operadores de manipulación de listas, ICaracterísticas comunes: Al evaluarlos, se obtiene error cuando se aplican sobre datos que no siguen su patrón sintáctico. La mayoría son funciones (no macros). FIRST (CAR) (first ) (first ‘(a b c)) >> A SECOND, THIRD, ..., NTH (second ) (second ‘(a b c)) >>> B (nth ) (nth 1 ‘(a b c)) >>> B

7 Operadores de manipulación de listas, IIREST (CDR) (rest ) (rest ‘(a b c)) >> (B C) NTHCDR (nthcdr ) (nthcdr (+ 1 1) ‘(a b c)) >> (C) (car (cdr (car ‘((a b c) d)))) >> B Es equivalente (cadar ‘((a b c) d)) CONS (cons ) (cons ‘(a b) ‘(c d e)) >>> ((A B) C D E) LIST (list *) (list ‘(a b) ‘(c d)) >>> ((A B) (C D))

8 Operadores de manipulación de listas, IIIAPPEND (append *) (append ‘(a b) ‘(c d)) >>> (A B C D) No destructivo. Crea copia (a primer nivel) de todos los argumentos menos el último Operadores destructivos: Suelen ser macros (setf a ‘(a b)); (setf b ‘(c d)); (setf c ‘(e f)) NCONC (append). Función. (nconc a b) >>> (A B C D) a >> (A B C D) ; b >>> (C D) PUSH (cons). Macro (push ‘r b) >>> (R C D) b >>> (R C D) POP. Macro (pop c) >>> E c >>> (F)

9 Operadores de manipulación de listas, IVEl macro SETF admite como primer argumento: Un símbolo: (setf dias ‘(lunes martes miercoles)) Una posición de memoria: (setf (second dias) ‘jueves)) dias >>> (LUNES JUEVES MIERCOLES) (setf (rest dias) ‘(viernes domingo)) dias >>> (LUNES VIERNES DOMINGO) (setf (rest dias) dias) >>> (LUNES LUNES ....) ¡Cuidado!, listas circulares

10 Operadores de manipulación de listas, VOtras funciones: LAST (last ) (last ‘(a b c)) >>> (C) REVERSE (reverse ) (reverse ‘(a b c)) >>> (C B A) LENGTH (lenght ) (lenght ‘(a b c)) >>> 3

11 Otras funciones LISP, I PROGN, PROG1 PRINTPermiten escribir instrucciones compuestas (como “{“ y “}” en el lenguaje C) Evalúan todas las instrucciones que contienen y devuelven la última o primera instrucción. (progn (+ 3 4) (+ 4 5)) >>> 9 (prog1 (+ 3 4) (+ 4 5)) >>> 7 PRINT (PRINT ) Si el valor de “” lo llamamos “A”, el valor es A. Adicionalmente al ejecutarse, también se imprime A > (progn (setf x (print ‘A)) (+ 3 4)) A >>> 7 > x >>> A

12 Otras funciones LISP, IIEVAL Evalúa dos veces una expresión (eval ‘(+ 3 4)) >> 7 Operadores matemáticos +, -, *, /, ABS EXPT (expt 2 4) >>> 16 MAX, MIN (max ) >>> 5 FLOAT (float 1/2) >>> 0.5 ROUND (round 3.2) >> 3

13 Condicionales, I El valor lógico de una forma LISP se considera “falso” si su valor LISP es NIL. En caso contrario, el valor lógico es “verdadero”. IF (macro) Sintaxis: (if [forma2]) Si el valor lógico de es “verdadero”, devuelve el valor de . Si es “falso”, devuelve el valor de . (if (> 5 (+ 2 2)) (+ 3 3) (+ 3 4)) >>> 6

14 Condicionales, II WHEN (macro) Sintaxis: (when (> 5 (+ 2 2))(when ...) Si el valor lógico de es “verdadero”, ejecuta las formas , , ... y devuelve como valor final el valor de . Si es “falso”, devuelve NIL. (when (> 5 (+ 2 2)) (+ 3 3) (+ 3 4)) >>> 7

15 Condicionales, III UNLESS (macro) Sintaxis: (unless (> 5 (+ 2 2))(unless ...) Si el valor lógico de es “falso”, ejecuta las formas , , ... y devuelve como valor final el valor de . Si es “verdadero”, devuelve NIL. (unless (> 5 (+ 2 2)) (+ 3 3) (+ 3 4)) >>> NIL

16 ...)Condicionales, IV COND (macro) Sintaxis: (cond ( ...) ( ...) ... ( ...)) Cuando encuentra una cuyo valor lógico de es “verdadero”, ejecuta las formas , , ... y devuelve como valor final el valor de . (cond ((> 5 7) (+ 3 4) (+ 4 5)) ((> 5 3) (+ 5 6) (+ 6 7)) (t (+ 7 8) (+ 8 9)) >>> 13

17 Predicados Usual calcular el valor lógico de expresiones LISP construidos con ellos. Tipos de datos: ( ) ATOM, STRINGP, NUMBERP, SYMBOLP, LISTP (atom ‘a) >>> T ; (atom NIL) >>> T (listp ‘a) >>> NIL ; (listp NIL) >>> T Numéricos: Los operandos deben ser números >, <, <=, >=, ZEROP, PLUSP, MINUSP, EVENP, ODDP Identificador listas vacías: NULL ¿Es la lista vacía? .¿Es su valor lógico “falso”? (null (rest ‘(a))) >>> T

18 Predicados de igualdad, IEQ, EQL, EQUAL, = = (= ) (= 3 (+ 2 1)) >>> T; (= 3 3.0) >>> T Ejemplos: (setf x ‘(a b 2)) ; (setf y ‘(a b 2)); (setf z x) EQ Comprueba igualdad a nivel de punteros (eq x y) >>> NIL ; (eq (first x) (first y)) >>> T (eq z x) >>> T EQL (eql ) >>> T Cuando y son átomos y además (eq ) se evalúa a T

19 Predicados de igualdad, IIEQUAL Comprueba a nivel simbólico si dos expresiones son iguales (al imprimirlas) (equal x y) >>> T (equal 3 3.0) >>> NIL El predicado EQUAL es más caro que el predicado EQ

20 Operadores lógicos, I AND (macro) OR (macro) NOT(and ... ) Si el valor lógico de todas las es “verdadero”, devuelve el valor de la última (). En caso contrario, devuelve NIL. Cuando encuentra alguna con valor lógico “falso”, ya no sigue evaluando el resto de las . (and (evenp 2) (plusp -3) (print 3)) >>> NIL OR (macro) (or ... ) Si el valor lógico de alguna de las es “verdadero”, devuelve su valor. En caso contrario, devuelve NIL. Cuando encuentra alguna con valor lógico “verdadero”, ya no sigue evaluando el resto de las . (or (evenp 2) (plusp -3) (print 3)) >>> T NOT (not ) Si el valor lógico de es “verdadero”, devuelve NIL. En caso contrario devuelve T.

21 Operadores lógicos, II NOT (not )Si el valor lógico de es “verdadero”, devuelve NIL. En caso contrario devuelve T. (not (oddp 2)) >>> T (not (list 2 3)) >>> NIL (not (oddp 3) >>> NIL

22 Variables locales y globales, I(setf dias ‘(lunes martes miercoles)) Es una variable global (puede ser llamada por el resto de instrucciones) Las variables globales en LISP se suelen denominar con “*”: *dias-de-la-semana*

23 Variables locales y globales, IILET (macro) Ejemplo: >(prog1 (let ((x ‘a) (y ‘b) z) (setf z (list x y)) (list z z)) (list 'final 'evaluacion)) >>> ((A B) (A B)) Sintaxis: (let (( ) ( ) ... ( )) .... )

24 Definición de funcionesEjemplo: >(defun factorial (numero) (cond ((= numero 0) 1) (t (* numero (factorial (- numero 1)))))) >>> FACTORIAL > (factorial 3) >>> 6 Sintaxis: (defun ... ) Comentarios: El valor de la función es el de la última forma (). No se puede utilizar “return” para devolver el valor de retorno (como en el lenguaje C). Los argumentos son también variables locales. Valor de un símbolo como variable y como función.

25 Iteraciones DOTIMES DOLIST WHILE LOOP(dotimes (i 3 (list 'final)) (list i i)) >>> (FINAL) Sintaxis: (dotimes ( [ ... ) DOLIST (dolist (i (list ‘a ‘b) (list 'final)) (list i i)) >> (FINAL) (dolist ( [ WHILE (while ... ) LOOP Sintaxis (la más sencilla): (loop ... ) En todos estos operadores, al utilizar (return ), se sale de una iteración devolviendo el valor de .

26 Ejemplos, I Cálculo de la potencia de un número con optimización(defun potencia (x n) "Optimizacion calculo potencia" (cond ((= n 0) 1) ((evenp n) (expt (potencia x (/ n 2)) 2)) (t (* x (potencia x (- n 1)))))) (potencia 2 3) >>> 8 Contar los átomos de cualquier expresión LISP: > (cuenta-atomos '(a (b c) ((d e) f))) >>> 6 >(defun cuenta-atomos (expresion) (cond ((null expresion) 0) ((atom expresion) 1) (t (+ (cuenta-atomos (first expresion)) (cuenta-atomos (rest expresion)))))) >>> CUENTA-ATOMOS

27 Ejemplos II Aplanar una lista:(aplana ‘(a (b c) ((d e) f))) >>> (A B C D E F) > (defun aplana (lista) (cond ((null lista) NIL) ((atom (first lista)) (cons (first lista) (aplana (rest lista)))) (t (append (aplana (first lista)) (aplana (rest lista))))))

28 Ejemplos III Número de sublistas de una lista (número de veces que se abre paréntesis, menos 1): (sublistas ‘(a (b c) ((d e) f))) >>> 3 > (defun sublistas (expresion) (cond ((or (null expresion) (atom expresion)) 0) (t (+ (if (atom (first expresion)) 0 1) (sublistas (first expresion)) (sublistas (rest expresion))))))

29 Ejemplos IV Producto escalar: (producto '(2 3) '(4 5)) >>> 23Versión recursiva: > (defun producto (vector1 vector2) (if (or (null vector1) (null vector2)) (+ (* (first vector1) (first vector2)) (producto (rest vector1) (rest vector2))))) Versión iterativa: (let ((suma 0)) (dotimes (i (length vector1)) (setf suma (+ suma (* (nth i vector1) (nth i vector2))))) suma))

30 Otros operadores, I Un mismo símbolo se puede utilizar para definir una variable y una función. (setf f ‘a) (defun f (x y) (list x y)) FUNCALL (funcall ... ) Son equivalentes: (f ‘a ‘b) >>> (A B) (funcall #’f ‘a ‘b) (progn (setf funcíon-f #’f) (funcall funcíon-f ‘a ‘b)) (funcall #’(lambda (x y) (list x y)) ‘a ‘b) FUNCIÓN ANÓNIMA APPLY (apply ( ... )) (apply #’f ‘(a b))

31 Otros operadores, II MAPCAR REMOVE(mapcar ... ) > (mapcar #’(lambda (x y) (list x x y y)) ‘(a b c) ‘(d e f)) >>> ((A A D D) (B B E E) (C C F F)) REMOVE (remove [:test ]) (remove ‘b ‘(a b c)) >>> (A C) Equivale a (remove ‘b ‘(a b c) :test #’eql) (remove ‘(a b) ‘(a (a b) c)) >>> (A (A B) C) (remove ‘(a b) ‘(a (a b) c) :test #’equal) >>> (A C)

32 Otros operadores, III DELETE MEMBER Versión destructiva de REMOVE(setf lista ‘(a b c)) (remove ‘b lista) >>> (A C) lista >>> (A B C) (delete ‘b lista) >>> (A C) lista >>> (A C) MEMBER Sintaxis: (member [:test ]) (member ‘b ‘(a b c)) >>> (B C) Equivale a (member ‘b ‘(a b c) :test #’eql) (member ‘(a b) ‘(a (a b) c)) >>> NIL >(member ‘(a b) ‘(a (a b) c) :test #’equal) >>> ((A B) C)

33 Otros operadores, IV Otros operadores cuyos argumentos son funciones:COUNT-IF, FIND-IF, REMOVE-IF, REMOVE-IF-NOT, DELETE-IF, DELETE-IF-NOT Observación: Al utilizar #’, si es un macro se tienen resultados inesperados. No usarlos, por tanto.

34 Argumentos de funcionesNúmero fijo de argumentos: (defun f (x y) (list x y)) (f ‘a ‘b ‘c) >>> error Número variable de argumentos (&rest): Función LIST (defun f (x y &rest z) (list x y z)) (f ‘a ‘b ‘c ‘d) >>> (A B (C D)) Argumentos opcionales con nombre y valor por defecto (&key): (defun f (x y &key (z ‘a) u (v ‘b)) (list x y z u v)) (f ‘a ‘b) >>> (A B A NIL B) (f ‘a ‘b :z ‘c :v ‘d) >>> (A B C NIL D)

35 DEBUGGING TRACE UNTRACE Uso de PRINT, DESCRIBE, etcFunción recursiva: (defun factorial (n) (if (= n 0) 1 (* n (factorial (- n 1))))) (trace factorial) > (factorial 2) FACTORIAL [call 5 depth 1] with arg: 2 FACTORIAL [call 6 depth 2] with arg: 1 FACTORIAL [call 7 depth 3] with arg: 0 FACTORIAL [call 7 depth 3] returns value: 1 FACTORIAL [call 6 depth 2] returns value: 1 FACTORIAL [call 5 depth 1] returns value: 2 UNTRACE (untrace), (untrace factorial) Uso de PRINT, DESCRIBE, etc (describe ‘factorial) No es posible uso de “breakpoints”, “steps”, etc

36 Funciones sobre stringsMás corriente el uso de símbolos Funciones: LENGTH, REVERSE STRING= (sensible a mayúsculas), STRING-EQUAL (read-from-string ) >>> (string ) >>> (prin1-to-string ) >>> (search ) (subseq ) >>> substring a partir de (concatenate +)

37 Arrays Acceso no secuencial a elementosEn listas, el acceso a los elementos es secuencial Más eficiente el acceso a elementos en arrays que en listas > (setf mi-array (make-array '(2 3))) >>> #2A((NIL NIL NIL) (NIL NIL NIL)) > (setf (aref mi-array 0 1) 'a) >>> A > mi-array >>> #2A((NIL A NIL) (NIL NIL NIL)) Operadores: MAKE-ARRAY, AREF

38 Estructuras, I Ejemplo: > (defstruct nombre-persona nombre(alias 'sin-alias) apellido) >>> NOMBRE-PERSONA > (setf persona1 (make-nombre-persona :nombre 'juan)) >>> #S(NOMBRE-PERSONA NOMBRE JUAN ALIAS SIN-ALIAS APELLIDO NIL) > (setf persona2 (make-nombre-persona :nombre 'pedro :alias 'perico)) >>> #S(NOMBRE-PERSONA NOMBRE PEDRO ALIAS PERICO

39 Estructuras, II Funciones definidas automáticamente por LISP:> (setf (nombre-persona-alias persona1) 'juanito) >>> JUANITO > persona1 #S(NOMBRE-PERSONA NOMBRE JUAN ALIAS JUANITO APELLIDO NIL) Funciones definidas automáticamente por LISP: NOMBRE-PERSONA-MAKE NOMBRE-PERSONA -NOMBRE, NOMBRE-PERSONA -ALIAS, NOMBRE-PERSONA -APELLIDO

40 Alternativa a estructurasLas listas son una alternativa al uso de estructuras: > (setf persona1 '((:NOMBRE JUAN) (:ALIAS JUANITO) (:APELLIDO NIL))) >>> ((:NOMBRE JUAN) (:APELLIDO NIL)) > (assoc :alias persona1) >>> (:ALIAS JUANITO) > (first (member :alias persona1 :test #'(lambda (x y) (eql x (first y))))) ASSOC utiliza por defecto EQL

41 Ejemplos > (defun producto (vector1 vector2)(apply #'+ (mapcar #'* vector1 vector2))) >>> PRODUCTO > (producto '(2 3) '(4 5)) >>> 23 > (defun profundidad-maxima (expresion) (cond ((null expresion) 0) ((atom expresion) 1) (t (+ 1 (apply #'max (mapcar #'profundidad-maxima expresion)))))) >>> PROFUNDIDAD-MAXIMA > (profundidad-maxima '(1)) >>>> 2 > (profundidad-maxima '((1 (2 (3))) 4)) >>>> 5

42 Otros temas en LISP, I Comentarios MacrosDespués de “;” y hasta final de línea Macros Permiten definir operadores que no evalúan sus argumentos: COND, SETF, DEFUN son macros (defmacro defun (nombre-funcion lista-argumentos &rest formas) ......) Uso de backquote (`) y de arroba Operadores adicionales al quote (‘) Muchas funciones ya implementadas en LISP: SORT, LOOP generalizado, etc CLOS (programación orientada a objetos)

43 Otros temas en LISP, II Dotted-pairs (en desuso)> (cons 'a 'b) >>> (A . B) Edición, carga compilación: COMPILE-FILE, LOAD-FILE Entrada-salida: PRINT, READ, FORMAT, READ-LINE, READ-CHAR Otros operadores de iteración: DO, DO* (su diferencia es equivalente a la de LET y LET*) (declare (special )) Argumentos opcionales (&optional) “Property-names” de símbolos Copias de listas: COPY-TREE Funciones sobre conjuntos: UNION, INTERSECTION, etc. Paquetes