PDF de programación - LISP II

Imágen de pdf LISP II

LISP IIgráfica de visualizaciones

Actualizado el 18 de Mayo del 2020 (Publicado el 20 de Diciembre del 2017)
329 visualizaciones desde el 20 de Diciembre del 2017
187,8 KB
10 paginas
Creado hace 14a (29/09/2005)
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
  • Links de descarga
http://lwp-l.com/pdf7969

Comentarios de: LISP II (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad