PDF de programación - El lenguaje LISP

El lenguaje LISP

“LISP is an easy language to learn”

(Henry et al 1984)
(Henry et.al., 1984)

1

1

Introducción

Origen: 1958
John McCarthy, pionero en IA, empezó

l

t b j

a trabajar con la primera
implementación de Lisp en 1958.
» McCarthy, Recursive functions of symbolic

i

i

d th i

expressions and their computation by
machine, Communications of the ACM, Vol
3, No 4, 1960.

b

ti

t

2

2

Introducción

Uso habitual en Inteligencia Artificial
LISt Processing
Características básicas

» Lenguaje Interpretado

– También posible compilado

» Todas las variables son punteros
» Liberación automática de memoria

i

i

» Eficiencia menor que otros lenguajes

(automatic garbage collection)
Efi
j
(causas: es interpretado, liberación
automática de memoria, ...).

l

» Adecuado para prototipados y cálculo
» Adecuado para prototipados y cálculo

simbólico.

Nuevo paradigma de programación:

programación funcional
programación funcional

3

3

Datos

Expresiones LISP:

» Átomos

Símbolos:
– Símbolos:

simbolo, simbolo3,ejemplo-de-simbolo
Especiales: nil, t
– Keywords (étiquetas):
:ejemplo, :keyword

– Strings (distinción minúsculas-mayúsculas)

“abc”, “ABC”, “string”

Números:
– 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”)

Listas: Grupo de átomos. Las listas también se

pueden agrupar en niveles superiores.

4

4

Evaluación

Forma LISP: cualquier expresión evaluable (expresión

LISP)

Evaluación

» Una expresión es evaluable cuando devuelve un valor
» Una expresión es evaluable cuando devuelve un valor

Distinción entre operadores

» Funciones: evalúan todos sus argumentos
» Macros: no evalúan todos los argumentos

– QUOTE

QUO

Macro: no evalúa su argumento

(quote (a b c)) >>> (A B C)

‘(a b c) equivale a (quote (a b c))

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))

Notación prefijo. El primer
elemento de una lista indica

qué se desea hacer

5

5

Operadores de

manipulación de listas, I

El macro SETF admite como primer

argumento:
» Un símbolo:
U í b l
– (setf dias ‘(lunes martes miercoles))

» Una posición de memoria:
– (setf (second dias) ‘jueves))
– (setf (second dias) jueves))
– dias >>> (LUNES JUEVES MIERCOLES)

Atención! Lista modificada!

– (setf (rest dias) ‘(viernes domingo))
– dias >>> (LUNES VIERNES DOMINGO)
– (setf (rest dias) dias) >>> (LUNES LUNES ....)

¡Cuidado!, listas circulares

(setf [<var1> <valor1>] ... [<varn> <valorn>])
Sirve para:
• Asignar valores a variables
• Modificar valores de componentes de listas, variables, etc.

6

6

Operadores de

manipulación de listas, II

Características comunes:

» Al evaluarlos, se obtiene error cuando se

aplican sobre datos que no siguen su
aplican sobre datos que no siguen su
patrón sintáctico.

» La mayoría son funciones (no macros).

FIRST o CAR

» Devuelve el primer elemento de la lista
» (first <lista>)
» (first ‘(a b c)) >> A
S CO
» (second <lista>)

SECOND, THIRD, ..., NTH

– (second ‘(a b c)) >>> B

» (nth <expresion> <lista>)
» (nth <expresion> <lista>)

– (nth 1 ‘(a b c)) >>> B
– Devuelve el elemento en la posición

<expresion> de la <lista>
Posición inicial: 0
– Posición inicial: 0
– Si <expresion> excede la dimensión de la lista

se devuelve NIL

7

7

Operadores de

manipulación de listas, III

REST o CDR

» Devuelve la lista sin el primer elemento
» (rest <lista>)
)
» (rest ‘(a b c)) >> (B C)

li t

(

t

NTHCDR

» (nthcdr <expresion> <lista>)
» (nthcdr (+ 1 1) ‘(a b c)) >> (C)

(car (cdr (car ‘((a b c) d)))) >> B
» Es equivalente (cadar ‘((a b c) d))
» C_ _ _ R _ = A (first) o D (rest)
Cómo crear listas?
Có o c ea s as
» cons
» append
» list
» list

8

8

Operadores de

manipulación de listas, IV

CONS

» (cons <expresion> <lista>)
» Crea una lista cuyo primer elemento es
» Crea una lista cuyo primer elemento es

<expresion> y cuyo resto es <lista>
– (cons ‘(a b) ‘(c d e)) >>> ((A B) C D E)

APPEND

d

l

t

li t

(cons ‘a (cons ‘b nil)) : construir una lista,
concatenando elementos a una lista vacía
í

t
» (append <lista>*)
» (append ‘(a b) ‘(c d)) >>> (A B C D)
(A B C (D) E F)
» (append '(a b) '(c (d)) '(e f)) >>> (A B C (D) E F)
» No destructivo. Crea copia (a primer nivel)

de todos los argumentos menos el último

d '( b) '(

(d)) '(

f))

(

» (append ‘a ‘b ‘c) >>> ?

ERROR

LIST

» (list <expresion>*)
» (list ‘(a b) ‘(c d)) >>> ((A B) (C D))
» (list '(a b) '(c (d)) '(e f)) >>> ((A B) (C (D)) (E F))
» (list ‘a ‘b ‘c) >>> ?

(A B C)

9

9

Operadores de

manipulación de listas, V

Operadores destructivos:

» Suelen ser macros
» (setf a ‘(a b)); (setf b ‘(c d)); (setf c ‘(e f))
f))

