(defun interprete-interactivo (prompt transformacion)
"Lee una expresion, la transforma e imprime el resultado"
(loop
(handler-case
(progn
(if (stringp prompt)
(print prompt)
(funcall prompt))
(print (funcall transformacion (read))))
;; en caso de error hacer esto:
(error (condicion)
(format t "~&;; Error: ~a ignorado, regrese al terminal."
condicion)))))
(defun prompt-generador (&optional (num 0) (cont-cad "[~d] "))
"Devuelve una funcion que imprime el prompt de la forma [1],[2],etc."
#'(lambda () (format t cont-cad (incf num))))
Una herramienta de coincidencia de patrones
La funcion patron-coincide fue una funcion de coincidencia de patrones hecha especificamente para el programa ELIZA. Los programas subsiguientes necesitaran concidencia de patrones tambien, y antes que escribir funciones especificas para cada nuevo programa es mas facil definir uno general que pueda cubrir la mayoria de las necesidades y sea extensible para cubrir las nuevas necesidades. El problema de diseñar una herramienta general es decidir que caracteristicas proveera. Podemos definir caracteristicas que sean utiles, pero es tambien una buena idea hacer la lista de caracteristicas abierta, asi que una nueva puede ser agregada facilmente cuando sea necesario. Las caracteristicas pueden ser agregadas por generalizacion o especializacion. Por ejemplo, si proveemos variables de segmento que coinciden con cero o mas elementos de entrada. Podemos especializar esto proveyendo un tipo de variable de segmento que hace coincidir uno o mas elementos o para una variable opcional que hace coincidir cero o un elemento. Otra posibilidad es generalizar las variables de segmento para especificar una coincidencia de m a n elementos. Esas ideas vienen de la experiencia con notaciones para la escritura de expresiones regulares, asi como de la heuristica general para la generalizacion, tal como "considerar importante a los casos especiales" y "cero y uno son considerados como importantes casos especiales".
Otra caracteristica util es permitir al usuario especificar un predicado arbitrario que debe satisfacer la coincidencia. La notacion (?es ?n numberp) seria usada para coincidir cualquier expresion que ed un numero y buscarla para la variable ?n. Esto luciria como:
> (patron-coincide '(x = (?es ?n numberp)) '(x = 34))
((?N . 34))
> (patron-coincide '(x = (?es ?n numberp)) '(x = x))
NIL
Debido a que los patrones son como expresiones booleanas, esto hace que construyamos operadores booleanos en ellos. Siguiendo la convencion del signo de pregunta, usaremos ?and ?or y ?not * para los operadores.
* Una alternativa podria ser reservar el signo de pregunta para las variables solamente y usar otra notacion para estos operadores. Las claves podrian ser una buena opcion, tales como :and, :or, :es, etc.
Se muestra a continuacion un patron que hace coincidir una expresion relaciomal con una de las tres relaciones. Esto tiene exito porque el < coincide con una de las tres posibilidades especificadas por (?or < = >).
> (patron-coincide '(?x (?or < = >) ?y) '(3 < 4)
((?Y . 4) (?X . 3))
A continuacion se muestra un ejemplo de un patron ?and que chequea si una expresion es un numero y ademas es impar.
> (patron-coincide '(x = (?and (?es ?n numberp) (?es ?n oddp)))
'(x = 3))
((?N . 3))
El patron siguiente usa ?not para comprobar que dos partes no son iguales:
> (patron-coincide '(?x =/ (?not ?x)) '(3 =/ 4))
((?X . 3))
Hemos visto antes la notacion de coincidencia de segmentos. Esta es aumentada para permitir tres posibilidades: cero o mas expresiomes, una o mas expresiones y cero o una expresion. Finalmente la notacion (?if exp) puede ser usada para probar ina relacion entre algunas variables. Es mejor que esten listadas como un patron de segmento antes que un patron simple debido a que de ese modo no consumen cualquiera de las entradas en todas:
> (patron-coincide '(?x > ?y (?if (> ?x ?y))) '(4 > 3))
((Y . 3) (X . 4))
Cuando la descripcion de un problema es complicada es una buema idea intentar una especificacion mas formal. La siguiente tabla describe una gramatica de patrones, usando las mismas reglas gramaticales descritas en el capitulo 2.
pat => var coincide con cualquier expresion
constante solo coincide este atomo
segmento-pat coincide con alguna secuencia
simple-pat coincide con alguna expresion
(pat . pat) coincide el primero y el resto
simple-pat => (?es var predicado) verifica el predicado en una expresion
(?and pat...) coincide con todos los patrones en una expresion
(?or pat...) coincide con cualquier patron en una expresion
(?not pat...) es exitosa si el/los patron/es no coincide/n
segmento-pat => ((?* var) ...) coincide con cero o mas expresiones
((?+ var) ...) coincide con una o mas expresiones
((?? var) ...) coincide con cero o una expresion
((?if exp) ...) verifica si se cumple exp (que puede
contener variables
var => ?caracteres un simbolo que comienza con ?
constante => atom cualquier atomo que no sea una
variable
A pesar de la complejidad agregada todos los patrones pueden ser clasificador en cinco casos. Los patrones deben ser variable, constante, un patron de segmento (generalizado), un patron simple (generalizado) o una lista de dos patrones. La siguiente definicion de patron-coincide refleja los cinco casos (con dos verificaciones para fallas):
(defun patron-coincide (patron entrada &optional (enlaces sin-enlaces))
"Coincidencia de patrones preparando la entrada en el ambito de los enlaces"
(cond ((eq enlaces falla) falla)
((variable-p patron)
(coincidir-variable patron entrada enlaces))
((eql patron entrada) enlaces)
((segmento-patron-p patron)
(segmento-coincide patron entrada enlaces))
((simple-patron-p patron) ;***
(simple-coincide patron entrada enlaces)) ;***
((and (consp patron) (consp entrada))
(patron-coincide (rest patron) (rest entrada)
(patron-coincide (first patron) (first entrada)
enlaces)))
(t falla)))
Para completar, repetimos aqui las constantes y las funciones de bajo nivel de ELIZA:
(defconstant falla nil "Indica que patron-coincide falla")
(defconstant sin-enlaces '((t . t))
"Indica el exito de patron-coincide, sin variables.")
(defun variable-p (x)
"x es una variable? (un simbolo que comienza con '?')"
(and (symbolp x) (equal (char (symbol-name x) 0) #\?)))
(defun obtener-enlace(var enlaces)
"Busca un par (variable . valor) en una lista de enlaces."
(assoc var enlaces))
(defun enlace-var(enlace)
"Obtiene la variable de un enlace."
(car enlace))
(defun enlace-val(enlace)
"Obtiene el valor de un enlace."
(cdr enlace))
(defun crear-enlace (var val) (cons var val))
(defun buscar(var enlaces)
"Obtiene el valor (para var) de una lista de enlaces."
(enlace-val (obtener-enlace var enlaces)))
(defun extender-enlaces(var valor enlaces)
"Agrega un par (var . value) a la lista de enlaces."
(cons (cons var valor)
;; Una vez que agregamos un enlace "real",
;; podemos eliminar el tonto sin-enlaces
(if (eq enlaces sin-enlaces)
nil
enlaces)))
(defun coincidir-variable (var entrada enlaces)
"Coincide VAR con entrada? Usa (o actualiza) y devuelve los enlaces."
(let ((enlace (obtener-enlace var enlaces)))
(cond ((not enlace) (extender-enlaces var entrada enlaces))
((equal entrada (enlace-val enlace)) enlaces)
(t falla))))
El siguiente paso es definir los predicados que reconocen segmentos generalizados, los patrones simples y las funciones de coincidencia que operan en ellos. Podriamos implementar segmento-coincide y simple-coincide con declaraciones que consideran todos los casos posibles. Sin embargo podria ser dificil extender estas funciones. Un programador que quiere agregar un nuevo tipo de patrones de segmento tendria que editat las definiciones de ambos segmento-coincide y simple-coincide para instalar la nueva caracterisitica. Esto en si mismo, ouede no ser muy malo, pero considere que pasa cuando dos programadores agregan caracteristicas de manera independientemente. Si quieres usar ambos, ninguna de las versiones de segmento-coincide (o simple coincide) funcionará. Tendras que editar todas lss funciones nuevamente solo para mantener las dos extensiones.
La solucion para este dilema es escribir una version de segmento-coincide, de una vez por todas, pero teniendo esas funciones referidas a una tabla de pares patron/accion. La tabla diria, "si tu ves ?* en el patron, entonces usa segmento-coincide" y asi sucesivamente. Luego, programadores que quieren extender esta funcion solo deben agregar entradas a la tabla. Y esto es trivial para mantener diferentes extensiones (sin tener en cuenta, por supuesto, que dos programadores hayan elegido exactamente los mismos simbolos para realizar distintas acciones).
Este estilo de programacion, donde los pares patron/accion son almacenados en una tabla, es llamada "programacion conducida por datos". Este es un estilo muy flexible que es apropiado para escribir sistemas extensibles.
Hay muchas maneras de implementsr tablas en Common-lisp, como due tratado en la seccion 3.6 en la pagina 73. En este caso, las claves de la tabla seran los símbolos (como ?*), y eso esta bien si la representación de la tabla esta distribuida en la memoria. De esta manera las listas de propiedades son una opcion apropiada. Tendremos dos tablas, representadas por la propiedad segmento-coincide y la propiedad simple-coincide de simbolos como ?*. El valor de cada propiedad será el nombre de la función que implementa la coincidencia. Aqui tenemos las entradas de la tabla para implementar la gramática listada previamente.
(setf (get '?es 'simple) 'funcion-es)
(setf (get '?and 'simple) 'funcion-and)
(setf (get '?or 'simple) 'funcion-or)
(setf (get '?not 'simple) 'funcion-not)
(setf (get '?* 'segmento) 'segmento)
(setf (get '?+ 'segmento) 'segmento+)
(setf (get '?? 'segmento) 'segmento?)
(setf (get '?if 'segmento) 'funcion-if)
Con la tabla definida, necesitamos hacer dos cosas. Primero definimos el "pegamento" que mantiene la tabla unida: las funciones de predicado y acción tomada. Una función que luce como una función conducida por datos y la llama (tales como segmento-coincide y simple-coincide), es llamada una funcion de reparto.
(defun segmento-patron-p (patron)
"Es este un patron de coincidencia de segmento?: (?* var) . pat)"
(and (consp patron) (consp (first patron))
(symbolp (first (first patron)))
(segmento-funcion (first (first patron)))))
(defun simple-patron-p (patron)
"Es este un patron de coincidencia simple?
Ej. (?es x predicado) (?and . patrones) (?or . patrones)"
(and (consp patron)
(simple-funcion (first patron))))
(defun segmento-coincide (patron entrada enlaces)
"Llama a la funcion correcta para este tipo de patron de segmento."
(funcall (segmento-funcion (first (first patron)))
patron entrada enlaces))
(defun simple-coincide(patron entrada enlaces)
"Llama a la funcion correcta para este tipo de patron simple"
(funcall (simple-funcion (first patron))
(rest patron) entrada enlaces))
(defun segmento-funcion (x)
"Obtener la funcion de segmento para x,
si este es un simbolo que tiene una"
(when (symbolp x) (get x 'segmento)))
(defun simple-funcion (x)
"Obtener la funcion simple para x"
(when (symbolp x) (get x 'simple)))
La ultima cosa para hacer es definir las funciones individuales de coincidencia. Primero las funciones de coincidencia de simple-patron:
(defun funcion-es (var-y-pred entrada enlaces)
"Aprueba y enlaza var si la entrada satisface pred,
donde var-y-pred es la lista (var pred)."
(let* ((var (first var-y-pred))
(pred (second var-y-pred))
(nuevos-enlaces (patron-coincide var entrada enlaces)))
(if (or (eq nuevos-enlaces falla)
(not (funcall pred entrada)))
falla
nuevos-enlaces)))
(defun funcion-or (patrones entrada enlaces)
"Tiene exito si alguno de los patrones coinciden con la entrada"
(if (null patrones)
falla
(let ((nuevos-enlaces (patron-coincide
(first patrones)
entrada enlaces)))
(if (eq nuevos-enlaces falla)
(funcion-or (rest patrones) entrada enlaces)
nuevos-enlaces))))
(defun funcion-and (patrones entrada enlaces)
"Tiene exito si todos los patrones coinciden con la entrada"
(cond ((eq enlaces falla) falla)
((null patrones) enlaces)
(t (funcion-and (rest patrones)
entrada
(patron-coincide (first patrones) entrada
enlaces)))))
(defun funcion-not (patrones entrada enlaces)
"Tiene exito si ninguno de los patrones coinciden con la entrada
nunca enlazara variables."
(if (funcion-or patrones entrada enlaces)
falla
enlaces))
Ahora las funciones de coincidencia de segmento-patron. Segmento-coincide es similar a la version presentada como parte de ELIZA. La diferencia esta en como determinamos pos, la posicion del primer elemento de la entrada que podria coincidir con el siguiente elemento del patron despues de la variable de segmento. En eliza hemos asumido que la variable de segmento fue tanto el ultimo elemento del patron como lo fue el seguido por una constante. En la siguiente version, permitimos patrones no constantes para las variables de segmento. La funcion primera-pos es agregada para manejar esto. Si el siguiente elemento es de hecho una constante, el mismo calculo es hecho usando "position". Si este no es una constante, entonces solo devolvemos la primera posicion posible del inicio. A menos que deba ponerlo antes al final de la entrada, en cuyo caso devolvemos nil para indicar falla:
(defun segmento (patron entrada enlaces &optional (inicio 0))
"Coincide el patron de segmento ((?* var) . pat) con la entrada"
(let ((var (second (first patron)))
(pat (rest patron)))
(if (null pat)
(coincidir-variable var entrada enlaces)
(let ((pos (primera-pos (first pat) entrada inicio)))
(if (null pos)
falla
(let ((b2 (patron-coincide
pat (subseq entrada pos)
(coincidir-variable var (subseq entrada 0 pos)
enlaces))))
;;si esta coincidencia falla, intenta otra mas larga
(if (eq b2 falla)
(segmento patron entrada enlaces (+ pos 1))
b2)))))))
(defun primera-pos (pat1 entrada inicio)
"Busca la primera posicion con que pat1 posiblemente coincidiria con la entrada,
comenzando en la posicion inicio. Si pat1 es no-constante entonces
solo devuelve inicio."
(cond ((and (atom pat1) (not (variable-p pat1)))
(position pat1 entrada :start inicio :test #'equal))
((< inicio (length entrada)) inicio)
(t nil)))
En el primer ejemplo abajo, la variable de segmento ?x coincide con la secuencia (b c). En el segundo ejemplo hay dos variables de segmento en una columna. La primera coincidencia exitosa es lograda con la primer variable, ?x, coincide con la secuencia vacía, y la segunda, ?y, coincide con (b c).
> (patron-coincide '(a (?* ?x) d) '(a b c d))
((?x B C ))
> (patron-coincide '(a (?* ?x) (?* ?y) d) '(a b c d))
((?Y B C) (?X))
En el siguiente ejemplo, ?x coincide con nil y ?y coincide con (b c d), pero falla, de esta manera intentamos hacer coincidir ?x con un segmento de longitud uno. Que falla tambien, pero finalmente la coincidencia es exitosa, con ?x coincidiendo con un segmento de dos elementos (b c) y ?y coincidiendo con (d).
> (patron-coincide '(a (?* ?x) (?* ?y) ?x ?y) '(a b c d (b c) (d)))
((?Y ?D) (?X B C))
Dada la coincidencia de segmentos, es facil definir las funciones para coincidir uno o mas elementos y la funcion para coincidir cero o un elemento:
(defun segmento+ (patron entrada enlaces)
"Coincide con uno o mas elementos de la entrada"
(segmento patron entrada enlaces 1))
(defun segmento? (patron entrada enlaces)
"Coincide con cero o un elemento de la entrada"
(let ((var (second (first patron)))
(pat (rest patron)))
(or (patron-coincide (cons var pat) entrada enlaces)
(patron-coincide pat entrada enlaces))))
Finalmente, abasteceremos la funcion para probar una pieza arbitraria de codigo Lisp. Ella hace esto mediante la evaluacion del codigo con los enlaces implicados en la lista de enlaces. Este es uno de los pocos casos donde es apropiado llamar a eval: cuando queremos dar al usuario acceso irrestricto al interprete Lisp.
(defun funcion-if (patron entrada enlaces)
"Prueba una expresion arbitraria envolviendo variables.
El patron luce como ((?if codigo) . rest)"
(and (progv (mapcar #'car enlaces)
(mapcar #'cdr enlaces)
(eval (second (first patron))))
(patron-coincide (rest patron) entrada enlaces)))
