Inteligencia Artificial e I.C. 2004/2005 1.3 Dpto. Leng. Ciencias Comp

R.1.1. Concepto de expresin. Evaluacin de nmeros y listas.
Evaluar las siguientes expresiones: a) (+ (* 3 (- 5 3)) (/ 8 4)) b) (* 3 2 1 (- 5 3)) c) (/ (+ 3 2 1) (- 5 3)) d) ((+) (* 2 (- 5 3)) (/ 8 4)) e) (2 + 2) ************************** SOLUCION: Una expresin es una lista o un tomo. Un tomo es un smbolo o un nmero. Un nmero se puede escribir en cualquiera de las notaciones habituales (punto decimal, exponencial, ...). Un smbolo se representa por un nombre, que est formado por caracteres alfanumricos que no puedan interpretarse como un nmero. Algunos caracteres, como ", #, espacio no deben emplearse en el nombre de un smbolo. Sin embargo, otros como -, +, *, / pueden emplearse libremente. Por ejemplo, son smbolos PEPE, X12, *PEPE*, PE//P, JUAN, PEPE-JUAN, PEPE_JUAN1. Una lista es una sucesin de cero o ms expresiones entre parntesis. El blanco -no la coma- es el separador de expresiones dentro de una lista. Cada una de estas expresiones se denomina elemento de la lista. Por ejemplo, son listas () (A B C) (A (B C)) cuyos elementos son respectivamente -ninguno -los tres smbolos A B C. -el smbolo A y la lista (B C). Una expresin proporcionada a LISP se puede evaluar, es decir, LISP devuelve un valor que ser otra expresin- o bien seala un "error". En estas lecciones, si E se evala a V escribiremos E=>V. Las expresiones que se evalan se llaman formas. Un nmero se evala a s mismo. Una lista se evala del siguiente modo: 1. El primer elemento de la lista debe ser un smbolo s cuyo significado funcional est definido. Algunos smbolos tienen significados funcionales predefinidos; en cualquier caso, el programador puede definirlos en LISP (vd. R.1.8). El significado funcional es un objetoprocedimiento o funcin propiamente dicha, F. F es la funcin en s, y no debe confundirse con el smbolo s. 2. Se evalan los restantes elementos de la lista, obteniendo los valores V1, ..., Vn. Si el nmero o tipo de los valores obtenidos no es coherente con los argumentos requeridos por F, se produce error. 3. La lista se evala a F(V1, ..., Vn). Los signos aritmticos tienen asociados sus significados funcionales habituales. Exigen uno o ms argumentos numricos. Por tanto a) (+ (* 3 (- 5 3)) (/ 8 4)) 2 6 2 8 b) (* 3 2 1 (- 5 3)) 2 12
Inteligencia Artificial e I.C. 2004/2005
1.3
Dpto. Leng. Ciencias Comp.
c) (/ (+ 3 2 1) (- 5 3)) 6 2 3 d) Error: (+) es una lista. e) Error: 2 es un nmero.
NOTA. Los tipos de expresiones presentados en este ejercicio constituyen lo que podemos denominar "LISP puro". Pueden resumirse en el siguiente cuadro: lista expresin tomo nmero En Common LISP existen adems muchos otros tipos.
NOTA. Common Lisp permite emplear las notaciones decimal, exponencial, binaria, hexadecimal, etc. Tanto 1. como .1 son notaciones vlidas . Vd. (CLtL2, pg. 15-23, ANSI 2.3.2). NOTA. El nombre de un smbolo puede contener casi cualquier carcter. Para ello se emplean los caracteres de escape \ y |. Vd. (CLtL2, pg. 27-29, ANSI 2.2.4). NOTA. El primer elemento de una lista que se ha de evaluar puede ser tambin una expresin lambda. Vd. leccin 3. NOTA. El significado funcional de un smbolo s puede ser, adems de un objeto-procedimiento, una macro o una forma especial. En este caso, la evaluacin de la lista (s ...) sigue reglas diferentes. Vd. R.1.3., etc.
smbolo
1.4
R.1.2. Funciones numricas predefinidas. Escribir una expresin LISP que devuelva el mismo valor que las siguientes expresiones aritmticas escritas en notacin habitual: a) (531 mod 3) + (1 + 43 + 6/(6 - 3))4 b) ln |4221 - 5670| c) max(0, min(2,1), max(-1, 45)) d) 1 + 1 +1 + (7 -1) ************************** SOLUCION: SQRT tiene como significado funcional predefinido la funcin raz cuadrada. EXP tiene como significado funcional predefinido la funcin exponencial de base e. EXPT tiene como significado funcional predefinido la funcin exponencial de base cualquiera, y por ello necesita dos argumentos, el primero la base y el segundo el exponente. LOG tiene como significado funcional predefinido la funcin logaritmo. Si se da un solo argumento, se supone logaritmo natural. Si se da un segundo argumento, este es la base. ABS tiene como significado funcional predefinido la funcin valor absoluto. MOD tiene como significado funcional predefinido la funcin mdulo. MAX tiene como significado funcional predefinido la funcin mximo de cualquier nmero de argumentos. MIN tiene como significado funcional predefinido la funcin mnimo de cualquier nmero de argumentos. 1+ tiene como significado funcional predefinido la funcin sucesor. 1- tiene como significado funcional predefinido la funcin predecesor. Para resolver el problema, hay que escribir las expresiones en notacin prefija, empleando estos smbolos para representar las funciones. Por tanto las soluciones son a) (+ (MOD 531 3) (EXPT (+ 1 (* 4 3) (/ 6 (- 6 3)) (SQRT 4)))) b) (LOG (ABS (- (* 42 21) 5670))) c) (MAX 0 (MIN 2 1) (MAX -1 4.5)) d) (1+ (1+ (1+ (1- 7)))) NOTA: Common Lisp tiene definidos los tipos numricos entero, racional, real, doble precisin y complejo, entre otros. Tambin un juego completo de funciones trigonomtricas, hiperblicas, trigonomtricas inversas e hiperblicas inversas. Vd. (CLtL2, cap. 12, ANSI 12). NOTA: En los smbolos, LISP no distingue maysculas de minsculas (salvo que se indique explcitamente mediante el uso de caracteres de escape). De esta forma, las siguientes expresiones son idnticas a las anteriores: a) (+ (Mod 531 3) (expt (+ 1 (* 4 3) (/ 6 (- 6 3)) (sqrt 4))) b) (log (ABS (- (* 42 21) 5670))) c) (mAX 0 (Min 2 1) (MAX -1 4.5)) Escribiremos siempre las expresiones LISP en maysculas, tipo de letra COURIER.
1.5
R.1.3. Evaluacin de smbolos. Forma especial QUOTE. Evaluar las siguientes expresiones: a) T b) NIL c) () d) PEPE e) (QUOTE PE-PE) f) (QUOTE (PEPE1 PEPA1 MARI2)) g) 'PEPE h) '(PEPE '(PEPA MARI)) i) 'T j) (QUOTE ()) k) '7 l) '(+ 3 4) m) ('+ 3 4) ************************** SOLUCION: NIL es un smbolo que representa la lista vaca. Esto implica que la lista vaca es tanto una lista como un smbolo. Los smbolos T y NIL se evalan a s mismos. Un smbolo s puede estar ligado, es decir, contener una referencia o indicacin a otra expresin V. Llamamos ligadura. al par (s, V). Un smbolo s (salvo T o NIL) se evala al valor V al que est ligado. Posteriormente estudiaremos las formas en las que un smbolo se puede ligar; por ahora supondremos que todos los smbolos estn sin ligar. Cuando queremos hacer nfasis en el uso de un smbolo en una ligadura, decimos que es una variable. Segn esto, las respuestas son a) T => T b) NIL => NIL c) () => NIL d) PEPE => ... Error: PEPE sin ligar. El significado funcional de un smbolo puede ser un objeto-procedimiento o funcin en sentido estricto. Tambin puede ser una macro o una forma especial. Cuando el significado funcional del primer elemento de una lista es una macro o una forma especial, la evaluacin de la lista no sigue las reglas dadas en R.1.1., sino reglas propias. QUOTE es una forma especial que tiene un slo argumento: (QUOTE expresin) El valor de (QUOTE expresin) es precisamente expresin, sin evaluar. Cuando dos expresiones expr1 y expr2 se evalan siempre al mismo valor, emplearemos la notacin expr1 == expr2 Ya que QUOTE se emplea muy frecuentemente, existe una abreviatura: (QUOTE expresin) == 'expresin El intrprete LISP deshace las abreviaturas antes de la evaluacin. Segn esto, las respuestas a los restantes apartados son e) (QUOTE PE-PE) => PE-PE f) (QUOTE (PEPE1 PEPA1 MARI2)) => (PEPE1 PEPA1 MARI2) g) 'PEPE => PEPE h) '(PEPE '(PEPA MARI)) => (PEPE (QUOTE (PEPA MARI))) i) 'T => T j) (QUOTE ()) => NIL k) '7 => 7 l) '(+ 3 4) => (+ 3 4) m) ('+ 3 4) => ...Error: (QUOTE +) no tiene significado funcional.
NOTA. Las formas especiales forman parte de la definicin del lenguaje (CLtL2, pg. 72, ANSI 3.1.2.1.2). El usuario no puede definir nuevas formas especiales. Por el contrario, s es posible definir nuevas macros. En cualquier caso, el lector puede olvidarse de la diferencia entre macros y formas especiales.
1.6
R.1.4. Manejo elemental de listas. Evaluar las siguientes expresiones: a) (CONS (CAR '(CUQUI LOLI PEPI)) (CDR '(FALI LELI RODRI))) b) (CDR (CDR (CONS T (CDR '(PEPI))))) c) (CAR (CAR (CONS T (CDR '(PEPI))))) ************************** SOLUCION: CAR tiene como significado funcional predefinido la siguiente funcin: (CAR lista) -un nico argumento que debe ser una lista. -si el argumento no es NIL, el valor devuelto es el primer elemento de la lista argumento. -si el argumento es NIL, el valor devuelto por CAR es NIL. CDR tiene como significado funcional predefinido la siguiente funcin: (CDR lista) -un nico argumento que debe ser una lista. -si el argumento no es NIL, el valor devuelto es la lista obtenida quitando el primer elemento de la lista argumento. -si el argumento es NIL, el valor devuelto por CDR es NIL. CONS tiene como significado funcional predefinido la siguiente funcin: (CONS expresin lista) -exactamente dos argumentos. El segundo debe ser una lista. -el valor devuelto es una lista cuyo primer elemento es el primer argumento, y cuyos restantes elementos son los del segundo argumento. Segn esto, a) (CONS (CAR '(CUQUI LOLI PEPI)) (CDR '(FALI LELI RODRI))) (CUQUI LOLI PEPI) (FALI LELI RODRI) CUQUI (LELI RODRI) (CUQUI LELI RODRI) b) (CDR (CDR (CONS T (CDR '(PEPI))))) (PEPI) NIL (T) NIL NIL c) (CAR (CAR (CONS T (CDR '(PEPI))))) (PEPI) NIL (T) T Error: T no es una lista. NOTA: Existen funciones equivalentes a CAR y CDR: (CAR lista) == (FIRST lista) (CDR lista) == (REST lista)
NOTA: En realidad, el segundo argumento de CONS no tiene que ser una lista. No obstante, si no lo es, el valor devuelto tampoco es una lista, sino una lista punteada; vd. (CLtL, pg. 30-31, ANSI 14) y la leccin 8.
1.7
R.1.5. Ms funciones para manejo de listas. Evaluar las siguientes expresiones: a) (CONS (CDAR '((CONS BUENOS DIAS))) (CADDR '(BUENAS B (TARDES NOCHES)))) b) (LIST (CONS '(CUQUI) '(LOLI)) (APPEND '(CUQUI) '(LOLI)) (LIST '(CUQUI) '(LOLI))) c) (LENGTH (APPEND '(CUQUI LOLI) '(LOLI CUQUI) '((CUQUI LOLI)))) ************************** SOLUCION: a) Si a1, ...an son caracteres A D y n<5, entonces est predefinido que (Ca1a2...anR lista) == (Ca1R (Ca2R ... (CanR lista) ...)) Por tanto (CONS (CDAR '((CONS BUENOS DIAS))) (CADDR '(BUENAS B (TARDES NOCHES)))) ((CONS BUENOS DIAS)) (BUENAS B (TARDES NOCHES)) (CONS BUENOS DIAS) (B (TARDES NOCHES)) (BUENOS DIAS) ((TARDES NOCHES)) (TARDES NOCHES) ((BUENOS DIAS) TARDES NOCHES) b) LIST tiene como significado funcional predefinido la siguiente funcin: (LIST [expresin]*) -un nmero indeterminado de argumentos. -si no hay ningn argumento, el valor devuelto es NIL. -si hay algn argumento, el valor devuelto es una lista cuyos elementos son los argumentos. APPEND tiene como significado funcional predefinido la siguiente funcin: (APPEND [lista]*) -un nmero indeterminado de argumentos, que deben ser listas. -si no hay ningn argumento, el valor devuelto es NIL. -si hay algn argumento, el valor devuelto es una lista cuyos elementos son los elementos de los argumentos. Por tanto LIST arg1: CONS arg1: (CUQUI) arg2: (LOLI) ((CUQUI) LOLI) arg2: APPEND arg1: (CUQUI) arg2: (LOLI) (CUQUI LOLI) arg3: LIST arg1: (CUQUI) arg2: (LOLI) ((CUQUI) (LOLI)) => (((CUQUI) LOLI) (CUQUI LOLI) ((CUQUI) (LOLI)))
1.8
c) LENGTH tiene como significado funcional predefinido la siguiente funcin: -un nico argumento, que debe ser una lista. -el valor devuelto es la longitud del argumento, es decir, el nmero de elementos de la lista. Por tanto LENGTH arg: APPEND arg1: (CUQUI LOLI) arg2: (LOLI CUQUI) arg3: ((CUQUI LOLI)) (CUQUI LOLI LOLI CUQUI (CUQUI LOLI)) => 5 NOTA: Existen funciones equivalentes a algunas de las anteriores: (CADR lista) == (SECOND lista) (CADDR lista) == (THIRD lista)
NOTA: En realidad, el ltimo argumento de APPEND no tiene que ser una lista. No obstante, si no lo es, el valor devuelto tampoco es una lista, sino una lista punteada; vd. (CLtL2 90, pg. 30-31, ANSI 14) y la leccin 8.
1.9
R.1.6. Manejo de listas. Relaciones notables. Discutir en qu condiciones son vlidas las siguientes afirmaciones: a) (CONS (CAR 'lista) (CDR 'lista)) => lista b) (CAR (CONS 'expresin 'lista)) => expresin c) (CDR (CONS 'expresin 'lista)) => lista d) (CONS 'expresin1 (LIST 'expresin2)) == (LIST 'expresin1 'expresin2) e) (CONS 'expresin1 (LIST NIL)) == (APPEND (LIST 'expresin1) NIL) ************************** SOLUCION: Supongamos que lista es realmente una lista. a) Si lista no es NIL, CAR devolver su primer elemento, CDR su resto, y CONS aplicado a estos argumentos devolver la lista original. Sin embargo, si la lista es NIL, CAR devolver NIL, CDR devolver NIL, y CONS aplicado a NIL NIL devolver (NIL). Por tanto, la afirmacin es vlida nicamente si lista es distinta de NIL. b y c) Si CONS se ha evaluado, el valor devuelto es una lista, cuyo primer elemento es expresin y cuyo resto es lista. Por tanto, CAR devolver expresin y CDR lista. Las afirmaciones son vlidas. d) Ambas expresiones son siempre equivalentes, ya que ambas se evalan a listas de dos elementos cuyo primer elemento es expresin1 y cuyo segundo elemento es expresin2. e) Ambas expresiones no son nunca equivalentes, ya que la primera se evala siempre a una lista de dos elementos y la segunda a una lista de slo un elemento. Por ejemplo, (CONS 'A (LIST NIL)) => (A NIL) (APPEND (LIST 'A) NIL) => (A)
Inteligencia Artificial e I.C. 2004/2005 1.10
R.1.7. La funcin EVAL. Evaluar las siguientes expresiones: a) (EVAL (APPEND (CDDDR '(- + * /)) (LIST (EVAL '(+ 3 5))) (CONS 4 NIL))) b) (EVAL (QUOTE (QUOTE (CAR (A B))))) c) (EVAL (QUOTE (CAR (QUOTE (A B))))) d) (EVAL (CAR (QUOTE (QUOTE (A B))))) e) (CAR (EVAL (QUOTE (QUOTE (A B))))) ************************** SOLUCION: EVAL tiene como significado funcional predefinido la siguiente funcin: (EVAL expresin) -un nico argumento. -el valor devuelto es el valor resultante de evaluar el argumento. De esta forma, (EVAL expresin) realiza dos evaluaciones de expresin: la primera, debida al ciclo normal de evaluacin; la segunda, debida al uso explcito de EVAL. Por tanto a) EVAL arg: APPEND arg1: CDDDR arg: (- + * /) (/) arg2: LIST arg: EVAL arg: (+ 3 5) 8 (8) arg3: CONS arg1: 4 arg2: NIL (4) (/ 8 4) => 2 b) (EVAL (QUOTE (QUOTE (CAR (A B))))) => (CAR (A B)) c) (EVAL (QUOTE (CAR (QUOTE (A B))))) => A d) (EVAL (CAR (QUOTE (QUOTE (A B))))) => error: QUOTE sin ligar e) (CAR (EVAL (QUOTE (QUOTE (A B))))) => A NOTA: No es buen estilo de programacin emplear la forma EVAL. Adems, EVAL no recupera los valores de las variables ligadas lxicamente. Por todo ello, "en la prctica, la principal utilidad de EVAL es explicar la semntica del lenguaje. EVAL y SET no se suelen usar realmente en los programas, as que si descubres que los ests empleando -y no ests implementando un intrprete LISP- es probable que ests haciendo algo mal" (Charniak 87, pg. 110).
R.1.8. Definicin de significados funcionales de smbolos. Concepto de entorno. Evaluar las siguientes expresiones en el orden dado, indicando los efectos laterales: a) (DEFUN CUADRADO (N) (* N N)) (CUADRADO 7) (CUADRADO (CUADRADO 7)) b) (DEFUN RAICES (A B C) (LIST (/ (+ (- B) (SQRT (- (* B B) (* 4 A C)))) (* 2 A)) (/ (- (- B) (SQRT (- (* B B) (* 4 A C)))) (* 2 A)))) (RAICES 1 0 -1) RAICES ************************** SOLUCION: DEFUN tiene el siguiente significado funcional predefinido: (DEFUN smbolo lista-lambda cuerpo) -DEFUN es una macro. Ello quiere decir que no evala sus argumentos en la forma explicada en R.1.1. DEFUN toma sus argumentos literalmente. -el primer argumento es un smbolo. -el segundo argumento es una lista-lambda. Por ahora, consideraremos que una lista-lambda es una lista de cero o ms smbolos que se denominan parmetros. -cuerpo est formado por un nmero cualquiera de expresiones. -el valor devuelto es smbolo. -Se entiende por efecto lateral cualquier consecuencia de la evaluacin de una expresin que no sea la simple determinacin del valor resultante. DEFUN tiene el siguiente efecto lateral: -se crea un objeto-procedimiento F a partir del cuerpo -se establece F como el significado funcional de smbolo. Concretamente, una vez ejecutado (DEFUN smbolo lista-lambda cuerpo), cuando se evala (smbolo [argumento]*) ocurre lo siguiente: -Se crea un entorno. Un entorno es un conjunto de ligaduras. Los smbolos ligados son precisamente los parmetros de la funcin, y sus valores los argumentos que se pasan. Si el nmero de argumentos no coincide con el de parmetros, se produce un error. -En este entorno se evalan las expresiones del cuerpo. -El valor devuelto por la funcin es el de la ltima expresin evaluada. Ms adelante se explicarn aspectos adicionales de los entornos. Por tanto a) (DEFUN CUADRADO (N) (* N N)) => CUADRADO y como efecto lateral, CUADRADO tiene como significado funcional "la funcin de n que devuelve el cuadrado de n". Representemos los entornos por rectngulos en cuyo interior figuran las ligaduras, y adosemos las expresiones a los entornos donde se evalan. Entonces (CUADRADO 7) == N<-7 (* N N) => 49 (CUADRADO (CUADRADO 7)) == N<-? (* N N) Para determinar el valor al que se liga N se realiza otra llamada a CUADRADO N<-7 (* N N) => 49 Por tanto
N<-49 (* N N) => 2401 b) (DEFUN RAICES (A B C) (LIST (/ (+ (- B) (SQRT (- (* B B) (* 4 A C)))) (* 2 A)) (/ (- (- B) (SQRT (- (* B B) (* 4 A C)))) (* 2 A)))) => RAICES y como efecto lateral, RAICES tiene el significado funcional "la funcin de a, b y c que devuelve la lista formada por las dos races de la ecuacin ax2+bx+c=0". Entonces (RAICES 1 0 -1) == A<- 1 B<- 0 C<- -1 (LIST (/ (+ (- B) (SQRT (- (* B B) (* 4 A C))))(* 2 A)) (/ (- (- B) (SQRT (- (* B B) (* 4 A C))))(* 2 A)) ) => (1 -1) Por otra parte RAICES => error: RAICES sin ligar En CommonLisp son independientes el significado funcional y la ligadura del smbolo: los valores establecidos para la una no afectan a la otra. Por tanto, el significado funcional establecido para RAICES no es su ligadura y al intentar evaluar el smbolo RAICES se produce un error. Podemos visualizar la situacin segn el esquema siguiente: significado funcional
"la funcin de a, b y c que devuelve la lista formada por las dos races de la ecuacin ax2+bx+c=0"
RAICES
????? ligadura
R.1.9. Evaluacin de funciones definidas por el usuario. Supuestas las definiciones de R.1.8, evaluar las siguientes expresiones en el orden dado, indicando los efectos laterales que se producen: a) (DEFUN CUADRADO (N) (+ N N)) (CUADRADO 7) b) (DEFUN LIO2 (L) (LIST (LIO1 L L) (CAR L))) (DEFUN LIO1 (L1 L2) (LIST (CAR L1) (CAR L2))) (LIO2 '(DICEN DE UN SABIO)) c) (DEFUN LIO3 (L) (LIO4 (CONS 'A L))) (DEFUN LIO4 (M) (APPEND L M)) (LIO3 '(VECES)) d) (DEFUN KK1 (N) 27) (KK1 PEPE) ************************** SOLUCION: a) (DEFUN CUADRADO (N) (+ N N)) => CUADRADO y como efecto lateral, CUADRADO tiene el significado funcional "la funcin de n que devuelve el duplo de n". Ntese que desaparece el significado funcional anteriormente asignado a CUADRADO. Entonces (CUADRADO 7) => 14 b) (DEFUN LIO2 (L) (LIST (LIO1 L L) (CAR L))) => LIO2 y como efecto lateral, LIO2 tiene el significado funcional "la funcin de L que devuelve una lista formada por lio1(L, L) y car(L)". (DEFUN LIO1 (L1 L2) (LIST (CAR L1) (CAR L2))) => LIO1 y como efecto lateral, LIO1 tiene el significado funcional "la funcin de L1 y L2 que devuelve una lista con los primeros elementos de L1 y L2". Entonces (LIO2 '(DICEN DE UN SABIO)) == L<-(DICEN DE UN SABIO) (LIST (LIO1 L L) (CAR L)) La evaluacin del primer argumento de LIST produce una llamada a LIO1: L1<-(DICEN DE UN SABIO) L2<-(DICEN DE UN SABIO) (LIST (CAR L1) (CAR L2)) => (DICEN DICEN) y por tanto L<-(DICEN DE UN SABIO) (LIST (LIO1 L L) (CAR L)) => ((DICEN DICEN) DICEN) c) (DEFUN LIO3 (L) (LIO4 (CONS 'A L))) => LIO3 y como efecto lateral, LIO3 pasa ahora a tener el significado funcional "la funcin de L que CONSa el smbolo A y L". (DEFUN LIO4 (M) (APPEND L M)) => LIO4 y como efecto lateral, LIO4 pasa ahora a tener el significado funcional "la funcin de M que APPENDa L y M". Pero, quin es L en esta definicin? Vemoslo: (LIO3 '(VECES)) => Error: L sin ligar. Sigamos paso a paso esta ltima evaluacin:
(LIO3 '(VECES)) == Entorno 1 L<-(VECES) (LIO4 (CONS 'A L)) == Entorno 2 M<-(A VECES) (APPEND L M) => Error: L sin ligar. Ntese que el entorno 2 se ha creado independientemente del entorno 1: las ligaduras de 1 no tienen efecto en 2 y, por tanto, L no est ligado a (VECES). En general, la creacin de entornos se rige por la regla siguiente: si al evaluar la expresin E1 resulta necesario evaluar una subexpresin E2, el entorno de evaluacin de E2 es independiente del entorno de evaluacin de E1. Esta regla se denomina regla de mbito lxico. d) (DEFUN KK1 (N) 27) => KK1 (KK1 PEPE) == => Error: PEPE sin ligar. Siguiendo la regla de evaluacin dada en R.1.1, se intenta evaluar el segundo elemento de la lista, que es un smbolo sin ligar; por tanto, se produce y seala este error. Sin embargo, si LISP fuera suficientemente astuto, habra razonado as: (KK1 PEPE) == la funcin que siempre devuelve 27, aplicada a la ligadura de PEPE => 27 pues es claro que no resulta necesario calcular el valor del argumento de KK1, ya que es irrelevante para calcular el valor que se debe devolver. El orden de evaluacin enunciado en R.1.1. es el que sigue LISP y se llama orden aplicativo, de llamada por valores o call-by-value. El orden de evaluacin sugerido ahora -que LISP no sigue- se llama orden normal, de llamada por necesidad o call-by-need.
R.1.10. Primeros ejercicios de diseo de funciones. Escribir en LISP las definiciones de las siguientes funciones: a)la funcin de L que devuelve la lista formada a partir de L poniendo su tercer elemento en primer lugar. b)la funcin de L (lista) y a (tomo) que devuelve la lista formada sustituyendo el tercer elemento de L por a. c)la funcin que da el determinante de una matriz de 2x2. Supngase que la matriz est representada como una lista de listas ((a11 a12) (a21 a22)). ************************** SOLUCION: a) El tercer elemento de L es (CADDR L) Sus dos primeros elementos son (CAR L)y(CADR L) La lista de los restantes elementos es (CDDDR L) Llamemos SUBIR-TERCERO a la funcin. La definicin pedida ser (DEFUN SUBIR-TERCERO (L) (CONS (CADDR L) (CONS (CAR L) (CONS (CADR L) (CDDDR L))))) b) Llamemos SUST-TERCERO a la funcin. Anlogamente (DEFUN SUST-TERCERO (A L) (CONS (CAR L) (CONS (CADR L) (CONS A (CDDDR L))))) c) Llamemos DET a la funcin. (DEFUN DET (M) (- (* (CAAR M) (CADADR M)) (* (CADAR M) (CAADR M))))
R.2.1. Predicados y conectivas lgicas. Evaluar las siguientes expresiones, indicando qu subexpresiones quedan sin evaluar: a) (AND PEPE (EQ PEPE Pepe) (= 7 7.0) (EQUAL (A) (A))) b) (OR (EQ (A) (A)) (EQUAL (A) (A)) BASURA) c) (OR (EQL (A)(A)) (EQL 7 7.0) (AND (EQL 7.0 7) (EQL A A))) d) (AND (NOT (EQ PEPE JOSE)) (> 3 2) (< 1 3) 34) e) (OR (NOT (ATOM NIL)) () (SYMBOLP 7) (NUMBERP T) (LISTP NIL)) f) (OR (ZEROP 1) (PLUSP -1) (MINUSP 0) (AND PEPE (KK QQ))) g) (OR (NULL PEPE) (NULL (A)) (ENDP (A)) (ENDP PEPE)) ************************** SOLUCION: Llamaremos predicados a las funciones que devuelven T o NIL. En LISP existen, entre otros, los siguientes predicados predefinidos de comparacin: T e1 y e2 son el mismo smbolo (EQL e1 e2) e1 y e2 son EQ o nmeros iguales de igual tipo (EQUAL e1 e2) e1 y e2 son EQL o listas iguales (= e1 e2 ...) e1, e2, ... son nmeros todos iguales de cualquier tipo (EQUALP e1 e2)e1 y e2 son EQUAL o son = (EQ e1 e2) (< e1 e2 ...) e1, e2, ... son nmeros y forman una sucesin estrict. creciente (> e1 e2 ...) e1, e2, ... son nmeros y forman una sucesin estrict. decreciente (<= e1 e2 ...)e1, e2, ... son nmeros y forman una sucesin creciente (>= e1 e2 ...)e1, e2, ... son nmeros y forman una sucesin decreciente error
algn argumento no numrico
algn argumento no numrico algn argumento no numrico algn argumento no numrico algn argumento no numrico
Llamaremos falso a NIL. Llamaremos verdadero a cualquier valor distinto de NIL. Las conectivas lgicas estn predefinidas mediante las siguientes macros: (NOT expresin) -un nico argumento. -el valor devuelto es T si expresin es falsa, y NIL si expresin es verdadera. (AND [expresin]*) -un nmero indeterminado de argumentos. -si algn argumento es falso, el valor devuelto es falso, es decir, NIL. Los argumentos que haya tras este no se evalan. -si ningn argumento es falso, el valor devuelto es el del ltimo argumento (T si hay 0 argumentos). (OR [expresin]*) -un nmero indeterminado de argumentos. -si algn argumento es verdadero, el valor devuelto es el del primer argumento verdadero. Los argumentos que haya tras este no se evalan. -si ningn argumento es verdadero, el valor devuelto es falso, es decir, NIL. En particular, si hay 0 argumentos, se devuelve NIL.
Inteligencia. Artificial e I.C.. 2004/05
2.3
Segn esto a) (AND PEPE (EQ PEPE Pepe) (= 7 7.0) (EQUAL (A) (A))) PEPE PEPE PEPE T T T =>T Todas las expresiones se evalan. b) (OR (EQ (A) (A)) (EQUAL (A) (A)) BASURA) NIL T =>T Queda sin evaluar BASURA. c) (OR (EQL (A)(A)) (EQL 7 7.0) (AND (EQL 7.0 7) (EQL A A))) NIL NIL NIL NIL =>NIL Queda sin evaluar (EQL A A)). d) (AND (NOT (EQ PEPE JOSE)) (> 3 2) (< 1 3) 34) NIL T T T 34 =>34 Todas las expresiones se evalan. En LISP existen, entre otros, los siguientes predicados predefinidos de tipo: T error (NULL e) e es NIL (ATOM e) e es un tomo (SYMBOLP e) e es un smbolo (NUMBERP e) e es un nmero (LISTP e) e es una lista (ENDP e) e es NIL (lista vaca) e no es una lista En LISP existen, entre otros, los siguientes predicados numricos predefinidos: T error (ZEROP e) e es 0 (cualquier tipo) e no es un nmero (PLUSP e) e>0 e no es un nmero (MINUSP e) e<0 e no es un nmero (EVENP e) e es un nmero par e no es un nmero entero (ODDP e) e es un nmero impar e no es un nmero entero Segn esto e) (OR (NOT (ATOM NIL)) () (SYMBOLP 7) (NUMBERP T) (LISTP NIL)) T NIL NIL NIL NIL T =>T Todas las expresiones se evalan. Inteligencia. Artificial e I.C.. 2004/05 2.4 Dpto. Leng. Ciencias Comp.
f) (OR (ZEROP 1) (PLUSP -1) (MINUSP 0) (AND 'PEPE '(KK QQ))) NIL NIL NIL (KK QQ) =>(KK QQ) Todas las expresiones se evalan. g) (OR (NULL PEPE) (NULL '(A)) (ENDP '(A)) (ENDP 'PEPE)) NIL NIL NIL Error: PEPE no es una lista.
NOTA: La definicin de EQ dada aqu no es correcta. Pero es la mejor que podemos dar de momento, ya que la autntica requiere el conocimiento de la representacin intermedia (clulas CONS): vd. leccin 8. NOTA: La diferencia entre ENDP y NULL no es meramente estilstica: en efecto, la primera da error cuando recibe un argumento que no es una lista, mientras que la segunda devuelve NIL.
2.5
R.2.2. Expresiones condicionales. Evaluar las siguientes expresiones, indicando qu subexpresiones quedan sin evaluar: a) (WHEN 'PEPE 'JOSE) b) (UNLESS 'PEPE (1 + 2)) c) (IF (SYMBOLP (CDR (A))) (CAR (A B)) (CDR (A B))) d) (COND ((EQ (A) (A)) ESTO ES BASURA) ((EQL (A) (A)) 'RANURA-2) ('RANURA-31 'RANURA-32 'RANURA-33) ((= (A) (A)) 'RANURA-4) (T NIL)) e) (COND ((EQ (A) (A)) 'RANURA-1) ((EQL (A) (A)) 'RANURA-2) ((EQUAL (A) (A))) ((= (A) (A)) ESTO ES BASURA)) ************************** SOLUCION: En LISP existen predefinidas varias macros y formas especiales que llevan a cabo evaluaciones condicionales. Las ms sencillas son WHEN y UNLESS: (WHEN condicin [expresin]*) -dos o ms argumentos: una condicin y un nmero indeterminado de expresiones. -siempre se evala condicin . Si resulta falsa, el valor devuelto es falso, es decir, NIL. Los argumentos que haya tras condicin no se evalan. -si resulta verdadera, se evalan todas las expresiones y el valor devuelto es el de la ltima de ellas. (UNLESS condicin [expresin]*) -dos o ms argumentos: una condicin y un nmero indeterminado de expresiones. -siempre se evala condicin . Si resulta verdadera, el valor devuelto es falso, es decir, NIL. Los argumentos que haya tras condicin no se evalan. -si resulta falsa, se evalan todas las expresiones y el valor devuelto es el de la ltima de ellas. Segn esto a) (WHEN 'PEPE 'JOSE) JOSE b) (UNLESS 'PEPE (1 + 2)) NIL Queda sin evaluar (1 + 2). Otra posibilidad de evaluacin condicional la proporciona IF: (IF condicin expresin-s [expresin-no]) -tres (o dos) argumentos: una condicin y dos (o una) expresiones. -siempre se evala condicin . Si resulta verdadera, se evala expresin-s y este es el valor que se devuelve. La otra expresin queda sin evaluar. -si resulta falsa, se evala expresin-no y este es el valor que se devuelve. La otra expresin queda sin evaluar. Si expresin-no se omite, se devuelve NIL. Segn esto c) (IF (SYMBOLP (CDR (A))) (CAR (A B)) (CDR (A B))) NIL T A =>A Queda sin evaluar (CDR (A B)).
2.6
Por ltimo, la forma ms verstil de evaluacin condicional la proporciona COND: (COND clusula*) -COND tiene un nmero indeterminado de argumentos. Cada argumento es una clusula. Una clusula es una lista formada por una o ms expresiones. La primera expresin de cada clusula es la condicin y a las restantes podemos denominarlas acciones: (condicin [accin]*) -se evalan secuencialmente las condiciones de cada clusula, en el orden en que estas aparecen, hasta encontrar la primera condicin verdadera. Una vez encontrada, se evalan secuencialmente las acciones de esta clusula. El valor de COND es el de la ltima de ellas. -las restantes expresiones quedan sin evaluar. Es decir, no se evala ningn elemento de las clusulas de ms abajo, ni las acciones de las clusulas de ms arriba. -si ninguna condicin es verdadera, el valor devuelto es NIL. Segn esto d) (COND ((EQ (A) (A)) ESTO ES BASURA) ((EQL (A) (A)) 'RANURA-2) ('RANURA-31 'RANURA-32 'RANURA-33) ((= (A) (A)) 'RANURA-4) (T NIL)) (EQ (A) (A)) => NIL (EQL (A) (A)) => NIL 'RANURA-31 => RANURA-31 => RANURA-33 Las restantes expresiones quedan sin evaluar. e) (COND ((EQ (A) (A)) 'RANURA-1) ((EQL (A) (A)) 'RANURA-2) ((EQUAL (A) (A))) ((= (A) (A)) ESTO ES BASURA)) (EQ (A) (A)) => NIL (EQL (A) (A)) => NIL (EQUAL (A) (A)) => T => T Las restantes expresiones quedan sin evaluar.
NOTA: Es un buen hbito de programacin hacer que la ltima clusula de COND sea siempre de la forma (T expresin), que equivale al otherwise o en otro caso de otros lenguajes de programacin. Ntese que si esta ltima clusula es (T NIL), podramos omitirla, ya que la definicin de COND la lleva implcita. No obstante, es costumbre escribirla explcitamente.
2.7
R.2.3. Recursin en N. Definir recursivamente funciones que resuelvan los siguientes problemas: a) calcular el factorial de un nmero natural. b) calcular los nmeros de Stirling de primera especie alguna de las siguientes propiedades:
n m, n, m 0. Para ello se har uso de
n n n 0 = 0, n > 0; m = 0, n < m; n = 1 n n 1 n 1 m= (n-1) m + m 1 en otro caso

c) calcular la siguiente funcin f: f tiene un nmero natural n como argumento. Si n>100, f(n) es la identidad; en otro caso, si n es par, f(n)=f(n+1)n/2 y si n es impar f(n)=f(3n+1). ************************** SOLUCION: a) Podra faltar este ejercicio en un curso de programacin? Caso base: n =0 y 0!=1. Recursin sobre el predecesor de n: n! =n(n-1)! En n pasos se alcanza el caso base, por tanto la definicin es vlida. En LISP, p. ej. con IF, ser (DEFUN FACTORIAL (N) (IF (ZEROP N) 1 (* N (FACTORIAL (1- N))))) b) De la segunda y tercera propiedades se sigue que es
0 0 = 1; = 0, m 0 0 m
Por tanto, podemos tomar como caso base n =0. La cuarta propiedad permite reducir el primer argumento una unidad en cada llamada, luego en n pasos se alcanza -por ambos caminos- el caso base. En LISP (DEFUN STIRLING-1 (N M) (COND ((ZEROP N) (IF (ZEROP M) 1 0)) (T (+ (* (1- N) (STIRLING-1 (1- N) M)) (STIRLING-1 (1- N) (1- M)))))) c) Caso base: n>100. Entonces f(n) = n. Recursin sobre los sucesores de n: f(n) se calcula en funcin de f(n+1) o de f(3n+1). En ambas llamadas recursivas se incrementa el argumento al menos en 1, luego a lo sumo en 100 - n pasos se alcanza el caso base por todos los caminos. En LISP (DEFUN F1 (N) (COND ((> N 100) N) ((EVENP N) (/ (* (F1 (1+ N)) N) 2)) (T (F1 (1+ (* N 3)))))) NOTA. Las definiciones que hacen uso de la recursin pueden llegar a ser muy ineficientes en espacio y tiempo, especialmente si como en b) se generan varias llamadas recursivas en cada llamada a la funcin. Trataremos esta cuestin en la leccin 5.
2.8
R.2.4. Recursin en R. a) La ecuacin f(x) = x3 - x2 - x - 2 = 0 tiene solamente una solucin en el intervalo (0, 5). Escribir un programa LISP que la encuentre, empleando el procedimiento de bsqueda dicotmica. b) La funcin f(x) = 3x4 - 4x3 - 6x2 - 24x + 7 tiene solamente un extremo, que es un mnimo, en el intervalo (-5, 5). Escribir un programa LISP que lo encuentre, empleando el mtodo de la razn urea. ************************** SOLUCION: a) Como es sabido, el procedimiento es el siguiente: sea c el punto medio de [a, b]; se calcula el valor de f(c) y se busca de nuevo en el intervalo [a, c] (si el cambio de signo de f(x) se produce en l) o en el [c, b] (en otro caso). El procedimiento se repite hasta que la longitud del intervalo considerado es menor que (valor pequeo fijado de antemano) y finalmente devuelve el punto medio del intervalo finalmente considerado. Ya que en cada paso la longitud del intervalo se reduce a la mitad, en log2(b-a)/ pasos se alcanza la terminacin. Podemos conceptualizar el proceso como una bsqueda irrevocable en un espacio de estados. El algoritmo general de bsqueda irrevocable es: "si el estado E es final, devolverlo como solucin; en otro caso, la solucin es la que devuelve el algoritmo aplicado a un sucesor de E". (DEFUN BUSCAR0 (E) (COND ((FINALP E) E) (T (BUSCAR0 (ELEGIR-SUC E))))) Tomamos como raz el punto medio del intervalo final: (DEFUN RAIZ-F () (PTO-MEDIO (BUSCAR0 (ESTADO-INICIAL)))) En este caso los estados son intervalos, dados por sus extremos IZQ y DER. Para evitar clculos redundantes, almacenamos adems en cada estado los valores de la funcin f en ambos extremos, FIZQ y FDER. Los constructores y selectores sern pues (DEFUN HACER-ESTADO (X Y) (LIST X Y (F X) (F Y))) (DEFUN IZQ (E) (CAR E)) (DEFUN DER (E) (CADR E)) (DEFUN FIZQ (E) (CADDR E)) (DEFUN FDER (E) (CADDDR E)) La nica operacin adicional sobre estados es calcular el punto medio: (DEFUN PTO-MEDIO (E) (/ (+ (IZQ E) (DER E)) 2)) Ya podemos completar la solucin, definiendo FINALP y ELEGIR-SUC (DEFUN FINALP (E) (< (ABS (- (IZQ E) (DER E))) EPSILON)) (DEFUN ELEGIR-SUC (E) (COND ((MISMO-SIGNO (F (PTO-MEDIO E)) (FIZQ E)) (HACER-ESTADO (PTO-MEDIO E) (DER E))) (T (HACER-ESTADO (IZQ E) (PTO-MEDIO E))))) y tambin el estado inicial: (DEFUN ESTADO-INICIAL () (HACER-ESTADO 0 5)) Hemos empleado adems algunas constantes y funciones numricas auxiliares: (DEFCONSTANT EPSILON 1F-6) (DEFUN MISMO-SIGNO (X Y) (PLUSP (* X Y))) (DEFUN F (X) (+ (* X (+ (* X (+ (* X 1) -1)) -1)) -2)) Hasta ahora no hemos dicho cmo se pueden representar valores constantes en LISP. Ello se consigue con la forma DEFCONSTANT: (DEFCONSTANT smbolo expresin) DEFCONSTANT evala la expresin, y el smbolo pasa a estar ligado permanentemente al valor resultante. No es posible cambiar esta ligadura; se produce un error al intentarlo.
2.9
b) Como es sabido, el procedimiento es el siguiente (vd. figura II.1): se consideran dos puntos b, c situados en [a, d] y tales que b = a + q(d -a) y c = a + p(d - a), donde p = (5 - 1)/2, q = p2 Se calculan los valores de f(b) y f(c); si f(b)<f(c), se busca de nuevo en el intervalo [a, c] y en otro caso a b c d en el [b, d]. El procedimiento se repite hasta que la longitud del intervalo considerado es menor que Fig. II.1. Bsqueda por el mtodo de la razn urea. (valor pequeo fijado de antemano) y finalmente devuelve el punto medio del intervalo finalmente considerado. Recurdese que los puntos b y c son tales que en la siguiente llamada podemos siempre reutilizar uno de ellos: por ejemplo, si seleccionamos el intervalo [b, d] el punto c es precisamente b + q(d -b), y si seleccionamos el intervalo [a, c] el punto b es precisamente a+ p(c-a). Ya que en cada paso la longitud del intervalo se reduce al menos en el factor 1/p, a lo sumo en log1/p(b-a)/ pasos se alcanza la terminacin. Podemos conceptualizar el proceso como una bsqueda irrevocable en un espacio de estados. El procedimiento principal ser anlogo al del apartado anterior: (DEFUN MIN-F () (PTO-MEDIO (BUSCAR0 (HACER-ESTADO -5 5)))) Cada estado es un intervalo [IZQ, DER], en el que adems almacenamos los dos valores b=MIZQ y c=MDER, as como los valores de la funcin en ellos: (DEFUN HACER-ESTADO (X Y) (LIST X (MED-AUR-1 X Y) (MED-AUR-2 X Y) Y (F (MED-AUR-1 X Y)) (F (MED-AUR-2 X Y)))) (DEFUN IZQ (E) (CAR E)) (DEFUN MIZQ (E) (CADR E)) (DEFUN MDER (E) (CADDR E)) (DEFUN DER (E) (CADDDR E)) (DEFUN FMIZQ (E) (NTH 4 E)) (DEFUN FMDER (E) (NTH 5 E)) Definimos adems una funcin que modifica un estado, bien por la derecha, bien por la izquierda: (DEFUN MODIFICAR-ESTADO (E EXTREMO) (COND ((EQ EXTREMO 'IZQ) (LIST (MIZQ E) (MDER E) (MED-AUR-2 (MIZQ E) (DER E)) (DER E) (FMDER E) (F (MED-AUR-2 (MIZQ E) (DER E))))) ((EQ EXTREMO 'DER) (LIST (IZQ E) (MED-AUR-1 (IZQ E) (MDER E)) (MIZQ E) (MDER E) (F (MED-AUR-1 (IZQ E) (MDER E))) (FMIZQ E))) (T NIL))) El sucesor de cada estado se define por (DEFUN ELEGIR-SUC (E) (COND ((< (FMIZQ E) (FMDER E)) (MODIFICAR-ESTADO E 'DER)) (T (MODIFICAR-ESTADO E 'IZQ)))) Y el estado final queda caracterizado por (DEFUN FINALP (E) (< (ABS (- (IZQ E) (DER E))) EPSILON)) Hemos empleado algunas funciones y constantes numricas adicionales: (DEFUN MED-AUR-1 (X Y) (+ X (* (EXPT COEF-AUR 2) (- Y X)))) (DEFUN MED-AUR-2 (X Y) (+ X (* COEF-AUR (- Y X)))) (DEFCONSTANT COEF-AUR (/ (+ (SQRT 5) -1) 2)) (DEFUN F (X) (+ (* X (+ (* X (+ (* X (+ (* X 3) -4)) -6)) -24)) 7))
2.10
R.2.5. Recursin sobre el CDR de listas. Empleando nicamente CAR, CDR y CONS como funciones para manejo de listas, definir recursivamente funciones que resuelvan los siguientes problemas: a) hallar la longitud de una lista. b) dados una lista L y una expresin e, encontrar la sublista de L comprendida entre la primera aparicin de e -incluyendo la misma- y el final de L. Si e no es elemento de L, se devuelve NIL. c) dados una lista L y una expresin e, encontrar la lista originada a partir de L suprimiendo todas las apariciones de e en L. Si e no es elemento de L, se devuelve la misma L. d) dados una lista de smbolos L y dos smbolos sv, sn, encontrar la lista originada a partir de L sustituyendo todas las apariciones de sv por sn. Si e no es elemento de L, se devuelve la misma L. e) dadas dos listas L1, L2, concatenar ambas listas. f)dada una lista L, invertir L, es decir, hallar la lista L que tiene los mismos elementos que L pero en orden inverso. Por ejemplo, a partir de ((MADRID (1 2)) (BARCELONA (1 3))) se obtendr ((BARCELONA (1 3)) (MADRID (1 2))) ************************** SOLUCION: a) Caso base: NIL. La longitud de NIL es 0. Definicin recursiva sobre el CDR: Si la longitud del CDR de L es n, la longitud de L es n+1. En n pasos se alcanza el caso base. Este resultado es general: siempre que se recurra nicamente sobre el CDR de una lista, la recursin acaba llamando a NIL en un nmero de pasos que es a lo sumo igual a la longitud de la lista. En LISP (DEFUN MI-LENGTH (L) (IF (NULL L) 0 (1+ (MI-LENGTH (CDR L))))) b) Caso base: L es NIL. Entonces, la solucin es NIL. Recursin sobre el CDR, considerando adems el CAR: Si el CAR de L es precisamente e, entonces el resultado es L. Si el CAR de L no es e, entonces el resultado debe ser el mismo que cuando aplicamos el proceso al CDR de L. En LISP (DEFUN MI-MEMBER (E L) (COND ((NULL L) NIL) ((EQUAL E (CAR L)) L) (T (MI-MEMBER E (CDR L))))) NOTA: (MEMBER E L :TEST #EQUAL) tiene este significado predefinido. (MEMBER E L) tiene un significado parecido, pero empleando EQL como predicado de comparacin. c) Caso base: L es NIL. Entonces, la solucin es NIL. Recursin sobre el CDR, considerando adems el CAR: Si el CAR de L es precisamente e, entonces el resultado es el aplicar la funcin al CDR de L. Si el CAR de L no es e, entonces el resultado se puede obtener CONSando el CAR de L con el resultado de aplicar el proceso al CDR de L. En LISP (DEFUN MI-REMOVE (E L) (COND ((NULL L) NIL) ((EQUAL E (CAR L)) (MI-REMOVE E (CDR L))) (T (CONS (CAR L) (MI-REMOVE E (CDR L)))))) Inteligencia. Artificial e I.C.. 2004/05 2.11 Dpto. Leng. Ciencias Comp.
NOTA: (REMOVE E L :TEST #EQUAL) tiene este significado predefinido. (REMOVE E L) tiene un significado parecido, pero empleando EQL como predicado de comparacin. d) Caso base: L es NIL. Entonces, la solucin es NIL. Recursin sobre el CDR, considerando adems el CAR: Si el CAR de L es precisamente sv, entonces el resultado se obtiene CONSando sn con el resultado de aplicar la funcin al CDR de L. Si el CAR de L no es sv, entonces el resultado se obtiene CONSando el CAR de L con el resultado de aplicar el proceso al CDR de L. En LISP (DEFUN MI-SUBSTITUTE (SV SN L) (COND ((NULL L) NIL) ((EQ SV (CAR L)) (CONS SN (MI-SUBSTITUTE SV SN (CDR L)))) (T (CONS (CAR L) (MI-SUBSTITUTE SV SN (CDR L)))))) NOTA: (SUBSTITUTE SV SN L) tiene este significado predefinido. e) Caso base: L1 es NIL. Entonces, la solucin es L2. Recursin sobre el CDR de L1: El resultado se puede obtener CONSando el CAR de L con el resultado de aplicar el proceso al CDR de L1 y L2. Recurrimos nicamente sobre el CDR de L1, luego si n es su longitud, a lo sumo en n pasos alcanzamos el caso base. En LISP (DEFUN MI-APPEND-2 (L1 L2) (IF (NULL L1) L2 (CONS (CAR L1) (MI-APPEND-2 (CDR L1) L2)))) f) Caso base: L es NIL. Entonces, la solucin es NIL. Recursin sobre el CDR: El resultado se obtiene APPENDando la inversin del CDR de L con la lista formada por el CAR de L. Si la longitud de L es n, en n pasos se alcanza el caso base. En LISP, por ejemplo con UNLESS, ser (DEFUN INVERTIR (L) (UNLESS (NULL L) (MI-APPEND-2 (INVERTIR (CDR L)) (CONS (CAR L) NIL)))) NOTA: REVERSE tiene este significado predefinido.
2.12
R.2.6. Recursin sobre el CAR y el CDR de listas. Empleando nicamente CAR, CDR, CONS y APPEND como funciones para manejo de listas, definir recursivamente las siguientes funciones de argumento una lista L: a)la profundidad de L, es decir, su mximo nivel de anidamiento de parntesis. Supondremos que la profundidad de NIL es 0 (puesto que NIL es lo mismo que (), tambin podramos haber definido su profundidad como 1). b)la lista "desnuda" o "linealizada" obtenida a partir de L, es decir, la lista L' obtenida quitando todos los parntesis de L, salvo la pareja exterior. Por ejemplo, a partir de ((MADRID (1 2)) (BARCELONA (1 3))) se obtendr (MADRID 1 2 BARCELONA 1 3) Si NIL aparece como elemento de una lista o sublista, se considerar como smbolo y no se suprimir. Por ejemplo, la linealizacin de ((()) ()) es (NIL NIL) c) la "inversin profunda" de L, obtenida invirtiendo L y todas las listas que aparezcan en L a cualquier nivel de anidamiento. Por ejemplo, a partir de ((MADRID (1 2)) (BARCELONA (1 3))) se obtendr (((3 1) BARCELONA) ((2 1) MADRID)) ************************** SOLUCION: a) Caso base: L es NIL. Entonces, la profundidad es 0 (consideramos que NIL es un smbolo). Recursin sobre el CDR y sobre el CAR: Si el CAR de L es un tomo, entonces la profundidad de L es la del CDR de L. Si el CAR de L no es un tomo, la profundidad ser el mayor de estos dos nmeros: a)la profundidad del CDR de L; b) la profundidad del CAR de L aumentada en 1. En LISP (DEFUN PROFUNDIDAD (L) (COND ((NULL L) 0) ((ATOM (CAR L)) (PROFUNDIDAD (CDR L))) (T (MAX (+ 1 (PROFUNDIDAD (CAR L))) (PROFUNDIDAD (CDR L)))))) Por desgracia esta definicin no es correcta, como fcilmente puede comprobar el lector: (PROFUNDIDAD '(A B)) =>0 El error radica en el ltimo paso de la recursin. En efecto, la profundidad de la lista (B) es 1, mientras que la profundidad de su CDR es 0. Ello nos sugiere esta modificacin: Caso base: L es NIL. Entonces, la profundidad es 0. Recursin sobre el CDR y sobre el CAR: Si el CDR de L es NIL, entonces la profundidad de L es la profundidad del CAR de L aumentada en 1. En otro caso, Si el CAR de L es un tomo, entonces la profundidad de L es la del CDR de L. Si el CAR de L no es un tomo, la profundidad ser el mayor de estos dos nmeros: a)la profundidad del CDR de L; b) la profundidad del CAR de L aumentada en 1. Sin embargo, en el primer caso llamamos a la profundidad con el CAR de L como argumento, que puede no ser una lista, y este caso no est considerado. Podemos definir que la profundidad de un tomo es siempre 0 y queda Caso base: L es la lista vaca NIL o cualquier otro tomo. Entonces, la profundidad es 0. Recursin sobre el CDR y sobre el CAR: Si el CDR de L es NIL, entonces la profundidad de L es la profundidad del CAR de L aumentada en 1. En otro caso, Si el CAR de L es un tomo, entonces la profundidad de L es la del CDR de L. Si el CAR de L no es un tomo, la profundidad ser el mayor de estos dos nmeros: a)la profundidad del CDR de L; b)la profundidad del CAR de L aumentada en 1.
2.13
En LISP (DEFUN PROFUNDIDAD (L) (COND ((ATOM L) 0) ((NULL (CDR L)) (+ 1 (PROFUNDIDAD (CAR L)))) ((ATOM (CAR L)) (PROFUNDIDAD (CDR L))) (T (MAX (+ 1 (PROFUNDIDAD (CAR L))) (PROFUNDIDAD (CDR L)))))) Pero en realidad las clusulas segunda y tercera de este COND son casos particulares de la cuarta, y simplificando ser finalmente (DEFUN PROFUNDIDAD (L) (IF (ATOM L) 0 (MAX (1+ (PROFUNDIDAD (CAR L))) (PROFUNDIDAD (CDR L))))) Escribamos como NIL todas las listas vacas situadas dentro de L. Llamemos f(L) a la suma del nmero de tomos y del nmero de signos de parntesis que aparecen en la lista L. Ser f(NIL)=2. Consideremos LNIL. Entonces f(car(L))<f(L) (pues disminuye el nmero de parntesis) y f(cdr(L))<f(L) (pues disminuye el nmero de tomos). En ambas llamadas recursivas disminuye estrictamente el valor de f para el argumento, luego en un nmero finito de pasos se alcanza NIL. Este razonamiento es vlido para cualquier funcin que recurra sobre el CAR y el CDR de una lista. b) Caso base: L es NIL. Entonces, la solucin es NIL. Recursin sobre el CDR y sobre el CAR: Si el CAR de L es un tomo, entonces el resultado se obtiene CONSando el CAR de L con la linealizacin del CDR de L. Si el CAR de L no es un tomo, entonces el resultado se obtiene APPENDando la linealizacin del CAR de L con la linealizacin del CDR de L. En LISP (DEFUN DESNUDAR (L) (COND ((NULL L) L) ((ATOM (CAR L)) (CONS (CAR L) (DESNUDAR (CDR L)))) (T (APPEND (DESNUDAR (CAR L)) (DESNUDAR (CDR L)))))) c) Caso base: L es NIL. Entonces, la solucin es NIL. Recursin sobre el CDR y sobre el CAR: Si el CAR de L es un tomo, entonces el resultado se obtiene APPENDando la inversin profunda del CDR de L con la lista formada por el CAR de L. Si el CAR de L no es un tomo, entonces el resultado se obtiene APPENDando la inversin profunda del CDR de L con la lista formada por la inversin profunda del CAR de L. En LISP (DEFUN INVERTIR-PROF (L) (COND ((NULL L) NIL) ((ATOM (CAR L)) (APPEND (INVERTIR-PROF (CDR L)) (CONS (CAR L) NIL))) (T (APPEND (INVERTIR-PROF (CDR L)) (CONS (INVERTIR-PROF (CAR L)) NIL))))) Supongamos ahora que empleamos la siguiente definicin recursiva: Caso base: L es NIL. Entonces, la solucin es NIL. Recursin sobre el CDR y sobre el CAR: Si el CAR de L es un tomo, entonces el resultado se obtiene APPENDando la inversin profunda del CDR de L con la lista formada por el CAR de L. Si el CAR de L no es un tomo, entonces el resultado se obtiene APPENDando la inversin profunda del CDR de L con la inversin profunda de la lista formada por el CAR de L. Inteligencia. Artificial e I.C.. 2004/05 2.14 Dpto. Leng. Ciencias Comp.
La definicin parece equivalente a la anterior. Sin embargo, esta nueva definicin no lleva a un programa que termine. En efecto, ntese que ahora el razonamiento anterior no es aplicable, pues si L tiene un slo elemento, L=LIST(CAR(L)) y obviamente f(LIST(CAR(L))=f(L). Consideremos por ejemplo la lista ((A)). La nueva definicin establece el valor de su inversin en funcin de la inversin de NIL... y de la inversin de ((A))! Por ltimo, al igual que en el ejercicio anterior podemos simplificar quedando finalmente (DEFUN INVERTIR-PROF (L) (IF (ATOM L) L (APPEND (INVERTIR-PROF (CDR L)) (LIST (INVERTIR-PROF (CAR L))))))
NOTA: En lo sucesivo, sealaremos con una lnea doble en el margen izquierdo los razonamientos o fragmentos de cdigo LISP errneos.
2.15
R.2.7. Recursin sobre partes cualesquiera de una lista. Sea L una lista de nmeros. Se desea ordenar L en orden creciente mediante el procedimiento "quicksort". Definir para ello la correspondiente funcin LISP. ************************** SOLUCION: Recordemos que el algoritmo "quicksort" es el siguiente: sea a el primer elemento de la lista. Seleccionamos los restantes elementos de la lista que son menores o iguales que a, y los ordenamos; seleccionamos los restantes elementos que son mayores que a, y los ordenamos; la lista ordenada se obtiene concatenando ambos resultados, sin olvidarnos del primer elemento a de la lista que debe ir entre ellos. Sea la lista L de longitud n. El argumento que se pasa a cada llamada recursiva es una sublista del CDR de L, luego tiene longitud n'<n, y se alcanza NIL a lo sumo en n pasos. En LISP, por ejemplo con COND, ser (DEFUN QUICKSORT (L) (COND ((NULL L) NIL) (T (APPEND (QUICKSORT (FILTRADOS 'LE (CAR L) (CDR L))) (LIST (CAR L)) (QUICKSORT (FILTRADOS 'GT (CAR L) (CDR L))))))) donde FILTRADOS es una funcin que tiene como argumentos un operador OP de comparacin LE o GT, un nmero N y una lista L, y devuelve la lista formada por los elementos e de L tales que que e OP N es verdadero: (DEFUN FILTRADOS (OP N L) (COND ((NULL L) NIL) ((EQ OP 'LE) (IF (> (CAR L) N) (FILTRADOS OP N (CDR L)) (CONS (CAR L) (FILTRADOS OP N (CDR L))))) ((EQ OP 'GT) (IF (> (CAR L) N) (CONS (CAR L) (FILTRADOS OP N (CDR L))) (FILTRADOS OP N (CDR L)))))) NOTA: Esta solucin no es demasiado eficiente, pues L se inspecciona dos veces por completo. Podemos evitar esto empleando una funcin que a partir de L construye una lista formada por dos listas, la de menores o iguales y la de mayores, y una ligadura local con LET (vd. leccin 5)
2.16
R.2.8. Representacin de datos (I). Deseamos disear un programa para representar y manejar cuadrados y tringulos equilteros, definidos ambos por las coordenadas de su centro y la longitud de su lado. El programa debe ser capaz de calcular las reas y los permetros de estas figuras. a) Definir una implementacin LISP en la que los objetos se representen como listas. b) Modificar la implementacin de a) para tratar tambin los crculos. c) Se entiende por dimetro de un polgono la longitud del mayor segmento que puede trazarse en el interior de un polgono: para el cuadrado es la diagonal y para el tringulo equiltero el lado. Modificar la implementacin de b) para calcular tambin los dimetros de crculos y polgonos. ************************** SOLUCION: a) En la lista deben figurar todos los datos que identifican la figura: las coordenadas del centro y la longitud del lado. Aadiremos adems una etiqueta de tipo -por ejemplo, en el CAR de la lista-, que permita distinguir entre tringulos y cuadrados. Los constructores sern pues (DEFUN HACER-TRIANGULO (X Y L) (LIST TRIANGULO X Y L)) (DEFUN HACER-CUADRADO (X Y L) (LIST CUADRADO X Y L)) Los predicados de tipo sern (DEFUN TIPO (OBJ) (CAR OBJ)) (DEFUN TRIANGULO-P (OBJ) (EQ (TIPO OBJ) TRIANGULO)) (DEFUN CUADRADO-P (OBJ) (EQ (TIPO OBJ) CUADRADO)) Los selectores sern (DEFUN LADO (OBJ) (CADDDR OBJ)) (DEFUN CENTROX (OBJ) (CADR OBJ)) (DEFUN CENTROY (OBJ) (CADDR OBJ)) Las funciones especificadas sobre los objetos se definirn ahora en trminos de los selectores: (DEFUN ALTURA (OBJ) (COND ((TRIANGULO-P OBJ) (* 0.5 (SQRT 3) (LADO OBJ))) ((CUADRADO-P OBJ) (LADO OBJ)))) (DEFUN AREA (OBJ) (COND ((TRIANGULO-P OBJ) (* 0.5 (LADO OBJ) (ALTURA OBJ))) ((CUADRADO-P OBJ) (* (LADO OBJ) (ALTURA OBJ))))) (DEFUN PERIMETRO (OBJ) (COND ((TRIANGULO-P OBJ) (* 3 (LADO OBJ))) ((CUADRADO-P OBJ) (* 4 (LADO OBJ))))) b) Es necesario aadir un constructor de crculos: (DEFUN HACER-CIRCULO (X Y R) ;constructor de crculos (LIST 'CIRCULO X Y R)) y un predicado de tipo (DEFUN CIRCULO-P (OBJ) (EQ (TIPO OBJ) 'CIRCULO)) Adems, hay que modificar la implementacin de (casi) todas las funciones: Inteligencia. Artificial e I.C.. 2004/05 2.17 Dpto. Leng. Ciencias Comp.
;;;Funcin LADO OBJ. ;;;Si OBJ no es un cuadrado o un tringulo, LADO devuelve NIL (DEFUN LADO (OBJ) (WHEN (OR (CUADRADO-P OBJ) (TRIANGULO-P OBJ)) (CADDDR OBJ))) ;;;Funcin RADIO OBJ. ;;;Si OBJ no es un crculo, LADO devuelve NIL (DEFUN RADIO (OBJ) (WHEN (CIRCULO-P OBJ) (CADDDR OBJ))) ;;;Funcin AREA OBJ. (DEFUN AREA (OBJ) (COND ((TRIANGULO-P OBJ) (* 1/2 (LADO OBJ) (ALTURA OBJ))) ;;el rea de un tringulo es 1/2 de su base por su altura ((CUADRADO-P OBJ) (* (LADO OBJ) (ALTURA OBJ))) ;;el rea de un cuadrado es su base por su altura ((CIRCULO-P OBJ) (* PI (EXPT (RADIO OBJ) 2))))) ;;el rea de un crculo es pi por r al cuadrado ;;;Funcin PERIMETRO OBJ. (DEFUN PERIMETRO (OBJ) (COND ((TRIANGULO-P OBJ) (* 3 (LADO OBJ))) ((CUADRADO-P OBJ) (* 4 (LADO OBJ))) ((CIRCULO-P OBJ) (* 2 PI (RADIO OBJ))))) c) Es necesario aadir la nueva funcin: (DEFUN DIAMETRO (OBJ) (COND ((TRIANGULO-P OBJ) (LADO OBJ)) ((CUADRADO-P OBJ) (* (SQRT 2) (LADO OBJ))) ((CIRCULO-P OBJ) (* 2 (RADIO OBJ))))) y nada ms. NOTA: PI es una constante predefinida. NOTA: LISP considera como comentarios todos los caracteres que siguen a un signo ; hasta el fin de la lnea. Estilsticamente, suele emplearse -un solo signo ; para comentarios insertados en una lnea de cdigo -un signo doble ;; para lneas de comentarios insertados en el cdigo de una funcin -un signo triple ;;; o cudruple ;;;; para encabezamientos de funciones y programas NOTA: En esta leccin empleamos listas para representar los diversos tipos de datos propuestos. Ello corresponde a la "edad antigua" de la programacin LISP y en la actualidad tiene una finalidad meramente didctica. El lector no debe engaarse suponiendo que CommonLISP carece de otros recursos para representar datos; al contrario, ofrece tambin estructuras (anlogas a los registros de otros lenguajes, pero ms potentes) y objetos (que se definen y procesan segn el modelo CLOS).
; 3 veces el lado ;4 veces el lado ;2pi veces el radio
2.18
R.2.9. Representacin de datos(II). El conocido problema de los misioneros y canbales se puede plantear como sigue: tres misioneros y tres canbales viajan juntos y deben atravesar un ro. Para ello disponen de una barca en la que pueden ir a lo sumo dos personas (y como mnimo una, ya que alguien debe tripularla). La barca puede pasar de una orilla a otra cuantas veces se desee, pero si en algn momento hay ms canbales que misioneros en una orilla, aquellos devorarn a estos y el viaje acabar trgicamente. En estas condiciones, es posible que la expedicin pase el ro? Se pide a) Definir una representacin basada en listas para los diversos posibles estados en los que se pueden encontrar los misioneros y canbales. b) Basada en la anterior, definir el espacio de estados del problema, mediante las funciones IMPOSIBLEP, FINALP e HIJOS. (IMPOSIBLEP estado) devuelve NIL si estado es un estado vlido segn la especificacin dada del problema, T en otro caso. (FINALP estado) devuelve T si estado es un estado final segn la especificacin dada del problema, NIL en otro caso. (HIJOS estado) devuelve una lista con todos los hijos vlidos de estado. c) A partir de HIJOS, definir ELEGIR-SUC y resolver el problema aplicando el algoritmo de bsqueda irrevocable de R.2.4. ************************** SOLUCION: Supongamos que la orilla inicial es la derecha. El estado se representa mediante una lista de tres elementos: - num. de barcas en la orilla derecha. - num. de misioneros en la orilla derecha. - num. de canibales en la orilla derecha. (DEFUN HACER-E (B M C) ;constructor (LIST B M C)) (DEFUN BARCAS-E (E) (CAR E)) (DEFUN MISIONEROS-E (E) (CADR E)) (DEFUN CANIBALES-E (E) (CADDR E)) ;consulta ;consulta ;consulta
Tambin es parte de la representacin el predicado de igualdad entre objetos. En este caso sera simplemente (DEFUN EQ-ESTADO (E1 E2) ;igualdad de estados. (EQUAL E1 E2)) pero para representaciones ms sofisticadas EQ-ESTADO puede tener una implementacin ms compleja. Usemos DEFCONSTANT para representar el nmero de misioneros, canbales y barcas: (DEFCONSTANT NUM-MISIONEROS 3) (DEFCONSTANT NUM-CANIBALES 3) (DEFCONSTANT NUM-BARCAS 1) Definamos ahora funciones auxiliares, a partir de los calcular lo que hay en la otra orilla: (DEFUN OTRA-B (E) ;numero de (IF (ZEROP (BARCAS-E E)) 1 0)) (DEFUN OTROS-MISIONEROS (E) ;numero de (- NUM-MISIONEROS (MISIONEROS-E E))) (DEFUN OTROS-CANIBALES (E) ;numero de (- NUM-CANIBALES (CANIBALES-E E))) selectores y constructores anteriores, para barcas en la otra orilla misioneros en la otra orilla canibales en la otra orilla
Tambin ser til una funcin que indica si el nmero de misioneros y/o canbales en la orilla derecha va a aumentar o a disminuir con el prximo movimiento. Si la barca est en la derecha, el nmero disminuir, y si est en la izquierda, aumentar: Inteligencia. Artificial e I.C.. 2004/05 2.19 Dpto. Leng. Ciencias Comp.
;signo-incr-der(e) devuelve 1 si la barca va a ir de derecha a izquierda, ;devuelve -1 si la barca va a ir de izquierda a derecha (DEFUN SIGNO-INCR-DER (E) (IF (ZEROP (BARCAS-E E)) 1 -1)) b) Un estado puede ser imposible por dos razones: -imposibilidad fsica, si se llega a un estado con nmero negativo o mayor de 3 de misioneros o canbales. -imposibilidad "social", si se llega a un estado en el que hay misioneros en una orilla, y el nmero de canbales en esa orilla lo supera. Todo esto debe ser considerado por el predicado IMPOSIBLEP. (DEFUN IMPOSIBLEP (E) (OR (> (MISIONEROS-E E) NUM-MISIONEROS) ;num. misioneros incorrecto (< (MISIONEROS-E E) 0) (> (CANIBALES-E E) NUM-CANIBALES) ;num. canibales incorrecto (< (CANIBALES-E E) 0) (> (BARCAS-E E) NUM-BARCAS) ;num barcas incorrecto (< (BARCAS-E E) 0) (AND (> (MISIONEROS-E E) 0) ;orilla dcha. incorrecta (> (CANIBALES-E E) (MISIONEROS-E E))) (AND (> (OTROS-MISIONEROS E) 0) ;orilla izq. incorrecta (> (OTROS-CANIBALES E) (OTROS-MISIONEROS E))))) Un estado es final cuando no quedan misioneros ni canbales en la orilla derecha (o cuando es imposible). Por tanto, FINALP sera (DEFUN FINALP (E) (AND (ZEROP (MISIONEROS-E E)) (ZEROP (CANIBALES-E E)))) Para implementar HIJOS hay que aplicar todas las reglas posibles a un estado e y almacenar los resultados en una lista. En este caso, las reglas las podemos conceptualizar como sigue: Regla 1: pasa un misionero solo en la barca. Regla 2: pasan dos misioneros. Regla 3: pasa un canbal. Regla 4: pasan dos canbales. Regla 5: pasan un misionero y un canbal. En un estado e, en general, no podrn aplicarse todas las reglas, ya que algunas de ellas llevaran a estados imposibles. Por ello habra que considerar las precondiciones de cada regla. Pero ahora seguiremos otro enfoque ms sencillo: los estados imposibles se generan en primera instancia, pero son posteriormente eliminados de la lista definitiva de hijos. Los cinco hijos posibles se generan por HIJOS-AUX (DEFUN HIJOS-AUX (E) (LIST (HACER-E (OTRA-B E) ;pasa un misionero (+ (MISIONEROS-E E) (* (SIGNO-INCR-DER E) 1)) (CANIBALES-E E)) (HACER-E (OTRA-B E) ;pasan dos misioneros (+ (MISIONEROS-E E) (* (SIGNO-INCR-DER E) 2)) (CANIBALES-E E)) (HACER-E (OTRA-B E) ;pasa un canibal (MISIONEROS-E E)(+ (CANIBALES-E E) (* (SIGNO-INCR-DER E) 1))) (HACER-E (OTRA-B E) ;pasan dos canibales (MISIONEROS-E E) (+ (CANIBALES-E E) (* (SIGNO-INCR-DER E) 2))) (HACER-E (OTRA-B E) ;pasan uno y uno (+ (* (SIGNO-INCR-DER E) 1) (MISIONEROS-E E)) (+ (* (SIGNO-INCR-DER E) 1) (CANIBALES-E E))))) Pero hay que excluir a los imposibles: (DEFUN HIJOS (E) (FILTRAR (HIJOS-AUX E))) Inteligencia. Artificial e I.C.. 2004/05 2.20 Dpto. Leng. Ciencias Comp.
(DEFUN FILTRAR (LISTA-E) (COND ((NULL LISTA-E) NIL) ((IMPOSIBLEP (CAR LISTA-E)) (FILTRAR (CDR LISTA-E))) (T (CONS (CAR LISTA-E) (FILTRAR (CDR LISTA-E)))))) c) En el caso ideal de bsqueda irrevocable, ELEGIR-SUC devuelve "el mejor" de los hijos de un estado e. En las bsquedas irrevocables de R.2.4 podamos definir la funcin de esta forma, por la mera inspeccin de todos los sucesores. Pero, en general, ello no es posible; por eso no siempre es adecuada la bsqueda irrevocable. Lo mejor que podemos hacer en nuestro caso es devolver un hijo al azar. Para ello habr que hacer lo siguiente: -generar la lista L de hijos de e; -devolver un elemento aleatorio de L. Para esto ltimo implementamos NTH-RANDOM ;; la funcin NTH-RANDOM (L) devuelve un elemento aleatorio de la lista L ;; si L es NIL, devuelve NIL (DEFUN NTH-RANDOM (L) (NTH (RANDOM (LENGTH L)) L)) Y ELEGIR-SUC puede definirse a partir de HIJOS, de forma muy sencilla: ;; la funcin ELEGIR-SUC (E) devuelve un sucesor aleatorio de E ;; si E no tiene hijos, devuelve NIL (DEFUN ELEGIR-SUC (E) (NTH-RANDOM (HIJOS E))) La funcin principal ser M-C: (DEFUN M-C () (MAKE-RANDOM-STATE T) ;aleatorizar el inicio (BUSCAR0 (HACER-E 1 3 3))) ;crear el estado inicial y buscar. Recordemos que el algoritmo BUSCAR0 se implementaba en R.2.4 como (DEFUN BUSCAR0 (E) (COND ((FINALP E) E) (T (BUSCAR0 (ELEGIR-SUC E))))) Pero hemos introducido un sutil cambio en la especificacin de (ELEGIR-SUC E), que hace que esta implementacin deje de ser correcta. En efecto, qu ocurrir ahora si no hay hijos de e, es decir, si (ELEGIR-SUC E) => NIL? En la siguiente llamada se intentar averiguar si NIL es un estado final y muy probablemente se producir un error. Para evitarlo, comprobaremos si el valor devuelto por la llamada a (ELEGIR-SUC E) es NIL antes de efectuar la llamada recursiva a BUSCAR0: (DEFUN BUSCAR0 (E) (COND ((FINALP E) E) (T (BUSCAR0-AUX (ELEGIR-SUC E))))) (DEFUN BUSCAR0-AUX (E) (COND ((NULL E) NIL) (T (BUSCAR0 E)))) NOTA. La expresin (MAKE-RANDOM-STATE T) se emplea para inicializar -cada vez de manera diferente- el generador de nmeros pseudoaletorios. La expresin (RANDOM n) se evala a un nmero pseudoaleatorio r distribuido uniformemente en el intervalo [0, n [. El nmero r es del mismo tipo (entero, racional, flotante), que el argumento n. NOTA. En la leccin 4 veremos que la implementacin de muchas de las operaciones de este ejercicio se puede realizar ms elegantemente con funciones MAP. En la leccin 5 veremos que Common Lisp ofrece tambin las construcciones iterativas clsicas de la programacin imperativa. NOTA. N-TH es una funcin prefedinida. (N-TH n lista) => el n-simo elemento de lista, suponiendo que CAR(lista) es el 0-simo. Si n longitud(lista), (N-TH n lista) => NIL Inteligencia. Artificial e I.C.. 2004/05 2.21 Dpto. Leng. Ciencias Comp.
R.2.10. Representacin de datos (III). Las frmulas ms sencillas del clculo de predicados (CP) son los tomos. Un tomo es una frmula de la forma p(a1, ..., an) donde p es un predicado y a1, ..., an -que se denominan argumentos- son trminos. Un trmino del CP es una constante c, una variable v o un trmino compuesto f(a1, ..., an), creado aplicando un funtor f a otros trminos a1, ..., an. Se pide: a) Disear una representacin de los tomos del CP basada en listas. b) Implementar el predicado aparecer(tg, tp), que devuelve "verdadero" si y slo si tg es un trmino y tp un trmino que coincide con tg, o que aparece como argumento -a cualquier nivel- de tg. c) Implementar la funcin sustituir(eg, tv, tn), que devuelve el resultado de sustituir en eg todas las apariciones -a cualquier nivel- de tv por tn. ************************** SOLUCION: Proponemos lo siguiente: -cada elemento sintctico (trmino o tomo) es una lista cuyo primer elemento es una etiqueta de tipo. -el segundo elemento de la lista es un smbolo cuyo nombre es el del elemento (constante, variable, funtor o predicado). -la lista correspondiente a un elemento compuesto (trmino con funtor o tomo) consta adems de los argumentos del elemento. Los constructores sern pues (DEFUN HACER-TERM-CP-SIMPLE (TIPO NOMBRE) (CASE TIPO (VAR (LIST 'VAR NOMBRE)) (CTE (LIST 'CTE NOMBRE)))) (DEFUN HACER-EXPR-CP-COMPUESTO (TIPO FUNTOR L-ARGS) (WHEN (OR (EQ TIPO 'FUN) (EQ TIPO 'ATM)) (CONS TIPO (CONS FUNTOR L-ARGS)))) Los selectores sern (DEFUN TIPO (EXPR-CP) (CAR EXPR-CP)) (DEFUN NOMBRE (EXPR-CP) (CADR EXPR-CP)) (DEFUN L-ARGS (EXPR-CP) (CASE (TIPO EXPR-CP) ((VAR CTE) NIL) ((FUN ATM) (CDDR EXPR-CP)))) Y el predicado de igualdad de expresiones del CP (DEFUN EQ-EXPR-CP (E1 E2) (EQUAL E1 E2)) Por ejemplo, para construir la variable x diremos (HACER-TERM-CP-SIMPLE 'VAR 'X) => (VAR X) Y para construir el tomo p(x, a) diremos (HACER-EXPR-CP-COMPUESTO 'ATM 'P (LIST (HACER-TERM-CP-SIMPLE 'VAR 'X) (HACER-TERM-CP-SIMPLE 'CTE 'A))) => (ATM P (VAR X) (CTE A))
b) La definicin recursiva es directa: si tg y tp son iguales, se devuelve "verdadero"; en otro caso, si tg es un trmino simple, se devuelve "falso"; en otro caso, se sigue buscando tp en el CAR de tg y en el CDR de tg.
2.22
(DEFUN APARECER (TG TP) (COND ((EQ-EXPR-CP TG TP) T) ((EQ 'VAR (TIPO TG)) NIL) ((EQ 'CTE (TIPO TG)) NIL) (T (APARECER-EN-L (L-ARGS TG) TP)))) Necesitamos definir la funcin aparecer-en-l(ltg, tp), que busca el trmino tp no en un solo trmino, sino en una lista de trminos ltg. (DEFUN APARECER-EN-L (LTG TP) (COND ((NULL LTG) NIL) (T (OR (APARECER (CAR LTG) TP) (APARECER-EN-L (CDR LTG) TP))))) c) La definicin recursiva es tambin directa: si eg y tv son iguales, se devuelve tn; en otro caso, si eg es un trmino simple, se devuelve el mismo eg; en otro caso, se devuelve la expresin del CP del mismo tipo y nombre que eg y de argumentos los resultantes de sustituir tv por tn en los argumentos de eg. (DEFUN SUSTITUIR (EG TV TN) (COND ((EQ-EXPR-CP EG TV) TN) ((EQ 'VAR (TIPO EG)) EG) ((EQ 'CTE (TIPO EG)) EG) (T (HACER-EXPR-CP-COMPUESTA (TIPO EG) (NOMBRE EG) (SUSTITUIR-EN-L (L-ARGS EG) TV TN))))) Anlogamente, la funcin sustituir-l(ltg, tv, tn) realiza la sustitucin en una lista de trminos ltg. (DEFUN SUSTITUIR-EN-L (LTG TV TN) (COND ((NULL LTG) NIL) (T (CONS (SUSTITUIR (CAR LTG) TV TN) (SUSTITUIR-EN-L (CDR LTG) TV TN)))))
NOTA. La macro (CASE expresin-clave clusula*) donde cada clusula es de la forma (clave|lista-claves expresin-valor*) se evala como sigue: -se evala expresin-clave, dando un valor V; -se inspeccionan secuencialmente las clave | lista-claves. -si se encuentra alguna clave o algn elemento de una lista-clave que sea T u OTHERWISE, se evalan secuencialmente las correspondientes expresin-valor, y se devuelve el valor de la ltima de ellas. -si se encuentra alguna clave o algn elemento de una lista-clave que coincide con el valor V, se evalan secuencialmente las correspondientes expresin-valor, y se devuelve el valor de la ltima de ellas; -si ninguna clave y ningn elemento de una lista-clave cumple alguna de estas condiciones, se devuelve NIL.
2.23
R.3.1. Expresiones lambda. Evaluar las siguientes expresiones: a) ((LAMBDA (X) (+ X 1)) 7) b) ((LAMBDA NIL 7 8 9)) c) ((LAMBDA (L1 L2) (LIST (CAR L1) (CAR L2))) '(ALONSO ALONZO) '(ALFONSO)) d) ((LAMBDA (X) (APPEND X X)) ((LAMBDA (X) (LIST X X)) 'CHURCH)) e) ((LAMBDA (L1) ((LAMBDA (L2) (LIST (CAR L1) (CAR L2))) '(ALONSO ALONZO))) '(ALFONSO)) f) ('(LAMBDA (X) (+ X 1)) 7) ************************** SOLUCION: Una expresin lambda es una lista de la forma (LAMBDA lista-lambda [expresin]*) donde lista-lambda supondremos por ahora que es una lista de smbolos (parmetros). Ntese la similitud sintctica de una expresin lambda con una forma DEFUN. Las expresiones lambda sirven para referirse a funciones sin necesidad de darles nombre. Una expresin lambda da directamente la definicin de una funcin. As, por ejemplo, la expresin (LAMBDA (X) (+ X X)) es la definicin de la funcin duplo, y se puede leer simplemente como "la funcin de x que devuelve x+x". Las expresiones lambda estn inspiradas en la notacin del lambda-clculo, en la que la funcin anterior se expresara como x.x+x Una expresin lambda puede aparecer en los mismos lugares que un smbolo con significado funcional. Por ejemplo, puede aparecer como primer elemento de una lista que se ha de evaluar; se dice entonces que tenemos una forma lambda. Los restantes elementos de la lista son los argumentos que se pasan a la definicin lambda: estos argumentos sustituyen a los parmetros en [expresin]* y se devuelve el valor de la ltima de ellas. Por tanto, para considerar las formas lambda la regla de evaluacin de listas dada en R.1.1 debe completarse de la siguiente manera: 1. Si el primer elemento de una lista es una expresin lambda, se considera el objetoprocedimiento F definido por la expresin. 2. Se evalan los restantes elementos de la lista, obteniendo los valores V1, ..., Vn. Si el nmero o tipo de los valores obtenidos no es coherente con los argumentos requeridos por F, se produce error. 3. La lista se evala a F(V1, ..., Vn). Ya podemos resolver los apartados a)-e): a) Es el caso ms sencillo: ((LAMBDA (X) (+ X 1)) 7) == X <- 7 (+ X 1) =>8 b) El nmero de argumentos de la definicin puede ser 0: ((LAMBDA NIL 7 8 9)) =>9 c) El nmero de argumentos puede ser mayor que 1:
Inteligencia Artificial e I.C.. 2004/05
3.3
((LAMBDA (L1 L2) (LIST (CAR L1) (CAR L2))) '(ALONSO ALONZO) '(ALFONSO)) =>(ALONSO ALFONSO) d) Para evaluar el argumento de la primera forma lambda, evaluamos otra: ((LAMBDA (X) (APPEND X X)) ((LAMBDA (X) (LIST X X)) 'CHURCH)) (CHURCH CHURCH) =>(CHURCH CHURCH CHURCH CHURCH) e) En este caso, el cuerpo de la primera definicin contiene una forma lambda: ((LAMBDA (L1) ((LAMBDA (L2) (LIST (CAR L1) (CAR L2))) '(ALONSO ALONZO))) '(ALFONSO)) Se crea un entorno E1 donde L1 est ligado a (ALFONSO) L1<- (ALFONSO) y en l se evala ((LAMBDA (L2) (LIST (CAR L1) (CAR L2))) '(ALONSO ALONZO))) para lo cual se crea un entorno E2 donde L2 est ligado a (ALONSO ALONZO)
L1 <- (ALFONSO) L2<- (ALONSO ALONZO) y en l se evala (LIST (CAR L1) (CAR L2)) que produce finalmente => (ALFONSO ALONSO) El entorno E2 se ha creado dentro del entorno E1, ya que la expresin lambda correspondiente a E2 aparece sintcticamente dentro de la expresin lambda que origina a E1. Ntese la diferencia con lo expuesto en R.1.9.c): en aquel caso, el nuevo entorno se creaba fuera del entorno anterior. Ello se debe a que Common Lisp crea entornos lxicos: el mbito de la ligadura de una variable coincide con el mbito sintctico en donde est definida esta variable. En el caso de este ejercicio, la aparicin de L1 en (LIST (CAR L1) (CAR L2))) est dentro del par de parntesis ((LAMBDA (L1) ...) que definen el mbito donde L1 es una variable. f) El primer elemento de una forma lambda debe ser simplemente una definicin lambda: ('(LAMBDA (X) (+ X 1)) 7) => Error: '(LAMBDA (X) (+ X 1)) no es una definicin lambda.
3.4
R.3.2. Objetos-procedimiento como datos. Suponiendo evaluada (DEFUN DEF-US (X) (LIST X X X)) y el smbolo JUAN ligado al smbolo CONS, evaluar las siguientes expresiones: a) (FUNCTION CONS) b) (FUNCTION 'CONS) c) (FUNCTION #'CONS) d) #'CONS e) #'DEF-US f) #'JUAN g) #'COND h) (FUNCTION (LAMBDA (X) (+ X 1))) i) #'(LAMBDA (X) (+ X 1)) j) (LAMBDA (X) (+ X 1)) k) (FUNCTION '(LAMBDA (X) (+ X 1))) l) #'PEPE m) (#'(LAMBDA (X) (+ X 1)) 7) ************************** SOLUCION: Hasta ahora hemos considerado en Lisp dos tipos de datos: tomos y listas. Lisp considera tambien como datos los objetos-procedimiento. Un objeto-procedimiento no debe confundirse con el smbolo que lo tiene por significado funcional. Por ejemplo, tras ejecutar (DEFUN F1 (X) (CONS X (Y PUNTO))) existe un objeto-procedimiento -llammosle F1- que es el significado funcional del smbolo F1 y cuya definicin lambda sera (LAMBDA (X) (CONS X (Y PUNTO))) El objeto-procedimiento F1 se recuperara implcitamente al evaluar una lista de la forma (F1 argumento). Hasta ahora esta manera de tratar los objetos-procedimiento, propia de los lenguajes imperativos, es la nica que hemos considerado. Sin embargo, en Lisp es posible manipular explcitamente un objeto-procedimiento mediante la forma especial FUNCTION: (FUNCTION argumento) -un solo argumento, que debe ser un smbolo o una expresin lambda. -FUNCTION toma literalmente su argumento. -el valor devuelto es: -si el argumento es un smbolo, el objeto-procedimiento que es el significado funcional del smbolo. -si el argumento es una expresin lambda, el objeto-procedimiento definido por la expresin. -es un error llamar a FUNCTION con otro tipo de argumento. -FUNCTION no puede devover operadores especiales ni macros; por tanto, se produce un error si el argumento de FUNCTION es un smbolo cuyo significado funcional sea de este tipo. Un objeto-procedimiento no es algo que se pueda imprimir. Los sistemas Lisp emplean una notacin del tipo de #<funcin nn> para imprimir el valor devuelto por FUNCTION. Al igual que para QUOTE, existe una abreviatura para FUNCTION: (FUNCTION argumento) == #'argumento Segn esto a) (FUNCTION CONS) => #<funcin compilada 114> b) (FUNCTION 'CONS) => Error: (QUOTE CONS) no es un argumento vlido. c) (FUNCTION #'CONS) =>Error: (FUNCTION CONS) no es un argumento vlido. d) #'CONS => #<funcin compilada 114> Inteligencia Artificial e I.C.. 2004/05 3.5 Dpto. Leng. Ciencias Comp.
e) Los objetos-procedimiento definidos por el programa tambin son recuperados por FUNCTION: #'DEF-US => #<funcin de usuario 415> f) Pero no hay que confundirlos con el valor de una ligadura: #'JUAN => Error: JUAN no tiene significado funcional. g) Como se ha dicho, se produce un error si el significado funcional de smbolo es una macro o una forma especial; por tanto #'COND => Error: el significado funcional de COND no es una funcin. Recurdese que AND y OR son macros. h) Los objetos-procedimiento definidos por una definicin lambda tambin son recuperados por FUNCTION: (FUNCTION (LAMBDA (X) (+ X 1))) => #<funcin 21A> i) #'(LAMBDA (X) (+ X 1)) => #<funcin 23B> j) ANSI Common Lisp permite realizar una abreviatura adicional; ya que es tan frecuente el uso de FUNCTION con las definiciones lambda, se permite omitirlo. Dicho de otra forma, cuando el primer elemento de una forma es LAMBDA, la forma se evala como (FUNCTION (LAMBDA ...)). De esta manera tenemos (LAMBDA (X) (+ X 1)) => #<funcin 23B> k) Sin embargo... (FUNCTION '(LAMBDA (X) (+ X 1))) => Error: (QUOTE (LAMBDA (X) (+ X 1))) no es un argumento vlido l) #'PEPE => Error: PEPE no tiene significado funcional. m) Recurdese que el primer elemento de una forma lambda debe ser una definicin lambda: (#'(LAMBDA (X) (+ X 1)) 7) => Error: #'(LAMBDA (X) (+ X 1)) no es una definicin lambda. NOTA: La abreviatura a la que aludimos en el apartado j) no ser empleada en el resto de estas lecciones. Ello se debe a dos razones: -ha sido introducida en el estndar ANSI; las versiones anteriores de Common Lisp no la permitan. Por tanto, se sealar un error si se ententa emplear en compiladores o intrpretes anteriores a 1995, y an en algunos posteriores. -puede inducir al programador a error, ya que enmascara la diferencia entre nombres de procedimientos y objetos-procedimiento. NOTA: En realidad FUNCTION hace algo ms que lo explicado aqu: crea si es necesario un cierre lxico. Vd. R.3.8
NOTA: Los objetos-procedimiento se denominan ms frecuentemente "funciones". Preferimos evitar esta palabra sobrecargada.
3.6
R.3.3. Objetos-procedimiento como argumento: FUNCALL. Suponiendo como en R.3.2. evaluada (DEFUN DEF-US (X) (LIST X X X)) y JUAN ligado a CONS, y adems el smbolo PEPE ligado al resultado de (FUNCTION CONS), evaluar las siguientes expresiones: a) (FUNCALL EXPT 2 3) b) (FUNCALL #'EXPT 2 3) c) (FUNCALL DEF-US 'LAMBDA) d) (DEF-US 'LAMBDA) e) (FUNCALL (FUNCTION DEF-US) 'LAMBDA) f) (FUNCALL PEPE 'LAMBDA '((X) X)) g) (FUNCALL #'PEPE 'LAMBDA '((X) X)) h) (PEPE 'LAMBDA '((X) X)) i) (JUAN 'LAMBDA '((X) X)) j) (FUNCALL #'(LAMBDA (X) (* X X)) 7) k) (FUNCALL #'AND T NIL T) l) (FUNCALL '+ 2 3) m) (FUNCALL (QUOTE DEF-US) 'LAMBDA) n) (FUNCALL JUAN 'LAMBDA '((X) X)) ************************** SOLUCION: Existen funciones predefinidas que manejan objetos-procedimiento. Por ejemplo, FUNCALL: (FUNCALL arg-funcional [argumento]*) -FUNCALL es una funcin propiamente dicha, es decir, evala todos sus argumentos. -el primer argumento debe ser un objeto-procedimiento F. -los restantes argumentos de FUNCALL arg1, ..., argn deben ser compatibles en nmero y tipo con los requeridos por F. -el valor devuelto es F(arg1, ..., argn). Recurdese lo dicho en R.1.8: en CommonLisp la ligadura y el significado funcional de un smbolo se procesan de manera independiente. Si en la llamada a FUNCALL aparece como argumento smbolo, se proceder segn el ciclo de evaluacin Lisp y smbolo se evaluar, es decir, se buscar su ligadura. En ningn caso se buscar su significado funcional. Segn esto a) (FUNCALL EXPT 2 3) =>Error: EXPT sin ligar. b) (FUNCALL #'EXPT 2 3) => 8 c) (FUNCALL DEF-US 'LAMBDA) =>Error: DEF-US sin ligar. d) (DEF-US 'LAMBDA) => (LAMBDA LAMBDA LAMBDA) e) (FUNCALL (FUNCTION DEF-US) 'LAMBDA) => (LAMBDA LAMBDA LAMBDA) Ntese la equivalencia (smbolo argumento) == (FUNCALL (FUNCTION smbolo) argumento) f) (FUNCALL PEPE 'LAMBDA '((X) X)) => (LAMBDA (X) X) g) (FUNCALL #'PEPE 'LAMBDA '((X) X)) Inteligencia Artificial e I.C.. 2004/05 3.7 Dpto. Leng. Ciencias Comp.
=> Error: PEPE no tiene significado funcional. h) (PEPE 'LAMBDA '((X) X)) => Error: PEPE no tiene significado funcional. i) (JUAN 'LAMBDA '((X) X)) => Error: JUAN no tiene significado funcional. j) (FUNCALL #'(LAMBDA (X) (* X X)) 7) => 49 k) (FUNCALL #'AND T NIL T) => Error: el objeto-procedimiento no es una funcin. El primer argumento de FUNCALL, es decir, el argumento funcional, debe ser un objetoprocedimiento; en otro caso se produce un error. Sin embargo, hay una excepcin a esta norma: si el argumento funcional es un nombre de funcin, FUNCALL recupera automticamente su significado funcional. Este pequeo remiendo en la semntica de Common Lisp se denomina coercin implcita y se debe a razones histricas. Segn esto l) (FUNCALL '+ 2 3) => 5 m) (FUNCALL (QUOTE DEF-US) 'LAMBDA) => (LAMBDA LAMBDA LAMBDA) n) (FUNCALL JUAN 'LAMBDA '((X) X)) => (LAMBDA (X) X)
3.8
R.3.4. Objetos-procedimiento como argumento: APPLY. Suponiendo evaluada (DEFUN DEF-US (X) (LIST X X X)), el smbolo PEPE ligado al resultado de (FUNCTION CONS) y el smbolo LISTA ligado a la lista (2 3 4), evaluar las siguientes expresiones: a) (APPLY EXPT '(2 3)) b) (APPLY DEF-US '(A)) c) (APPLY #'MAX LISTA) d) (APPLY (FUNCTION DEF-US) 'A) e) (APPLY PEPE '(A (B))) f) (APPLY #'(LAMBDA (X) (* X X)) (7)) g) (APPLY #'AND '(T NIL T)) h) (APPLY '+ LISTA) i) (APPLY (QUOTE DEF-US) '(LAMBDA)) ************************** SOLUCION: La funcin predefinida APPLY permite aplicar un objeto-procedimiento a la lista de sus argumentos. (APPLY arg-funcional lista-args) -APPLY es una funcin propiamente dicha, es decir, evala todos sus argumentos. -tiene exactamente dos argumentos. -el primer argumento debe ser un objeto-procedimiento F. -el segundo argumento de APPLY debe ser una lista formada por elementos arg1, ..., argn compatibles en nmero y tipo con los requeridos por F. -el valor devuelto es F(arg1, ..., argn). Segn esto a) (APPLY EXPT '(2 3)) =>Error: EXPT sin ligar. b) (APPLY DEF-US '(A)) =>Error: DEF-US sin ligar. c) (APPLY #'MAX LISTA) => 4 d) (APPLY (FUNCTION DEF-US) 'A) => Error: A no es una lista. e) (APPLY PEPE '(A (B))) => (A B) f) (APPLY #'(LAMBDA (X) (* X X)) '(7)) => 49 g) (APPLY #'AND '(T NIL T)) => Error: el objeto-procedimiento no es una funcin. Las mismas observaciones sobre la coercin son vlidas para APPLY. Segn esto h) (APPLY '+ LISTA) => 9 i) (APPLY (QUOTE DEF-US) '(LAMBDA)) => (LAMBDA LAMBDA LAMBDA)
NOTA: En realidad, el nmero de argumentos de APPLY es indefinido. La autntica definicin de APPLY es esta: APPLY LISTa todos sus argumentos, salvo el primero y el ltimo, y a continuacin APPENDa ste; la lista resultante contiene los argumentos que se pasan al argumento funcional. Por ejemplo, (APPLY #'+ 1 2 '(3 4)) == (APPLY #'+ '(1 2 3 4)) => 10
3.9
R.3.5. Objetos-procedimiento como argumento: funciones definidas. Escribir definiciones Lisp de las siguientes funciones: a) la funcin sumatorio, que tiene como argumentos una funcin f : R>R y dos nmeros naturales i0, in; sumatorio devuelve f(i0) + f (i0+1) +... + f (in) si i0 in, 0 en otro caso; y la funcin productorio, que tiene como argumentos una funcin f : R>R y dos nmeros naturales i0, in; productorio devuelve f(i0) f (i0+1) ... f(in) si i0 in, 1 en otro caso. b)la funcin acumular, que tiene como argumento: -una funcin f : R>R -dos nmeros naturales i0, in -un nmero valor-inicial -una operacin conmutativa y asociativa acum : R2>R; acumular devuelve f(i0) acum f(i0+1)... acum f(in) si i0 in, valor-inicial en otro caso. c) la funcin bsqueda-dicotmica, que tiene como argumentos una funcin numrica f:R> R y dos nmeros a, b tales que f tiene una raz en [a, b]; bsqueda-dicotmica devuelve precisamente el valor de esa raz. ************************** SOLUCION: a) Demos una definicin recursiva de sumatorio: si i0 > in, se devuelve 0; en otro caso, se devuelve la suma de f(i0) y el valor del sumatorio desde i0+1 hasta in. En Lisp (DEFUN SUMATORIO (F I0 IN) (COND ((> I0 IN) 0) ( T (+ (FUNCALL F I0) (SUMATORIO F (1+ I0) IN))))) Y una definicin recursiva de productorio: si i0>in, se devuelve 1; en otro caso, se devuelve el producto de f(i0) y el valor del productorio desde i0+1 hasta in. En Lisp (DEFUN PRODUCTORIO (F I0 IN) (COND ((> I0 IN) 1) ( T (* (FUNCALL F I0) (PRODUCTORIO F (1+ I0) IN))))) b) Las dos funciones del apartado anterior son muy parecidas; podemos abstraer la operacin y considerarla como otro argumento (lo mismo con el valor inicial). Quedar (DEFUN ACUMULAR (F I0 IN V-INI ACUM) (COND ((> I0 IN) V-INI) ( T (FUNCALL ACUM (FUNCALL F I0) (ACUMULAR F (1+ I0) IN V-INI ACUM))))) c) El ejercicio ya est prcticamente resuelto en R.2.4: ahora basta abstraer la funcin y el intervalo y considerarlos argumentos. El procedimiento principal ser ahora (DEFUN BUSQUEDA-DICOTOMICA (F A B) (PTO-MEDIO (BUSCAR0 (HACER-ESTADO F A B)))) El constructor HACER-ESTADO es ahora (DEFUN HACER-ESTADO (F X Y) (LIST X Y (FUNCALL F X) (FUNCALL F Y) F)) Aadimos el selector (DEFUN FUNCION-ESTADO (E) (NTH 4 E)) Y modificamos ELEGIR-SUC (DEFUN ELEGIR-SUC (E) (COND ((MISMO-SIGNO (FUNCALL (FUNCION E) (PTO-MEDIO E)) (FIZQ E)) (HACER-ESTADO (FUNCION-ESTADO E) (PTO-MEDIO E) (DER E))) (T (HACER-ESTADO (FUNCION-ESTADO E) (IZQ E) (PTO-MEDIO E)))))
3.10
R.3.6. Funciones MAP. Definir las siguientes funciones: a) la funcin mapa-b, que tiene tres argumentos: una funcin f (de un argumento) y dos nmeros enteros n, m. mapa-b devuelve una lista formada por los resultados de aplicar f a n, n+1, n+2, ... m (NIL si n > m). b)la funcin mi-mapcar, que tiene dos argumentos: una funcin f (de un argumento) y una lista L. mi-mapcar devuelve la lista formada aplicando f a cada elemento de L. Por ejemplo, si f es CAR y L es ((A B) (C D)) mi-mapcar debe devolver (A C). c)la funcin mi-maplist, anloga a mi-mapcar, con la diferencia de que aplica f sucesivamente a L, a CDR(L), a CDDR(L), .... mientras no se llegue a NIL. Por ejemplo, si f est definido por (LAMBDA (X) (CONS 'DIGO X)) y L es (QUE SI) el resultado debe ser ((DIGO QUE SI) (DIGO SI)) d)la funcin mi-mappendcar, anloga a mi-mapcar, con la diferencia de que agrupa los diversos resultados con APPEND en lugar de LIST. e)la funcin mi-mappendlist, anloga a mi-maplist, con la diferencia de que agrupa los diversos resultados con APPEND en lugar de LIST. ************************** SOLUCION: a)Recursin en N: si n > m, se devuelve NIL. En otro caso, mapa-b CONSa f(n) con el resultado de aplicar mapa-b a f, n+1 y m. En Lisp (DEFUN MAPA-B (F N M) (COND ((> N M) NIL) ( T (CONS (FUNCALL F N) (MAPA-B F (1+ A) B))))) b)Recursin sobre la lista L: Si L es NIL, entonces mi-mapcar devuelve NIL. En otro caso, mimapcar de L se obtiene CONSando el resultado de aplicar f a CAR(L) y el resultado de aplicar mimapcar a f y CDR(L). En Lisp: (DEFUN MI-MAPCAR (F L) (COND ((NULL L) NIL) ( T (CONS (FUNCALL F (CAR L)) (MI-MAPCAR F (CDR L)))))) NOTA: existe la funcin predefinida MAPCAR, algo ms general que MI-MAPCAR. MAPCAR tiene como primer argumento una funcin f de cualquier nmero de argumentos. Los restantes argumentos de MAPCAR son listas. MAPCAR va aplicando f a tuplas formadas por un elemento de cada lista, hasta que se agota alguna de ellas. Por ejemplo, (MAPCAR #'(LAMBDA (X Y) (+ X Y)) '(1 2 3) '(200 100)) => (201 102) c) Recursin sobre la lista L: si L es NIL, entonces, mi-maplist devuelve NIL. En otro caso, mimaplist de L se obtiene CONSando el resultado de aplicar f a L y el resultado de aplicar mi-maplist a f y CDR(L). En Lisp: (DEFUN MI-MAPLIST (F L) (COND ((NULL L) NIL) ( T (CONS (FUNCALL F L) (MI-MAPLIST F (CDR L)))))) NOTA: existe la funcin predefinida MAPLIST, algo ms general que MI-MAPLIST. MAPLIST tiene como primer argumento una funcin f de cualquier nmero de argumentos. Los restantes argumentos de MAPLIST son listas. MAPLIST va aplicando f a tuplas formadas por las listas, los CDR de las listas, los CDDR de las listas, ... hasta que se agota alguna de ellas. Por ejemplo, (MAPLIST #'(LAMBDA (X Y) (APPEND X Y X)) '(A B) '(X Y Z)) => ((A B X Y Z A B) (B Y Z B))
3.11
NOTA: Un empleo impremeditado de MAPLIST puede llevar a computaciones redundantes. d)Basta aplicar APPEND al resultado de MAPCAR: (DEFUN MI-MAPPENDCAR (F L) (APPLY #'APPEND (MAPCAR F L))) NOTA: existe la funcin predefinida MAPCAN -versin destructiva de MI-MAPPENDCAR- que emplea NCONC en lugar de APPEND (vd. leccin 8). e)Basta aplicar APPEND al resultado de MAPLIST: (DEFUN MI-MAPPENDLIST (F L) (APPLY #'APPEND (MAPLIST F L))) NOTA: existe la funcin predefinida MAPCON -versin destructiva de MI-MAPPENDLIST- que emplea NCONC en lugar de APPEND (vd. leccin 8).
3.12
R.3.7. Uso de funciones MAP. Empleando funciones MAP, escribir definiciones Lisp de las funciones siguientes: a) la suma de vectores. Los vectores se representarn mediante listas de nmeros. b) el apareamiento de L1 y L2, que es la lista formada por listas de dos elementos, tomados el primero de L1 y el segundo de L2. Por ejemplo, el apareamiento de (DO RE MI) y (C D E) es ((DO C) (RE D) (MI E)). Si las listas son de distinta longitud, se aparean hasta que una de ellas se acabe. Por ejemplo, (A) y (X Y Z) dan ((A X)). c) poner-comillas, que tiene como argumento una lista (e1 e2 ...) y devuelve la lista ('e1 'e2 ...). d) la distancia entre dos puntos. Los puntos se representarn por listas de nmeros. e) la lista desnuda o linealizada obtenida a partir de una lista con anidamientos (vd. R.2.6) ************************** SOLUCION: a)Para resolver problemas con funciones MAP, descomponemos el problema inicial de la siguiente forma: -procesar cada elemento de la lista de la forma adecuada. Esto queda reflejado en el argumento funcional de la funcin MAP. -componer los resultados de estos procesamientos de forma adecuada. Esto queda reflejado en la eleccin de la funcin MAP (MAPCAR, MAPCAN, MAPPENDCAR, ...). A veces tambin es necesario aplicar otros pasos posteriores de procesamiento. En el caso de la suma vectorial: -hay que sumar cada elemento de V1 con el correspondiente de V2. El argumento funcional ser #'+. -hay que formar una lista con los resultados. La funcin ser MAPCAR. En Lisp (DEFUN SUMA-VECTORIAL (V1 V2) (MAPCAR #'+ V1 V2)) NOTA: "Las funciones MAP deberan usarse siempre que su aplicacin sea natural, puesto que esto aumenta la claridad del cdigo" [CLtL2], p. 172. b)Tenemos que hacer lo siguiente: para cada elemento de L1, formar una lista con l y el correspondiente de L2; y formar una lista con los resultados. En Lisp (DEFUN APAREAR (L1 L2) (MAPCAR #'LIST L1 L2))
c)Tenemos que hacer lo siguiente: -para cada elemento e de L, formar la lista (QUOTE e). No hay ninguna funcin predefinida que haga exactamente esto; pero no es necesario (ni conveniente) emplear DEFUN para definir este proceso. En lugar de ello, escribimos directamente la definicin en la llamada a MAPCAR. -formar una lista con los resultados. En Lisp (DEFUN PONER-COMILLAS (L) (MAPCAR #'(LAMBDA (X) (LIST 'QUOTE X)) L))
d)Tenemos que hacer lo siguiente: -para cada par de elementos correspondientes e, e', calcular (e - e')2. -formar una lista con los resultados. -sumar todos los elementos de la lista y hallar la raz cuadrada de la suma. En Lisp
3.13
(DEFUN DISTANCIA (P1 P2) (SQRT (APPLY #'+ (MAPCAR #'(LAMBDA (X Y) (SRQT (- X Y))) P1 P2)))) e)Tenemos que hacer lo siguiente: -para cada elemento e, calcular su linealizacin. Ntese que ello implica una definicin recursiva. El caso base se dar cuando e sea un tomo. -APPENDar los resultados. Por tanto, en el caso base se debe devolver la lista (e). En Lisp (DEFUN DESNUDAR (L) (COND ((ATOM L) (LIST L)) ( T (MI-MAPPENDCAR #'DESNUDAR L)))) NOTA: MI-MAPPENDCAR no es una funcin predefinida. Se define en R.3.6.
3.14
R.3.8. Cierres lxicos. Evaluar las siguientes formas Lisp en el orden dado: a) (DEFUN F1 (X) (APPEND X L2)) b) (DEFUN F2 (L1 L2) (F1 L1)) c) (F2 '(Y PUNTO) '(HE DICHO)) d) (DEFUN G0 () #'(LAMBDA (X) (APPEND X '(Y PUNTO)))) e) (G0) f) (FUNCALL (G0) '(COMA)) g) (DEFUN G1 (L) #'(LAMBDA (X) (APPEND X L))) h) (G1 '(COMA)) i) (FUNCALL (G1 '(Y PUNTO)) '(COMA)) ************************** SOLUCION: a) (DEFUN F1 (X) (APPEND X L2)) => F1 b) (DEFUN F2 (L1 L2) (F1 L1)) => F2 c)Recurdese lo explicado en R.1.8 sobre la creacin de entornos: Se crea un entorno E1 para evaluar la expresin completa (F2 '(Y PUNTO) '(HE DICHO)) == L1<- (Y PUNTO) L2<- (HE DICHO) (F1 L1) y para evaluar esta subexpresin se crea otro entorno E2: (F1 L1) == X<- (Y PUNTO) (APPEND X L2)) X es parmetro de F1 y por tanto se liga al valor del argumento (Y PUNTO). Sin embargo, en el entorno E2 L2 est sin ligar y por tanto no se puede evaluar. El resultado final es pues => Error: L2 sin ligar. Sin embargo L2 estaba ligado en el entorno E1, desde donde se cre el entorno E2. Ello no importa: las ligaduras de E1 son irrelevantes en los entornos creados a partir de l. Esto se suele expresar diciendo que Common Lisp crea entornos lxicos. d) => G0 e) (G0) => #<funcin 1 #xDFF024> (una funcin de X que APPENDa X y la lista (Y PUNTO)) f) (FUNCALL (G0) '(COMA)) El primer argumento es (G0) => una funcin de X que APPENDa X y la lista (Y PUNTO) El segundo argumento es (COMA) FUNCALL aplica el primer argumento al segundo y produce (COMA Y PUNTO) Inteligencia Artificial e I.C.. 2004/05 3.15 Dpto. Leng. Ciencias Comp. (DEFUN G0 () #'(LAMBDA (X) (APPEND X '(Y PUNTO))))
g)
(DEFUN G1 (L) #'(LAMBDA (X) (APPEND X L)))
=> G1 h) (G1 '(COMA)) => #<cierre 1 #xE0F824> (una funcin de X que APPENDa X y la lista L) Ntese que Lisp no afirma devolver una funcin, sino un cierre. Cul es la diferencia? El siguiente ejemplo lo aclarar: i) (FUNCALL (G1 '(Y PUNTO)) '(COMA)) == FUNCALL evala sus argumentos. El primero es una llamada a G1, luego se crea un entorno para evaluarla: (G1 '(Y PUNTO)) == L<- (Y PUNTO) #'(LAMBDA (X) (APPEND X L))) => #< cierre 1 #xE0F811> FUNCALL aplica esta funcin devuelta por G1 al segundo argumento (COMA): ((LAMBDA (X) (APPEND X L)) '(Y PUNTO)) y el resultado depender del valor al que est ligado L. Pero L era el parmetro de G1, y ya no estamos en el entorno de evaluacin de G1; por lo tanto, podra esperarse que el resultado fuera => Error: L1 sin ligar. Sin embargo, no es as. Para justificar esto, tenemos que introducir el concepto de cierre lxico y modificar la descripcin dada en R.3. 2 de la forma especial FUNCTION. Un cierre lxico es un par formado por un objeto-procedimiento F y un entorno. Cuando se aplique F, siempre habr de hacerse en este entorno. Ahora podemos dar la descripcin completa de FUNCTION, que es como sigue: (FUNCTION argumento) -un solo argumento, que debe ser un smbolo o una expresin lambda. -FUNCTION toma literalmente su argumento. -el valor devuelto es: -si el argumento es un smbolo, el objeto-procedimiento que es el significado funcional del smbolo. -si el argumento es una expresin lambda, un cierre lxico. Un cierre lxico es un objetoprocedimiento que adems conserva una referencia al entorno vigente durante la evaluacin de FUNCTION. Hasta ahora todas las llamadas a FUNCTION se haban realizado en un entorno vaco, por lo que no haba sido necesario introducir el concepto de cierre lxico. Pero al evaluar (G1 '(Y PUNTO)) se produce una llamada a FUNCTION: #'(LAMBDA (X) (APPEND X L))) en el entorno L<- (Y PUNTO) Por tanto el resultado es un cierre lxico: => #<cierre lxico 10A># que representaremos grficamente como L<- (Y PUNTO) (LAMBDA (X) (APPEND X L))) Y tras esta explicacin podemos justificar que (FUNCALL (G1'(Y PUNTO)) '(HE DICHO)) == L<- (Y PUNTO) (LAMBDA (X) (APPEND X L)) '(HE DICHO) => (Y PUNTO HE DICHO) Los cierres lxicos permiten crear en tiempo de ejecucin funciones "variables", es decir, funciones cuya definicin depende del entorno en que se crean. Por ejemplo, una llamada a la funcin anterior (G1 argG1) crea una funcin F(argf) que modifica argf de una forma que depende del valor que tuviera argG1.
3.16
R.3.9. Funciones que devuelven cierres lxicos. Escribir definiciones Lisp de las funciones siguientes: a)la funcin composicin de dos funciones de un argumento. b)la funcin que devuelve la funcin suma de dos funciones de un argumento numrico. c)la funcin que aproxima la funcin derivada de una funcin real de una variable real (supngase una funcin sin argumentos deltax que da el incremento de x para calcular la aproximacin). d)la funcin que tiene como argumentos una funcin f de un argumento y un natural n, y devuelve la funcin iterada f n. ************************** SOLUCION: a)Ntese que COMPOSICION devuelve un objeto-procedimiento ms unas ligaduras, es decir, un cierre lxico. La nica manera de conseguir esto es emplear FUNCTION. Por otra parte, la composicin de f y g es la funcin que aplicada a x devuelve f(g (x)). En Lisp (DEFUN COMPOSICION (F G) #'(LAMBDA (X) (FUNCALL F (FUNCALL G X)))) b) la definicin de SUMA-FUNCIONAL es sencilla: la funcin de f y g que devuelve la funcin que aplicada a x devuelve f(x) + g(x). En Lisp (DEFUN SUMA-FUNCIONAL (F G) #'(LAMBDA (X) (+ (FUNCALL F X) (FUNCALL G X)))) c) Recordemos que la derivada de f en x se define como el lmite de f(x + dx) - f(x) dx cuando dx tiende a 0. Podemos aproximarla por el valor de este cociente cuando dx es pequeo. En Lisp (DEFCONSTANT DELTAX 1D-6) (DEFUN DERIVADA (F) #'(LAMBDA (X) (/ (- (FUNCALL F (+ DELTAX X)) (FUNCALL F X)) DELTAX))) d) Recursin sobre n: si n=0, la funcin devuelta es la identidad; en otro caso, el resultado de componer f con el valor devuelto para n -1. Empleando la funcin composicin ser (DEFUN ITERACION (F N) (COND ((ZEROP N) #'(LAMBDA (X) X)) (T (COMPOSICION F (ITERACION F (1- N)))))) o bien directamente (DEFUN ITERACION (F N) (COND ((ZEROP N) #'(LAMBDA (X) X)) (T #'(LAMBDA (X) (FUNCALL F (FUNCALL (ITERACION F (1- N)) X))))))
3.17
R.3.10. Uso de funciones MAP (II). Empleando funciones MAP, escribir definiciones Lisp de las funciones siguientes: a)sustituir-todo, que dados una lista de smbolos L y dos smbolos sv, sn, devuelve la lista originada a partir de L sustituyendo todas las apariciones de sv (como elemento de L) por sn. b)sustituir-prof, que dados una lista de smbolos L y dos smbolos sv, sn, devuelve la lista originada a partir de L sustituyendo todas las apariciones de sv (como elemento de L o elemento de alguno de los elementos de L, etc. ...) por sn. c)producto-cartesiano, que dadas dos listas de smbolos sin repeticiones L1 y L2 devuelve la lista de todos los pares formados por un elemento de L1 y otro de L2. c)permutaciones, que dada una lista de smbolos sin repeticiones L devuelve la lista de todas las permutaciones de L (consideradas como listas). ************************** SOLUCION: a)Tenemos que hacer lo siguiente: -para cada elemento e, sustituirlo por sn (si es sv) o dejarlo inalterado (si es distinto de sv). -LISTar los resultados. El lector poco atento puede sugerir la siguiente implementacin: (DEFUN SUST-AUX (X) (IF (EQ X SV) SN X)) (DEFUN SUSTITUIR-TODO (SN SV L) (MAPCAR #'SUST-AUX L)) Pero esta implementacin es completamente incorrecta. En efecto, la llamada a SUST-AUX desde MAPCAR siempre produce un error, ya que SV y SN estn sin ligar en el entorno creado al llamar a SUST-AUX. La solucin es emplear # para generar un cierre lxico: (DEFUN SUSTITUIR-TODO (SN SV L) (MAPCAR (SUST-AUX SN SV) L)) (DEFUN SUST-AUX (SN SV) #'(LAMBDA (X) (IF (EQ X SV) SN X))) Pero, par que definir una funcin auxiliar? La mejor solucin es simplemente (DEFUN SUSTITUIR-TODO (SN SV L) (MAPCAR #'(LAMBDA (X) (IF (EQ X SV) SN X)) L)) b)Tenemos que hacer lo siguiente: -para cada elemento e, si es un tomo, sustituirlo por sn (si es sv) o dejarlo inalterado (si es distinto de sv). Si e es una lista, sustituirla por el resultado de aplicarle sustituir-prof. -LISTar los resultados. (DEFUN SUSTITUIR-PROF (SN SV L) (MAPCAR #'(LAMBDA (X) (COND ((ATOM X) (IF (EQ X SV) SN X)) (T (SUSTITUIR-PROF SN SV X)))) L)) c)Tenemos que hacer lo siguiente: -para cada elemento s1 de L1, formar una lista con todos los pares de la forma (s1, s2), siendo s2 de L2. -APPENDar los resultados. A su vez, para la primera parte tendremos que -para cada elemento s2 de L2, formar la lista (s1, s2). -LISTar los resultados. Esto ltimo se consigue con Inteligencia Artificial e I.C.. 2004/05 3.18 Dpto. Leng. Ciencias Comp.
(MAPCAR #'(LAMBDA (S2) (LIST S1 S2)) L2)) Ntese que S1 est libre en esta expresin, pero si S1 est ligado en una expresin exterior la presencia de #' asegura que este valor se conserva al aplicar (LAMBDA (S2) (LIST S1 S2)) Por tanto en Lisp la funcin pedida ser (DEFUN PRODUCTO-C (L1 L2) (MI-MAPPENDCAR #'(LAMBDA (S1) (MAPCAR #'(LAMBDA (S2) (LIST S1 S2)) L2)) L1)) NOTA: MI-MAPPENDCAR no es una funcin predefinida. Se define en R.3.6. d)Tenemos que hacer lo siguiente: -si L es vaca, la lista de sus permutaciones es (NIL) -en otro caso -para cada elemento s de L, hay que considerar todas las permutaciones de L-{s} y prefijarles s. -hay que APPENDar los resultados. Para prefijar s a todas las listas elementos de una lista de listas L-LISTAS podemos definir (DEFUN PREFIJAR (S L-LISTAS) (MAPCAR #'(LAMBDA (L) (CONS S L)) L-LISTAS)) Y finalmente la funcin pedida es (DEFUN PERMUTACIONES (L) (COND ((NULL L) (LIST NIL)) (T (MI-MAPPENDCAR #'(LAMBDA (S) (PREFIJAR S (PERMUTACIONES (REMOVE S L)))) L)))) NOTA: MI-MAPPENDCAR no es una funcin predefinida. Se define en R.3.6.
3.19
R.4.1. Filtrado de listas (I) Definir las siguientes funciones: a) Mi-remove-if y mi-remove-if-not, que tienen dos argumentos: un predicado p (de un argumento) y una lista L. Mi-remove-if devuelve una lista formada por los elementos de L que no satisfacen p. Mi-remove-if-not devuelve una lista formada por los elementos de L que satisfacen p. b) Mi-substitute-if, que tiene tres argumentos: una expresin e, un predicado p (de un argumento) y una lista L. Mi-substitute-if devuelve una lista formada por los mismos elementos que L, salvo los que satisfacen p, que son sustituidos por e. c) Mi-some y mi-every, que tienen dos argumentos: un predicado p (de un argumento) y una lista L. Mi-some devuelve T si algn elemento de ,L satisface p, NIL en otro caso. Mi-every devuelve T si todos los elementos de L satisfacen p, NIL en otro caso. d) Mi-find-if, que tiene dos argumentos: un predicado p (de un argumento) y una lista L. Mi-find-if devuelve el primer elemento de L que satisface p, o NIL si ninguno lo satisface. ************************** SOLUCION: a) Podemos dar una definicin recursiva directa: si L es NIL, el valor es NIL; en otro caso, si car(L) satisface p, el valor es el resultado de aplicar la funcin sobre cdr(L); en otro caso, el valor es el resultante de CONSar car(L) con el resultado de aplicar la funcin sobre cdr(L). En Lisp (DEFUN MI-REMOVE-IF (P L) (COND ((NULL L) NIL) ((FUNCALL P (CAR L)) (MI-REMOVE-IF P (CDR L))) (T (CONS (CAR L) (MI-REMOVE-IF P (CDR L)))))) De MI-REMOVE-IF-NOT tambin podemos dar una definicin directa; pero, para qu escribir tanto? Definamos la funcin inversa-booleana: (DEFUN INVERSA-BOOLEANA (P) #'(LAMBDA (X) (NOT (FUNCALL P X)))) y ser simplemente (DEFUN MI-REMOVE-IF-NOT (P L) (MI-REMOVE-IF (INVERSA-BOOLEANA P) L)) b) Como antes, podemos dar una definicin recursiva directa; pero anora la daremos empleando MAPCAR. Para cada elemento en de L devolvemos e o bien el mismo en, segn satisfaga o no el predicado p. En Lisp (DEFUN MI-SUBSTITUTE-IF (E P L) (MAPCAR #'(LAMBDA (X) (IF (FUNCALL P X) E X)) L)) c) Anlogamente (DEFUN MI-SOME (P L) (COND ((NULL L) NIL) ((FUNCALL P (CAR L)) T) (T (MI-SOME P (CDR L))))) y (DEFUN MI-EVERY (P L) (COND ((NULL L) T) ((FUNCALL P (CAR L)) (MI-EVERY P (CDR L))) (T NIL))) o bien (DEFUN MI-EVERY (P L) (NOT (MI-SOME (INVERSA-BOOLEANA P) L))) d) Por ltimo (DEFUN MI-FIND-IF (P L) (COND ((NULL L) NIL) ((FUNCALL P (CAR L)) (CAR L)) (T (MI-FIND-IF P (CDR L))))) NOTA. Todas estas funciones estn predefinidas en Common Lisp. Su definicin es ms general, pues no slo se aplican a listas, sino a sucesiones (listas, vectores y cadenas). NOTA. Todas estas funciones tienen un "aire de familia"; es posible abstraer un grado ms y definirlas como instancias de una funcin de reduccin o plegado (vd. R.4.3) Inteligencia Artificial e I.C.. 2002/03 4.3 Dpto. Leng. Ciencias Comp.
R.4.2. Filtrado de listas (II). a) Definir en Lisp la funcin substitute-if-2, que tiene tres argumentos: un predicado binario p, una funcin binaria f y una lista L. Substitute-if-2 devuelve una lista formada a partir de L suprimiendo el primer par de elementos consecutivos e, e de L tales que satisfacen p(e, e), y sustituyndolos por f(e, e). Si no existe tal par, se devuelve la misma L. Por ejemplo (SUBSTITUTE-IF-2 #'< #'+ '(6 4 2 3 10 8)) => (6 4 5 10 8) (SUBSTITUTE-IF-2 #'= #'+ '(6 4 2 3 10 8)) => (6 4 2 3 10 8) b) Definir en Lisp la funcin substitute-if-n, que tiene tres argumentos: un predicado p (de dos argumentos), una funcin binaria f y una lista L. Substitute-if-n devuelve una lista calculada aplicando sucesivamente substitute-if-2, hasta que se alcance un valor fijo. c) La sucesin de Hilgemeier {hi} es una sucesin de listas de enteros dada por h0 = (1) es decir, un uno (1 1) es decir, dos unos h1 = h2 = (2 1) es decir, un dos un uno h3 = (1 2 1 1) es decir, un uno un dos dos unos h4 = (1 1 1 2 2 1) ... hi+1 = la descripcin de hi escrita como lista de nmeros. Definir la funcin HILGE(n), que devuelve el n-simo trmino de la sucesin de Hilgemeier. ************************** SOLUCION: a)Si L esta vaca o consta de un solo valor es L; en otro caso, si los dos primeros elementos satisfacen p, se devuelve la lista formada CONSando f(car(L), cadr(L)) y cdr(L); en otro caso se recurre sobre cdr(L). En Lisp (DEFUN SUBSTITUTE-IF-2 (P F L) (COND ((NULL L) NIL) ((NULL (CDR L)) L) ((FUNCALL P (CAR L) (CADR L)) (CONS (FUNCALL F (CAR L) (CADR L)) (CDDR L))) (T (CONS (CAR L) (SUBSTITUTE-IF-2 P F (CDR L)))))) b) Lo que se est definiendo es la funcin de punto fijo correspondiente a SUBSTITUTE-IF-2. Definamos la funcin "punto fijo", que tiene como argumentos una funcin f y una expresin prueba, y devuelve el primer valor de la sucesin {ei }dada por e0 =prueba, ei+1 =f(ei) tal que ei+1=ei: (DEFUN PUNTO-FIJO (F PRUEBA) (COND ((EQUAL PRUEBA (FUNCALL F PRUEBA)) PRUEBA) (T (PUNTO-FIJO F (FUNCALL F PRUEBA))))) Para no llamar dos veces a F, podemos introducir una funcin auxiliar: (DEFUN PUNTO-FIJO (F PRIMERA-PRUEBA) (PUNTO-FIJO-AUX F PRIMERA-PRUEBA (FUNCALL F PRIMERA-PRUEBA))) (DEFUN PUNTO-FIJO-AUX (F S FS) (COND ((EQUAL S FS) S) (T (PUNTO-FIJO-AUX F FS (FUNCALL F FS))))) Y an podemos mejorar esta definicin, considerando que el predicado de igualdad se puede pasar como argumento a PUNTO-FIJO: (DEFUN PUNTO-FIJO (F PRIMERA-PRUEBA P) (PUNTO-FIJO-AUX F PRIMERA-PRUEBA (FUNCALL F PRIMERA-PRUEBA) P)) (DEFUN PUNTO-FIJO-AUX (F S FS P) (COND ((FUNCALL P S FS) S) (T (PUNTO-FIJO-AUX F FS (FUNCALL F FS) P)))) Ahora SUBSTITUTE-IF-N ser simplemente (DEFUN SUBSTITUTE-IF-N (PRED F LISTA) (PUNTO-FIJO #'(LAMBDA (L) (SUSBSTITUTE-IF-2 PRED F L)) LISTA))
4.4
El punto fijo se alcanza en un nmero finito de pasos: en efecto, (REPLACE-IF-2 P L) devuelve o bien L, en cuyo caso ya se ha llegado al punto fijo, o bien una lista de longitud inferior en una unidad, lo cual slo puede ocurrir un nmero finito de veces. c) La definicin recursiva es fcil, supuesta definida sig-hilge que calcula el siguiente elemento de la sucesin: (DEFUN HILGE (N) (COND ((ZEROP N) (LIST 1)) ( T (SIG-HILGE (HILGE (1- N)))))) El valor de sig-hilge(L) puede calcularse de muchas formas. La que proponemos aqu es elegante (aunque no necesariamente eficiente): 1) contemos una vez cada elemento de L, creando as una lista de listas L. Por ejemplo, si L es (1 1 1 2 2 1) L ser ((1 1) (1 1) (1 1) (1 2) (1 2) (1 1)) Ello equivale a calcular la lista L, formada a partir de L LISTando cada uno de sus elementos y el nmero 1. Es decir, L es el resultado de aplicar #'(LAMBDA (X) (LIST 1 X)) a cada elemento de L, o sea, L es el resultado de (MAPCAR #'(LAMBDA (X) (LIST 1 X)) L). Por ejemplo, si L es (1 1 1 2 2 1) L ser ((1 1) (1 1) (1 1) (1 2) (1 2) (1 1)) 2) si dos cuentas consecutivas se refieren al mismo valor, debemos acumularlas en una sola cuenta. Por ejemplo, si L es ((1 1) (1 1) (1 1) (1 2) (1 2) (1 1)) debemos quedarnos con ((2 1) (1 1) (1 2) (1 2) (1 1)), ((3 1) (1 2) (1 2) (1 1)) y finalmente con ((3 1) (2 2) (1 1)) Ello equivale a aplicar a L el proceso REPLACE-IF-N con predicado #'(LAMBDA (L1 L2) (= (CADR L1) (CADR L2))) y funcin de reemplazamiento #'(LAMBDA (L1 L2) (LIST (+ (CAR L1) (CAR L2)) (CADR L1))) 3) Formemos una sola lista con los pares que finalmente hayan quedado. Es decir, APPLYamos #'APPEND al resultado anterior. En Lisp (DEFUN SIG-HILGE (L) (APPLY #'APPEND (REPLACE-IF-N #'(LAMBDA (L1 L2) (= (CADR L1) (CADR L2))) #'(LAMBDA (L1 L2) (LIST (+ (CAR L1) (CAR L2)) (CADR L1))) (MAPCAR #'(LAMBDA (X) (LIST 1 X)) L))))
4.5
R.4.6. Programacin por paso de mensajes. Deseamos disear un programa para representar y manejar cuadrados y tringulos equilteros, definidos ambos por las coordenadas de su centro y la longitud de su lado. El programa debe ser capaz de calcular las reas y los permetros de estas figuras. a)Definir una implementacin Lisp basada en el paso de mensajes, en la que los objetos se representen como cierres lxicos. b)En esta implementacin, trazar la evaluacin de (PERIMETRO (HACER CUADRADO 210 120 1)) c)Modificar la implementacin para tratar tambin los crculos, definidos por su centro y radio. d)Modificar la implementacin para calcular tambin los dimetros de los objetos. Se entiende por dimetro de un polgono la longitud del mayor segmento que puede trazarse en el interior del polgono: para el cuadrado es la diagonal y para el tringulo equiltero el lado. ************************** SOLUCION: a)En R.2.8 representbamos los objetos mediante listas, y las operaciones sobre los objetos mediante un conjunto de funciones independientes de estas listas. En la representacin basada en cierres lxicos se adopta un punto de vista radicalmente opuesto: cada objeto se encarga de definir sus propias funciones. Los constructores son por tanto ms complejos: (DEFUN HACER-TRIANGULO (X Y L) #'(LAMBDA (MSJ) (CASE MSJ (LADO L) (CENTROX X) (CENTROY Y) (ALTURA (* 0.5 (SQRT 3) L)) (AREA (* 0.5 L (* 0.5 (SQRT 3) L))) (PERIMETRO (* 3 L))))) (DEFUN HACER-CUADRADO (X Y L) #'(LAMBDA (MSJ) (CASE MSJ (LADO L) (CENTROX X) (CENTROY Y) (ALTURA L) (AREA (* L L)) (PERIMETRO (* 4 L))))) Por el contrario, las funciones son muy sencillas. Definimos un aplicador genrico (DEFUN OPERAR (MSJ OBJ) (FUNCALL OBJ MSJ)) Y, si lo deseamos, podemos dar nombres a las operaciones especificadas: (DEFUN LADO (OBJ) (OPERAR LADO OBJ)) (DEFUN CENTROX (OBJ) (OPERAR 'CENTROX OBJ)) (DEFUN CENTROY (OBJ) (OPERAR 'CENTROY OBJ)) (DEFUN ALTURA (OBJ) (OPERAR 'ALTURA OBJ)) (DEFUN AREA (OBJ) (OPERAR 'AREA OBJ)) (DEFUN PERIMETRO (OBJ) (OPERAR 'PERIMETRO OBJ)) b) Evaluemos el argumento (HACER-CUADRADO 210 120 1) => X <- 210 Y <- 120 L <- 1 #'(LAMBDA (MSJ) (CASE MSJ (LADO) L) (CENTROX X) (CENTROY Y) (ALTURA L) (AREA (* L L)) (PERIMETRO (* 4 L)))) Inteligencia Artificial e I.C.. 2002/03 4.6 Dpto. Leng. Ciencias Comp.
Llamemos C1 a este cierre lxico. Ahora se puede evaluar la expresin propuesta: (PERIMETRO (HACER-CUADRADO 210 120 1)) == OBJ <- C1 (OPERAR 'PERIMETRO OBJ) == OBJ <- C1 MSJ <- PERIMETRO (FUNCALL OBJ MSJ) == (* 4 1) => 4 c)Es necesario aadir un constructor de crculos: (DEFUN HACER-CIRCULO (X Y R) #'(LAMBDA (MSJ) (CASE MSJ (RADIO R) (CENTROX X) (CENTROY Y) (AREA (* PI R R)) (PERIMETRO (* 2 PI R))))) y aadir la nueva funcin RADIO: (DEFUN RADIO (OBJ) (OPERAR RADIO OBJ)) El resto permanece igual. d)Es necesario modificar todos los constructores: (DEFUN HACER-TRIANGULO (X Y L) #'(LAMBDA (MSJ) (CASE MSJ (LADO L) (CENTROX X) (CENTROY Y) (ALTURA (* 0.5 (SQRT 3) X)) (AREA (* 0.5 L (* 0.5 (SQRT 3) X))) (PERIMETRO (* 3 L)) (DIAMETRO L)))) (DEFUN HACER-CUADRADO (X Y L) #'(LAMBDA (MSJ) (CASE MSJ (LADO L) (CENTROX X) (CENTROY Y) (ALTURA L) (AREA (* L L)) (PERIMETRO (* 4 L)) (DIAMETRO (* (SQRT 2) L))))) (DEFUN HACER-CIRCULO (X Y R) #'(LAMBDA (MSJ) (CASE MSJ (RADIO R) (CENTROX X) (CENTROY Y) (AREA (* PI R R)) (PERIMETRO) (* 2 PI R)) (DIAMETRO (* 2 R))))) y aadir la nueva funcin DIAMETRO: (DEFUN DIAMETRO (OBJ) (OPERAR DIAMETRO OBJ))
4.7
R.4.7. Programacin dirigida por los datos. Disear una implementacin alternativa para los apartados a), b), c) de R.4.6, en la que los objetos se representen por listas y exista un operador genrico OPERAR; la manera de efectuar las operaciones ser mediante llamadas (OPERAR operacin objeto) ************************** SOLUCION: a)Podemos emplear los mismos constructores y predicados de tipo que en R.2.8: (DEFUN HACER-TRIANGULO (X Y L) (LIST 'TRIANGULO X Y L)) (DEFUN HACER-CUADRADO (X Y L) (LIST 'CUADRADO X Y L)) (DEFUN TIPO (OBJ) (CAR OBJ)) (DEFUN TRIANGULO-P (OBJ) (EQ (TIPO OBJ) 'TRIANGULO)) (DEFUN CUADRADO-P (OBJ) (EQ (TIPO OBJ) 'CUADRADO)) Sin embargo, las funciones deben implementarse de otra forma para permitir la definicin de OPERAR. Definiremos una pequea funcin annima para cada operacin sobre cada tipo de objeto; por ejemplo, el lado del cuadrado ser (LAMBDA (OBJ) (CADDDR OBJ)) El permetro del cuadrado ser (LAMBDA (OBJ) (* 4 (CADDDR OBJ))) y anlogamente los dems casos. Todas estas funciones annimas se ponen en correspondencia con los tipos mediante una tabla, que para cada tipo y nombre de operacin devuelve la funcin que corresponde: (DEFUN TABLA (OPERACION TIPO) (CASE TIPO (TRIANGULO (CASE OPERACION (LADO #'(LAMBDA (OBJ) (CADDDR OBJ))) (CENTROX #'(LAMBDA (OBJ) (CADR OBJ))) (CENTROY #'(LAMBDA (OBJ) (CADDR OBJ))) (ALTURA #'(LAMBDA (OBJ) (* 0.5 (SQRT 3) (OPERAR 'LADO OBJ)))) (AREA #'(LAMBDA (OBJ) (* 0.5 (OPERAR 'LADO OBJ) (OPERAR 'ALTURA OBJ)))) (PERIMETRO #'(LAMBDA (OBJ) (* 3 (OPERAR 'LADO OBJ)))))) (CUADRADO (CASE OPERACION (LADO #'(LAMBDA (OBJ) (CADDDR OBJ))) (CENTROX #'(LAMBDA (OBJ) (CADR OBJ))) (CENTROY #'(LAMBDA (OBJ) (CADDR OBJ))) (ALTURA #'(LAMBDA (OBJ) (OPERAR 'LADO OBJ))) (AREA #'(LAMBDA (OBJ) (* (OPERAR 'LADO OBJ) (OPERAR 'ALTURA OBJ)))) (PERIMETRO #'(LAMBDA (OBJ) (* 4 (OPERAR 'LADO OBJ)))))))) La funcin OPERAR genrica ser simplemente (DEFUN OPERAR (OPERACION OBJ) (FUNCALL (TABLA OPERACION (TIPO OBJ)) OBJ)) c )Aadimos el constructor de crculos: (DEFUN HACER-CIRCULO (X Y R) (LIST CIRCULO X Y R)) (DEFUN CIRCULO-P (OBJ) (EQ (TIPO OBJ) CIRCULO)) Consideramos las funciones elementales necesarias: por ejemplo, para el radio (LAMBDA (OBJ) (CADDDR OBJ)) Para el rea (LAMBDA (OBJ) (* PI (OPERAR 'RADIO OBJ) (OPERAR 'RADIO OBJ))) Inteligencia Artificial e I.C.. 2002/03 4.8 Dpto. Leng. Ciencias Comp.
Y para el permetro (LAMBDA (OBJ) (* 2 PI (OPERAR 'RADIO OBJ))) Y las insertamos en la tabla: (DEFUN TABLA (OPERACION TIPO) (CASE TIPO (CIRCULO (CASE OPERACION (RADIO #'(LAMBDA (OBJ) (CADDDR OBJ))) (CENTROX #'(LAMBDA (OBJ) (CADR OBJ))) (CENTROY #'(LAMBDA (OBJ) (CADDR OBJ))) (ALTURA #'(LAMBDA (OBJ) (* 0.5 (SQRT 3) (OPERAR 'LADO OBJ)))) (AREA #'(LAMBDA (OBJ) (* PI (OPERAR 'RADIO OBJ) (OPERAR 'RADIO OBJ)))) (PERIMETRO #'(LAMBDA (OBJ) (* 2 PI (OPERAR 'RADIO OBJ)))))) (TRIANGULO (CASE OPERACION (LADO #'(LAMBDA (OBJ) (CADDDR OBJ))) (CENTROX #'(LAMBDA (OBJ) (CADR OBJ))) (CENTROY #'(LAMBDA (OBJ) (CADDR OBJ))) (ALTURA #'(LAMBDA (OBJ) (* 0.5 (SQRT 3) (OPERAR 'LADO OBJ)))) (AREA #'(LAMBDA (OBJ) (* 0.5 (OPERAR 'LADO OBJ) (OPERAR 'ALTURA OBJ)))) (PERIMETRO #'(LAMBDA (OBJ) (* 3 (OPERAR 'LADO OBJ)))))) (CUADRADO (CASE OPERACION (LADO #'(LAMBDA (OBJ) (CADDDR OBJ))) (CENTROX #'(LAMBDA (OBJ) (CADR OBJ))) (CENTROY #'(LAMBDA (OBJ) (CADDR OBJ))) (ALTURA #'(LAMBDA (OBJ) (OPERAR 'LADO OBJ))) (AREA #'(LAMBDA (OBJ) (* (OPERAR 'LADO OBJ) (OPERAR 'ALTURA OBJ)))) (PERIMETRO #'(LAMBDA (OBJ) (* 4 (OPERAR 'LADO OBJ)))))))) d) Aadimos las operaciones elementales necesarias: Para el dimetro del crculo: (LAMBDA (OBJ) (* 2 (RADIO OBJ))) Para el dimetro del cuadrado: (LAMBDA (OBJ) (* (SQRT 2) (LADO OBJ))) y las insertamos en la tabla: Modificamos la tabla, insertando estas nuevas funciones: (DEFUN TABLA (OPERACION TIPO) (CASE TIPO (CIRCULO (CASE OPERACION (DIAMETRO #'(LAMBDA (OBJ) (* 2 (RADIO OBJ))) ... ...)) (TRIANGULO (CASE OPERACION (DIAMETRO #'(LAMBDA (OBJ) (CADDDR OBJ))) ... ...)) (CUADRADO (CASE OPERACION (DIAMETRO #'(LAMBDA (OBJ) (* (SQRT 2) (LADO OBJ)))) ... ...)))) Inteligencia Artificial e I.C.. 2002/03 4.9 Dpto. Leng. Ciencias Comp.
R.5.1. Recursin por la cola. a) Dar una definicin recursiva y otra recursiva por la cola del factorial de un nmero natural. b) Id. de la longitud de una lista. c) Supongamos un subconjunto de Lisp en el que solamente existen los operadores predefinidos CONS, CAR, CDR, NULL, ZEROP, 1+, 1-, COND, QUOTE, EQ, ATOM. Adems, las clusulas de una forma COND constan siempre de dos elementos. Implementar un predicado REC-COLA-P tal que la forma (REC-COLA-P smbolo expresin) devuelva "verdadero" cuando expresin sea una definicin recursiva por la cola de smbolo, "falso" en otro caso. Por ejemplo (REC-COLA-P 'KK '(KK (1- X))) => T (REC-COLA-P 'KK '(1+ (KK (1- X)))) => NIL ************************** SOLUCION: Una definicin es recursiva por la cola si ninguna llamada recursiva se encuentra i) en el mbito de otra funcin; ni ii) como condicin de una forma COND o anloga. Es decir, el resultado que devuelva la llamada recursiva i+1-sima pasar a ser tambin el resultado de la llamada recursiva i-sima. Por tanto, al llegar a la llamada i+1-sima, el intrprete o compilador LISP puede borrar el entorno de la llamada anterior, y la pila de entornos no crecer, conservando tamao unidad. Muchas de las definiciones recursivas vistas hasta ahora no lo son por la cola. Una forma habitual de transformarlas de manera que lo sean es emplear un argumento adicional, llamado acumulador. El argumento acumulador para una funcin F debe cumplir las siguientes propiedades: -en la llamada inicial, el argumento acumulador es el valor que F devuelve para el caso base. -cuando se alcanza el caso base, el valor devuelto es el argumento acumulador. -en la llamada recursiva correspondiente a cada paso de recursin, el valor del argumento acumulador es el necesario para conservar la correccin. Segn esto, a) Consideremos la definicin de factorial dada en R.2.3: (DEFUN FACTORIAL (N) (IF (ZEROP N) 1 (* N (FACTORIAL (1- N))))) La llamada recursiva est en el mbito de la funcin *; por tanto, la definicin no es recursiva por la cola. Introducimos una funcin auxiliar con argumento acumulador, cuyo valor inicial debe ser 1: (DEFUN FACTORIAL (N) (FACT-AUX N 1)) La funcin auxiliar devuelve el acumulador en el caso base, en otro caso realiza una llamada recursiva en la que el acumulador se ha multiplicado por N: (DEFUN FACT-AUX (N AC) (IF (ZEROP N) AC (FACT-AUX (1- N) (* N AC)))) Realicemos el anlisis de complejidad de las dos versiones de (FACTORIAL N). Para la versin recursiva no por la cola es claro que la pila de llamadas alcanza un tamao mximo de N (al llegar al argumento 0) y que la pila debe almacenar un solo valor (el de N). La complejidad en espacio es O(N). Por otra parte, la versin recursiva por la cola tiene complejidad constante (un solo entorno almacenado) aunque en este caso el entorno tiene tamao 2 (N y AC). En cuanto al tiempo, ambas versiones tienen igual complejidad de orden O(N) (N decrementos, N comparaciones y N productos).
b) Anlogamente, la versin dada en R.2.5 es Inteligencia Artificial e I.C.. 2002/2003 5.3 Dpto. Leng. Ciencias Comp.
(DEFUN MI-LENGTH (L) (IF (NULL L) 0 (1+ (MI-LENGTH (CDR L))))) que no es recursiva por la cola. Introducimos la funcin auxiliar, con valor inicial del acumulador el correspondiente al caso base, es decir, 0: (DEFUN MI-LENGTH (L) (LENGTH-AUX L 0)) La funcin auxiliar devuelve el acumulador en el caso base, en otro caso realiza una llamada recursiva en la que el acumulador se ha incrementado en 1: (DEFUN LENGTH-AUX (L AC) (IF (NULL L) AC (LENGTH-AUX (CDR L) (+ 1 AC)))) c) Este ejercicio ilustrar un hecho notable: no suele ser difcil escribir un programa Lisp que analice programas Lisp. Esto se debe a que, como el lector habr percibido, los programas Lisp tienen la misma sintaxis que (un subconjunto de) los datos Lisp. La definicin de recursividad por la cola expresa que "ninguna llamada...". Resultar ms cmodo expresarla como "no es verdad que alguna llamada...". O sea (DEFUN REC-COLA-P (F S) (NOT (NO-REC-COLA-P F S))) Adems, la definicin habla de "llamadas en el mbito de otra funcin, o en una condicin". Hay que distinguir pues entre las apariciones de smbolo dentro y fuera de estos mbitos prohibidos. Aadimos un argumento DENTRO que ser T si nos encontramos dentro de lo prohibido, NIL en otro caso. Al principio, DENTRO ser NIL: (DEFUN NO-REC-COLA-P (F S) (NO-REC-COLA-AUX F S NIL)) Y ya no hay ms que considerar todos los casos posibles para expresin: (DEFUN NO-REC-COLA-AUX (F S DENTRO) (COND ((ATOM S) NIL) ;los tomos no cuentan ((EQ 'QUOTE (CAR S)) NIL) ;ni lo quotado ((EQ F (CAR S)) ;llamada recursiva a smbolo (IF DENTRO ;si dentro de lo prohibido T ;es no-rec-cola (SOME #'(LAMBDA (S1) ;en otro caso, ver el resto (NO-REC-COLA-AUX F S1 T)) ;que ya es proh. (CDR S)))) ((EQ 'COND (CAR S)) ;caso mas complicado (OR (SOME #'(LAMBDA (CL) ;las condiciones son ambito proh. (NO-REC-COLA-AUX F (CAR CL) T)) (CDR S)) (SOME #'(LAMBDA (CL) (NO-REC-COLA-AUX F (CADR CL) DENTRO)) (CDR S)))) (T (SOME #'(LAMBDA (S1) ;ver el resto, que ya es (NO-REC-COLA-AUX F S1 T)) ;ambito proh. (CDR S)))))
5.4
R.5.2. Listas-lambda: &OPTIONAL, &REST. a) Supnganse las siguientes definiciones: (DEFUN KK-OPT1 (A1 &OPTIONAL B1 (B2 0) &REST C1) (LIST A1 B1 B2 C1)) (DEFUN KK-OPT2 (A1 &OPTIONAL B1 (B2 (+ A1 B1)) &REST C1) (LIST 'REQUERIDOS A1 'OPCIONALES B1 B2 'RESTANTE C1)) Evaluar las siguientes expresiones: (KK-OPT1 'A (KK-OPT1 'B) (KK-OPT1 'C 'D) (KK-OPT1 'E 'F 'G)) (KK-OPT2 'A (KK-OPT2 'B) (KK-OPT2 'C 'D) (KK-OPT2 'E 'F 'G)) b) Reescribir las definiciones recursivas por la cola de R.5.1, sin emplear funciones auxiliares. c) Definir FUNCALL en trminos de APPLY. d) Sea una funcin numrica f y un conjunto de argumentos a1, ..., an. Definir una funcin (INFIMO f a1, ..., an) que devuelve el ai para el que f(ai) es mnimo. ************************** SOLUCION: a) En R.1.8 qued dicho que el segundo argumento de DEFUN es una lista-lambda y que por el momento una lista-lambda sera una lista de cero o ms smbolos denominados parmetros. En realidad, una lista lambda puede ser ms compleja. Para resolver estos ejercicios necesitamos conocer el empleo de los parmetros opcionales, el parmetro restante y los parmetrosclaves (seguimos sin decir toda la verdad sobre las listas lambda). Una lista lambda es de la forma (smbolo* [&OPTIONAL parm-opcional*] [&REST smbolo][&KEY parm-clave*]) donde parm-opcional y parm-clave son de la forma smbolo | (smbolo expresin) Los primeros smbolos se denominan parmetros requeridos. El que sigue a &REST, parmetro restante. Los parmetros que siguen a &OPTIONAL son opcionales. Esto quiere decir que la lista de argumentos que se pase a la funcin los puede contener o no. Si no los contiene, se supone que valen NIL o bien el valor resultante de evaluar la expresin con la que se emparejen. Las expresiones para los valores por defecto se evalan secuencialmente: por tanto, es posible emplear en ellas los argumentos anteriores de la lista lambda. Los parmetros opcionales sirven para definir funciones con nmero de argumentos variable entre ciertos lmites (por ejemplo, de 3 a 7 argumentos) y para dar valores por defecto a los argumentos que faltan en la llamada. Por ejemplo, sea F1 la funcin dada por (DEFUN F1 (NOMBRE &OPTIONAL (PESO 100) SEXO) (LIST NOMBRE PESO SEXO)) F1 tiene de 1 a 3 argumentos, con valores por defecto para los ltimos 100 y NIL. (F1) => Error: nmero incorrecto de argumentos. (F1 'PEPE 50) => (PEPE 50 NIL) (F1 'PEPE 50 'V) => (PEPE 50 V) El parmetro que sigue a &REST se liga a una lista formada por los argumentos sobrantes tras emparejar todos los parmetros requeridos y todos los parmetros opcionales. Por tanto, el parmetro restante sirve para definir funciones con un nmero indeterminado de argumentos. Segn esto (KK-OPT1 'A =>(A (B NIL (KK-OPT2 'A =>Error: A1 (KK-OPT1 'B) (KK-OPT1 'C 'D) (KK-OPT1 'E 'F 'G)) 0 NIL) (C D 0 NIL) ((E F G NIL))) (KK-OPT2 'B) (KK-OPT2 'C 'D) (KK-OPT2 'E 'F 'G)) no es un nmero
b) Emplearemos argumentos opcionales: (DEFUN FACTORIAL (N &OPTIONAL (AC 1)) (IF (ZEROP N) AC (FACTORIAL (1- N) (* N AC)))) Inteligencia Artificial e I.C.. 2002/2003 5.5 Dpto. Leng. Ciencias Comp.
(DEFUN MI-LENGTH (L &OPTIONAL (AC 0)) (IF (NULL L) AC (MI-LENGTH (CDR L) (+ 1 AC)))) c) La nica diferencia entre ambas funciones radica en que APPLY supone que los argumentos de su argumento funcional forman una lista: (DEFUN MI-FUNCALL (FUNCION &REST ARGS) (APPLY FUNCION ARGS)) Sera igualmente sencillo definir APPLY en trminos de FUNCALL? d) El argumento f ser obligado, los a1, ..., an formarn el argumento restante. Cul es el nfimo del conjunto vaco? Caben dos respuestas: -no est definido; debe producirse un error. Empleando REDUCE, (DEFUN INFIMO (F &REST ARGS) (REDUCE #'(LAMBDA (X Y) (IF (< (FUNCALL F X) (FUNCALL F Y)) X Y)) ARGS)) NOTA. (REDUCE funcin lista) aplica la funcin binaria funcin a los dos primeros elementos de lista; luego a este resultado y al tercer elemento de lista; y as sucesivamente hasta agotar lista. El ltimo valor as calculado es el valor de (REDUCE funcin lista). Si lista es unitaria, el valor es su nico elemento. Si lista es vaca, el valor es el que devolvera funcin con 0 argumentos. -otra opcin es devolver el elemento neutro de la comparacin, es decir, el mximo valor numrico representable.
5.6
R.5.3. Listas-lambda: &KEY. a) Supnganse las siguientes definiciones: (DEFUN KK-CLA1 (A1 A2 &KEY (FUNCION #'LIST) OTRO-VALOR) (FUNCALL FUNCION A1 A2 OTRO-VALOR)) (DEFUN KK-CLA2 (&KEY A B C) (LIST A B C)) (DEFUN KK-CLA3 (A &KEY B C) (LIST A B C)) Evaluar las siguientes expresiones: (KK-CLA1 'A (KK-CLA1 1 2 :OTRO-VALOR 3 :FUNCION #'+ )) (KK-CLA1 1 2 (IF (ATOM 1) :OTRO-VALOR :FUNCION) 3) (KK-CLA2 :B :B :C :C) (KK-CLA3 :B :B :C :C) (KK-CLA3 :B :B :C :C :A) b) Usando parmetros clave, reimplementar la funcin OPERAR de R.4.6. ************************** SOLUCION. a) Los parmetros de una lista lambda que siguen a &KEY son parmetros-claves. Los parmetros-claves son siempre opcionales, es decir, la llamada a la funcin puede tener los correspondientes argumentos o carecer de ellos. Pero adems de esto, cuando en una lista lambda aparece un parmetro-clave las reglas para asignar los argumentos a los parmetros no son las vistas en R.1.9, es decir, los argumentos no se asignan en el mismo orden en que aparecen en la llamada. Las reglas son las siguientes: a) los parmetros requeridos se emparejan con los primeros argumentos de la llamada. Si hay ms o menos, se produce un error. b) a cada parmetro clave se le hace corresponder una palabra-clave, aadindole al principio el signo :. Las palabras-clave son smbolos que se evalan a s mismos. c) si en la llamada figuran argumentos para los parmetros-claves, cada uno debe ir precedido por la correspondiente palabra-clave. El emparejamiento entre parmetros y argumentos se produce precisamente de esta forma, independientemente del orden de aparicin de los argumentos. Sea F1 la funcin dada por (DEFUN F1 (NOMBRE &KEY (PESO 100) SEXO) (LIST NOMBRE PESO SEXO)) Las siguientes llamadas se evalan as: (F1) => Error: nmero incorrecto de argumentos. (F1 'PEPE :PESO 50) => (PEPE 50 NIL) (F1 'PEPE :SEXO 'V) => (PEPE 100 V) (F1 'PEPE :PESO 50 :SEXO 'V) => (PEPE 50 V) (F1 'PEPE :SEXO 'V :PESO 50) => (PEPE 50 V) (F1 :SEXO 'V 'PEPE :PESO 50) => Error: V no es una palabra-clave. (F1 'PEPE 50 'V) => Error: 50 no es una palabra-clave. (F1 :PESO 50 :SEXO 'V) => Error: 50 no es una palabra-clave. Es posible, aunque poco recomendable, emplear en la misma lista-lambda parmetros-clave y parmetros opcionales y restantes. Segn esto a.1) (KK-CLA1 1 2 :OTRO-VALOR 3 :FUNCION #'+ ) ;suma de 1,2 y 3 => 6 Inteligencia Artificial e I.C.. 2002/2003 5.7 Dpto. Leng. Ciencias Comp.
y por tanto (KK-CLA1 'A (KK-CLA1 1 2 :OTRO-VALOR 3 :FUNCION #'+)) ;lista de A,6 y NIL =>(A 6 NIL) a.2) (IF (ATOM 1) :OTRO-VALOR :FUNCION) => :OTRO-VALOR por tanto (KK-CLA1 1 2 (IF (ATOM A1) :OTRO-VALOR :FUNCION) 3) ;3 es :OTRO-VALOR =>(1 2 3) a.3):B y :C -tambin en sus segundas apariciones- se evalan a s mismos y son los valores de los parmetros B y C: (KK-CLA2 :B :B :C :C) => (NIL :B :C) a.4):B en su primera aparicin se evala a s mismo y es el valor del parmetro requerido A. En su segunda aparicin sirve para indicar que sigue el argumento para B, que ser :C (en su primera aparicin). La segunda aparicin de :C indica que sigue el valor de C. Pero este valor falta, luego se produce un error: (KK-CLA3 :B :B :C :C) => Error: palabra-clave sin su argumento. a.5) Todo es como en a.3, con la diferencia de que la segunda aparicin de :C va seguida por :A. Por tanto, no hay error: (KK-CLA3 :B :B :C :C :A) => (:B :C :A) NOTA: este ejercicio no tiene otra finalidad que mostrar en detalle el significado de las listas lambda. El cdigo anterior no debe tomarse como ejemplo de buen estilo, y el alumno har bien si evita que en sus programas aparezcan estas expresiones teratolgicas.
b) Quin va antes, el mensaje o el objeto? Para evitar dudas, empleemos parmetros clave: (DEFUN OPERAR (&KEY MENSAJE OBJETO) (FUNCALL OBJETO MENSAJE)) y tendremos (OPERAR 'AREA (HACER-CUADRADO 2 2 10)) => Error: AREA no es una clave (OPERAR :MENSAJE 'AREA :OBJETO (HACER-CUADRADO 2 2 10)) => 100 (OPERAR :OBJETO (HACER-CUADRADO 2 2 10) :MENSAJE 'AREA) => 100
5.8
R.5.4. Ligaduras locales: LET. LET*. a) Representemos por expresin(s1, ..., sn) una expresin LISP donde aparecen los smbolos s1, ..., sn; por ejemplo, (CONS A B) es una expresin donde aparecen los smbolos A y B. Supongamos que queremos hallar el valor de expresin(s1, ..., sn) en un entorno donde s1, ..., sn estn ligados a los valores de expr1, ..., exprn, respectivamente; por ejemplo, queremos que A valga el valor de (CDR '(C D)) y B valga el valor de (CDR '(E F)). Escribir una expresin LISP que tenga como subexpresin expresin(s1, ..., sn) y se evale a este valor. En el ejemplo dado, queremos obtener el valor ((C D) E F). b) Supongamos adems que cada expresin expri contiene posiblemente apariciones de los smbolos s1, ..., si-1. Supongamos que deseamos que el valor de expri tenga en cuenta las ligaduras establecidas por expr1, ..., expri-1 para estos smbolos. Por ejemplo, queremos evaluar (CONS A B) cuando A est ligado al valor de (CDR '(X C D)) y B est ligado al valor de (CDR A). Escribir la correspondiente expresin LISP. c) Evaluar las siguientes expresiones en el orden dado: (LET ((A 7)) (LET ((B 10)) (+ A B))) (FUNCALL (LET ((A 7)) #'(LAMBDA (X) (+ X A))) 10) (LET ((A 7)) (MAPCAR #'(LAMBDA (X) (+ X A)) '(10 20 30))) (LET ((A 7)) (DEFUN F1 (X) (+ X A))) (F1 10) d) Reimplementar, empleando LET o LET*, la funcin QUICKSORT de R.2.7. e) Reimplementar, empleando LET o LET*, la funcin ELEGIR-SUC de R.2.4. ************************** SOLUCION: a) Sabemos cmo crear entornos: al evaluar una expresin funcional (una lista) se cra un entorno donde los parmetros que aparecen en la definicin de la funcin estn ligados ordenadamente a los argumentos que se pasan. Tambin sabemos cmo crear funciones annimas: mediante el uso de LAMBDA. Por tanto, la solucin pedida es ((LAMBDA (S1 ... SN) EXPRESION) EXPR1 ... EXPRN) es decir, en el ejemplo dado, ((LAMBDA (A B) (CONS A B)) (CDR '(C D)) (CDR '(E F))) => ((D) F) Para crear entornos, CommonLISP proporciona la forma predefinida LET, que es completamente equivalente a lo anterior: (LET (ligadura*) expresin-cuerpo*) donde ligadura puede ser smbolo | (smbolo expresin-inicial) Es decir, se crea un entorno donde cada smbolo se liga ordenadamente y en paralelo al valor de cada expresin-inicial (el valor por defecto de sta es NIL). En este entorno se evala cada expresin-cuerpo y se devuelve el valor de la ltima. En nuestro ejemplo (LET ((A (CDR '(C D))) (B (CDR '(E F)))) (CONS A B)) => ((D) F) Inteligencia Artificial e I.C.. 2002/2003 5.9 Dpto. Leng. Ciencias Comp.
Por supuesto, ahora seguimos teniendo A=> Error: A sin ligar B=> Error: B sin ligar. b) La solucin anterior no funciona: ((LAMBDA (A B) (CONS A B)) (CDR '(X C D)) (CDR A)) => Error: A sin ligar. y anlogamente (LET ((A (CDR '(X C D))) (B (CDR A))) (CONS A B)) => Error: A sin ligar. Efectivamente, para la aparicin de A como argumento de la funcin no es vlida la ligadura establecida para A como parmetro de la funcin. La solucin en este caso es un poco ms complicada: ((LAMBDA (A) ((LAMBDA (B) (CONS A B)) (CDR A))) (CDR '(X C D))) => ((C D) D) es decir, en el caso general, ((LAMBDA (S1) ... ((LAMBDA (SN) EXPRESION) EXPRN) ... EXPR1) Para crear entornos de esta segunda manera, CommonLISP proporciona la forma predefinida LET*, que es completamente equivalente a lo anterior: (LET* (ligadura*) expresin-cuerpo*) donde ligadura puede ser smbolo | (smbolo expresin-inicial) Es decir, se crea un entorno donde cada smbolo se liga ordenadamente y secuencialmente al valor de cada expresin-inicial (el valor por defecto de sta es NIL). En este entorno se evala cada expresin-cuerpo y se devuelve el valor de la ltima. En nuestro ejemplo (LET*((A (CDR '(X C D)) (B (CDR A)) (CONS A B)) => ((C D) D) Tambin ahora tenemos A=> Error: A sin ligar B=> Error: B sin ligar. c) Puesto que las formas LET son equivalentes a listas con expresiones LAMBDA, las reglas de mbito lxico vistas en R.3.1. siguen siendo vlidas. En particular, las ligaduras del LET exterior son accesibles en el LET interior. Por tanto (LET ((A 7)) (LET ((B 10)) (+ A B))) =>17 Inteligencia Artificial e I.C.. 2002/2003 5.10 Dpto. Leng. Ciencias Comp.
Al crear un cierre lxico, se almacena el entorno lxico vigente. Ello rige tambin para las ligaduras establecidas por LET. Por tanto, en la llamada a FUNCTION del siguiente ejemplo queda almacenada la ligadura de A, que se emplea posteriormente al aplicar FUNCALL: (FUNCALL (LET ((A 7)) #'(LAMBDA (X) (+ X A))) 10) =>17 Lo mismo ocurre al emplear MAPCAR: (LET ((A 7)) (MAPCAR #'(LAMBDA (X) (+ X A)) '(10 20 30))) =>(17 27 37) El siguiente ejemplo ilustra una caracterstica de DEFUN que hasta ahora no habamos mencionado. Sabemos que DEFUN crea un objeto procedimental y lo asigna al significado funcional de un smbolo (R.1.8). Pero al evaluar DEFUN se hace algo ms: en realidad, se crea un cierre lxico donde se almacena el entorno lxico vigente. Por tanto, en el ejemplo siguiente el significado funcional de F1 lleva consigo la ligadura de A establecida con LET: (LET ((A 7)) (DEFUN F1 (X) (+ X A))) =>F1 y ahora (F1 10) =>17 d) Cambiemos levemente la especificacin de QUICKSORT dada en R.2.7: el criterio de ordenacin es un segundo argumento opcional (< por defecto). En cuanto a la implementacin, para recorrer la lista una sola vez por llamada, definimos una funcin auxiliar DOSLISTAS recursiva por la cola, que tiene como argumentos el elemento PIVOTE, el RESTO de la lista y el predicado de comparacin P, y devuelve un par de listas ACCHICOS AC-GRANDES tales que AC-CHICOS contiene los elementos de RESTO menores que PIVOTE, y AC-GRANDES los elementos mayores o iguales: (DEFUN DOSLISTAS (PIVOTE RESTO P &OPTIONAL AC-CHICOS AC-GRANDES) (COND ((NULL RESTO) (LIST AC-CHICOS AC-GRANDES)) ((FUNCALL P (CAR RESTO) PIVOTE) (DOSLISTAS PIVOTE (CDR RESTO) P (CONS (CAR RESTO) AC-CHICOS) AC-GRANDES)) (T (DOSLISTAS PIVOTE (CDR RESTO) P AC-CHICOS (CONS (CAR RESTO) AC-GRANDES))))) Ahora la funcin pedida ser (DEFUN QUICKSORT (L &OPTIONAL (P #'<)) (LET* ((L2 (DOSLISTAS (CAR L) (CDR L) P)) (CHICOS (CAR L2)) (GRANDES (CADR L2))) (IF (NULL L) NIL (APPEND (QUICKSORT CHICOS P) (CONS (CAR L) (QUICKSORT GRANDES P))))))
e) En cada llamada hay que calcular el punto medio y el valor de la funcin en l; introduciendo variables locales ligadas a estos valores tendremos la siguiente definicin: Inteligencia Artificial e I.C.. 2002/2003 5.11 Dpto. Leng. Ciencias Comp.
(DEFUN ELEGIR-SUC (E) (LET* ((M (PTO-MEDIO E)) (F (FUNCION E)) (FM (FUNCALL F M))) (COND ((MISMO-SIGNO FM (FIZQ E)) (HACER-ESTADO F M (DER E) FM (FDER E))) (T (HACER-ESTADO F (IZQ E) M (FIZQ E) FM))))) La complejidad de esta implementacin es menor que la de la dada en R.2.4. En efecto, ahora se calcula una sola vez en cada paso el punto medio y el valor de F en l. Por el contrario, antes se calculaban tres veces el punto medio y dos veces el valor de la funcin. En cualquier caso, la complejidad asinttica de la bsqueda efectuada por BUSCAR0 no ha variado, y sigue siendo del orden de O(log(L/)), donde L es la longitud del intervalo inicial. NOTA: la forma (TIME expresin) proporciona informacin acerca del tiempo invertido en evaluar expresin. El alumno puede emplearla para comprobar, con distintos tamaos del intervalo inicial, si se gana con la nueva implementacin un tiempo apreciable.
5.12
R.5.5. Funciones locales: FLET. LABELS. a) Evaluar en el orden dado las siguientes expresiones: (FLET ((F1 (N) (* N 7)) (F2 (N) (- N 7))) (FLET ((F3 (N) (+ N 7))) (LIST (F1 10) (F2 10) (F3 10)))) (F1 10) (LABELS ((F1 (N) (* N 7)) (F2 (N) (- N 7))) (FLET ((F3 (N) (+ N 7))) (LIST (F1 10) (F2 10) (F3 10)))) (F2 10) (LABELS ((F1 (N) (IF (ZEROP N) N (+ N (F1 (1- N))))) (F2 (N) (F1 (1+ N)))) (LIST (F1 10) (F2 10))) (FLET ((F1 (N) (+ 2 N)) (F2 (N) (F1 N))) (F2 10)) Empleando FLET o LABELS, dar definiciones de las siguientes funciones: b) El factorial de un nmero natural. c) La funcin QUICKSORT de R.5.4.d). ************************** SOLUCION: a) Desde R.1.8 estamos definiendo nuevas funciones en Lisp, y dndoles nombre: DEFUN lleva a cabo esta misin. Como sabemos, el mbito del significado funcional establecido por DEFUN para un smbolo no sigue las reglas lxicas, sino que es global. Ahora bien, muchas veces queremos definir funciones auxiliares cuyo uso solamente tiene sentido dentro de un mbito lxico concreto. Para ello podemos emplear los operadores FLET o LABELS. La sintaxis de una forma FLET/LABELS es (FLET|LABELS (definicin-funcin*) cuerpo) donde definicin-funcin es de la forma (smbolo lista-lambda cuerpo) y cuerpo es una sucesin de expresiones. Cada una de estas definiciones establece un significado funcional para el correspondiente smbolo, de manera anloga a DEFUN. El cuerpo de la forma FLET|LABELS se evala en un entorno donde estn vigentes las definicinfuncin. El valor de la ltima expresin del cuerpo de la forma FLET|LABELS es el valor de la forma FLET o LABELS. Adems, en el caso de LABELS las definiciones de cada funcin estn vigentes en el mbito (definicin-funcin*), lo que permite definir funciones recursivas. Segn esto (FLET ((F1 (N) (* N 7)) (F2 (N) (- N 7))) (FLET ((F3 (N) (+ N 7))) (LIST (F1 10) (F2 10) (F3 10)))) => (70 3 17) (F1 10) => error, F1 no tiene significado funcional. (LABELS ((F1 (N) (* N 7)) (F2 (N) (- N 7))) (FLET ((F3 (N) (+ N 7))) (LIST (F1 10) (F2 10) (F3 10)))) => (70 3 17)
5.13
(F2 10) => error, F2 no tiene significado funcional. (LABELS ((F1 (N) (IF (ZEROP N) N (+ N (F1 (1- N))))) (F2 (N) (F1 (1+ N)))) (LIST (F1 10) (F2 10))) =>(55 66) (FLET ((F1 (N) (IF (ZEROP N) N (+ N (F1 (1- N)))))) (F1 10)) => error, F1 no tiene significado funcional. (FLET ((F1 (N) (+ 2 N)) (F2 (N) (F1 N))) (F2 10)) => error, F1 no tiene significado funcional. b) Esta es la cuarta definicin que ofrecemos de FACTORIAL: (DEFUN FACTORIAL (N) (LABELS ((FACT-AUX (N AC) (IF (ZEROP N) AC (FACT-AUX (1- N) (* N AC))))) (FACT-AUX N 1))) La definicin es prcticamente igual a la dada en R.5.1; la nica diferencia es que ahora la definicin de FACT-AUX slo es vlida en el mbito lxico de la definicin de FACTORIAL. Los programadores Lisp empedernidos prefieren este tipo de definiciones a las ms elegantes de R.5.2, que emplean parmetros opcionales. Ello se debe a que, en la mayora de las implementaciones Lisp, una llamada a una funcin con parmetros opcionales, claves o restantes lleva consigo un poco de trabajo extra. c) Una primera versin podra ser la siguiente, en la cual la funcin auxiliar DOSLISTAS se define nicamente para el entorno lxico de la definicin de QUICKSORT: (DEFUN QUICKSORT (L &OPTIONAL (P #'<)) (LABELS ((DOSLISTAS (PIVOTE RESTO P &OPTIONAL AC-CHICOS AC-GRANDES) (COND ((NULL RESTO) (LIST AC-CHICOS AC-GRANDES)) ((FUNCALL P (CAR RESTO) PIVOTE) (DOSLISTAS PIVOTE (CDR RESTO) P (CONS (CAR RESTO) AC-CHICOS) AC-GRANDES)) (T (DOSLISTAS PIVOTE (CDR RESTO) P AC-CHICOS (CONS (CAR RESTO) AC-GRANDES)))))) (IF (NULL L) NIL (LET* ((LL (DOSLISTAS (CAR L) (CDR L) P)) (CHICOS (CAR LL)) (GRANDES (CADR LL))) (APPEND (QUICKSORT CHICOS P) (CONS (CAR L) (QUICKSORT GRANDES P))))))) Si lo deseamos, podemos seguir transformando la definicin para suprimir todos los parmetros opcionales, salvo el inicial:
5.14
(DEFUN QUICKSORT (L &OPTIONAL (P #'<)) (LABELS ((DOSLISTAS (PIVOTE RESTO P AC-CHICOS AC-GRANDES) (COND ((NULL RESTO) (LIST AC-CHICOS AC-GRANDES)) ((FUNCALL P (CAR RESTO) PIVOTE) (DOSLISTAS PIVOTE (CDR RESTO) P (CONS (CAR RESTO) AC-CHICOS) AC-GRANDES)) (T (DOSLISTAS PIVOTE (CDR RESTO) P AC-CHICOS (CONS (CAR RESTO) AC-GRANDES))))) (QUICKSORT-NO-OPT (L P) (IF (NULL L) NIL (LET* ((LL (DOSLISTAS (CAR L) (CDR L) P NIL NIL)) (CHICOS (CAR LL)) (GRANDES (CADR LL))) (APPEND (QUICKSORT-NO-OPT CHICOS P) (CONS (CAR L) (QUICKSORT-NO-OPT GRANDES P))))))) (QUICKSORT-NO-OPT L P)))
5.15
R.5.6. Iteracin general: DO, DO*. Evaluar las siguientes expresiones: a) (DO ((X '(A B C) (CDR X)) (Y '(D E F G H) (CDR Y)) (Z '(A B))) ((NULL X) (APPEND Y Z))) b) (DO ((X '(A B C) (CDR X)) (Y '(D E F G H)) (Z)) ((NULL X) (CONS Y Z)) (CONS X Y)) c) (DO ((N 1 (1+ N)) (M N (* 2 M))) ((> M 10) N)) d) (DO* ((N 1 (1+ N)) (M N (* 2 M))) ((> M 10) M N)) Empleando DO o DO*, implementar las siguientes funciones: e) la longitud de una lista L. f) la funcin BUSCAR0 de R.2.4 ************************** SOLUCION: Las formas iterativas ms generales en LISP son DO y DO* (DO (ligadura*) (test resultado*) expresin-cuerpo*) o bien (DO* (ligadura*) (test resultado*) expresin-cuerpo*) donde ligadura puede ser smbolo|(smbolo)|(smbolo expr-inicial)|(smbolo expr-inicial expr-paso) El significado es el siguiente: -Se crea un entorno con ligaduras para los smbolos indicados. -Se evala cada expr-inicial (valor por defecto, NIL) y sus valores son asignados a los correspondientes smbolos. La evaluacin es en paralelo para DO y secuencialmente para DO*. -Se evala test. -Si test es verdadero, se evala cada expresin de la sucesin resultado* , la evaluacin de DO acaba y el valor que se devuelve es el de la ltima (valor por defecto, NIL). -Si test es falso, la evaluacin de DO contina: primeramente se evalan secuencialmente -caso de existir- las expresiones del cuerpo. A continuacin se evalan las expr-paso (en paralelo para DO y secuencialmente para DO*) y los valores son asignados a los correspondientes smbolos. Si para un smbolo no hay expr-paso su ligadura no se modifica. A continuacin, se evala de nuevo el test y se repite todo el proceso. Segn esto a) Las variables locales del entorno son X, Y, Z. La inicializacin es X<=(A B C), Y<=(D E F G H), Z<=(A B) En el siguiente paso es X<=(B C), Y<=(E F G H), Z<=(A B) En el siguiente paso es X<=(), Y<=(G H), Z<=(A B) Ahora el test se satisface, luego se calcula (APPEND Y Z) y se devuelve este valor: (DO ((X '(A B C) (CDR X)) (Y '(D E F G H) (CDR Y)) (Z '(A B))) ((NULL X) (APPEND Y Z))) => (G H A B) b) Las variables locales del entorno son X, Y, Z. La inicializacin es X<=(A B C), Y<=(D E F G H), Z<=()
5.16
Se calcula (CONS X Y)=>((A B C) D E F G H);en el siguiente paso es X<=(B C), Y<=(D E F G H), Z<=(). Se calcula (CONS X Y)=>((B C) D E F G H), en el siguiente paso es X<=(C), Y<=(D E F G H), Z<=(). Se calcula (CONS X Y)=>((C) D E F G H), en el siguiente paso es X<=(), Y<=(D E F G H), Z<=(). Ahora el test se satisface, luego se calcula (CONS Y Z) y se devuelve este valor: (DO ((X '(A B C) (CDR X)) (Y '(D E F G H)) (Z)) ((NULL X) (CONS Y Z)) (CONS X Y)) => ((D E F G H)) NOTA: Obsrvese que los valores calculados para las expresiones del cuerpo no han servido para nada. Qu sentido tiene pues el uso de estas expresiones? En general, pueden servir para muchas cosas: efectos laterales de E/S (leccin 6), asignaciones explcitas a las variables locales (leccin 7) o finalizacin anticipada de la computacin. c) Las variables locales del entorno son N, M. La inicializacin es N<=1, M<=N. Pero ambas operaciones se llevan a cabo en paralelo, luego el valor de N no est an disponible y se produce un error: (DO ((N 1 (1+ N)) (M N (* 2 M))) ((> M 10) N)) => Error: N sin ligar. c) Las variables locales del entorno son N, M. La inicializacin es N<=1, M<=N. Ambas operaciones se llevan a cabo secuencialmente, luego el valor de N est ya disponible y M=1 En el siguiente paso N<=2, M<=2. En el siguiente paso N<=3, M<=4. En el siguiente paso N<=4, M<=8. En el siguiente paso N<=5, M<=16. El test se satisface, se evalan M a 16, N a 5 y se devuelve este ltimo valor: (DO ((N 1 (1+ N)) (M N (* 2 M))) ((> M 10) M N)) => 5 Lo dicho en la nota anterior es vlido tambin para el caso de emplear varias expresiones en el resultado: salvo la ltima se emplean por sus efectos laterales. e) Consideremos el siguiente ciclo: (DEFUN LENGTH-IT (L) (DO ((L-AUX L (CDR L-AUX)) (N 0 (1+ N))) ((NULL L-AUX) N))) Suponiendo L-AUX no NIL, en todo ciclo se conserva invariante la suma N + longitud(L-AUX). El valor inicial de la suma es 0 + longitud(L) = longitud(L). En todo ciclo disminuye longitud(L-AUX). Cuando L-AUX es NIL, se sale del ciclo. Por tanto, la implementacin es correcta. f) La recursin de R.2.4 equivale exactamente a la iteracin dada por (DEFUN BUSCAR0-ITER (E0) (DO ((E E0 (ELEGIR-SUC E))) ((FINALP E) E))) Como en la versin recursiva, si el estado E es final, se devuelve E; en otro caso, E pasa a ser uno de sus sucesores, dado por de ELEGIR-SUC. NOTA: No siempre la recursin equivale a la iteracin: ntese que lo que en la recursin es la creacin de un nuevo entorno para E, se convierte en la iteracin en la asignacin de un nuevo valor en el mismo entorno. Ello puede tener inesperadas consecuencias si se estn creando cierres lxicos (medtese sobre el ejercicio P.5.10).
5.17
R. 5.7. Funciones multivaluadas. a) Suponiendo las siguientes definiciones (DEFUN MULTIF (X) (VALUES (/ X 2) X (* X 2))) (DEFUN NULAF (X) (VALUES)) (DEFUN MULTIF2 (X) (MULTIF X)) evaluar las siguientes expresiones: (MULTIF 4) (NULAF 4) (MULTIF2 4) (+ (MULTIF 4) (MULTIF 6)) (CONS (MULTIF 4) (VALUES NIL NIL NIL)) (MULTIPLE-VALUE-BIND (X Y Z) (VALUES 'A 'B 'C) (LIST X Y Z)) (MULTIPLE-VALUE-BIND (X Y Z) (VALUES 'A 'B) (LIST X Y Z)) (MULTIPLE-VALUE-BIND (X Y) (VALUES 'A 'B 'C) (LIST X Y)) (MULTIPLE-VALUE-CALL #'+ (VALUES 1 2 3)) b) Reimplementar las funciones QUICKSORT y DOSLISTAS de R.5.4 usando VALUES y MULTIPLEVALUE-BIND. ************************** SOLUCION: Las funciones de CommonLisp predefinidas o definidas por el usuario- no estn obligadas a devolver un solo valor. En realidad, pueden devolver cualquier nmero de valores (cero, uno o ms). Ello se consigue mediante el uso de VALUES. La funcin VALUES tiene un nmero indeterminado de argumentos, que son precisamente los valores que devuelve. Segn esto, (MULTIF 4) => 2 4 8 (NULAF 4) => (MULTIF2 4) Estos valores mltiples pueden pasar a travs de cualquier nmero de llamadas: (MULTIF2 4) => 2 4 8 Sin embargo, si una funcin espera un solo valor, slo se tendr en cuenta el primero de los devueltos por VALUES, descartndose los dems. Si no devuelve ninguno, se supone que devuelve NIL: (+ (MULTIF 4) (MULTIF 6)) => 5 (CONS (MULTIF 4) (VALUES NIL '(A) '(A B))) => (2) (CONS 'A (VALUES)) => (A) Para recoger los valores mltiples, se emplea el operador MULTIPLE-VALUE-BIND. Una forma MULTIPLE-VALUE-BIND es en parecida a un LET: (MULTIPLE-VALUE-BIND (variable*) expr-multivaluada cuerpo) Para evaluar esta expresin, se crea un entorno lxico donde cada variable est ligada ordenadamente a uno de los valores devueltos por expr-multivaluada. En este entorno se Inteligencia Artificial e I.C.. 2002/2003 5.18 Dpto. Leng. Ciencias Comp.
evala el cuerpo, que est formado por un nmero cualquiera de expresiones. MULTIPLEVALUE-BIND devuelve el valor de la ltima. Si el nmero de variables es mayor que el de valores devueltos por expr-multivaluada, se completan con NIL. Si el nmero de valores es mayor que el de variables, se desprecian los que sobren. Segn esto, (MULTIPLE-VALUE-BIND (X Y Z) (VALUES 'A 'B 'C) (LIST X Y Z)) => (A B C) (MULTIPLE-VALUE-BIND (X Y Z) (VALUES 'A 'B) (LIST X Y Z)) => (A B NIL) (MULTIPLE-VALUE-BIND (X Y) (VALUES 'A 'B 'C) (LIST X Y)) => (A B) La forma MULTIPLE-VALUE-CALL permite pasar mltiples valores a una funcin que espera un nmero indeterminado de ellos: (MULTIPLE-VALUE-CALL #'+ (VALUES 1 2 3)) => 6 b) Recordemos que en la implementacin de R.5.4 y R.5.5. la funcin DOSLISTAS devolva una lista de dos elementos AC-CHICOS y AC-GRANDES, que la funcin principal QUICKSORT haba inmediatamente de separar. Para evitar este desperdicio de espacio y tiempo, los programadores Lisp inventaron el procedimiento ejemplificado en este ejercicio: DOSLISTAS, empleando VALUES, devolver dos valores "sueltos", que no forman una lista; y QUICKSORT los recoger en un entorno mediante MULTIPLE-VALUE-BIND. Es decir (DEFUN QUICKSORT (L &OPTIONAL (P #'<)) (LABELS ((DOSLISTAS (PIVOTE RESTO P &OPTIONAL AC-CHICOS AC-GRANDES) (COND ((NULL RESTO) (VALUES AC-CHICOS AC-GRANDES)) ((FUNCALL P (CAR RESTO) PIVOTE) (DOSLISTAS PIVOTE (CDR RESTO) P (CONS (CAR RESTO) AC-CHICOS) AC-GRANDES)) (T (DOSLISTAS PIVOTE (CDR RESTO) P AC-CHICOS (CONS (CAR RESTO) AC-GRANDES)))))) (IF (NULL L) NIL (MULTIPLE-VALUE-BIND (CHICOS GRANDES) (DOSLISTAS (CAR L) (CDR L) P) (APPEND (QUICKSORT CHICOS P) (CONS (CAR L) (QUICKSORT GRANDES P)))))))
5.19
R.6.1. E/S de supervivencia. a) Escribir una funcin sin argumentos que devuelva la suma de dos nmeros ledos del teclado. b) Escribir una funcin sin argumentos que devuelva NIL y como efecto lateral escriba en la pantalla: i) dos mensajes solicitando cada uno que se teclee un nmero y ii) el resultado de su suma. c) Escribir una funcin EVALQUOTE que modifique la interaccin con LISP de la siguiente forma: - el aviso (prompt) del intrprete debe ser EVALQUOTE> -si el usuario teclea >EVAL, se vuelve al modo habitual -en otro caso, el usuario debe teclear un nombre de funcin (en sentido estricto, es decir, no valen formas especiales ni macros) y la lista de sus argumentos sin comillas. Por ejemplo > EVALQUOTE EVALQUOTE> CONS(A (B)) (A B) EVALQUOTE> EVAL > ************************** SOLUCION: a) READ es una funcin que tiene el siguiente significado funcional predefinido: (READ) -ningn argumento (de momento). -el valor devuelto se toma de la corriente de entrada por defecto. Por ahora, podemos suponer que se toma del teclado. Segn esto, la solucion ser (DEFUN KK1 () (+ (READ) (READ))) b) PRIN1 es una funcin que tiene el siguiente significado funcional predefinido: (PRIN1 expresin) -un nico argumento. -el valor devuelto es del argumento. -como efecto lateral, el valor es enviado a la corriente de salida por defecto. Por ahora podemos suponer que el valor se escribe en la pantalla. (TERPRI) escribe una lnea en blanco. (PRINT expresin) es como PRIN1, con la siguiente diferencia: -como efecto lateral, el valor es enviado a la corriente de salida por defecto, precedido por un salto de lnea y seguido por un espacio. Por el ap. anterior, sabemos que (+ (READ) (READ)) calcula la suma de dos nmeros ledos del teclado. Para escribirla tendremos que hacer (PRINT (+ (READ) (READ))) Sin embargo, de esta forma no consegimos escribir los mensajes que piden los datos. Para ello hay que aadir para cada READ un PRINT que lo abrace: (PRINT (+ (CADR (LIST (PRINT '(DAME UN NUMERO)) (READ))) (CADR (LIST (PRINT '(DAME UN NUMERO)) (READ))))) y finalmente (DEFUN KK2 () (PRINT (+ (CADR (LIST (PRINT '(DAME UN NUMERO)) (READ))) (CADR (LIST (PRINT '(DAME UN NUMERO)) (READ))))) NIL) NOTA: El intrprete escribe siempre en la pantalla el valor de la expresin que se le teclea. Por tanto, si la anterior expresin se teclea directamente al intrprete, el resultado aparecer dos veces en la pantalla: una, por el funcionamiento normal del intrprete; otra, como efecto lateral de su evaluacin.
6.3
NOTA: [Ch] afirman (p. 29): "LISP tiene varias funciones, como PRINT o MAPC, que existen solamente por sus efectos laterales. No es en absoluto una buena idea depender de sus valores". Sin embargo, el valor de PRINT est perfectamente especificado en la definicin de Common Lisp, y el empleo de este valor no debe ocasionar problemas.
c) Una definicin recursiva por la cola: (DEFUN EVALQUOTE () (PRINT 'EVALQUOTE>) (LET ((F (READ))) (COND ((EQ F '>EVAL) NIL) ( T (PRINT (APPLY F (READ))) (EVALQUOTE)))))
;escribir nueva lnea y el aviso ;leer la funcion f ;si es >EVAL, acabar, si no ;leer lista, aplicar f, ;escribir nueva lnea y f(lista) ;y seguir en evalquote
NOTA. El funcionamiento normal del intrprete puede describirse como un bucle READ-EVALPRINT: se lee una expresin con READ, se evala con EVAL y se escribe el resultado con PRINT. El ejercicio anterior muestra cun fcilmente se puede simular o modificar este bucle.
6.4
R.6.2. Caracteres y cadenas. a) Evaluar las siguientes expresiones: #\A #\Space (CHARACTER 41) (EQ #\A #\a) (EQ #\A #\A) (EQL #\A #\A) (CHAR= #\A #\A) (CHAR= #\SPACE (CHARACTER 32)) (CHAR-EQUAL #\A #\a) b) Evaluar las siguientes expresiones: "Hoy es jueves" (EQUAL #\A "A") (EQL "AB" "AB") (EQUAL "AB" "AB") (EQUAL (STRING 'A) (STRING #\A)) (EQ (INTERN "ABC") 'ABC) (ELT (STRING 'PEPE) 1) (LENGTH (STRING 'PEPE)) (CONCATENATE 'STRING "ABC" "XYZ") (EQUAL "PEPE" "PEPE") (STRING= "PEPE" "pepe") (STRING-EQUAL "PEPE" "pepe") c) Indicar qu se imprime al introducir sucesivamente las siguientes expresiones: (PRINC #\k) (PRINC "pEPE") (PRINC "C:\\PEPE") (PRINC "PEPE\"") (PRIN1 "PEPE") (DEFUN MI-PRINC (S) (TERPRI) (PRINC S)) (MI-PRINC "PEPE") ************************** SOLUCION: a) Adems de nmeros, smbolos, funciones y listas, CommonLisp tiene predefinidos otros tipos de datos: por ejemplo, los caracteres (character). Los caracteres son tomos y se evalan a s mismos. Para indicar que algo es un carcter, el usuario (y PRINT) lo escribe precedido de #\. La funcin (CHARACTER n) devuelve el carcter designado por n (la forma concreta de designacin depende de la implementacin; por ejemplo, n puede ser el cdigo ASCII del carcter). Por tanto #\A =>#\A #\Space =>#\Space (CHARACTER 41) => #\) No es obligado que distintas apariciones de un mismo carcter sean EQ, pero s que sean EQL. Las funciones especializadas CHAR= y CHAR-EQUAL sirven para comparar nicamente caracteres. CHAREQUAL no distingue entre maysculas y minsculas. Por supuesto, un smbolo cuyo nombre conste de un solo carcter no es lo mismo que un carcter. Por tanto (EQ #\A #\a) => NIL (EQ #\A #\A) => ...depende de la implementacin... (EQL #\A #\A) => T (CHAR= #\A #\A) => T (CHAR= #\SPACE (CHARACTER 32)) => T (CHAR-EQUAL #\A #\a) => T b) El tipo cadena (string) est tambin predefinido. Las cadenas son tomos y se evalan a s mismas. Una cadena de un solo carcter no es lo mismo que un carcter. Para indicar que algo es una cadena, el usuario (y PRINT) lo escribe entre comillas dobles. La funcin STRING transforma caracteres y smbolos en cadenas. La funcin INTERN transforma cadenas en smbolos. Por tanto
6.5
"Hoy es jueves" => "Hoy es jueves" (EQUAL #\A "A") => NIL (EQL "AB" "AB") => NIL (EQUAL "AB" "AB") => T (EQUAL (STRING 'A) (STRING #\A)) => T (EQ (INTERN "ABC") 'ABC) => T La funcin (ELT cadena n) extrae el n-simo carcter de cadena (el primero es el 0-simo). (ELT (STRING 'PEPE) 1) => #\E La funcin LENGTH da la longitud de una cadena: (LENGTH (STRING 'PEPE)) => 4 Ntese que la misma funcin LENGTH sirve para listas y de cadenas. De la misma forma, ELT puede emplearse tambin para extraer el ensimo elemento de una lista. La razn es que estas funciones, y otras muchas, estn definidas para el tipo sucesin (sequence), que comprende listas, cadenas y vectores. La funcin CONCATENATE, por ejemplo, sirve para APPENDar tato listas como cadenas. Su primer argumento es un smbolo que indica el tipo del resultado. Por tanto (CONCATENATE 'STRING "ABC" "XYZ") => "ABCXYZ" y tambin tendramos (CONCATENATE 'LIST '(A B C) '(D C)) => (A B C D C) (CONCATENATE 'LIST "ABC" "XYZ") => (#\A #\B #\C #\X #\Y #\Z) No es obligado que distintas apariciones de una misma cadena sean EQL, pero s que sean EQUAL. Las funciones especializadas STRING= y STRING-EQUAL sirven para comparar nicamente cadenas, anlogamente a CHAR= y CHAR-EQUAL. Por tanto (EQUAL "PEPE" "PEPE") => T (STRING= "PEPE" "pepe") => NIL (STRING-EQUAL "PEPE" "pepe") => T c) La funcin PRINC es anloga a PRIN1, con la diferencia de que escribe sin delimitadores cadenas y caracteres: > (PRINC #\k)k #\k > (PRINC "pEPE")pEPE "pEPE" > (PRIN1 "PEPE")"PEPE" "PEPE" El carcter \ sirve como carcter de escape dentro de una cadena, para indicar que el siguiente carcter debe tomarse literalmente. Su empleo es necesario si se desea que " o \ formen parte de la cadena: > (PRINC "C:\\PEPE")C:\PEPE "C:\\PEPE" > (PRINC "PEPE\"")PEPE" "PEPE\"" > (DEFUN MI-PRINC (S) (TERPRI) (PRINC S)) MI-PRINC > (MI-PRINC "PEPE") PEPE "PEPE" . NOTA: La diferencia entre PRIN1 y PRINC puede resumirse como sigue: PRIN1 escribe su argumento respetando las convenciones exigidas por READ; PRINC escribe su argumento de forma que un ser humano lo lea cmodamente.
6.6
R.6.3. FORMAT Escribir una funcin KK1 que lleve a cabo la siguiente tarea: solicitar al usuario que introduzca una expresin numrica y escribir en distintos renglones los valores de su cubo y su cuadrado, con los correspondientes mensajes, en formato decimal y con dos decimales. En caso de introducir un dato no numrico se dar al usuario un mensaje adecuado y se le solicitar de nuevo un valor. La funcin devuelve siempre T. Por ejemplo: Dime una expresin: PEPE PEPE no es un nmero, lo siento. Dime una expresin: 2E-1 El cuadrado es 0.04 y el cubo es 0.00. Adis. T ************************** SOLUCION: Para conseguir salidas formateadas se emplea la funcin FORMAT: (FORMAT destino cadena-control expresin*) donde destino es la corriente de salida. Si es T, se toma la corriente de salida por defecto (normalmente, la pantalla); si es NIL, se crea una cadena que contiene la salida. expresin* es una sucesin de expresiones, que se evalan secuencialmente para obtener valor1, ..., valorn. cadena-control es una cadena. Si destino es NIL, FORMAT devuelve la cadena descrita ms adelante. En otro caso, FORMAT se evala a NIL y como efecto lateral escribe en destino los valores valor1, ..., valorn, formateados de acuerdo a las instrucciones de la cadena de control. Concretamente: -La cadena de control se escribe literalmente en la corriente de salida, a excepcin de los caracteres precedidos por ~, que se denominan directivas de formateo. -La directiva ~S hace que en su lugar se escriba (como con PRIN1) uno de los valores valor1, ..., valorn. La directiva ~A hace que en su lugar se escriba (como con PRINC) uno de los valores valor1, ..., valorn. El valor es determinado secuencialmente (el primer valor con el primer ~S o ~A, ...). Si hay ms directivas que valores, se produce un error. Si hay ms valores que directivas, no se produce por ello error: simplemente, los ltimos valores no se escriben. -La directiva ~% escribe un salto de lnea. -La directiva ~<nueva lnea> ignora la <nueva lnea> y los blancos que la sigan. Por ejemplo >(FORMAT T "~%Hoy es ~S de ~S de ~S." 12 "enero" 1492) Hoy es 12 de "enero" de 1492. NIL >(FORMAT T "~%Hoy es ~S de ~A de ~S." 12 "enero" 1492) Hoy es 12 de enero de 1492. NIL >(FORMAT NIL "~%Hoy es ~S de ~A de ~S." 12 "enero" 1492) " Hoy es 12 de enero de 1492." -La directiva ~n,mF escribe un nmero en formato decimal, como mnimo con un total de n caracteres, empleando m decimales. Por ejemplo >(FORMAT T "~% Un nmero:~10,3F.~% El mismo nmero:~5,2F.~% Y otra vez ~ el mismo nmero:~2,0F." 123.1 123.1 123.1) Un nmero: 123.100. El mismo nmero:123.10. Y otra vez el mismo nmero:123.. NIL Segn esto (DEFUN MENSAJE (CADENA)
6.7
(PRINC CADENA) (READ)) (DEFUN KK1 () (LET ((S (MENSAJE "Dime una expresion: "))) (COND((NUMBERP S) (FORMAT T "~%El cuadrado es ~6,2F y el cubo es ~6,2F~ .~%Adios." (* S S) (* S S S)) T) (T (FORMAT T "~%~S no es un numero, lo siento." S) (KK1))))) NOTA: (FORMAT T ...) devuelve NIL. Para respetar la definicin especificada de KK1, es necesario por tanto introducir explcitamente T como valor del COND. Comprese con PRIN1 o PRINT, que devuelven el valor de su argumento. NOTA. La definicin completa de FORMAT ocupa 29 pginas de CLtL2 (581-609), y otras tantas del estndar ANSI. El alumno interesado puede consultar all todas las posibilidades de formateo (numrico, alfanumrico, condicional, mediante funciones, ...) que FORMAT proporciona.
6.8
R.6.4. Secuenciacin. Evaluar las siguientes expresiones: (PROGN (+ 1 2 3) (CAR '(A B))) (PROG1 (+ 1 2 3) (CAR '(A B))) (LOOP (+ 1 2 3) (CAR '(A B))) (LOOP (PRINT 'DIGA?) (WHEN (EQ (READ) 'FIN) (RETURN)) (PRINT 'OIDO)) (LOOP (PRINT 'DIGA?) (WHEN (EQ (READ) 'FIN) (RETURN T)) (PRINT 'OIDO)) (BLOCK PEPE (+ 1 2 3) (CAR '(A B))) (BLOCK PEPE (PRINT 'DIGA?) (WHEN (EQ (READ) 'FIN) (RETURN-FROM PEPE)) ESTO ES BASURA) (BLOCK PEPE (BLOCK JUAN (PRINT 'DIGA?) (IF (EQ (READ) 'PEPE) (RETURN-FROM PEPE 'ADIOS) (RETURN-FROM JUAN 'JA))) ESTO ES BASURA) ************************** SOLUCION: La secuenciacin es la forma bsica en que fluye la ejecucin de los programas imperativos. Sin embargo, en los programas funcionales la secuenciacin tiene una importancia ms reducida. De hecho, hasta ahora no la hemos mencionado explcitamente. Sin embargo, al programar mediante "efectos laterales" (entrada/salida, asignacin), es inevitable el uso de la secuenciacin. Los operadores ms sencillos son PROGN y PROG1, que evalan secuencialmente las expresiones de su cuerpo y devuelven el ltimo valor o el primero, respectivamente: (PROGN (+ 1 2 3) (CAR '(A B))) => A (PROG1 (+ 1 2 3) (CAR '(A B))) => 6 NOTA. Muchas de las construcciones ya estudiadas (DEFUN, COND, ...) ejecutan siempre secuencialmente las expresiones de su cuerpo. Pero ntese que en IF y en las inicializaciones y actualizaciones de LET y DO es necesario para ello un PROGN explcito. El operador LOOP evala secuencialmente las expresiones de su cuerpo, una y otra vez; en principio, no devuelve ningn valor: (LOOP (+ 1 2 3) (CAR '(A B))) => ...computacin infinita... Sin embargo, si dentro del cuerpo se evala una forma (RETURN), finaliza el clculo y LOOP devuelve NIL. El mbito desde el cual se puede RETURNar se determina lxicamente. (LOOP (PRINT 'DIGA?) (WHEN (EQ (READ) 'FIN) (RETURN)) (PRINT 'OIDO)) => DIGA? HOLA OIDO DIGA? FIN
6.9
NIL Si se evala (RETURN e), se devuelve el valor de e: (LOOP (PRINT 'DIGA?) (WHEN (EQ (READ) 'FIN) (RETURN T)) (PRINT 'OIDO)) => DIGA? HOLA OIDO DIGA? FIN T El operador ms general que establece la posibilidad de RETURNar es BLOCK, que se emplea en formas como (BLOCK nombre expresin*) nombre es un smbolo que no se evala. Las restantes expresiones se evalan secuencialmente y BLOCK devuelve el valor de la ltima. Pero si alguna de ellas es de una forma (RETURN-FROM nombre resultado) el valor de resultado pasa a ser el de la forma BLOCK y las restantes expresiones quedan sin evaluar. (BLOCK PEPE (+ 1 2 3) (CAR '(A B))) => A (BLOCK PEPE (PRINT 'DIGA?) (WHEN (EQ (READ) 'FIN) (RETURN-FROM PEPE)) ESTO ES BASURA) => DIGA? FIN NIL Los bloques pueden anidarse. En los anidamientos se siguen las reglas de mbito lxico. (BLOCK PEPE (BLOCK JUAN (PRINT 'DIGA?) (IF (EQ (READ) 'PEPE) (RETURN-FROM PEPE 'ADIOS) (RETURN-FROM JUAN 'JA))) ESTO ES BASURA) => DIGA? PEPE ADIOS (BLOCK PEPE (BLOCK JUAN (PRINT 'DIGA?) (IF (EQ (READ) 'PEPE) (RETURN-FROM PEPE 'ADIOS) (RETURN-FROM JUAN 'JA))) ESTO ES BASURA) => DIGA? NO-PEPE Error: ESTO sin ligar. NOTA. DEFUN establece implcitamente un bloque con el nombre de la funcin. LOOP, DO y sus variantes establecen implcitamente un bloque con el nombre NIL. En lugar de RETURN-FROM NIL se puede escribir simplemente RETURN
6.10
R.6.5. Manejo elemental de archivos. Sea un sistema bajo MS-DOS. En un fichero llamado KK.DAT, situado en el directorio C:\DBVARIOS, se almacenan las lecturas de un sensor, tomadas cada hora. El primer dato del archivo es la fecha (formato dd-mm-aa), el segundo la hora de la primera lectura y el tercero los minutos de la primera lectura. a) Evaluar las siguientes expesiones, indicando los efectos laterales: (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) 1 2 3 F1) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (READ F1)(READ F1)) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\QQ.DAT" :DIRECTION :OUTPUT) (PRIN1 'PEPE F1) (PRIN1 2 F1)) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (LOOP (READ F1))) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (LOOP (READ F1 NIL))) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (LOOP (UNLESS (READ F1 NIL) (RETURN NIL)))) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) EE) b) Escribir una funcin LISP LEE1 que lea el archivo y escriba en pantalla una tabla como la siguiente: Datos del da 17-2-96 HORA LECTURA ==== ======= 00:20 123.14 01:20 0.00 02:20 23.01 ... c) Escribir una funcin LISP LEE2 que lea el archivo y escriba una tabla como la anterior en un fichero KK.TXT. ************************** SOLUCION: En CommonLisp, una fuente o sumidero de datos se denomina corriente (stream). Una corriente es un objeto Lisp, y por tanto puede ser el valor de la ligadura de un smbolo. Por otra parte, una corriente debe corresponder a un objeto del mundo exterior, de donde se toman los datos o a donde se envan. Las funciones de E/S ya vistas (READ, PRINT, ...) pueden operar sobre cualquier corriente. Para ello la corriente se introduce como argumento adicional: (READ expresin-c) (PRIN1 expresin expresin-c) (PRINC expresin expresin-c) (PRINT expresin expresin-c) En cuanto a FORMAT, ya hemos dicho que su primer argumento puede ser, adems de T o NIL, cualquier corriente: (FORMAT expresin-c cadena-control expresin*) En todos estos casos, expresin-c debe evaluarse a una corriente. Una corriente puede ser binaria o de caracteres; puede usarse para slo lectura, slo escritura o ambas operaciones a la vez; y puede estar abierta (accesible como fuente o sumidero de datos) o cerrada (inaccesibe). La manera ms sencilla y recomendable de crear corrientes para comunicarse con ficheros, y adems ligarlas a smbolos, es emplear la forma WITH-OPEN-FILE: (WITH-OPEN-FILE (smbolo expr-fichero opcin*)expr*) donde expr-fichero es una expresin que debe evaluarse a un nombre de fichero valido segn las convenciones del sistema operativo subyacente. La evaluacin de WITH-OPEN-FILE crea primeramente una corriente ligada a este fichero, que queda ligada a smbolo en todo el mbito de la evaluacin. Esta corriente se abre de la forma sealada por opcin*. De esta forma se evalan las expresiones siguientes. Finalmente se cierra la corriente. El valor devuelto por WITH-OPEN-FILE es el de la ltima expresin. El archivo siempre queda cerrado, aun cuando la evaluacin de WITH-OPENFILE haya terminado prematuramente.
6.11
La corriente se describe mediante los siguientes parmetros clave: :DIRECTION. Puede ser :INPUT, :OUTPUT, :IO. Por defecto es :INPUT :ELEMENT-TYPE. Puede ser CHARACTER, BIT, SIGNED-BYTE, UNSIGNED-BYTE... Por defecto es CHARACTER (en realidad, un subtipo de CHARACTER). Por tanto a) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) 1 2 3 F1) => #<closed-file-stream C:\DBVARIOS\KK.DAT #xE2F5D0> (Se ha creado una corriente para lectura de caracteres asociada al archivo C:\DBVARIOS\KK.DAT, se ha abierto y se ha cerrado). (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (READ F1)(READ F1)) => 0 (Se ha creado una corriente para lectura de caracteres asociada al archivo C:\DBVARIOS\KK.DAT y se ha abierto. El primer READ ha ledo el primer dato del archivo -la fecha- y el segundo, el segundo dato -la hora de la primera lectura, que es 0- Finalmente, el archivo se ha cerrado). (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\QQ.DAT" :DIRECTION :OUTPUT) (PRIN1 'PEPE F1) (PRIN1 2 F1)) =>2 (Se ha creado una corriente para escritura de caracteres asociada al archivo C:\DBVARIOS\QQ.DAT y se ha abierto. El primer PRIN1 ha escrito PEPE y el segundo, 2. Finalmente, el archivo se ha cerrado. Ntese que PRIN1 no aade blancos ni saltos de lnea, por lo que el contenido del archivo es ahora PEPE2). Los siguiente ejemplos hacen uso del operador LOOP. En el caso ms sencillo, (LOOP cuerpo) evala una y otra vez las expresiones que forman cuerpo. Por tanto (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (LOOP (READ F1))) => Error: intento de leer ms all del fin del fichero. (Se ha creado una corriente para lectura de caracteres asociada al archivo C:\DBVARIOS\KK.DAT y se ha abierto. Se han ejecutado los READ hasta llegar al fin del fichero, donde se ha producido un error). El error anterior se puede evitar, aadiendo ms argumentos a READ: (READ expresin-c error-eof-p [valor-eof]) Si error-eof-p es falso, no se produce el error de fin de fichero, sino que READ devuelve valoreof (valor por defecto, NIL) cuando intenta ir ms all. Por tanto: (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (LOOP (READ F1 NIL))) ... (bucle infinito: no se produce error y READ se evala a NIL una vez alcanzado el fin del fichero) (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (LOOP (UNLESS (READ F1 NIL) (RETURN NIL)))) => NIL (DEFUN F (N) (+ N EE)) => F (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (F 1)) => Error: EE sin ligar. Tanto en este caso como en alguno de los anteriores, se ha producido un error de ejecucin mientras se estaba leyendo o escribiendo un fichero. En general, esto puede tener consecuencias fatales para la informacin contenida en l; sin embargo, la forma WITH-OPEN-FILE se asegura de que el fichero no se perjudique. Sea cual sea el error que haga abortar la evaluacin de una forma WITH-OPENFILE, el sistema garantiza que el fichero queda cerrado. An ms: el fichero queda cerrado independientemente de que el error se haya producido en un entorno como el del ltimo ejemplodonde lxicamente no estaba vigente la ligadura que lo seala.
6.12
NOTA. Este efecto puede programarse explcitamente con una forma UNWIND-PROTECT. b) Hay que abrir para lectura de caracteres el fichero C:\DBVARIOS\KK.DAT. Primero se lee la fecha, hora y minutos iniciales. A continuacin se leen los datos del sensor. Como no sabemos cuntos hay, leemos con (READ NIL 'EOF) para evitar el error de fin de fichero: (DEFUN LEE1 () (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (LET ((FECHA (READ F1)) (HORA (READ F1)) (M (READ F1))) (FORMAT T "~%Datos del da ~A" FECHA) (FORMAT T "~%HORA LECTURA") (FORMAT T "~%==== =======") (DO ((L (READ F1 NIL 'EOF)(READ F1 NIL 'EOF)) (H HORA (1+ H))) ((EQ L 'EOF) NIL) (FORMAT T "~%~2,D:~2,D ~6,2F" H M L))))) c) Al programa anterior hay que aadirle la creacin de una corriente de salida. Ntese que pueden crearse cuantas corrientes sea necesario, as como tenerlas simultneamente abiertas. Ntese tambin que FORMAT escribe en el fichero exactamente lo que escribira en la pantalla si el primer argumento fuera T. (DEFUN LEE2 () (WITH-OPEN-FILE (F1 "C:\\DBVARIOS\\KK.DAT" :DIRECTION :INPUT) (WITH-OPEN-FILE (FS "C:\\DBVARIOS\\KK.TXT" :DIRECTION :OUTPUT) (LET* ((FECHA (READ F1)) (HORA (READ F1)) (M (READ F1))) (FORMAT FS "~%Datos del da ~A" FECHA) (FORMAT FS "~%HORA LECTURA") (FORMAT FS "~%==== =======") (DO ((L (READ F1 NIL 'EOF)(READ F1 NIL 'EOF)) (H HORA (1+ H))) ((EQ L 'EOF) NIL) (FORMAT FS "~%~2,D:~2,D ~6,2F" H M L))))))
6.13
R.6.6. Lectura de lneas y caracteres. a) Escribir una funcin CODIFICAR, que tenga como argumentos dos nombres de fichero ENTRADA y SALIDA y produzca como efecto lateral la escritura en SALIDA de los caracteres contenidos en ENTRADA codificados segn la siguiente regla: si el cdigo ASCII de c es n, su codificacin es el carcter de cdigo (n +23) mod 128. b) Escribir en LISP una funcin TFD que corresponda a un traductor finito determinista para convertir una cadena de caracteres en una lista de tokens. Se suponen los tokens "variable" y "constante" y las reglas de Prolog para definir ambos. Para separar los diversos identificadores en la entrada se admiten blancos, comas, tabuladores y saltos de lnea. La funcin debe devolver para cada par (estado, carcter de entrada) el nuevo estado y el token emitido correspondiente (NIL si no se emite ninguno). El fin de la cadena de entrada se supone sealado por el carcter "$". c) Escribir en LISP una funcin TRADUCIR que tenga como argumentos un TFD y una cadena de caracteres, y devuelva la traduccion de la cadena hasta donde haya sido posible hacerla. Adems, como valor secundario, se devolver T si la traduccin se ha podido efectuar por completo, NIL si ha acabado en fracaso. d) Escribir en LISP una funcin TRADUCIR-FICHERO-TEXTO que tenga como argumentos el cierre lxico de un TFD y dos nombres de fichero ENTRADA y SALIDA. La funcin escribir como efecto lateral la traduccion de ENTRADA en SALIDA hasta donde haya sido posible hacerla. El valor de la funcin ser T si la traduccin se ha podido efectuar por completo, NIL si ha acabado en fracaso. ************************** SOLUCION: Hemos dicho que READ lee una a una las expresiones LISP. Pero en realidad no slo lee, sino que lleva a cabo un anlisis lexicogrfico y sintctico de lo ledo, para determinar, por ejemplo, dnde acaba cada expresin. Existen otras funciones de lectura ms elementales, como por ejemplo READCHAR y READ-LINE, que s se limitan a leer de una corriente. (READ-CHAR expresin-c error-eof-p [valor-eof]) lee un carcter. La funcin devuelve precisamente ese carcter. (READ-LINE expresin-c error-eof-p [valor-eof]) lee una lnea completa, es decir, lee todos los caracteres hasta encontrar un salto de lnea. La funcin devuelve la cadena formada por todos los caracteres de la lnea (salvo el de salto). Es por ello muy til para leer del teclado. READ-LINE devuelve tambin un segundo valor: "verdadero", si la lnea acaba con el carcter de fin de fichero, "falso" en otro caso. Por tanto a) La funcin que realiza la codificacin de un carcter es (LAMBDA (C) (CHARACTER (MOD (+ (CHAR-CODE C) 23) 128))) Leeremos de ENTRADA carcter a carcter, realizaremos la transformacin y escribiremos en SALIDA carcter a carcter: (DEFUN CODIFICAR (&KEY ENTRADA SALIDA) (FLET ((DESPLAZAR (C) (CHARACTER (MOD (+ (CHAR-CODE C) 23) 128)))) (WITH-OPEN-FILE (CE ENTRADA :DIRECTION :INPUT) (WITH-OPEN-FILE (CS SALIDA :DIRECTION :OUTPUT) (LOOP (LET ((C (READ-CHAR CE NIL :EOF))) (WHEN (EQ C :EOF) (RETURN)) (PRINC (DESPLAZAR C) CS))))))) b) Un TFD queda definido por los siguientes elementos: -la tabla de transiciones. Cada transicin es una tripla o cudrupla de la forma (estado carcter-ledo nuevo-estado [smbolo-emitido]). Cuando el TFD est en estado y lee carcter-ledo pasa a nuevoestado y emite smbolo-emitido, caso de que exista. Si en la tabla no hay ninguna transicin que empiece por esta combinacin (estado carcter-ledo ...), la traduccin acaba en fracaso. Nunca hay ms de una transicin para una misma combinacin (estado carcter-ledo ...). -un conjunto de estados finales. Si al acabar de leer la cadena de entrada el TFD se halla en un estado final, la traduccin ha acabado con xito, caso contrario, en fracaso.
6.14
-un estado inicial, en el que se halla el TFD antes de leer ningn carcter. Representaremos los elementos anteriores por los siguientes datos LISP: - El segundo elemento de cada transicin ser un predicado, en lugar de un carcter. De esta forma reducimos considerablemente el tamao de la tabla. La transicin se considera aplicable a todos los caracteres que satisfacen el predicado. Segn la gramtica de Prolog, son variables las cadenas alfanumricas que comienzan por una letra mayscula o por "_". Son constantes las cadenas alfanumricas que empiezan por una letra minscula. (DEFUN SEPARADORP (C) (MEMBER C (LIST #\Newline #\Space #\Tab #\,))) (DEFUN TERMINADORP (C) (EQL C #\$)) (DEFUN TERMINAR (CAD) (CONCATENATE 'STRING CAD "$")) (DEFUN VACIAP (CADENA) (= 0 (LENGTH CADENA))) El TFD ser (todos los estados finales)
letra, dgito, _
E1
separador mayscula, _
E0
minscula letra, dgito, _
E2
Para considerar la terminacin de la cadena, aadimos un estado T al que se llega al leer "$" en un estado final:
letra, dgito, _
E1
separador mayscula, _ $
E0
minscula $ letra, dgito, _
E2
En Lisp
6.15
(DEFUN TFD1 (ESTADO C-LEIDO) (CASE ESTADO (E0 (COND ((TERMINADORP C-LEIDO) (VALUES T NIL)) ((FUNCALL #'UPPER-CASE-P C-LEIDO) (VALUES 'E1 NIL)) ((FUNCALL #'LOWER-CASE-P C-LEIDO) (VALUES 'E2 NIL)) ((FUNCALL #'(LAMBDA (C) (EQL C #\_)) C-LEIDO) (VALUES 'E1 NIL)) ((FUNCALL #'SEPARADORP C-LEIDO) (VALUES 'E0 NIL)))) (E1 (COND ((TERMINADORP C-LEIDO) (VALUES T 'VAR)) ((FUNCALL #'ALPHA-CHAR-P C-LEIDO) (VALUES 'E1 NIL)) ((FUNCALL #'(LAMBDA (C) (EQL C #\_)) C-LEIDO) (VALUES 'E1 NIL)) ((FUNCALL #'DIGIT-CHAR-P C-LEIDO) (VALUES 'E1 NIL)) ((FUNCALL #'SEPARADORP C-LEIDO) (VALUES 'E0 'VAR)))) (E2 (COND ((TERMINADORP C-LEIDO) (VALUES T 'CTE)) ((FUNCALL #'ALPHA-CHAR-P C-LEIDO) (VALUES 'E2 NIL)) ((FUNCALL #'(LAMBDA (C) (EQL C #\_)) C-LEIDO) (VALUES 'E2 NIL)) ((FUNCALL #'DIGIT-CHAR-P C-LEIDO) (VALUES 'E2 NIL)) ((FUNCALL #'SEPARADORP C-LEIDO) (VALUES 'E0 'CTE))))))
c) La funcin emplear por acumuladores, uno para la salida y otro para el estado en que se encuentra el traductor. Por otra parte, la entrada se completa en un primer paso con el carcter terminador: (DEFUN TRADUCIR (TFD ENTRADA &OPTIONAL SALIDA (ESTADO 'E0)) (LABELS ((TTRAD (TFD ENTRADA SALIDA ESTADO) (COND ((VACIAP ENTRADA) (VALUES (REVERSE SALIDA) ESTADO)) (T (MULTIPLE-VALUE-BIND (NUEVO-E NUEVA-SAL) (FUNCALL TFD ESTADO (ELT ENTRADA 0)) (COND ((NOT NUEVO-E) (VALUES (REVERSE SALIDA) NIL)) ((NOT NUEVA-SAL) (TTRAD TFD (SUBSEQ ENTRADA 1) SALIDA NUEVO-E)) (T (TTRAD TFD (SUBSEQ ENTRADA 1) (CONS NUEVA-SAL SALIDA) NUEVO-E)))))))) (LET ((ENTRADA (TERMINAR ENTRADA))) (TTRAD TFD ENTRADA SALIDA ESTADO))))
d) No hay ms que llamar sucesivamente a TRADUCIR con las diversas lneas de ENTRADA, escribiendo al tiempo las traducciones en SALIDA. (DEFUN TRADUCIR-FICHERO-TEXTO (&KEY TRADUCTOR ENTRADA SALIDA) (WITH-OPEN-FILE (CORR1 ENTRADA :DIRECTION :INPUT) (WITH-OPEN-FILE (CORR2 SALIDA :DIRECTION :OUTPUT) (LOOP (LET ((LINEA (READ-LINE CORR1 NIL :EOF))) (WHEN (EQ LINEA :EOF) (RETURN T)) (MULTIPLE-VALUE-BIND (TRADUCC EXITO) (TRADUCIR TRADUCTOR LINEA) (WHEN (NOT EXITO) (RETURN)) (PRINT TRADUCC CORR2)))))))
6.16
R.6.7. Caracteres Macro. a) Evaluar en el orden dado las siguientes expresiones: (SET-MACRO-CHARACTER #\? #'(LAMBDA (CORRIENTE CARACTER) (LIST 'A 'B 'C)))) '(? (?)) (SET-MACRO-CHARACTER #\? #'(LAMBDA () (LIST 'A 'B 'C)))) '(? (?)) b) Queremos representar en un programa frmulas de la lgica de primer orden. Para ello las variables lgicas sern listas de la forma (VAR X), cuyo CAR es el smbolo VAR y cuyo CADR es el nombre X de la variable. Modificar el significado de READ de manera que ?expresin se lea como (VAR expresin). ************************** SOLUCION: Un carcter macro es un carcter tal que READ lo trata de manera especial cuando lo encuentra, expandindolo en un conjunto de caracteres. Ya conocemos un carcter macro predefinido, el apstrofo: cuando READ (bien en el ciclo normal del intrprete, bien en una llamada explcita) encuentra 'expresin, lo transforma inmediatamente en (QUOTE expresin). Es posible definir nuevos caracteres macro mediante la funcin SET-MACRO-CHARACTER: (SET-MACRO-CHARACTER carcter funcin) donde carcter es el caracter macro que se define y funcin es la funcin de expansin, que que determina lo que debe sustituir al carcter macro. Esta funcin debe tener dos argumentos: una corriente y un carcter. SET-MACRO-CHARACTER devuelve T y como efecto lateral modifica el significado de READ. A partir de este momento, cuando READ encuente el carcter macro lo sustituir por el resultado de aplicar la funcin. Por tanto (SET-MACRO-CHARACTER #\? #'(LAMBDA (CORRIENTE CARACTER) (LIST 'A 'B 'C)))) => T '(? (?)) =>((A B C) ((A B C))) En este sencillo caso la funcin de expansin no emplea sus argumentos. Sin embargo, es necesario que figuren en su lista lambda: (SET-MACRO-CHARACTER #\? #'(LAMBDA () (LIST 'A 'B 'C)))) =>T '(? (?)) =>Error: nmero equivocado de argumentos. De hecho, lo ms habitual ser que la funcin de expansin contenga una llamada a (READ corriente ...). En este caso hay que aadir un cuarto argumento a READ con valor T (por qu? vd. nota). b) La funcin siguiente realiza la modificacin especificada: (DEFUN HAZ-MI-READ () (SET-MACRO-CHARACTER #\? #'(LAMBDA (CORRIENTE CARACTER) (LIST 'VAR (READ CORRIENTE T NIL T)))))
6.17
> (HAZ-MI-READ) T > '?X (VAR X) > '??X (VAR (VAR X))
NOTA: Es bastante peligroso definir como caracteres macro caracteres alfabticos o de uso comn: a partir de ese momento, cualquier aparicin de ellos se ver sustituida por su expansin. Por ejemplo, tras ejecutar la funcin HAZ-MI-READ de este ejercicio, no es posible emplear en el programa el signo de interrogacin (salvo usando caracteres de escape). NOTA: Los caracteres macro se pueden agrupar en una tabla de lectura (readtable). Pueden existir varias tablas de lectura alternativas; segn la que se cargue, READ leer de una manera o de otra. NOTA: la definicin completa de READ es (READ expresin-c error-eof-p valor-eof llamada-recursiva-p) donde todos los argumentos son opcionales. El cuarto, llamada-recursiva-p, (valor por defecto, NIL) indica si el READ se ejecuta en el nivel superior o bien proviene de la ejecucin de otro READ. Puede ser importante distinguir entre ambos casos (vd. CLtL, pg. 568-569)
6.18
R.6.8. Caracteres macro de envo. a) Evaluar en el orden dado las siguientes expresiones: (MAKE-DISPATCH-MACRO-CHARACTER #\z) (SET-DISPATCH-MACRO-CHARACTER #\z #\z #'(LAMBDA (CORRIENTE SUBCAR NUM) (LIST 'A 'B 'C))) 'zz 'za 'ZZ b) Ahora queremos escribir el cuantificador universal como $E, abreviatura de la lista (EXISTE variable) y el universal como $U, abreviatura de la lista (PARA-TODO variable). Modificar adecuadamente el significado de READ. ************************** SOLUCION: a) Un carcter macro de envo (dispatching macro character) tambin es un carcter tal que READ lo trata de manera especial cuando lo encuentra, expandindolo en un conjunto de caracteres. Pero en este caso la expansin realizada depende, no slo del carcter macro, sino tambin del siguiente carcter ledo (subcaracter). Ya conocemos un carcter macro de envo predefinido, el sostenido: cuando READ (bien en el ciclo normal del intrprete, bien en una llamada explcita) encuentra #'expresin, lo transforma inmediatamente en (FUNCTION expresin). Es posible definir nuevos caracteres macro de envo mediante las funciones MAKE-DISPATCHMACRO-CHARACTER y SET-DISPATCH-MACRO-CHARACTER: (MAKE-DISPATCH-MACRO-CHARACTER carcter) Esta funcin devuelve T y hace que carcter sea un carcter macro de envo. Pero an no establece su significado. Para ello es necesario emplear adems (SET-DISPATCH-MACRO-CHARACTER carcter subcarcter funcin) donde carcter es el caracter macro de envo, subcarcter es el subcaracter macro de envo, que se define y funcin es la funcin de expansin, que determina por lo que se debe sustituir esta cadena de dos caracteres. Esta funcin debe tener tres argumentos: una corriente y un carcter, y un nmero (vd. nota; si as lo desea, prescinda el alumno de conocer el significado de este nmero, pero es un parmetro requerido). SET-DISPATCH-MACRO-CHARACTER devuelve T y como efecto lateral modifica el significado de READ. A partir de este momento, cuando READ encuente la combinacin carcter-subcarcter la sustituir por el resultado de aplicar la funcin. Por tanto (MAKE-DISPATCH-MACRO-CHARACTER #\z) => T (SET-DISPATCH-MACRO-CHARACTER #\z #\z #'(LAMBDA (CORRIENTE SUBCAR NUM) (LIST 'A 'B 'C))) => T 'zz => (A B C) 'za => Error: combinacin ilegal z a Ntese que READ seala un error cuando encuentra una combinacin carcter-subcarcter no definida. 'ZZ => ZZ 'zZ => (A B C) Ntese que en el subcarcter no se distingue entre maysculas y minsculas, pero s en el carcter. b) Agrupemos en una sola funcin HAZ-MI-READ-2 todas las modificaciones pedidas en este ejercicio y el anterior: (DEFUN HAZ-MI-READ-2 () (SET-MACRO-CHARACTER #\? #'(LAMBDA (CORRIENTE CARACTER)
6.19
(LIST 'VAR (READ CORRIENTE T NIL T)))) (MAKE-DISPATCH-MACRO-CHARACTER #\$) (SET-DISPATCH-MACRO-CHARACTER #\$ #\E #'(LAMBDA (CORRIENTE SUBCAR NUM) (LIST 'EXISTE (READ CORRIENTE T NIL T)))) (SET-DISPATCH-MACRO-CHARACTER #\$ #\U #'(LAMBDA (CORRIENTE SUBCAR NUM) (LIST 'PARA-TODO (READ CORRIENTE T NIL T))))) y ahora >(HAZ-MI-READ) T >'$E?X (EXISTE (VAR X)) >'$U ?X (PARA-TODO (VAR X)) NOTA: la funcin de expansin de un carcter macro de envo debe tener 3 parmetros: la corriente, el subcarcter y un nmero. Este nmero puede aparecer, como un natural en notacin decimal, entre el carcter y el subcarcter. De esta forma los caracteres macros de envo tienen mayor flexibilidad. Si no hay ningn nmero, el tercer parmetro de la funcin de expansin se liga a NIL.
6.20
R.6.9. Manejo de errores (I). Implementar versiones de la funcin factorial tales que a) (FACTORIAL N) devuelva NIL cuando N no sea un nmero natural. b) (FACTORIAL N) seale un error y aborte la computacin cuando N no sea un nmero natural. c) (FACTORIAL N) seale un error y aborte la computacin cuando N no sea un nmero natural. Opcionalmente, si el argumento proporcionado es numrico, se calcular el factorial de un nmero parecido al dado: por ejemplo, el factorial de |n| si n es negativo, o de int(n) si n es fraccionario. d) (FACTORIAL N) seale un error y aborte la computacin cuando N no sea un nmero natural. Opcionalmente, se solicitar al usuario un nuevo valor y se calcular el factorial de ste. ************************** SOLUCION: a) Partamos, por ejemplo, de la implementacin recursiva ingenua: (DEFUN FACTORIAL (N) (COND ((ZEROP N) 1) (T (* N (FACTORIAL (1- N)))))) Qu ocurre cuando FACTORIAL recibe un argumento inadecuado, por ejemplo, -9.9? Nunca se alcanzar el caso base y la recursin proseguir hasta que se agota la memoria disponible. La forma ms burda de evitar esto es la especificada en este apartado: (DEFUN FACT-EXTENDIDO (S) (COND ((NOT (NUMBERP S)) (PRINT 'ERROR) NIL) ((NOT (INTEGERP S)) (PRINT 'ERROR) NIL) ((MINUSP S) (PRINT 'ERROR) NIL) (T (FACTORIAL S)))) Y ahora ser (FACT-EXTENDIDO 9.9)=> NIL escribndose adems el mensaje ERROR El lector debe ser consciente de que FACT-EXTENDIDO no implementa la funcin matemtica factorial , sino una versin extendida de ella: factorial(X), si X es un nmero natural fact-extendido(X) = NIL, en otro caso. Ello puede llevar a errores algo difciles de comprender. Por ejemplo, (* 2 (FACT-EXTENDIDO 9.9)) => Error: NIL no es un nmero. b) Por lo dicho en a), es mejor sealar explcitamente un error cuando el argumento no es adecuado. Para ello, CommonLisp proporciona la funcin ERROR: (ERROR cadena-control expresin*) Al intentar evaluar ERROR, se genera un mensaje de error formateado segn las reglas de FORMATque se enva a la corriente establecida para los mismos; se entra en el entorno de depuracin. Todas las evaluaciones pendientes quedan abortadas y es imposible continuarlas. Segn esto, la implementacin pedida en este apartado ser (DEFUN FACT-PROTEGIDO (S) (COND ((NOT (NUMBERP S)) (ERROR "~S no es un numero." S)) ((NOT (INTEGERP S)) (ERROR "~D no es entero." S)) ((MINUSP S) (ERROR "~D es negativo." S)) (T (FACTORIAL S)))) Y ahora tendremos: (FACT-PROTEGIDO 9.9) => Error: 9.9 no es entero. (* 2 (FACT-PROTEGIDO 9.9)) => Error: 9.9 no es entero.
6.21
NOTA. Es costumbre que los mensajes de error sean frases completas, acabadas con un punto. No es necesario mencionar en ellos la funcin en la que se produce el error, ya que se supone que el entorno del intrprete o compilador ser capaz de aadir automticamente esta informacin. c) Adems de los errores irrecuperables empleados en b), el programador puede definir errores continuables o recuperables. Para ello, CommonLisp proporciona la funcin CERROR: (CERROR cadena-control1 cadena-control2 expresin*) Al intentar evaluar CERROR, se genera un mensaje de error formateado segn las reglas de FORMAT aplicadas a cadena-control2 y a expresin*- que se enva a la corriente establecida para los mismos. Adems, se genera otro mensaje error formateado segn las reglas de FORMAT aplicadas a cadena-control1 y a expresin*- que informa al usuario de lo que ocurrir si la computacin no es abortada. Se entra en el entorno de depuracin y el usuario puede elegir entre abortar las evaluaciones pendientes o continuar. Si elige continuar, CERROR devuelve NIL y se contina normalmente con las evaluaciones pendientes. Segn esto, la implementacin pedida puede ser (DEFUN FACT-CERROR (S) (COND ((NOT (NUMBERP S)) (ERROR "~S no es un numero." S)) ((NOT (INTEGERP S)) (CERROR "Se calculara el factorial de INT(~D)." "~D no es entero." S) (FACT-CERROR (FLOOR S))) ((MINUSP S) (CERROR "Se calculara el factorial de |~D|." "~D es negativo." S) (FACTORIAL (- S))) (T (FACTORIAL S)))) Y ahora tendremos el siguiente dilogo (usuario en cursiva): > (FACT-CERROR 9) Error: -9 es negativo. Para continuar, teclee CONTINUE Se calcular el factorial de |-9|. CONTINUE 362880 Pero > (FACT-CERROR 9) Error: -9 es negativo. Para continuar, teclee CONTINUE Se calcular el factorial de INT(-9). ABORT > d) Lo que se pide podra implementarse mediante CERROR. Sin embargo, existe una manera ms cmoda de hacerlo, empleando una forma ASSERT. (ASSERT expresin-test [(smbolo*) [cadena-control expresin*]]) Al intentar evaluar una forma ASSERT, se realiza el siguiente proceso: 1. Se evala expresin-test. Si es verdadera, ASSERT devuelve NIL y se contina normalmente. 2. Si expresin-test es falsa, ASSERT seala un error y enva un mensaje de error indicando este hecho. 3. Si figura la lista (smbolo*), se proporciona al usuario la posibilidad de modificar el entorno vigente, asignando nuevos valores a cada uno de los smbolos de la lista. Si el usuario elige esta opcin, se volver al paso 1. 4. Si el usuario as lo elige, se abortarn las computaciones pendientes. Los argumentos cadena-control expresin* sirven para formar segn las reglas de FORMAT-el mensaje que se enva al usuario.
6.22
Por ejemplo, tras definir (DEFUN FACT-ASSERT1 (S) (ASSERT (AND (NUMBERP S) (INTEGERP S) (OR (ZEROP S) (PLUSP S)))) (FACTORIAL S)) se produce el siguiente dilogo: >(FACT-ASSERT1 -9) Error: la asercin (AND (NUMBERP S) (INTEGERP S) (OR (ZEROP S) (PLUSP S))) ha fracasado. Tras definir (DEFUN FACT-ASSERT2 (S) (ASSERT (AND (NUMBERP S) (INTEGERP S) (OR (ZEROP S) (PLUSP S))) (S)) (FACTORIAL S)) se produce el siguiente dilogo: >(FACT-ASSERT2 -9) Error: la asercin (AND (NUMBERP S) (INTEGERP S) (OR (ZEROP S) (PLUSP S))) ha fracasado. Teclee otra expresin para S: 9 362880 o bien >(FACT-ASSERT2 -9) Teclee otra expresin para S: ABORT Y tras definir (DEFUN FACT-ASSERT3 (S) (ASSERT (AND (NUMBERP S) (INTEGERP S) (OR (ZEROP S) (PLUSP S))) (S) "Lo siento, ~S no es un argumento valido para factorial." S) (FACTORIAL S)) El dilogo es >(FACT-ASSERT3 -9) Lo siento, -9 no es un argumento valido para factorial. Teclee otra expresin para S: 9 362880 NOTA. Es obvio que la forma concreta del dilogo entre sistema y usuario depende de la implementacin del intrprete o compilador.
6.23
R.6.10. Manejo de errores (II). a) Implementar una versin de EVALQUOTE (vd. R.6.1.c) que nunca seale error. b) Implementar una versin de EVALQUOTE que nunca seale error, y adems nunca salga del ciclo EVALQUOTE a causa de un error. c) Implementar una versin de EVALQUOTE que nunca seale error, y adems salga del ciclo EVALQUOTE solamente a causa de los errores aritmticos. ************************** SOLUCION. En R.6.9 hemos aprendido a definir errores. En este ejercicio aprenderemos a programar el manejo de errores, tanto predefinidos como definidos por el programa. a) La siguiente forma CommonLisp nos permite realizar esto de una manera sencilla: (IGNORE-ERRORS expresin*) IGNORE-ERRORS evala sus expresiones secuencialmente y si no se producen errores devuelve el valor de la ltima. Por el contrario, si durante la evaluacin se seala un error, IGNORE-ERRORS devuelve de manera inmediata NIL (y adems el objeto error) y vuelve al nivel superior de interaccin, sin entrar en el entorno de depuracin. Ntese que el mbito de IGNORE-ERRORS es dinmico, no lxico, es decir, los errores despreciados son aquellos que se producen durante la ejecucin de expresin* o de cualquier otra expresin que se haya llamado desde ellas. Segn esto, la funcin pedida ser (DEFUN EEVALQUOTE0 () (IGNORE-ERRORS (PRINT 'EVALQUOTE>) (LET ((F (READ))) (COND ((EQ F 'EVAL>) NIL) (T (PRIN1 (APPLY F (READ))) (EEVALQUOTE0)))))) y ahora tendremos el siguiente dilogo: > (EEVALQUOTE0) EVALQUOTE> / (2 0) NIL #<SIMPLE-ERROR @ #xE204F4> > b) CommonLisp permite manejar los errores de forma flexible. Para ello proporciona los siguientes recursos: -los errores son objetos Lisp (ms concretamente, objetos CLOS de tipo condicin). -existe una jerarqua predefinida de errores. -se puede programar explcitamente el manejador de cualquier clase de error, es decir, se pueden indicar las formas que se evaluarn cuando se seale un error de esa clase. Para esto ltimo se emplea la forma HANDLER-CASE, que en su formato ms sencillo es (HANDLER-CASE expresin {(tipo-error (smbolo) expresin*)}*) Se evala expresin (ntese que es exactamente una). Si durante su evaluacin se seala un error de un tipo mencionado en una de las clusulas (tipo-error expresin*), entonces se transfiere el control a las expresin* y smbolo se liga al objeto error sealado. Si el error satisface varios tipos, se transfiere el control a la primera de las clusulas cuyo tipo lo satisfaga. tipo-error no se evala. . Ntese que el mbito de HANDLER-CASE es dinmico, no lxico Segn esto, podemos conseguir lo especificado con la siguiente definicin: (DEFUN EEVALQUOTE1 () (HANDLER-CASE (PROGN (PRINT 'EVALQUOTE>) (LET ((F (READ))) (COND ((EQ F 'EVAL>) NIL)
6.24
(T (PRIN1 (APPLY F (READ))) (EEVALQUOTE1))))) (ERROR (CONDICION) (FORMAT T "Error ~S. ~%Se desprecia y se sigue en EVALQUOTE." CONDICION) (EEVALQUOTE1)))) y ahora el dilogo puede ser > (EEVALQUOTE1) EVALQUOTE> / (2 0) Error #<SIMPLE-ERROR @ #xE21AAC>. Se desprecia y se sigue en EVALQUOTE. EVALQUOTE> C) Ntese que no es necesario emplear un nico manejador de errores, como se ha hecho en el apartado anterior. Para resolver el nuevo problema emplearemos dos (el segundo se emplear slo si el primero no es aplicable al error sealado): (DEFUN EEVALQUOTE2 () (HANDLER-CASE (PROGN (PRINT 'EVALQUOTE>) (LET ((F (READ))) (COND ((EQ F 'EVAL>) NIL) (T (PRIN1 (APPLY F (READ))) (EEVALQUOTE2))))) (ARITHMETIC-ERROR (CONDICION) (FORMAT T "Error ~S. ~%Se desprecia y se sale de EVALQUOTE." CONDICION) 0) (ERROR (CONDICION) (FORMAT T "Error ~S. ~%Se desprecia y se sigue en EVALQUOTE." CONDICION) (EEVALQUOTE2)))) y ahora el dilogo puede ser > (EEVALQUOTE2) EVALQUOTE> CAR (2) Error #<SIMPLE-ERROR @ #xE21ADA>. Se desprecia y se sigue en EVALQUOTE. EVALQUOTE> / (2 0) Error #<SIMPLE-ERROR @ #xE21AAC>. Se desprecia y se sale de EVALQUOTE. 0 >
6.25
7.2
Dpto. L.C.C (Universidad de. Mlaga).
R.7.1. Asignacin: SETQ. Evaluar las siguientes expresiones en el orden indicado: ((LAMBDA (Y) (SETQ Y 2) Y) 10) (LET ((X 10)) (SETQ X 2)) X (LET ((X 1)) (LET ((X 10)) (SETQ X 2))) (LET ((X 1)) (LET ((X 10)) (SETQ X 2)) X) (LET (X Y Z) (SETQ X 1 Y (1+ X) Z (1+ Y)) (LIST X Y Z)) (LET ((X 10)) (SETF X 2) X) (LET ((X 3) (Y 10)) (DOTIMES (I X) (PRIN1 I) (SETF X (+ X I))))) (LET ((K NIL) (L (LIST 'A 'B 'C))) (DOLIST (E L K) (SETF K (CONS E K)))) ************************** SOLUCION: Hasta ahora hemos creado ligaduras mediante llamadas a funciones y mediante formas como LET, DO, WITH-OPEN-FILE. Con estos y otros procedimientos se puede ligar cualquier smbolo a cualquier valor. Sin embargo, las ligaduras son difciles de modificar una vez creadas: la nica manera que conocemos es la actualizacin en la forma DO. An as, hemos podido implementar procedimientos bastante complicados. CommonLisp proporciona tambin la posibilidad de modificar libremente cualquier ligadura existente (asignacin), de manera no estructurada. Esto se consigue mediante la forma especial SETQ: (SETQ smbolo expresin) SETQ es una forma especial que no evala su primer argumento, que debe ser un smbolo. El valor devuelto es el del segundo argumento. SETQ se emplea por su efecto lateral: modificar la ligadura vigente de smbolo, de manera que smbolo pasa a estar ligado al valor de expresin. Por tanto ((LAMBDA (Y) (SETQ Y 2) Y) ; se modifica el entorno e Y<-2 10) ; se crea un entorno con Y<-10 =>2 (LET ((X 10)) ; se crea un entorno con X<-10 (SETQ X 2) X) ; se modifica el entorno y X<-2 => 2 X => Error: X sin ligar. (LET ((X 1)) (LET ((X 10)) (SETQ X 2))) => 2 ; se crea un entorno con X<-1 ; se crea otro entorno con X<-10, que lo ensombrece ; en este se asigna X<-2
7.3
(LET ((X 1)) (LET ((X 10)) (SETQ X 2)) X) => 1
; se crea un entorno con X<-1 ; se crea otro entorno con X<-10, que lo ensombrece ; en este se asigna X<-2
El nmero de argumentos de SETQ es par, pero indeterminado: pueden realizarse varias asignaciones con una misma llamada a SETQ. (SETQ [smbolo expresin]*) En ese caso, las asignaciones se realizan secuencialmente. Por tanto, (LET (X Y Z) (SETQ X 1 Y (1+ X) Z (1+ Y)) (LIST X Y Z)) => (1 2 3) SETF es otra forma especial equivalente a SETQ: (SETF [smbolo expresin]*) Por tanto, (LET ((X 10)) (SETF X 2) X) => 2 PSETF tiene un significado parecido: (PSETF [smbolo expresin]*) con la salvedad de que realiza en paralelo la evaluacin de las expresin*. NOTA: SETQ es en realidad un caso particular de SETF. SETF admite como primer argumento no slo un smbolo, sino muchas otras cosas sealadas por punteros (lugares o variables generalizadas). Supngase que se desea realizar lo siguiente: dados un smbolo contador, una expresin numrica veces que se evala al entero n, una expresin opcional expr-final (NIL por defecto), y una sucesin de expresiones expr-cuerpo*, evaluar expr-cuerpo* sucesivamente con contador ligado a los valores enteros 0, ..., n-1 y finalmente devolver el resultado de evaluar expr-final con contador ligado a n. CommonLisp proporciona un operador DOTIMES para llevar a cabo esta tarea: (DOTIMES (contador veces [expr-final]) expr-cuerpo*) Por tanto (LET ((X 3) (Y 10)) (DOTIMES (I X) (PRIN1 I) (SETF X (+ X I))))) 012 (efecto lateral) => NIL Supngase que se desea realizar lo siguiente: dados un smbolo variable, una expresin expr-lista que se evala a la lista lista, una expresin opcional expr-final (NIL por defecto), y una sucesin de expresiones expr-cuerpo*, evaluar expr-cuerpo* sucesivamente con variable ligado a los valores car(lista), cadr(lista), ..., car(last(lista)) y finalmente devolver el resultado de evaluar expr-final con variable ligada a NIL. CommonLisp proporciona un operador DOLIST para llevar a cabo esta tarea: (DOLIST (variable lista [expr-final]) expr-cuerpo*) Por tanto (LET ((K NIL) (L (LIST 'A 'B 'C))) (DOLIST (E L K) (SETF K (CONS E K)))) => (C B A)
7.4
R.7.2. Variables globales. Variables dinmicas. Evaluar las siguientes expresiones en el orden indicado: a) (DEFVAR *X* 1000) *X* (LET ((*X* 2)) (SETQ *X* (1+ *X*))) *X* (SETQ *X* 100) *X* (DEFUN KKX1 (*X*) (KKX2)) (DEFUN KKX2 () *X*) (KKX1 1) b) (SETQ *Y* 100) *Y* (LET ((*Y* 2)) (SETQ *Y* (1+ *Y*))) *Y* (DEFUN KKY1 (*Y*) (KKY2)) (DEFUN KKY2 () *Y*) (KKY1 1) ************************** SOLUCION: En R.7.1 hemos introducido el concepto de asignacin y SETQ como forma de realizarla. Pero hemos tenido buen cuidado de asignar valores a variables ligadas lxicamente, es decir, variables definidas en el entorno lxico donde se realiza la asignacin. En Lisp existe una forma alternativa de crear variables, variables que no son lxicas sino que reciben la denominacin de variables dinmicas o especiales. Es la forma DEFVAR: (DEFVAR smbolo [expresin]) DEFVAR asigna a smbolo el valor de expresin. Si expresin no figura, o si smbolo ya tiene un valor, no se realiza ninguna asignacin. Pero DEFVAR hace algo ms: declara que smbolo es una variable especial, es decir, que el mbito de sus ligaduras no se determina segn las reglas lxicas, sino segn las reglas dinmicas: sus valores se buscan en los entornos desde los cuales se ha creado el actual. Adems, la variable as creada es una variable global: su valor es accesible desde cualquier punto del programa. Es decir, adems de los entornos vistos hasta ahora, CommonLisp mantiene un entorno tope o entorno global cuyas ligaduras estn accesibles siempre. Segn esto, tendremos (DEFVAR *X* 1000) => *X* (DEFVAR devuelve el smbolo) *X* => 1000 Efectivamente, se ha realizado la asignacin global. (LET ((*X* 2)) (SETQ *X* (1+ *X*))) => 3 *X* => 1000 La ligadura recuperada y modificada ha sido la del LET, no el valor global. (SETQ *X* 100) => 100 *X* => 100 El valor global de *X* puede modificarse con SETQ. Hasta aqu no hay nada sorprendente. Pero obsrvese lo que ocurre a continuacin:
7.5
(DEFUN KKX1 (*X*) (KKX2)) => KKX1 (DEFUN KKX2 () *X*) => KKX2 (KKX1 1) => 1 Desde el entorno de evaluacin creado por la llamada a (KKY1 1) (con *X* ligado a 1), la llamada a (KKY2) crea otro entorno, donde finalmente se evalua *X*. Puesto que *X* es una variable especial, la ligadura vigente se determina por las reglas dinmicas, acudiendo al entorno desde donde se cre el actual. En l *X* vale 1, que es el valor devuelto finalmente. b) Hasta ahora hemos tenido buen cuidado de no asignar valores a variables libres. Un variable se dice que est libre cuando aparece fuera de cualquier entorno donde est ligada. Por suerte o por desgracia, este cuidado no es exigido por la definicin de CommonLisp, y las implementaciones son libres de hacer lo que deseen con estas variables. Normalmente, pese a que *Y* est libre, no se producir error: (SETQ *Y* 100) => 100 En qu mbito tiene vigencia la asignacin realizada? Explicaremos lo que hace CLisp. *Y* => 100 ya que esta aparicin, *Y* est libre y se supone global. Sin embargo (LET ((*Y* 2)) (SETQ *Y* (1+ *Y*))) => 3 ya que esta aparicin, *Y* est ligada a 2. An ms, *Y* => 100 La asignacin del ltimo SETQ no ha afectado al entorno tope, sino al entorno lxico del LET dentro del cual apareca *Y*. De la misma forma (DEFUN KKY1 (*Y*) (KKY2)) => KKY1 (DEFUN KKY2 () *Y*) => KKY2 (KKY1 1) => 100 Desde el entorno de evaluacin creado por la llamada a (KKY1 1) (con *Y* ligado a 1), la llamada a (KKY2) crea otro entorno, donde finalmente se evalua *Y*. Puesto que *Y* est libre, se usa su valor global, es decir, 100. Es decir, *Y* es una variable con un valor global, pero sus ligaduras siguen comportndose lxicamente. (Pero vd. nota b))
NOTAS IMPORTANTES. a) Es buena prctica de programacin identificar las variables especiales mediante asteriscos al comienzo y final de su nombre. b) Todas las variables globales deberan definirse con DEFVAR. El comportamiento de las variables globales no declaradas puede variar de implementacin en implementacin (unas las suponen dinmicas, otras no). c) Las variables globales o dinmicas deben emplearse con mucha parsimonia. Su uso slo est justificado para describir el estado global del sistema Lisp o del programa (p. ej. cul es el dispositivo de E/S por defecto, etc.).
7.6
R.7.3. Funciones con memoria. Implementar la funcin MEMORIZA, que produce funciones con memoria. MEMORIZA tiene como argumento una funcin f (de un argumento), y devuelve una implementacin de f tal que nunca se vuelven a calcular los valores de f ya calculados. ************************** SOLUCION: Llamemos F' al resultado de (MEMORIZA F). F' debe almacenar de alguna forma los valores ya calculados: por ejemplo, en una lista L de la forma ((a1 f(a1)) (a2 f(a2)) ...) donde a1, a2, ... son los argumentos ya procesados en llamadas anteriores a la funcin. El valor inicial de L ser la lista vaca. Por otra parte, L debe ser una lista accesible slo desde la funcin F'; por tanto, F' debe ser un cierre lxico. Ya sabemos, por tanto, que MEMORIZA tiene la siguiente estructura: (DEFUN MEMORIZA (FUNCION) (LET ((L NIL)) #'(LAMBDA (X) ...))) Ahora nos queda implementar el cuerpo de (LAMBDA (X) ...). El proceso es sencillo: 1. Comprobar si en la lista L figura un elemento de la forma (X valor). Ello se consigue con la forma (MEMBER X L :TEST#'(LAMBDA (E1 E2) (EQUAL E1 (CAR E2))) 2. en caso afirmativo, devolver este valor como F'(X). 3. en caso negativo, ! Calcular f(X) mediante (FUNCALL FUNCION X); llammosle OTRO-VALOR ! Almacenar en L el par (X f(X)) mediante (SETQ L (CONS (LIST X OTRO-VALOR) L) ! Devolver OTRO-VALOR En resumen, (DEFUN MEMORIZA (FUNCION) (LET ((L NIL)) #'(LAMBDA (X) (LET ((CALCULADO (MEMBER X L :TEST #'(LAMBDA (E1 E2) (EQUAL E1 (CAR E2)))))) (IF CALCULADO (CADAR CALCULADO) (LET ((OTRO-VALOR (FUNCALL FUNCION X))) (SETQ L (CONS (LIST X OTRO-VALOR) L)) OTRO-VALOR)))))) Veamos un ejemplo del uso de MEMORIZA. Supongamos la definicin (DEFUN KK (S) (DOTIMES (I 100000 S) (- I I))) Creemos una versin memoriosa de KK: (SETQ MEMO-KK (MEMORIZA #'KK)) => #<cierre 1 #xE0F984> Preguntemos dos veces sucesivas cunto tarda el sistema en calcular KK(Pepe): (TIME (KK 'PEPE)) => ... Timing: (KK 'PEPE) Execution time: 2.15 seconds plus 1.37 seconds garbage collecting (2145, 1370 clock ticks) => PEPE
7.7
(TIME (KK 'PEPE)) => ... Timing: (KK 'PEPE) Execution time: 2.22 seconds plus 1.09 seconds garbage collecting (2220, 1090 clock ticks) => PEPE Hemos comprobado que la segunda vez se tarda el mismo tiempo que la primera. Veamos qu ocurre con la versin memoriosa: (TIME (FUNCALL MEMO-KK 'PEPE))=>... Timing: (FUNCALL MEMO-KK'PEPE) Execution time: 2.27 seconds plus 1.55 seconds garbage collecting (2268, 1550 clock ticks) PEPE (TIME (FUNCALL MEMO-KK 'PEPE))=> ... Timing: (FUNCALL MEMO-KK 'PEPE) Execution time: 0.00 seconds (0 clock ticks) PEPE NOTA. Almacenar en una lista los valores ya calculados es una solucin muy burda: en efecto, si se han calculado ya N valores, comprobar si un valor ha sido ya calculado consume un tiempo del orden O(N).La solucin buena es almacenarlos en una tabla hash (vd. R. 7.6).
7.8
R.7.4. Generadores. a) Supongamos un retculo indefinido de lado unidad, cuyos nodos se identifican por un par (x,y), x,y. Definir una funcin LISP HAZ-RETICULO (X0 XF Y0 YF) que devuelva un cierre lxico capaz de generar un nodo cualquiera (x, y) del retculo, es decir, una lista (x, y) tal que x0xxf, y0yyf. Dos llamadas al cierre nunca devolvern el mismo nodo, a menos que ya se hayan generado todos los nodos posibles. b) Supuesto a), asignar dos generadores distintos a las variables *R1* y *R2*. ************************** SOLUCION: Habr n=(xf -xo +1)(yf y0 +1) puntos, que pueden numerarse 1, 2, ..., i,..., n. En funcin de y, las coordenadas x, y sern x = i mod (xf -xo +1) y = i div (xf -xo +1) Cada vez que se llame al cierre, el valor de i pasar a ser (i + 1) mod n. En resumen (DEFUN HAZ-RETICULO (X0 XF Y0 YF) (LET* ((NX (1+ (- XF X0))) (NY (1+ (- YF Y0))) (N (* NX NY)) (I -1))
;numero de columnas ;numero de filas ;numero total de puntos ;num. de orden del ltimo punto ;generado
(WHEN (OR (< NX 1) (< NY 1)) (ERROR "Final antes del principio")) #'(LAMBDA () (SETQ I (MOD (1+ I) N)) ;siguiente punto (LIST (+ X0 (MOD I NX)) ;siguiente fila (+ Y0 (FLOOR I NX)))))) ;siguiente columna b) Ello se conseguir con dos SETQ: (SETQ *R1* (HAZ-RETICULO 0 2 10 11)) => #<cierre 0 #xE10E58> (SETQ *R2* (HAZ-RETICULO 0 2 10 11)) => #<cierre 0 #xE1C59C> Si ahora llamamos a ambos cierres, vemos que los valores forman dos sucesiones diferentes: (FUNCALL *R1*) => (0 10) (FUNCALL *R1*) => (1 10) (FUNCALL *R1*) => (2 10) (FUNCALL *R2*) => (0 10) (FUNCALL *R1*) => (1 11) Pero si ahora realizamos una nueva llamada a HAZ-RETICULO y la asignamos a *R1*, la sucesin empieza de nuevo: (SETQ *R1* (HAZ-RETICULO 0 2 10 11)) => #<cierre 0 #xE31858> (FUNCALL *R1*) => (0 10)
7.9
R.7.5. Objetos con estado. Deseamos disear un programa para representar y manejar cuadrados y tringulos equilteros, definidos ambos por las coordenadas de su centro y la longitud de su lado. El programa debe ser capaz de calcular las reas y los permetros de estas figuras, as como de a) Dilatar la figura un factor alfa. b) Trasladar la figura a un nuevo centro (x', y') c) Trasladar la figura a un nuevo centro (x + deltax, y + deltay) donde (x, y) es el centro actual. Estas operaciones no se llevarn a cabo creando un nuevo objeto, sino modificando el objeto original. ************************** SOLUCION: El lector habr notado que este ejercicio es continuacin de R.4.6. Pero, a diferencia de lo especificado entonces, ahora se nos exige considerar mensajes capaces de modificar el objeto original. Para ello ser necesario manipular las ligaduras del cierre lxico, cambiando el valor al que estn ligadas las variables que almacenan las coordenadas del centro y el lado de la figura. Recordemos que en la representacin basada en cierres lxicos cada objeto se encarga de definir las funciones que lo manejan. Por tanto, dentro de cada objeto habr que aadir funciones para dilatarlo y trasladarlo. El valor que devuelvan ser irrelevante, ya que las emplearemos por su efecto lateral: modificar los valores de las ligaduras del cierre lxico, es decir, del objeto. Concretamente, las funciones que debemos aadir son: a) Para dilatar la figura: si el lado era L, ahora ser alfa*L; el centro sigue igual. b) Para trasladar la figura a un nuevo centro: el centro ahora ser (x', y'). El lado sigue igual c) Para trasladar la figura cierta distancia: si el centro era (x, y), ahora ser (x + deltax, y + deltay). El lado sigue igual. Otra diferencia con R.4.3. es que ahora las operaciones sobre los objetos requieren argumentos, que habrn de pasarse en el mensaje. Cada operacin puede requerir un nmero diferente de argumentos: por ejemplo, dilatar requiere uno slo (alfa), mientras que nuevo-centro requiere dos (x' e y'), al igual que trasladar (deltax y deltay). Ello significa que la funcin SEND tiene un nmero variable de argumentos, lo cual se puede implementar sencillamente como (DEFUN SEND (MSJ OBJ &REST ARGS) (APPLY OBJ (CONS MSJ ARGS))) Y si el lector recuerda la definicin de APPLY cuya justificacin aparece ahora patente- podr escribir de forma ms compacta (DEFUN SEND (MSJ OBJ &REST ARGS) (APPLY OBJ MSJ ARGS)) El constructor de tringulos ser (DEFUN HACER-TRIANGULO (X Y L) #'(LAMBDA (MSJ &REST ARGS) (CASE MSJ ((LADO) L) ((CENTROX) X) ((CENTROY) Y) ((ALTURA) (* 0.5 (SQRT 3) X)) ((AREA) (* 0.5 L (* 0.5 (SQRT 3) X))) ((PERIMETRO) (* 3 L)) ((DILATAR) (SETQ L (* L (CAR ARGS)))) ((NUEVO-CENTRO) (LET ((XPRIMA (CAR ARGS)) (YPRIMA (CADR ARGS))) (SETQ X XPRIMA Y YPRIMA))) ((TRASLADAR) (LET ((DELTAX (CAR ARGS)) (DELTAY (CADR ARGS))) (SETQ X (+ X DELTAX) Y (+ Y DELTAY)))))))
7.10
Y el constructor de cuadrados ser (DEFUN HACER-CUADRADO (X Y L) #'(LAMBDA (MSJ &REST ARGS) (CASE MSJ ((LADO) L) ((CENTROX) X) ((CENTROY) Y) ((AREA) (* L L)) ((PERIMETRO) (* 4 L)) ((DILATAR) (SETQ L (* L (CAR ARGS)))) ((NUEVO-CENTRO) (LET ((XPRIMA (CAR ARGS)) (YPRIMA (CADR ARGS))) (SETQ X XPRIMA Y YPRIMA))) ((TRASLADAR) (LET ((DELTAX (CAR ARGS)) (DELTAY (CADR ARGS))) (SETQ X (+ X DELTAX) Y (+ Y DELTAY))))))) Ahora podremos mandener un dilogo como el siguiente: (SETQ T1 (HACER-TRIANGULO 0 10 100)) => #<closure 1 #xE46340> (SEND 'LADO T1) => 100 (SEND 'DILATAR T1 10) => 1000 (SEND 'LADO T1) => 1000 (SEND 'TRASLADAR T1 10 0) => 10 (SEND 'CENTROX T1) => 10 (SEND 'CENTROY T1) => 10 (SEND 'NUEVO-CENTRO T1 200 20) => 20 (SEND 'CENTROX T1) => 200 (SEND 'CENTROY T1) => 20 NOTA. El lector puede apreciar que atributos y mtodos son tratados de la misma forma en esta implementacin.
7.11
R.7.6. Asignacin a lugares. Tablas hash. a) Empleando tablas hash, reimplementar la funcin MEMORIZA de R.7.3. b) Supongamos el rbol de decisin de la figura 7.1. Representarlo en LISP, empleando para ello una tabla hash que asocie etiquetas de nodo con cierres lxicos. Implementar una funcin (INVESTIGAR etiqueta) que mantenga el dilogo necesario a partir del nodo etiqueta hasta llegar a una conclusin.
Es un animal? SI Corre? SI NO Gacela Tortuga Lechuga NO Es un vegetal? SI NO
La piedra de Rosetta
Figura 7.1 ************************** SOLUCION: CommonLisp proporciona el tipo de datos predefinido tabla hash. Para crear una tabla se emplea la forma MAKE-HASH-TABLE: (MAKE-HASH-TABLE &KEY (:test #'eql) (:size 10) (:rehash-size 1.3) (:rehash-threshold 0.7)) Esta forma crea una nueva tabla y la devuelve como valor. :test debe ser EQ, EQL o EQUAL (por defecto EQL). :size indica aproximadamente el tamao inicial de la tabla. Cuando la tabla est llena en un procentaje mayor o igual a :rehash-threshold, se aumenta automticamente su tamao en el factor :rehash-size. Los valores por defecto de estos tres parmetros dependen de la implementacin. Para acceder a un elemento de la tabla se emplea la funcin GETHASH (GETHASH clave tabla- hash &OPTIONAL valor-defecto) La funcin devuelve el valor asociado con clave en tabla-hash, o bien valor-defecto, si no se ha encontrado ninguno. Cmo se almacenan valores en la tabla? El valor asociado a una clave en una tabla es un lugar. Como ya mencionamos en R.7.1, la forma SETF no slo modifica las ligaduras de los smbolos, sino que tambin puede alterar el contenido de cualquier lugar. Por tanto, para escribir que valor est asociado a clave en la tabla tabla-hash emplearemos la construccin (SETF (GETHASH clave tabla- hash) valor). Por ejemplo (SETQ T1 (MAKE-HASH-TABLE)) => #<HASH-TABLE #xE34454> (GETHASH 'PEPE T1) => NIL NIL (SETF (GETHASH 'PEPE T1) 18) => 18 (GETHASH 'PEPE T1) => 18 T (SETF (GETHASH 'PEPE T1) 14) => 14 (GETHASH 'PEPE T1) =>14 T
7.12
a) Segn esto la implementacin pedida ser (DEFUN MEMORIZA (FUNCION) (LET ((TF (MAKE-HASH-TABLE :TEST #'EQUAL))) #'(LAMBDA (X) (LET ((CALCULADO (GETHASH X TF))) (IF CALCULADO CALCULADO (LET ((OTRO-VALOR (FUNCALL FUNCION X))) (SETF (GETHASH X TF) OTRO-VALOR))))))) NOTA. GETHASH devuelve tambin un valor secundario: falso si no hay valor asociado a la clave, verdadero en otro caso. De esta forma se puede distinguir entre un valor NIL asociado a una clave y un valor NIL que indica que no hay valor asociado a la clave. (SETF (GETHASH 'JUAN T1) NIL) => NIL (GETHASH 'JUAN T1) => NIL T b) La idea fundamental es que cada nodo es una funcin sin argumentos que se encarga de -realizar al usuario la pregunta que corresponde a ese nodo; -en funcin de su respuesta, dar la solucin. Para ello ser necesario llamar a los nodos hijos del nodo actual. Por simplificar, supondremos que las respuestas vlidas del usuario son SI y NO. Para representar el rbol de decisin en conjunto, identificaremos cada nodo con una etiqueta NOMBRE, y emplearemos una tabla hash indexada por NOMBRE. La tabla ser el valor de una variable global *NODOS* (DEFVAR *NODOS* (MAKE-HASH-TABLE)) La funcin DEFNODO nos servir para construir los nodos y almacenarlos en la tabla hash. DEFNODO tendr como argumentos la etiqueta del nodo, el mensaje asociado al nodo y las etiquetas de sus dos hijos. Obviamente, si el nodo es un nodo hoja, es decir, corresponde a una respuesta final, DEFNODO no recibir las etiquetas de los hijos. De esta forma, la lista-lambda de DEFNODO ser (DEFUN DEFNODO (&KEY NOMBRE CONTENIDO NODO-SI NODO-NO) ... En nuestro ejemplo, las llamadas necesarias a DEFNODO sern ;;un arbol de decision concreto (DEFNODO :NOMBRE 'INICIO :CONTENIDO "Animal?" :NODO-SI 'ANIMAL :NODO-NO 'NO-ANIMAL) (DEFNODO :NOMBRE 'ANIMAL :CONTENIDO "Corre?" :NODO-SI 'CORREDOR :NODO-NO 'NO-CORREDOR) (DEFNODO :NOMBRE 'NO-ANIMAL :CONTENIDO "Vegetal?" :NODO-SI 'VEGETAL :NODO-NO 'MINERAL) (DEFNODO :NOMBRE 'CORREDOR :CONTENIDO "Gacela") (DEFNODO :NOMBRE 'NO-CORREDOR :CONTENIDO "Tortuga") (DEFNODO :NOMBRE 'VEGETAL :CONTENIDO "Lechuga") (DEFNODO :NOMBRE 'MINERAL :CONTENIDO "La piedra de Rosetta") El valor que devuelve la funcin es el siguiente: -si el nodo es una hoja, es decir, si el argumento opcional NODO-SI no figura en la llamada, DEFNODO devuelve la funcin sin argumentos que devuelve el mensaje almacenado en CONTENIDO. -en otro caso, DEFNODO devuelve la funcin sin argumentos que lee la respuesta del usuario y, en funcin de ella, devuelve el valor que devolvera NODO-SI o el que devolvera NODO-NO. Definimos tambin una funcin INVESTIGAR que tiene como argumento el nombre del nodo inicial de la bsqueda. En resumen,
7.13
(DEFUN DEFNODO (&KEY NOMBRE CONTENIDO NODO-SI NODO-NO) (SETF (GETHASH NOMBRE *NODOS*) (IF NODO-SI #'(LAMBDA () (FORMAT T "~%~A~%>> " CONTENIDO) (CASE (READ) (SI (INVESTIGAR NODO-SI)) (NO (INVESTIGAR NODO-NO)) (T (ERROR "Respuesta no valida.")))) #'(LAMBDA () CONTENIDO)))) (DEFUN INVESTIGAR (NOMBRE-NODO) (FUNCALL (GETHASH NOMBRE-NODO *NODOS*))) Ahora tendremos, por ejemplo, (INVESTIGAR 'INICIO) Animal? >> SI Corre? >> NO "Tortuga"
7.14
R.7.7. Estructuras. Definir una estructura para representar los estados del problema de misioneros y canbales. ************************** SOLUCION: CommonLisp proporciona la posibilidad de definir nuevos tipos de datos estructurados llamados estructuras. Para definir una estructura se emplea la forma DEFSTRUCT: (defstruct nombre {descripcin-slot}*) donde cada descripcin-slot es de la forma nombreslot o bien de la forma (nombreslot valor-inicial) DEFSTRUCT tiene las siguientes efectos laterales: -define procedimientos de lectura para los valores de los slots (ranuras o atributos) llamados nombre-nombreslot. -permite que SETF pueda modificar los valores de los slots. -define un predicado de tipo (llamado nombre-p) -define un constructor del tipo nombre llamado make-nombre. Este constructor tiene tantos argumentos clave como slots se hayan definido. Un ejemplo aclarar lo anterior: (defstruct alumno nombre (diligencia 'ESTUDIOSO) (curso 4)) => ALUMNO (defvar *alumno-1* (make-alumno :nombre 'pepe :curso 5)) => *ALUMNO-1* (defvar *alumno-2* (make-alumno)) => *ALUMNO-2* (alumno-curso *alumno-1*) => 5 (alumno-diligencia *alumno-2*) => ESTUDIOSO (setf (alumno-diligencia *alumno-2*) 'VAGO) => VAGO (alumno-diligencia *alumno-2*) => VAGO (alumno-p *alumno-2*) => T (alumno-p '(list 'juan 'ESTUDIOSO 4)) => NIL As que lo que nos piden es simplemente (defstruct estado-mc b m c) => ESTADO-MC
7.15
R.7.8. Objetos con herencia. a) Empleando tablas hash para representar los objetos, escribir las funciones necesarias para manejar los centros y lados de tringulos equilteros y cuadrados. b) Empleando tablas hash para representar los objetos, reimplementar el ejercicio R.7.6. Aadir una clase ms general FIGURA para la cual se definan las funciones comunes a tringulos y cuadrados. ************************** SOLUCION: a) Representaremos un objeto como un conjunto de pares atributo-mtodo. Este conjunto ser almacenado en una tabla hash indexada por los atributos. Si el valor del atributo es, por ejemplo, 27, el mtodo almacenado ser la funcin que siempre devuelve 27. Nos ser til por tanto la siguiente definicin: (DEFUN F-CTE (E) #'(LAMBDA (&REST XS) E)) Los constructores de tringulos y cuadrados sern las siguientes funciones: (DEFUN HACER-TRIANGULO (&KEY CENTROX CENTROY LADO) (LET ((OBJ (MAKE-HASH-TABLE))) (SETF (GETHASH 'CENTROX OBJ) (F-CTE CENTROX) (GETHASH 'CENTROY OBJ) (F-CTE CENTROY) (GETHASH 'LADO OBJ) (F-CTE LADO)) OBJ)) (DEFUN HACER-CUADRADO (&KEY CENTROX CENTROY LADO) (LET ((OBJ (MAKE-HASH-TABLE))) (SETF (GETHASH 'CENTROX OBJ) (F-CTE CENTROX) (GETHASH 'CENTROY OBJ) (F-CTE CENTROY) (GETHASH 'LADO OBJ) (F-CTE LADO)) OBJ)) La funcin de paso de mensajes debe aplicar el mtodo, correspondiente al mensaje y al objeto, a los argumentos adicionales: (DEFUN SEND (MSJ OBJ &REST ARGS) (APPLY (GETHASH MSJ OBJ) ARGS)) b) Ahora tendremos que definir para cada objeto un mtodo que nos d su padre. De esta forma, los constructores de tringulos y cuadrados sern: (DEFUN HACER-TRIANGULO (&KEY CENTROX CENTROY LADO PADRE) (LET ((OBJ (MAKE-HASH-TABLE))) (SETF (GETHASH 'CENTROX OBJ) (F-CTE CENTROX) (GETHASH 'CENTROY OBJ) (F-CTE CENTROY) (GETHASH 'LADO OBJ) (F-CTE LADO) (GETHASH 'PADRE OBJ) (F-CTE PADRE)) OBJ))
7.16
(DEFUN HACER-CUADRADO (&KEY CENTROX CENTROY LADO PADRE) (LET ((OBJ (MAKE-HASH-TABLE))) (SETF (GETHASH 'CENTROX OBJ) (F-CTE CENTROX) (GETHASH 'CENTROY OBJ) (F-CTE CENTROY) (GETHASH 'LADO OBJ) (F-CTE LADO) (GETHASH 'PADRE OBJ) (F-CTE 'CLASE-CUADRADO)) OBJ)) La funcin de paso de mensajes debe aplicar al objeto el mtodo correspondiente al mensaje (y los argumentos adicionales). Este mtodo puede que est almacenado directamentamente el el objeto (en cuyo caso nos lo dar la funcin METODO-NOH), o bien puede que est almacenado en algn antepasado (en cuyo caso nos lo dar la funcin METODO-H): (DEFUN METODO-NOH (MSJ OBJ) (GETHASH MSJ OBJ)) (DEFUN METODO-H (MSJ OBJ) (LET ((M (METODO-NOH MSJ OBJ)) (M-PADRE (METODO-NOH 'PADRE OBJ))) (COND (M) (M-PADRE (METODO-H MSJ (FUNCALL M-PADRE OBJ))) (T (ERROR "No hay mtodo para el mensaje ~S." MSJ))))) (DEFUN SEND (MSJ OBJ &REST ARGS) (APPLY (METODO-H MSJ OBJ) OBJ ARGS)) Las clases tringulo y cuadrado almacenarn distintos mtodos para el clculo de alturas, permetros y reas: (DEFUN HACER-CLASE-TRIANGULO (&KEY PADRE) (LET ((CLASE (MAKE-HASH-TABLE))) (SETF (GETHASH 'PADRE CLASE) (F-CTE PADRE) (GETHASH 'ALTURA CLASE) #'(LAMBDA (OBJ) (* 0.5 (SQRT 3) (SEND 'LADO OBJ))) (GETHASH 'AREA CLASE) #'(LAMBDA (OBJ) (* (SEND 'ALTURA OBJ) (SEND 'LADO OBJ))) (GETHASH 'PERIMETRO CLASE) #'(LAMBDA (OBJ) (* 3 (SEND 'LADO OBJ)))) CLASE))
(DEFUN HACER-CLASE-CUADRADO (&KEY PADRE) (LET ((CLASE (MAKE-HASH-TABLE))) (SETF (GETHASH 'PADRE CLASE) (F-CTE PADRE) (GETHASH 'AREA CLASE) #'(LAMBDA (OBJ) (* (SEND 'LADO OBJ) (SEND 'LADO OBJ))) (GETHASH 'PERIMETRO CLASE) #'(LAMBDA (OBJ) (* 4 (SEND 'LADO OBJ)))) CLASE))
7.17
La clase figura almacenar los mtodos de dilatar y trasladar, que son comunes a todas las clases: (DEFUN HACER-CLASE-FIGURA (&KEY PADRE) (LET ((CLASE (MAKE-HASH-TABLE))) (SETF (GETHASH 'DILATAR CLASE) #'(LAMBDA (OBJ ALFA) (SETF (GETHASH 'LADO OBJ) (F-CTE (* ALFA (SEND 'LADO OBJ))))) (GETHASH 'NUEVO-CENTRO CLASE) #'(LAMBDA (OBJ X1 Y1) (SETF (GETHASH 'CENTROX OBJ) (F-CTE X1) (GETHASH 'CENTROY OBJ) (F-CTE Y1))) (GETHASH 'TRASLADAR CLASE) #'(LAMBDA (OBJ DX DY) (SETF (GETHASH 'CENTROX OBJ) (F-CTE (+ DX (GETHASH 'CENTROX OBJ))) (GETHASH 'CENTROY OBJ) (F-CTE (+ DY (GETHASH 'CENTROY OBJ)))))) CLASE)) Ahora podemos tener la siguiente sesin: (SETQ F (HACER-CLASE-FIGURA)) => #<HASH-TABLE #xE47458> (SETQ T1 (HACER-CLASE-TRIANGULO :PADRE F)) => #<HASH-TABLE #xE58E80> (SETQ T2 (HACER-TRIANGULO :CENTROX 1 :CENTROY 10 :LADO 100 :PADRE T1)) => #<HASH-TABLE #xE6CBDC> (SEND 'PERIMETRO T2) => 300 (SEND 'DILATAR T2 2) => #<closure 0 #xE48F50> (SEND 'LADO T2) => 200 (SEND 'LADO T1) => Error: No hay mtodo para el mensaje LADO. NOTA. El lector puede apreciar que en esta implementacin clases e instancias son tratados de la misma forma.
7.18
R.7.9. Uso de arrays: Conecta-4. a) Empleando arrays definir un tipo de datos tablero para el juego del conecta-4. b) Definir las siguientes operaciones sobre tableros: (tablero-pos-valida tab f c), devolver cierto si la posicin (f,c) pertenece al tablero tab, y falso en otro caso. (tablero-columna-libre tab c), devolver cierto si la columna c no est llena en el tablero tab, y falso en otro caso. (ver-tablero tab), que no devuelva ningn valor, y muestre adecuadamente el contenido de un tablero por pantalla. c) Empleando estructuras definir un tipo de datos estado para el juego del conecta-4. d) Definir las siguientes operaciones sobre estados: (elegir-suc-nth c e), devolver un nuevo estado resultante de soltar una ficha en la columna c del tablero. (agotado e), devolver cierto si el tablero del estado e est lleno. (finalp e), devolver 1 si el estado e es final y ganador para el jugador 1, -1 si es final y ganador para el jugador 2, o NIL en otro caso. e) Escribir una funcin conecta-4 encargada de coordinar y mostrar por pantalla una partida de conecta-4. La funcin recibir como argumento dos funciones (max y min), encargadas de proporcionar los movimientos de uno de los jugadores, mostrar por pantalla la evolucin del juego despus de cada jugada, y terminar cuando uno de los dos jugadores haya ganado el juego o el tablero est completamente lleno. El valor devuelto por la funcin ser 1 si gan max, -1 si gan min, y 0 si hubo empate. Las funciones de los jugadores recibirn como argumentos el estado del tablero y el ltimo movimiento realizado por el oponente, y devolvern el movimiento que desean realizar ************************** SOLUCION: Common Lisp proporciona el tipo de datos predefinido array. Para crear un array se emplea la forma MAKE-ARRAY: (MAKE-ARRAY dimensiones &KEY param-clave) Esta forma crea un nuevo array y lo devuelve como valor. El parmetro necesario dimensiones debe ser una lista de enteros no negativos que sern las dimensiones del array. La longitud de la lista define la dimensionalidad del array. Entre los parmetros clave se encuentran :element-type, :initial-element, e :initial-contents. El valor por defecto de :element-type es T, lo cual significa que el contenido de las posiciones del array puede ser cualquier objeto Lisp. Los parmetros :initial-element, e :initial-contents permiten especificar el contenido inicial del array y son excluyentes. Si no se emplea ninguno de ellos el contenido inicial del array no est definido. En el caso de :initial-element se debe proporcionar un objeto del tipo definido por :element-type , que pasar a ser el contenido inicial en todas las posiciones del array. En el caso de :initial-contents se puede proporcionar una lista de listas anidadas que proporcionen el contenido de cada posicin del array. Para acceder a un elemento de un array se emplea la funcin AREF (AREF array &REST subndices) La funcin devuelve el objeto guardado en la posicin del array especificada por los subndices. El nmero de subndices debe coincidir con la dimensionalidad del array, y cada uno debe encontrarse dentro del rango correspondiente. Cmo se almacenan valores en un array? Cada posicin de un array es un lugar. Como ya mencionamos en R.7.1, la forma SETF no slo modifica las ligaduras de los smbolos, sino que tambin puede alterar el contenido de cualquier lugar. Por tanto, para escribir que valor est asociado a cada posicin del array emplearemos la construccin (SETF (AREF array subndice*) valor). Para concer la dimensionalidad de un array se emplea la funcin ARRAY-RANK (ARRAY-RANK array). Para conocer la longitud de una dimensin concreta del array se utiliza la funcin ARRAYDIMENSION (ARRAY-DIMENSION array dimensin).
7.19
La funcin EQUALP aplicada a dos arrays devolver T si ambos tienen el mismo nmero de dimensiones, las dimensiones coinciden y los elementos correspondientes son todos EQUALP. Por ejemplo: (SETQ A1 (MAKE-ARRAY (2) :initial-element 25)) => #<ARRAY #xf323> (AREF A1 0) => 25 (SETF (AREF A1 0) 18 (AREF A1 1) 14) => 14 (AREF A1 0) => 18 (AREF A1 1) =>14 (ARRAY-RANK A1) =>1 (ARRAY-DIMENSION A1 0) =>2 (SETQ A2 (MAKE-ARRAY (2 3) :initial-contents ((1 2 3) (4 5 6)))) => #<ARRAY #xf442> (AREF A2 1 2) => 6 a) Cada tablero ser un array de *nfilas* filas y *ncolumnas* columnas. Cada casilla del tablero podr estar vaca o contener una ficha que podr ser de tipo max o min. (defvar *nfilas*) (setf *nfilas* 6) (defvar *ncolumnas*) (setf *ncolumnas* 7) (defconstant *vacio* '_) (defconstant *jugador-1* 1) (defconstant *jugador-2* 0) ;posicin vaca del tablero ;ficha del jugador 1 ;ficha del jugador 2
Como constructores consideraremos varias funciones. La primera, hacer-tablero-vacio, crear un tablero nuevo con las casillas vacas. La segunda, copiar-tablero, devolver un tablero nuevo con las mismas dimensiones y contenidos que otro dado. Por ltimo, tablerosoltar-ficha recibir un tablero, una columna y una ficha, y devolver dos valores: un nuevo tablero igual que el original y donde adems se ha soltano una ficha por la columna indicada; y adicionalmente la fila donde qued colocada la ficha. (defun hacer-tablero-vacio (&optional (nfilas *nfilas*) (ncolumnas *ncolumnas*)) (make-array (list nfilas ncolumnas) :initial-element *vacio*)) (defun copy-tablero (tab) (let ((tab2 (make-array (array-dimensions tab)))) (dotimes (f (array-dimension tab 0)) (dotimes (c (array-dimension tab 1)) (setf (aref tab2 f c) (aref tab f c)))) tab2))
7.20
(defun tablero-soltar-ficha (tab-orig c ficha) (let ((tab (copy-tablero tab-orig))) (dotimes (f (array-dimension tab 0)) (when (equal *vacio* (aref tab f c)) (setf (aref tab f c) ficha) (return (values tab f)))))) Definiremos tambin selectores para consultar las dimensiones de un tablero, el contenido de una posicin dada, y si una posicin dada pertenece o no al tablero. (defun tablero-nfilas (tab) (array-dimension tab 0)) (defun tablero-ncolumnas (tab) (array-dimension tab 1)) (defun tablero-contenido (tab f c) (aref tab f c)) b) Las definiciones seran las siguientes: (defun tablero-pos-valida (tab f c) (and (<= 0 f (1- (tablero-nfilas tab))) (<= 0 c (1- (tablero-ncolumnas tab)))) (defun tablero-columna-libre (tab c) (equal *vacio* (tablero-contenido tab (1- (tablero-nfilas tab)) c))) Para ver un tablero mostraremos su contenido adecuadamente: la primera fila ser la inferior, y la ltima la superior. Adems mostraremos debajo de cada columna su ndice (del 0 al 9). (defun ver-tablero (tab) (let ((nfilas (tablero-nfilas tab)) (ncolumnas (tablero-ncolumnas tab))) ;muestra el contenido del tablero en el primer cuadrante (dotimes (f nfilas tab) (format t "~% ") (dotimes (c ncolumnas) (princ (tablero-contenido tab (- nfilas (1+ f)) c)))) ;muestra debajo de cada columna su ndice (format t "~% ") (dotimes (c ncolumnas) (princ #\=)) (format t "~% ") (dotimes (c ncolumnas) (princ (mod c 10))) (terpri) (values))) c) La funcin conecta-4 conservar una representacin del estado del juego para poder mostrarla por pantalla, consultar al jugador en su turno, e informarle del ltimo movimiento realizado. Para ello definiremos un tipo de datos estado de la siguiente forma: (defstruct estado "situacin del juego en un momento dado" (it 0) ;nmero de jugadas realizadas (jug1? nil) ;le toca jugar a jug1? (tablero nil) ;contenido del tablero (ultimo-mov nil)) ;ultimo movimiento realizado (posicin marcada)
7.21
(defun hacer-estado-inicial (make-estado :it :jug1? :tablero :ultimo-mov
() 0 T (hacer-tablero-vacio) nil))
(defun ver-estado (e) (format t "~%It: ~S *****~%" (estado-it e)) (ver-tablero (estado-tablero e)) (format t "~%Le toca al jugador ~S~%" (if (estado-jug1? e) 1 2)) (values))
Cada vez que un jugador propone un movimiento (en este caso soltar una ficha en una columna), es necesario comprobar que el movimiento es vlido y a continuacin actualizar el estado del juego. (defun posiblep (n e) "Es posible soltar una ficha en la columna n en el estado e?" (tablero-columna-libre (estado-tablero e) n))
;;elegir-suc-nth (n e) ;; Devuelve un estado resultado de que el jugador actual deje caer ;; una ficha por la columna c del tablero, nil si no es posible (defun elegir-suc-nth (n e) (multiple-value-bind (tab2 f) (tablero-soltar-ficha (estado-tablero e) n (if (estado-jug1? e) *jugador-1* *jugador-2*)) (make-estado :it (1+ (estado-it e)) :jug1? (not (estado-jug1? e)) :tablero tab2 :ultimo-mov (list f n)))) Cada vez que un jugador realiza un movimiento ser necesario comprobar si ha ganado el juego, para ello definiremos la funcin finalp, que devolver la ficha del jugador del turno anterior si este gan el juego, y falso en otro caso. Para comprobar que hay 4 fichas conectadas en diagonal, horizontal y vertical slo ser necesario comprobarlo a partir del ltimo movimiento. Para ello definiremos la operacin tablero-conectadas. (defvar *long-ganadora*) (setf *long-ganadora* 4) ;nm. de fichas conectadas para ganar
(defun agotado (e) "est lleno el tablero del estado e? (= (estado-it e) (* (tablero-ncolumnas (estado-tablero e)) (tablero-nfilas (estado-tablero e)))))
7.22
(defun finalp (e) Devuelve el ganador (1, -1) o NIL si no hay (let* ((mov (estado-ultimo-mov e)) (f (car mov)) (c (cadr mov)) (ficha (if (estado-jug1? e) *jugador-2* *jugador-1*)) (tab (estado-tablero e))) (when (and mov (<= *long-ganadora* (max (tablero-conectadas tab f c 1 0 ficha) (tablero-conectadas tab f c 0 1 ficha) (tablero-conectadas tab f c -1 1 ficha) (tablero-conectadas tab f c 1 1 ficha)))) ficha))) (defun tablero-conectadas (tab f c df dc &optional (ficha (tablero-contenido tab f c))) "nmero de fichas conectadas con (f,c) en la direccin df, dc" (+ (tablero-contar tab f c df dc ficha) (tablero-contar tab f c (- df) (- dc) ficha) -1)) ; (f,c) se cuenta 2 veces (defun tablero-contar (tab f c df dc ficha &optional (ac 0)) (if (and (tablero-pos-valida tab f c) (equal (tablero-contenido tab f c) ficha)) (tablero-contar tab (+ f df) (+ c dc) df dc ficha (1+ ac)) ac)) Podemos definir la funcin encargada de coordinar el juego del siguiente modo utilizando recursin por la cola: (defun conecta4 (jugador-1 jugador-2 &optional (e (hacer-estado-inicial))) (ver-estado e) (cond ((finalp e) (if (estado-jug1? e) -1 1)) ;ganador ((agotado e) 0) ;empate (t (conecta4 jugador-1 jugador-2 (elegir-suc-nth (if (estado-jug1? e) (funcall jugador-1 e) (funcall jugador-2 e)) e))))) Por ltimo podemos definir dos funciones para los jugadores. La primera smplemente pide por pantalla un movimiento y lo lee de teclado. La segunda mueve aleatoriamente: (defun estrategia0 (e) (format t "~%En qu columna soltamos la ficha? (let ((c (read))) (if (posiblep c e) c (estrategia0 e))))
")
(defun estrategia-random (e) (let ((c (random (tablero-ncolumnas (estado-tablero e))))) (if (posiblep c e) c (estrategia-random e)))) De momento podemos jugar con la mquina empleando la llamada: (conecta4 #'estrategia-random #'estrategia0) Ms adelante desarrollaremos un adversario ms digno para nuestra inteligencia.
7.23
R.8.1. Clases y mtodos. Deseamos disear un programa para representar y manejar cuadrados y tringulos equilteros, definidos ambos por las coordenadas de su centro y la longitud de su lado. El programa debe ser capaz de calcular las reas y los permetros de estas figuras. a) Definir una implementacin CLOS de las clases cuadrado y tringulo equiltero. b) Definir mtodos adecuados para el clculo de reas y permetros. c) Modificar la implementacin para tratar tambin los crculos, definidos por su centro y radio. d) Modificar la implementacin para calcular tambin los dimetros de los objetos. Se entiende por dimetro de un polgono la longitud del mayor segmento que puede trazarse en el interior del polgono: para el cuadrado es la diagonal y para el tringulo equiltero el lado. ************************** SOLUCION: a) En la dcada de los 80 del siglo XX el paradigma de la programacin orientada a objetos vivi un gran auge y se experimentaron muy diversas formas de incorporarlo en los lenguajes de programacin. Los diversos dialectos de Lisp existentes en la poca no fueron ajenos a esta tendencia, y varios de ellos incorporaron diversas formas de orientacin a objetos, incluyendo, entre otros, el modelo del paso de mensajes. En 1995, el standard ANSI Common Lisp incluy en su especificacin un sistema de objetos denominado CLOS (Common Lisp Object System), basado en el modelo de la programacin dirigida por datos. El resultado es que Common Lisp incorpora los principios de la programacin orientada a objetos con un estilo distinto al de otros lenguajes corrientes en uso, proporcionando a cambio una integracin limpia, cmoda y elegante de este paradigma con las restantes caractersticas y estilos de programacin que hemos estudiado en lecciones anteriores. Todos los tipos de datos Lisp son clases CLOS, y todos ellos heredan en ltima instancia de una nica clase llamada T. Se pueden definir nuevas clases empleando la macro defclass: (defclass nom-clase (superclase*) ((nom-slot opcion-slot*)*) opcion-clase*) CLOS permite la herencia mltiple, es decir, una clase puede heredar de varias superclases. Esta caracterstica debe emplearse con mucha cautela y la debida parsimonia. En la mayora de aplicaciones es ms que suficiente que cada clase herede de una nica superclase. Como veremos enseguida, una clase hereda de sus superclases tanto sus slots como los mtodos que le son aplicables. Cada clase posee una lista de definiciones de slots (ranuras o campos). Cada definicin de slot es a su vez una lista con el nombre del slot y una serie de opciones. Destacamos entre ellas las siguientes: opcion-slot = :reader :writer :accessor :initform :initarg :allocation nom-funcion-lectura | nom-funcion-escritura | nom-funcion-acceso | expresion | palabra-clave :instante | :class
Para cada slot pueden definirse funciones de lectura, escritura, o acceso (lectura y escritura). Cada slot de una clase es un lugar donde puede guardarse un valor empleando la macro setf, de un modo similar al ya estudiado en la leccin anterior para arrays, tablas hash, o estructuras. Cada slot puede tener una expresion de valor inicial en la opcin :initform. Una vez definida una clase, podemos crear objetos (instancias) de la misma llamando a la funcin genrica make-instance con la siguiente sintaxis: (make-instance nom-clase {initarg valor}*)
Lab. de Int. Art. 2007/2008
8.2
Dpto. Leng. C. Comp.
Aquellos slots para los que se ha incluido la opcin :initarg pueden recibir un valor inicial en el momento de la llamada a make-instance indicando el nombre del initarg (que debe ser una palabra clave), y su valor. En caso de no indicarse ningn valor, se tomar el de la expresin :initform, y si esta no existe, el slot quedar no ligado1. Entre las opciones de clase destacamos nicamente la siguiente, que permite introducir una cadena de caracteres para documentar la clase. (:documentation cadena) Para definir las clases pedidas podemos abstraer la clase figura (figura geomtrica). Toda figura geomtrica tendr las coordenadas x,y de su centro geomtrico. Las clases triangulo y cuadrado heredarn de figura: (defclass figura () ((x :accessor centro-x :initarg :centro-x :initform 0) (y :accessor centro-y :initarg :centro-y :initform 0)) (:documentation "Figura coordenadas de su centro"))
geomtrica
genrica
definida
por
las
(defclass cuadrado (figura) ((l :accessor lado :initarg :lado :initform 1)) (:documentation "Polgono cuadrado definido por su lado")) (defclass triangulo (figura) ((l :accessor lado :initarg :lado :initform 1)) (:documentation "Polgono triangulo definido por su lado")) Podemos crear ya objetos de las clases cuadrado y tringulo: > (setf *cd* (make-instance 'cuadrado :centro-x 10 :centro-y 10 :lado 4)) #<CUADRADO #x1A1A6299> > (setf *tr* (make-instance 'triangulo :lado 3 :centro-y 10)) #<TRIANGULO #x1A18D5DD> > (centro-x *cd*) 10 > (centro-y *cd*) 10 > (lado *cd*) 4 > (centro-x *tr*) 0 > (centro-y *tr*) 10 > (lado *tr*) 3
Existe una opcin adicional intermedia para dar valor a un slot, la opcin de clase :defaultinitargs.
8.3
Al haber definido funciones de acceso, podemos incluso modificar destructivamente los valores de los slot empleando setf: >(setf (centro-x *tr*) 30) 30 > (centro-x *tr*) 30 b) Podemos definir operaciones sobre los objetos de una clase empleando funciones como las que ya conocemos, o bien empleando mtodos. Emplear mtodos puede presentar ventajas en algunos casos. Los mtodos aplicables a una clase tambin lo son a sus herederas. Tambin puede definirse una operacin abstracta para varias clases de objetos (con un nombre genrico nico), y luego implementarla para cada uno de ellos definiendo los mtodos correspondientes. Esta caracterstica recibe el nombre de polimorfismo. Para definir mtodos en CLOS se emplea la macro defmethod. Una sintaxis simplificada de la misma es la siguiente: (defmethod nombre lista-lambda-especializada expr*) La nica diferencia evidente en principio con una macro defun es, aparte del nombre de la macro, la existencia de una lista lambda especializada. Esta es igual que cualquier lista lambda, excepto que algunos de los parmetros necesarios pueden reemplazarse por parmetros especializados de la forma (nom-param nom-clase), indicando que el mtodo ser aplicable nicamente cuando el parmetro sea de la clase indicada o una de sus subclases2. Para aquellos parmetros no especializados, el nombre de clase por defecto es T. Podemos definir por tanto los siguientes mtodos especializados para la clase cuadrado: (defmethod altura ((obj cuadrado)) (lado obj)) (defmethod area ((obj cuadrado)) (expt (lado obj) 2)) (defmethod perimetro ((obj cuadrado)) (* 4 (lado obj))) Y ahora otros tantos especializados para la clase tringulo: (defmethod altura ((obj triangulo)) (* (sqrt 3) 0.5 (lado obj))) (defmethod area ((obj triangulo)) (* (lado obj) (altura obj))) (defmethod perimetro ((obj triangulo)) (* 3 (lado obj))) La aplicacin de un mtodo a una instancia no se diferencia sintcticamente de la llamada a una funcin ordinaria. Una vez definidos los mtodos, las nuevas operaciones estn ya disponibles incluso sobre los objetos creados anteriormente. As, > (area *cd*) 16 > (perimetro *cd*) 16
En lugar de nom-clase puede emplearse tambin una lista de especializacin de la forma (eql expresion).
8.4
> (area *tr*) 7.7942286 > (perimetro *tr*) 9 c) La modificacin pedida es inmediata. No es necesario cambiar nada de lo ya escrito. (defclass circulo (figura) ((r :accessor radio :initarg :radio :initform 1)) (:documentation "Figura geomtrica crculo definida por su radio")) (defmethod area ((obj circulo)) (* pi (expt (radio obj) 2))) (defmethod perimetro ((obj circulo)) (* 2 pi (radio obj))) Los objetos y mtodos anteriormente definidos no se ven afectados por las nuevas definiciones. > (setf *cc* (make-instance 'circulo :radio 2)) #<CIRCULO #x1A1E85DD> > (radio *cc*) 2 > (area *cc*) 12.566370614359172954L0 > (perimetro *cc*) 12.566370614359172954L0 > (perimetro *tr*) 9 Ntese que, > (radio *tr*) ERROR No hay mtodo aplicable > (lado *cc*) ERROR No hay mtodo aplicable d) Nuevamente la modificacin es trivial. Definimos nuevos mtodos: (defmethod diametro ((obj cuadrado)) (* (sqrt 2) (lado obj))) (defmethod diametro ((obj triangulo)) (lado obj)) (defmethod diametro ((obj circulo)) (* 2 (radio obj))) Y las nuevas operaciones estn disponibles incluso sobre los objetos ya creados anteriormente: > (diametro *cd*) 5.656854 > (diametro *tr*) 3 > (diametro *cc*) 4
8.5
R.8.2. Funciones genricas. Macro defgeneric. Suponiendo vigentes las definiciones realizadas en R.8.1, evaluar las siguientes expresiones, a) #radio b) #diametro c) (functionp #radio) d) (functionp #diametro) e) (defmethod radio3 ((obj circulo)) (* 3 (radio obj))) f) (functionp (defmethod radio4 ((obj circulo)) (* 4 (radio obj)))) g) (diametro *cc*) h) (defgeneric desplazar (objeto deltax deltay) (:documentation desplazamiento relativo del objeto)) i) (defmethod desplazar ((obj figura) dx dy) (incf (centro-x obj) dx) (incf (centro-y obj) dy)) j) (mapcar #'diametro (list *cd* *tr* *cc*)) ************************** SOLUCION: a,b,c,d) Es interesante observar que tanto radio como diametro son funciones (!), > #'radio #<STANDARD-GENERIC-FUNCTION RADIO> > #'diametro #<STANDARD-GENERIC-FUNCTION DIAMETRO> >(functionp #'radio) T >(functionp #'diametro) T e,f) Cada llamada a defmethod devuelve un objeto de tipo mtodo. Sin embargo, los mtodos no son funciones: > (defmethod radio3 ((obj circulo)) (* 3 (radio obj))) #<STANDARD-METHOD (#<STANDARD-CLASS CIRCULO>)> > (functionp (defmethod radio4 ((obj circulo)) (* 4 (radio obj)))) NIL Como ya observamos en R.8.1, las llamadas a funciones definidas con defun y la invocacin de mtodos son sintcticamente indistinguibles en Common Lisp. Tambin observamos que se pueden definir mtodos con el mismo nombre pero especializados para clases distintas (por ejemplo, definimos tres mtodos diametro especializados para las clases cuadrado, triangulo, y circulo respectivamente). Cmo determina el intrprete qu mtodo debe invocarse en cada momento? Y por qu existen funciones llamadas radio y diametro si los mtodos que hemos definido no son funciones propiamente dichas?
8.6
En CLOS todas las invocaciones de mtodos sobre objetos se realizan a travs de funciones genricas. Es importante comprender el mecanismo de las funciones genricas, pues son el elemento central del modelo de objetos de CLOS. Una funcin genrica es una funcin cuyo comportamiento depende de las clases de los argumentos que se le proporcionan. Bsicamente, 3 est definida por su nombre, una lista lambda, y un conjunto de mtodos . La lista lambda de una funcin genrica es una lista lambda simplificada, en la que slo importa el nmero y tipo de parmetros (necesarios, opcionales, clave, y/o restante), de modo que se da una visin general de la forma que tendrn las llamadas a la funcin genrica. Los mtodos son las partes de una funcin genrica que proporcionan informacin sobre cmo debe comportarse esta cuando sus argumentos sean objetos de determinadas clases. Podemos dar ahora una definicin ms completa de lo que ocurre cada vez que se realiza una llamada a defmethod. 1. El intrprete comprueba si existe una funcin genrica del mismo nombre. 2. Si no existe, se crea automticamente la funcin genrica correspondiente, elaborando la lista lambda a partir de la del mtodo. El mtodo a su vez entrar a formar parte del repertorio de mtodos disponibles para la funcin genrica. 3. Por el contrario, si la funcin genrica ya existe, se comprueba la congruencia de la lista lambda del mtodo con la de la funcin. Si hay alguna incongruencia se seala un error, en caso contrario, el mtodo pasa a formar parte del repertorio de mtodos disponibles para la funcin genrica. g) Ya evaluamos esta expresin en R.8.1, pero ahora podemos dar una definicin ms completa de lo que ocurre: > (diametro *cc*) 4 El intrprete reconoce que dimetro es el nombre de una funcin genrica, que sigue el ciclo normal de evaluacin de las funciones. Tras comprobar que el nmero de argumentos es congruente con los parmetros de la funcin genrica, el intrprete pasa el objeto crculo a la misma. Esta comprueba si hay algn mtodo cuyo parmetro est especializado para la clase circulo o alguna de sus superclases. Si no hay ningn mtodo aplicable se seala un error. Si 4 hay un mtodo, se invoca sobre los argumentos recibidos . h,i) Hemos visto que la primera llamada a defmethod provoca la creacin de una funcin genrica del mismo nombre. Sin embargo, tambin podemos definir explcitamente una funcin genrica mediante la macro defgeneric. Aunque no es imprescindible, algunos autores recomiendan efusivamente su uso antes de definir los mtodos correspondientes por cuestiones de estilo: a) la expresin defgeneric sirve como documentacin interna del programa; b) el intrprete comprobar la congruencia de la lista lambda de todos los mtodos definidos para dicha funcin genrica. Su sintaxis bsica es la siguiente, (defgeneric nombre lista-lambda-fg opcion*) Dentro de las opciones destacaremos nicamente de momento, opcion = (:documentation cadena)
As, por ejemplo, podemos definir,

3
Y, en realidad, tambin por un tipo de combinacin de mtodos, que decide cmo debe actuarse en caso de que varios mtodos sean aplicables a una misma llamada. 4 Si hubiera varios mtodos aplicables se construira uno nico segn el tipo de combinacin de mtodos de la funcin genrica.
8.7
> (defgeneric desplazar (objeto deltax deltay) (:documentation desplazamiento relativo del objeto)) #<STANDARD-GENERIC-FUNCTION DESPLAZAR> La llamada a defgeneric define el nombre de la operacin y la forma de la lista lambda. Todos los mtodos desplazar definidos en adelante debern poseer una lista lambda especializada congruente con la de la funcin genrica (en este caso, tres parmetros necesarios). Sern estos mtodos los que se encarguen de describir la operacin a llevar a cabo en cada caso. Ntese que ni siquiera el nombre de los parmetros es relevante, slo su nmero y tipo (necesarios, opcionales, clave, o restante). Tcnicamente, una lista lambda es congruente si tiene el mismo nmero de parmetros necesarios y opcionales, y es capaz de aceptar cualquier argumento restante o clave especificado en la funcin genrica. As, por ejemplo, para desplazar una figura, >(defmethod desplazar ((obj figura) dx dy) (incf (centro-x obj) dx) (incf (centro-y obj) dy)) #<STANDARD-METHOD (#<STANDARD-CLASS FG> #<BUILT-IN-CLASS T> #<BUILTIN-CLASS T>)> Ntese que, al estar especializado el mtodo sobre la clase figura, es aplicable a todas sus subclases por herencia, > 0 > 0 > 3 > 2 > 3 (centro-x *cc*) (centro-y *cc*) (desplazar *cc* 2 3) (centro-x *cc*) (centro-y *cc*)
j) El uso de funciones genricas para la invocacin de mtodos permite una serie de caractersticas avanzadas de difcil incorporacin en otros modelos de programacin orientada a objetos. As, por ejemplo, todas las funciones Lisp con argumento funcional aceptarn sin mayor complicacin una funcin genrica, >(mapcar #'diametro (list *cd* *tr* *cc*)) (5.656854 3 4) Podemos mencionar algunas otras caractersticas avanzadas del uso de funciones genricas. En primer lugar, es posible especializar un mtodo sobre ms de una clase, para ello basta con indicar en la lista lambda especializada la clase de ms de un parmetro. Este tipo de mtodos recibe el nombre de multimtodos. Tambin es posible definir un mtodo especializado para una clase y otros adicionales para una o ms de sus subclases. De este modo, para una misma llamada a una funcin genrica puede haber varios mtodos que sean aplicables en cada momento. CLOS permite establecer mecanismos flexibles para decidir cundo y cmo deben combinarse los distintos mtodos aplicables.
8.8
R.8.3. Macro with-slots Supongamos definida la siguente clase: (defclass alumno () ((nom :initarg :nombre :initform (error "Debe proporcionarse un nombre.") :reader nombre) (curso :initarg :curso :initform 1 :accessor curso) (asig :initform '(iaic pl ise)))) a) Definir una operacin ver-asignaturas, que dado un alumno muestre por pantalla las asignaturas en las que est matriculado. b) Definir una operacin cambiar-nombre que dado un alumno y un nombre, cambie el nombre del alumno por el proporcionado. ************************** SOLUCION: a) Por algn motivo, la clase alumno no tiene definidas funciones de acceso para el slot asig, donde se guardan las asignaturas en las que est matriculado cada alumno. Sin embargo, Common Lisp proporciona mecanismos para acceder a cualquier slot en cualquier momento. Emplearemos en este caso la macro with-slots, (with-slots (nom-slot*) instancia expr*) Sea instancia la instancia de una clase que deseamos manipular, y nom-slot* los nombres de los slots a los que deseamos acceder. En el cuerpo de with-slots, cada nombre de slot nom-slot puede emplearse como una variable cuyo valor es el del slot correspondiente. La funcin pedida ser, (defmethod ver-asignaturas ((al alumno)) (with-slots (asig nom) al (format t "~%Lista de asignaturas del alumno ~A:" nom) (dolist (x asig) (print x)))) Podemos probarla de la siguiente forma, > (setf al1 (make-instance 'alumno)) ERROR Debe proporcionarse un nombre. > (setf al1 (make-instance 'alumno :nombre 'pepe)) #<ALUMNO #x1A198A41> > (ver-asignaturas al1) Lista de asignaturas del alumno PEPE IAIC PL ISE NIL b) Tambin es fcil empleando with-slots, (defmethod cambiar-nombre ((al alumno) nom2) (with-slots (nom) al (setf nom nom2))) Podemos probarlo del siguiente modo,
8.9
> (cambiar-nombre al1 'jose) JOSE > (nombre al1) JOSE Sin embargo, ntese que, > (setf (nombre al1) 'luis) ERROR Funcin (setf nombre) no definida. Podemos comprobar pues que las funciones de acceso (reader, writer, accessor) tienen por finalidad mostrar la interfaz pblica de acceso a los slots de una clase. En principio, el usuario de una clase no debera depender de los nombres de los slots, sino de las funciones de acceso. No obstante, Common Lisp no favorece en ningn caso el encapsulamiento de datos. Es decir, empleando los mecanismos adecuados el programador tiene acceso de lectura y escritura a cualquier campo de cualquier instancia.
8.10
R.8.3. Mtodos :before y :after Definir una funcin (ver <objeto>) que, dado un objeto figura como los definidos en R.8.1, muestre su estado por pantalla. ************************** SOLUCION: Una figura viene definida por las coordenadas x,y de su centro geomtrico. Por tanto la definicin pedida es: (defgeneric ver (objeto) (:documentation "Muestra por pantalla el estado del objeto")) (defmethod ver ((f figura)) (format t "~%Coordenadas (x,y): (~s,~s)" (centro-x f) (centro-y f))) Supongamos los siguientes definiciones: > (setf *cc* (make-instance 'circulo :centro-x 10 :centro-y 10 :radio 2)) #<CIRCULO #x1A1BB4D5> > (setf *cd* (make-instance 'cuadrado :centro-x 0 :centro-y 2 :lado 4)) #<CUADRADO #x1A1A0315> > (setf *tr* (make-instance 'triangulo :centro-x 7 :centro-y 0 :lado 3)) #<TRIANGULO #x1A1A6CAD> Es fcil observar que crculos, tringulos y cuadrados heredan el mtodo ver de la clase figura. Sin embargo, su comportamiento no es el deseado, ya que el estado de estos objetos es ms extenso (poseen lado o radio). > (ver *cc*) Coordenadas (x,y): (10,10) NIL Comenzando con los crculos, una solucin podra ser redefinir el mtodo heredado, ocultndolo: (defmethod ver ((cc circulo)) (format t "~%Coord. crculo (x,y): (~s,~s)" (centro-x cc) (centro-y cc)) (format t "~%Radio: ~s" (radio cc))) > (ver *cc*) Coord. crculo (x,y): (10,10) Radio: 2 NIL Sin embargo, esta solucin no es la ms deseable, pues nos obliga a duplicar cdigo en los mtodos de todos los herederos de la clase figura. Afortunadamente CLOS permite dividir el trabajo de una funcin genrica entre varios mtodos. Esto se consigue gracias a la herencia y a la posibilidad de los mtodos de ejercer diversos roles. Los mtodos estudiados hasta el momento se denominan mtodos primarios, pues son los encargados de realizar el grueso del trabajo para una clase dada. Un mtodo primario puede recibir apoyo de mtodos auxiliares. Dos de estos mtodos son los mtodos-before y los mtodos-after. Los mtodos-before se
8.11
ejecutan antes del mtodo primario, y los mtodos after despus. Ambos tienen una finalidad meramente imperativa, pues el valor devuelto ser siempre el del mtodo primario. Los mtodos-before y mtodos-after permiten dividir fcilmente el trabajo entre una clase y sus superclases. En muchos casos una clase proporcionar el mtodo primario para realizar la tarea fundamental, mientras que las clases restantes proporcionarn mtodos auxiliares que se encarguen de los detalles. La funcin ver es un buen ejemplo de ello. Para definir un mtodo como before o after, basta introducir un cualificador en el lugar adecuado. Podemos ampliar la sintaxis bsica de defmethod introducida en R.8.1. (defmethod nombre [cualificador] lista-lambda-especializada expr*) cualificador = :before | :after De este modo, los nuevos mtodos se encargarn nicamente de aadir los detalles propios de su clase5: (defmethod ver :after ((c cuadrado)) (format t "~%Lado: ~s" (lado c))) (defmethod ver :after ((tr triangulo)) (format t "~%Lado: ~s" (lado tr))) (defmethod ver :after ((cc circulo)) (format t "~%Radio: ~s" (radio cc))) > (ver *cc*) Coordenadas (x,y): (10,10) Radio: 2 NIL > (ver *cd*) Coordenadas (x,y): (0,2) Lado: 4 NIL El funcionamiento bsico de la funcin genrica es el siguiente : 1. Se llaman todos los mtodos-before aplicables del ms especfico al ms general. 2. Se llama al mtodo primario aplicable ms especfico. 3. Se llaman todos los mtodos-after aplicables del ms general al ms especfico.
6
En caso de que hubiramos definido el mtodo ver para crculos, podemos deshacernos de el dinmicamente empleando la funcin remove-method, (remove-method (symbol-function 'ver) (find-method (symbol-function 'ver) nil (list (find-class 'circulo)))) 6 Este funcionamiento bsico puede modificarse empleando mtodos-around y la funcin (callnext-method).
8.12
R.8.4. Un tablero para el Conecta-4. Consideremos el problema del conecta-4 en un tablero 6 x 7, o de modo ms general, el conecta-k en un tablero n x m. Definir una clase tablero para el juego del conecta-k que responda a la siguiente interfaz,
(defun hacer-tablero-vacio (&key nfilas ncolumnas contenido-inicial)) (defgeneric soltar-ficha (tablero columna ficha) (:documentation Devuelve un nuevo tablero resultante de soltar la ficha en la columna)) (defgeneric nfilas (tablero) (:documentation Numero de filas del tablero)) (defgeneric ncolumnas (tablero) (:documentation Numero de columnas del tablero)) (defgeneric contenido (tablero f c) (:documentation Contenido del tablero en la fila f, columna c)) (defgeneric pos-valida (tablero f c) (:documentation T si (f,c) es una posicin del tablero)) (defgeneric columna-libre (tablero c) (:documentation "T si es posible soltar alguna ficha en la columna c")) (defgeneric ver (obj) (:documentation Muestra el estado del objeto por pantalla) (defgeneric conectadas (tablero f c df dc) (:documentation Numero de fichas iguales a la de la posicin (f,c) en la direccin df,dc))
************************** SOLUCION: Representaremos internamente un tablero como un array bidimensional. Nos ser muy til en adelante la siguiente funcin que crea una copia de un array bidimensional. (defun copy-matriz (m) (let ((m2 (make-array (array-dimensions m)))) (dotimes (f (array-dimension m 0) m2) (dotimes (c (array-dimension m 1)) (setf (aref m2 f c) (aref m f c)))))) El estado de un tablero vendr definido por el propio array, as como por el valor guardado en cada casilla para indicar si est o no vaca. (defclass tablero () ((m :initarg :matriz :accessor matriz) (pv :initarg :pvacia :reader pvacia)))
;matriz ;contenido de una posicin vaca
Consideremos ahora los constructores. El primero, hacer-tablero-vacio, crear un tablero nuevo con las casillas vacas. El segundo, soltar-ficha recibir un tablero, una columna y una ficha, y devolver dos valores: un nuevo tablero igual que el original y donde adems se ha soltado una ficha por la columna indicada; y adicionalmente la fila donde qued colocada la ficha. (defun hacer-tablero-vacio (&key (nfil 3) (ncol 3) (ini #\_)) (make-instance 'tablero :matriz (make-array (list nfil ncol) :initial-element ini) :pvacia ini))
8.13
(defmethod soltar-ficha ((tab tablero) c ficha) (let* ((m (copy-matriz (matriz tab))) (fila (dotimes (f (array-dimension m 0)) (when (equal (pvacia tab) (aref m f c)) (setf (aref m f c) ficha) (return f)))) (tab2 (make-instance 'tablero :matriz m :pvacia (pvacia tab)))) (values tab2 fila)))
Definiremos tambin selectores para consultar las dimensiones de un tablero, el contenido de una posicin dada, y si una posicin dada pertenece o no al tablero. (defmethod nfilas ((tab tablero)) (array-dimension (matriz tab) 0)) (defmethod ncolumnas ((tab tablero)) (array-dimension (matriz tab) 1)) (defmethod contenido ((tab tablero) f c) (aref (matriz tab) f c)) La siguiente funcin nos muestra el estado de un tablero por pantalla, cuidando de mostrar la fila 0 abajo, y una leyenda debajo indicando el ndice de cada columna. (defmethod ver ((tab tablero)) (let ((nfilas (nfilas tab)) (ncolumnas (ncolumnas tab))) ;muestra el contenido del tablero en el primer cuadrante (dotimes (f nfilas tab) (format t "~% ") (dotimes (c ncolumnas) (princ (contenido tab (- nfilas (1+ f)) c)))) ;muestra debajo de cada columna su ndice (format t "~% ") (dotimes (c ncolumnas) (princ #\=)) (format t "~% ") (dotimes (c ncolumnas) (princ (mod c 10))) (terpri))) Podemos pasar ya a definir las restantes operaciones sobre tableros, que nos permiten consultar cundo es posible colocar una ficha en una posicin dada del tablero. (defmethod pos-valida ((tab tablero) f c) "T si (f,c) es una posicin del tablero" (and (<= 0 f (1- (nfilas tab))) (<= 0 c (1- (ncolumnas tab))))) (defmethod columna-libre ((tab tablero) c) "T si es posible soltar alguna ficha en la columna c" (equal (pvacia tab) (contenido tab (1- (nfilas tab)) c))) Esta ltima operacin nos permitir comprobar fcilmente ms adelante, si se han podido conectar k fichas en el tablero. (defmethod conectadas ((tab tablero) f c df dc) "nmero de fichas iguales conectadas con (f,c) en la direccin df, dc" (let ((ficha (contenido tab f c))) (+ (contar tab f c df dc ficha) (contar tab f c (- df) (- dc) ficha) -1))) ; (f,c) se cuenta 2 veces
8.14
(defmethod contar ((tab tablero) f c df dc ficha &optional (ac 0)) (if (and (pos-valida tab f c) (equal (contenido tab f c) ficha)) (contar tab (+ f df) (+ c dc) df dc ficha (1+ ac)) ac))
Podemos crear algunos tableros y realizar alguna prueba. > (setf *t1* (hacer-tablero-vacio :nfil 3 :ncol 3)) #<TABLERO #x1A1AB399> > (ver *t1*) ___ ___ ___ === 012 > (setf *t2* (soltar-ficha *t1* 0 'X)) #<TABLERO #x1A1E8E3D> > (ver *t2*) ___ ___ X__ === 012 > (setf *t3* (soltar-ficha *t2* 0 'O)) #<TABLERO #x1A179AA9> > (ver *t3*) ___ O__ X__ === 012 > (setf *t4* (soltar-ficha *t3* 1 'X)) #<TABLERO #x1A1789C5> > (ver *t4*) ___ O__ XX_ === 012 CL-USER> (conectadas *t4* 0 0 0 1) 2
8.15
R.8.5. Estado del juego del Conecta-k. Consideremos el juego del conecta-k con dos jugadores que usan fichas diferentes y se alternan en sus movimientos. Definir una clase para representar los distintos estados en que puede encontrarse el juego del conecta-k, que responda a la siguiente interfaz,
(defun hacer-conectak-inicial (&optional nfil ncol long-ganadora) (defgeneric hijos (e) (:documentation Lista de estados directamente accesibles desde e)) (defgeneric agotado (e) (:documentation T si e es final y hay empate, NIL en otro caso)) (defgeneric ganador (e) (:documentation Ficha del jugador que ha ganado, o NIL si nadie gan en e)) (defgeneric jug1? (e) (:documentation T si es el turno del primer jugador, NIL en otro caso)) (defgeneric ver (obj) (:documentation Muestra el estado del objeto por pantalla)
************************** SOLUCION: Adems del tablero del juego, el estado viene representado por el turno del jugador al que le toca jugar. Para determinar cundo ha terminado el juego, ser interesante conservar la longitud ganadora, las fichas del juego, y la posicin del tablero sobre la que se realiz el ltimo movimiento. Tambin llevaremos la cuenta del nmero de movimientos realizados (iteraciones del juego). (defclass conectak () ((k :initform 4 :initarg :long-ganadora :reader long-ganadora) (it :initform 0 :initarg :it :reader it) (j1? :initform nil ;le toca mover al :initarg :jug1? :reader jug1?) (fj1 :initform #\X ;ficha del jugador :initarg :ficha1 :reader ficha1) (fj2 :initform #\O ;ficha del jugador :initarg :ficha2 :reader ficha2) (tbl :initarg :tablero ;tablero del juego :reader tablero) (um :initform nil ;ltimo movimiento :initarg :ultimo-mov :reader ultimo-mov))) (defmethod ficha-actual ((e conectak)) "Ficha del jugador al que le toca jugar" (if (jug1? e) (ficha1 e) (ficha2 e))) (defmethod ficha-otro ((e conectak)) "Ficha del jugador contrario al que le toca jugar" (if (jug1? e) (ficha2 e) (ficha1 e)))
jugador 1?
realizado
8.16
La siguiente funcin nos permite construir un estado inicial del juego (tablero vaco, le toca al primer jugador). El mtodo ver nos permite mostrarlo por pantalla. (defun hacer-conectak-inicial (&optional (nfil 6) (ncol 7) (long-ganadora 4)) (make-instance 'conectak :long-ganadora long-ganadora :it 0 :jug1? T :tablero (hacer-tablero-vacio :nfil nfil :ncol ncol) :ultimo-mov nil)) (defmethod ver ((ck conectak)) (format t "~%It: ~S *****~%" (it ck)) (ver (tablero ck)) (format t "~%Longitud ganadora: ~s" (long-ganadora ck)) (format t "~%ltimo movimiento: ~s" (ultimo-mov ck)) (format t "~%Ficha jugador 1: ~A Ficha jugador 2: ~A" (ficha1 ck) (ficha2 ck)) (format t "~%Le toca jugar al jugador ~s~%" (if (jug1? ck) 1 2)) (values)) La funcin hijos nos permite examinar todas las posibles continuaciones del juego. Esta funcin nos resultar muy til en lecciones posteriores, cuando construyamos programas capaces de jugar por s solos. Para implementar hijos usaremos en este caso dos funciones que nos resultarn convenientes. En este juego podemos numerar las posibles jugadas teniendo en cuenta que cada movimiento posible corresponde a soltar una ficha en una columna determinada. La funcin elegir-suc-nth recibir un nmero de columna y un estado, y devolver el estado de soltar una ficha en la columna indicada. Como no siempre ser posible realizar todos los movimientos, definiremos tambin la funcin posiblep, que nos devolver cierto si es posible realizar el movimiento indicado. (defmethod posiblep (n (e conectak)) "T si es posible soltar una ficha en la columna n en el estado e" (and (<= 0 n (1- (ncolumnas (tablero e)))) (columna-libre (tablero e) n))) (defmethod elegir-suc-nth (n (e conectak)) "estado resultado de mover en la columna n en el estado e" (multiple-value-bind (tab2 f) (soltar-ficha (tablero e) n (ficha-actual e)) (make-instance 'conectak :it (1+ (it e)) :jug1? (not (jug1? e)) :tablero tab2 :ultimo-mov (list f n) :ficha1 (ficha1 e) :ficha2 (ficha2 e) :long-ganadora (long-ganadora e)))) Por tanto, el mtodo hijos puede definirse fcilmente del siguiente modo: (defmethod hijos ((e conectak)) (let ((lhijos nil)) (dotimes (i (ncolumnas (tablero e)) lhijos) (when (posiblep i e) (push (elegir-suc-nth i e) lhijos)))))
8.17
Por ltimo, nos queda determinar cundo ha terminado el juego. Las siguientes operaciones se encargan de ello. (defmethod agotado ((e conectak)) "Cierto si ya se realizaron todos los movimientos posibles" (= (it e) (* (ncolumnas (tablero e)) (nfilas (tablero e))))) (defmethod finalp ((e conectak)) "pieza del jugador que ha ganado, o nil (let* ((mov (ultimo-mov e)) (f (car mov)) (c (cadr mov)) (tab (tablero e))) (when (and mov (<= (long-ganadora e) (max (conectadas tab f (conectadas tab f (conectadas tab f (conectadas tab f (ficha-otro e)))) Podemos realizar algunas pruebas, > (setf *e1* (hacer-conectak-inicial 3 3 3)) #<CONECTAK #x1A1B60D5> > (ver *e1*) It: 0 ***** ___ ___ ___ === 012 Longitud ganadora: 3 ltimo movimiento: NIL Ficha jugador 1: X Ficha jugador 2: O Le toca jugar al jugador 1 > (setq *e2* (elegir-suc-nth 0 *e1*)) #<CONECTAK #x1A1F2269> > (ver *e2*) It: 1 ***** ___ ___ X__ === 012 Longitud ganadora: 3 ltimo movimiento: (0 0) Ficha jugador 1: X Ficha jugador 2: O Le toca jugar al jugador 2 si no ha ganado ninguno"
c c c c
1 0) 0 1) -1 1) 1 1))))
8.18
> (setf *e3* (elegir-suc-nth 1 *e2*)) #<CONECTAK #x1A1A58D1> > (setf *e4* (elegir-suc-nth 0 *e3*)) #<CONECTAK #x1A1C5CC5> > (setf *e5* (elegir-suc-nth 1 *e4*)) #<CONECTAK #x1A1CC231>
> (setf *e6* (elegir-suc-nth 0 *e5*)) #<CONECTAK #x1A1D27AD> > (ver *e6*) It: 5 ***** X__ XO_ XO_ === 012 Longitud ganadora: 3 ltimo movimiento: (2 0) Ficha jugador 1: X Ficha jugador 2: O Le toca jugar al jugador 2 > (finalp *e6*) #\X
8.19
R.8.6. Juguemos al Conecta-k. Supongamos que toda clase que representa un jugador implementa la siguiente interfaz: (defgeneric mueve (jugador estado) (:documentation "Estado resultante de que el jugador mueva en el estado.")) a) Definir una funcin que reciba dos jugadores y el estado inicial de un juego, y controle el desarrollo del mismo hasta que la partida haya terminado. Suponer que los jugadores y el estado del juego implementan las interfaces ya definidas. La funcin devolver 1, 0, -1, segn gane el primer jugador, haya empate, o gane el segundo jugador, respectivamente. b) Definir las clases y mtodos necesarios para representar dos tipos de jugadores: el primero realizar movimientos aleatorios, y el segundo preguntar por teclado el movimiento a realizar. ************************** SOLUCION: a) La siguiente funcin es independiente de la clase de juego e y de las clases de los jugadores jug1 y jug2, siempre y cuando todas ellas implementen las interfaces establecidas. Aadiremos a la funcin un parmetro adicional eco, que nos permitir opcionalmente mostrar por pantalla el desarrollo del juego. (defun jugar (jug1 jug2 e &optional (eco T)) (when eco (ver e)) (cond ((ganador e) (if (jug1? e) -1 1)) ((agotado e) 0) (t (let ((jug (if (jug1? e) jug1 jug2))) ;le toca a jug (jugar jug1 jug2 (mueve jug e) eco ))))) b) El caso ms sencillo es un jugador aleatorio. Podemos definir fcilmente la clase y el mtodo mueve. Ntese que este jugador puede jugar a cualquier juego que implemente el mtodo hijos. (defclass jugador-aleatorio () ()) (defmethod mueve ((j jugador-aleatorio) e) (let ((lh (hijos e))) (elt lh (random (length lh))))) (defun hacer-jugador-aleatorio () (make-instance 'jugador-aleatorio)) La creacin de un jugador que pida el movimiento a realizar por teclado ya no se puede hacer de forma genrica, ya que cada juego puede tener distintos tipos de movimientos. A continuacin se define una clase jugador-humano, y un mtodo mueve vlido para la implementacin del conecta-k estudiada en la seccin anterior. Concretamente, aprovecharemos los mtodos posiblep y elegir-suc-nth. El mtodo mueve pide una columna sobre la que soltar una ficha hasta que el usuario devuelve una columna vlida: (defclass jugador-humano () ()) (defmethod mueve ((j jugador-humano) (e conectak)) (format t "~%En qu columna soltamos la ficha?") (let ((c (read))) (if (posiblep c e) (elegir-suc-nth c e) (mueve j e)))) (defun hacer-jugador-humano () (make-instance 'jugador-humano))
8.20
Para poder jugar a otros juegos, bastar con definir nuevos mtodos mueve, especializados para las distintas clases de juegos. Las siguientes funciones crean partidas entre un jugador aleatorio y otro humano, as como entre dos jugadores aleatorios (en realidad, podra ser el mismo). (defun juega0 (&optional (eco T)) (jugar (hacer-jugador-aleatorio) (hacer-jugador-humano) (hacer-conectak-inicial) eco)) (defun juega1 (&optional (eco T)) (jugar (hacer-jugador-aleatorio) (hacer-jugador-aleatorio) (hacer-conectak-inicial) eco)) Ms adelante desarrollaremos adversarios ms dignos para nuestra inteligencia.
8.21

Inteligencia Artificial e I.C. 2004/2005 1.3 Dpto. Leng. Ciencias Comp

Cargado por

Información del documentohacer clic para expandir la información del documento

Copyright:

Formatos disponibles

Inteligencia Artificial e I.C. 2004/2005 1.3 Dpto. Leng. Ciencias Comp

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Inteligencia Artificial e I.C. 2004/2005 1.3 Dpto. Leng. Ciencias Comp

Cargado por

Copyright:

Formatos disponibles

R.1.1. Concepto de expresin. Evaluacin de nmeros y listas.

Inteligencia Artificial e I.C. 2004/2005

Dpto. Leng. Ciencias Comp.

c) (/ (+ 3 2 1) (- 5 3)) 6 2 3 d) Error: (+) es una lista. e) Error: 2 es un nmero.

Inteligencia Artificial e I.C. 2004/2005

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005 1.10

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005 1.11

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005 1.12

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005 1.13

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005 1.14

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005 1.15

Dpto. Leng. Ciencias Comp.

Inteligencia Artificial e I.C. 2004/2005 1.16

Dpto. Leng. Ciencias Comp.

algn argumento no numrico

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

n m, n, m 0. Para ello se har uso de

n n n 0 = 0, n > 0; m = 0, n < m; n = 1 n n 1 n 1 m= (n-1) m + m 1 en otro caso

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.

; 3 veces el lado ;4 veces el lado ;2pi veces el radio

Inteligencia. Artificial e I.C.. 2004/05

Dpto. Leng. Ciencias Comp.