tf b ‘( d)) (

‘( b)) (

tf

(

tf

‘(

– NCONC (append). Función.

(nconc a b) >>> (A B C D)
a >> (A B C D) ; b >>> (C D)
)

) ;

(

(

Modifica la primera lista

– PUSH (cons). Macro

(push ‘r b) >>> (R C D)
(R C D)
b >>> (R C D)

b

Introduce elemento. Modifica la lista

– POP. Macro

(pop c) >>> E
c >>> (F)

Saca elemento. Modifica la lista

10

10

Operadores de

manipulación de listas, VI

Otras funciones:

– LAST

(last <lista>)
(last <lista>)
(last ‘(a b c)) >>> (C)
(last ‘((A B) (C D))) >>> ((C D))

– REVERSE

Devuelve el último elemento
(del primer nivel de anidamiento)

(reverse <lista>)
(reverse ‘(a b c)) >>> (C B A)
(reverse '((A B) (C D))) >>> ((C D) (A B))
((C D) (A B))

(reverse ((A B) (C D)))

Da la vuelta al primer nivel de la lista

– LENGTH

(lenght <lista>)
3
(lenght ‘(a b c)) >>> 3
ht ‘( b ))

(l

Longitud de la lista, del primer nivel

– SUBST

(

(subst <nuevo> <viejo> <lista>)
)
(subst ‘a ‘b ‘(a b c)) >>> (A A C)

j

Sustituir con <nuevo> todas las
apariciones de <viejo> en <lista>

11

11

Otras funciones LISP, I

PROGN, PROG1

» Permiten escribir instrucciones compuestas

(como “{“ y “}” en el lenguaje C)
(como “{“ y “}” en el lenguaje C)

» Evalúan todas las sentencias que contienen

y devuelven la última o primera sentencia.

» (progn (+ 3 4) (+ 4 5)) >>> 9
» (progn (+ 3 4) (+ 4 5)) >>> 9
» (prog1 (+ 3 4) (+ 4 5)) >>> 7

(progn [<sentencia1>]
[<sentenciaN>])
(progn [<sentencia1>]… [<sentenciaN>])

(prog1 <sentencia1> [<sentencia2>]…

[<sentenciaN>])
[<sentenciaN>])

progn puede no recibir ningun argumento, entoces
devuelve NIL
devuelve NIL
prog1 tiene que recibir al menos una sentencia

12

12

Otras funciones LISP, II

PRINT

» (PRINT <forma>)
» Mostrar información al usuario
» Mostrar información al usuario.
» Si el valor de “<forma>” lo llamamos “A”, el

valor es A. Adicionalmente al ejecutarse,
también se imprime A

p

» > (progn (setf x (print ‘A)) (+ 3 4))

A

>>> 7

» > x
» > x

>>> A
READ

» (SETF variable (READ))
» (SETF variable (READ))
» Leer información del usuario

– CL-USER(1): (setf variable (read))
– HOLA! (lo introduce usuario y pulsa intro)
– HOLA!
– CL-USER(2): variable
– HOLA!
– CL-USER(3):

13

13

Otras funciones LISP, III

EVAL (en desuso)

» Evalúa dos veces una expresión
» (eval ‘(+ 3 4)) >> 7
» (eval (+ 3 4)) >> 7
» (setf a 'b)
» (setf b ‘c)
» a >> b
» b >> c
» (eval a) >> c
p
» +, -, *, /, ABS
» EXPT

Operadores matemáticos

– (expt 2 4) >>> 16
» MAX, MIN
MAX MIN
– (max 2 3 4 5) >>> 5

» FLOAT

» ROUND

– (float 1/2) >>> 0.5

(

)

– (round 3.2) >> 3

14

14

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
NIL. En caso contrario, el valor lógico
es “verdadero”.

IF (macro)
» Sintaxis:

Condicionales:
* if * when
* unless *cond

– (if <expresion> <forma1> [forma2])
– Si el valor lógico de <expresión> es “verdadero”,

devuelve el valor de <forma1>. Si es “falso”,
devuelve el valor de <forma2>.

» (if (> 5 (+ 2 2))

(+ 3 3)
(+ 3 4))

>>> 6

Si se desea que se evalúen
varias formas cuando sea cierta o
falsa la condición, qué hacemos?

Usamos progn o prog1
15

15

Condicionales, II

WHEN (macro)

» Sintaxis:

(when <expresion>
– (when <expresion>

<forma-1> <forma-2> ...<forma-n>)

– Si el valor lógico de <expresión> es “verdadero”,

ejecuta las formas <forma-1>, <forma-2>, ...
f
<forma-n> y devuelve como valor final el valor
l
l
de <forma-n>. Si es “falso”, devuelve NIL.

d

fi

l

l

l

» (when (> 5 (+ 2 2))

(+ 3 3)
( 3 3)
(+ 3 4))

>>> 7

j

S
Se ejecuta todo, no hace falta
h
poner progn o prog1

t d

f lt

t

No hay parte else!

y p

(when <exp> <forma>+) (if <exp> (progn <forma>+))
(when <exp> <forma>+) (if <exp> (progn <forma>+))

16

16

Condicionales, III

UNLESS (macro)

» Sintaxis:

(unless <expresion>
– (unless <expresion>

<forma-1> <forma-2> ...<forma-n>)

– Si el valor lógico de <expresión> es “falso”,
ejecuta las formas <forma-1>, <forma-2>, ...
f
<forma-n> y devuelve como valor final el valor
l
de <forma-n>. Si es “verdadero”, devuelve NIL.

d

fi

l

l

l

l

» (unless (> 5 (+ 2 2))

(+ 3 3)
( 3 3)
(+ 3 4))
>>> NIL

unless es el contrario a when

Cuando se devuelve NIL, no se
ha ejecutado nada en este caso