PDF de programación - LISP II

LISP II
(cid:122) Contenido de la sesión

(cid:190) Organización de memoria y

Operaciones destructivas

(cid:190) Funciones anónimas. Variables.

Alcances.

(cid:190) A-listas. Pattern matching.

1

Organización de la

memoria (1)

(cid:122) Celdas CONS

> (CONS ‘x ‘caza)

» Formadas por 2 punteros: CAR y CDR
» La función CONS crea una celda CONS a partir de memoria libre
> (CONS arg1 arg2)
arg1: inicializa la celda CAR
arg2: inicializa la celda CDR
(x . caza)
La notación par-punto es la utilizada por LISP para indicar
los elementos apuntados por el CAR y el CDR de una
celda CONS. Cuando CDR apunta a NIL, LISP simplifica
esta notación no mostrando dicho elemento apuntado.

(cid:122) MODIFICACIÓN DE CELDAS CONS

» Con SETF

– arg1: dirección de puntero en memoria
– arg2: la nueva dirección que deseamos que contenga arg1
> (SETF *c* ‘( x . caza))
(x . caza)
> (SETF (CAR *c*) ‘y)
(y . caza)
> (SETF (CDR *c*) ‘pesca)
(y . pesca)
> *c*
(y . pesca)

2

1

Organización de la

memoria (2)

Celda CONS:

(CONS ‘x ‘caza)

car cdr

x

caza

*c*

(SETF *c* ‘(x . caza))

x

caza

(SETF (CAR *c*) ‘y)

*c*

y

caza

*c*

(SETF (CDR *c*) ‘pesca)

y

pesca

3

Organización de la

memoria (3)
(cid:122) Disgregación de celdas CONS

» Asignando NIL al CDR de la/s celda/s que

deseamos disgregar

» Creando nuevas celdas CONS con SETF
>(SETF *d* ‘(A B C))
>(SETF *d2* (CDR *d*))
>*d*
>(SETF (CDR *d*) nil)
>(SETF *d3* (CDR *d2*))
>(SETF (CDR *d2*) nil)

(A B C)
(B C)
(A B C)
nil
(C)
nil

(cid:122) cada vez que el CDR de una celda se apunta
a NIL, el resto de celdas CONS que estaban
apuntadas por dicha celda quedan ocupando
memoria y no se pueden reutilizar.
» Tratar de optimizar las asignación de memoria

evitando el uso abusivo de variables globales

» Recuperar la memoria usada e inservible (garbage

collection)

4

2

Organización de la

memoria (4)

(cid:122) Garbage Collection

>*e*

>(SETF *e* ‘(dato1 dato2 dato3))
>(SETF *e* ‘(dato4 dato5 dato6))

» Analizamos el siguiente ejemplo:
(dato1 dato2 dato3)
(dato4 dato5 dato6)
(dato4 dato5 dato6)

(cid:122) La memoria utilizada en la primera asignación de
SETF (una serie de datos) queda ligada a la lista
inicial y no es accesible

(cid:122) Se denomina basura (garbage) a los objetos usados

que ocupan memoria y no pueden volver a ser
utilizados.
En el caso anterior, son basura:
(dato1 dato2 dato3)

5

Operaciones destructivas

(cid:122) Consideremos el siguiente ejemplo
(dogo galgo mastín labrador)
(dogo galgo mastín labrador)
(labrador mastín galgo dogo)
(labrador mastín galgo dogo)
(dogo)

>(SETF e ‘(dogo galgo mastín labrador))
>(SETF old-e e)
>(SETF e (NREVERSE old-e))
>e
>old-e

(cid:122) NREVERSE destruye la lista old-e, reasignando
punteros con el fin de no generar basura. Al
concluir, ambas listas comparten la última celda

e

Old-e

dogo

galgo

mastín

labrador

e

dogo

galgo

mastín

labrador

6

3

NREVERSE redefinido

(defun our-nreverse (n)

(our-nreverse-1 nil n))

(defun our-nreverse-1 (head tail)

(let ((residual (cdr tail)))

(our-nreverse-2 (setf (cdr tail) head)

residual
tail)))

(defun our-nreverse-2 (drop residual tail)

(if (null residual)

tail
(our-nreverse-1 tail residual)

Funciones anónimas

(cid:122) Orígenes

» Deriva de la notación usada por

Whitehead y Russell de los Principia
Mathematica

» Aplicada por vez primera por Alonzo
Church en 1941 en su definición del
cálculo lambda del que deriva LISP.
– ^x(x + x) (evolución de x-

circunflejo)

– Λx(x + x) (evolución de ^ a Λ)
– λx(x + x) (evolución de Λ a λ)
– (lambda (x) (+ x x)) (McCarthy

1958)
(cid:122) Utilización

» Mediante la notación #’
» (funcall #’(lambda (x) (+ x x)))

7

8

4

Ejemplos de aplicación
(cid:122) Problema: “Dada la lista (1 2 3), obtener sus cuadrados”
(cid:122) Solución 1
> (defun n-square (n) (expt n 2))
> (defun square-iterate (list)

(if (null list)

nil
(cons (n-square (car list))

(square-iterate (cdr list)))))

> (square-iterate ‘(1 2 3))
(1 4 9)
(cid:122) Solución 2
> (mapcar #’(lambda (x)

(expt x 2)) ‘(1 2 3))

(1 4 9)
(cid:122) Solución 3
> (mapcar #’n-square ‘(1 2 3))
(1 4 9)

Evaluación

(cid:122) Mediante

» Eval: en desuso

>(eval ‘(+ 1 2 3 4))
10

» Funcall: se aplica sobre una lista de

argumentos simples
>(funcall #‘+ 1 2 3 4)
10

» Apply: se aplica sobre una lista de uno o
más argumentos el último de los cuales
debe ser una lista
>(apply #’+ 1 2 ‘(3 4))
10
>(apply #’+ ‘(1 2 3 4))
10

9

10

5

Alcance léxico (lexical scope)

(cid:122) Este término hace referencia al conjunto de

reglas necesarias para determinar, sin
ambigüedad, la ligadura asociada a las variables
utilizadas en un fragmento de código.

(cid:122) En él, un símbolo hace referencia a la variable

que posee dicho nombre en el contexto en el que
dicho símbolo aparece
>(let ((x 10)) (defun foo () x))
>(let ((x 20)) (foo))

(cid:122) Cada vez que se efectúa una ligadura entre

variables se determina un cierre léxico para la
misma. Dicha variable es visible dentro del cierre
léxico que le corresponda.
(ejemplo-de-alcance z 3))

> (defun main (z)

10

> (defun ejemplo-de-alcance (x y)
(append (let ((x (car x)))
(list x y))

x
z))

z es lexicamente invisible

11

Alcance dinámico (dynamic

scope)

> (let ((x 10))

(defun foo ()

(declare (special x))
x))

12

6

(cid:122) Para que una variable posea alcance dinámico
debemos declararla como special en todos los
contextos en los que aparezca

(cid:122) En este ejemplo la x de la función no hace

referencia a la variable léxica definida, lo hará a
cualquier variable x que sea declarada como
especial en el momento de invocar la función

(cid:122) > (let ((x 20))

(declare (special x))
(foo))

(cid:122) Por tanto, en el alcance dinámico buscamos la

variable en el entorno en que fue definida la
función.

(cid:122) Utilidad: para dar a una variable global un valor
> (let ((*print-base* 16)) (print 32))

temporal diferente.

20

20
32

Tipos de variables

(cid:122) Libres

» Se denomina a aquellas variables que se definen fuera

de la función que las referencia (x en el ejemplo)

> (setf fn (let ((i 3))

#’(lambda (x) (+ x i))))

> (funcall fn 2)
5

(cid:122) Se pueden declarar (declare para local, declaim para

global), tipos (type) de variables con propósitos de
eficiencia de compilación (Graham 13.3).

13

A-listas. Pattern-matching.

(cid:122) Mediante EQUAL comparamos datos para ver si tienen
la misma estructura
>(EQUAL ‘(* pi (expt r 2) h) ‘(* pi (expt r 2) h))
T

(cid:122) EQUAL no puede comparar expresiones que tengan

partes constantes y partes variables. Supongamos, por
ejemplo, la función match:
>(match ‘(a b c) ‘(a b ?v))
((?v c))
>(match ‘(a c c) ‘(a b ?v))
nil
» Observamos que se crea una ligadura variable-valor

entre los términos que coincidan

(cid:122) Para conseguir este efecto utilizaremos las listas de

asociación (a-listas) que sirven para comparar
expresiones (patrones).

(cid:122) A-listas

» Son listas formadas por listas anidadas
» Cada sublista posee

– Una llave (el CAR)
– Un dato (el CDR)
– ((?padre Juan) (?hijo José))

» Para explorar una a-lista utilizamos ASSOC.

> (assoc :padre ((:padre Juan) (:hijo José)))
(:padre Juan)
> (assoc :abuelo ((:padre Juan) (:hijo José)))
Nil

(cid:122) A la vista de los alcances léxico y dinámico

comentados anteriormente diferenciamos los
siguientes tipos de variables:

(cid:122) Locales

(cid:122) Globales

» Su alcance es el del contexto en que se definen
» implícitamente poseen alcance léxico

» Se definen con setf (usar defparameter en archivos

de código fuente)

» Son visibles en cualquier lugar
» Poseen alcance dinámico, implícitamente son special
» Por convenio se denotan entre asteriscos

14

7

Ejemplo de uso de assoc

en NLP, (1)

(cid:122) La siguiente FSTN (Finite State Transition
Network) permite reconocer oraciones en
inglés como “A man is a consumer and often
very very stupid”
MOD

DET

1

NP
N

2

BV

3

ADV

4

5

DET

DET

MOD

8

ADJ

6

ADJ

7

N

9

CNJ

CNJ

• NP: kim, sandy, lee
• DET: a, the, her
• N: consumer, man, woman
• BV: is, was
• CNJ: and, or

• ADJ: happy, stupid
• MOD: very
• ADV: often, always,

Sometimes

• #: “jump”

15

Ejemplo de uso de assoc

en NLP, (2)

(cid:122) Definimos la asignación siguiente como

representación de la red anterior
(setf english

‘((:Initial (1))

(:Final (9))
(From 1 to 3 by NP)
(From 1 to 2 by DET)
(From 2 to 3 by N)
(From 3 to 4 by BV)
(From 4 to 5 by ADV)
(From 4 to 5 by |#|)
(From 5 to 6 by DET)
(From 5 to 7 by DET)
(From 5 to 8 by |#|)
(From 6 to 6 by MOD)
(From 6 to 7 by ADJ)
(From 7 to 9 by N)
(From 8 to 8 by MOD)
(From 8 to 9 by ADJ)
(From 9 to 4 by CNJ)
(From 9 to 1 by CNJ)))

16

8

Ejemplo de uso de assoc

en NLP, (3)

(cid:122) Las funciones siguientes nos permiten
acceder a los elementos descriptores
de la red (inicio, fin y transiciones)

(defun initial-nodes (network)

(nth 1 (assoc :Initial network)))

(defun initial-nodes (network)

(nth 1 (assoc :Final network)))

(defun transitions (network)

(cddr network))

(cid:122) Las transiciones tienen la estructura de

la lista
» (From <node> to <newnode> by <label>)
Ejercicio propuesto: Dado un nodo, obtener la
lista de sus destinos <newnode> y etiquetas
<label>. Ejemplo:

> (nodo 1 red)

((3 NP) (2 DET))

17

Ejemplo de uso de assoc

Match I, (1)

(cid:122) Podemos, por ejemplo, usar ASSOC para

construir una función que haga comparación
de patrones.

(defun match (pattern data bindings)
;; caso base: pattern es un átomo

(cond ((atom pattern)

(if (variablep pattern)

(psble-bind pattern data bindings)
(if (equal pattern data)

bindings
‘fallo)))

;; caso base: pattern no es un átomo y data sí

((atom data) ‘fallo)

;; caso recursivo

(t (let ((car-bind (match (car pattern)

(car data)
bindings)))

(if (eq car-bind ‘fallo)

‘fallo
(match (cdr pattern)

(cdr data)
car-bind))))))

18

9

Ejemplo de uso de assoc

Match II, (2)

(defun psble-bind (var data bindings)

(let ((ligaduras (as