Inteligencia Artificial: Creacion de herramientas de software

Hola amigos. Sigo traduciendo el libro de Peter Norvig. Dejo el link del libro en ingles (Esta en formato djvu). Si alguien quiere ayudarme con la traduccion, me avisa y lo agrego como colaborador. Aqui dejo el enlace con el archivo.lisp que tiene las funciones tratadas en esta entrada.

En las secciones anteriores vimos lo comcerniente a dos programas particulares SGP y ELIZA. Ahora volveremos a examinar estos dos programas para descubrir algunos patrones comunes. Estos patrones seran abstraidos en forma de herramientas de software reutilizable que seran de gran ayuda en los capitulos siguientes.

Un interprete interactivo

La estructura del programa eliza es comun. La repetimos abajo:

(defun eliza ()

  "Responde a la entrada del usuario usando reglas de coincidencia de patrones."

  (loop

      (print 'eliza>)

      (print  (aplanar (usar-reglas-eliza (read *query-io*))))))

Muchas otras aplicaciones usan este patron, incluido el mismo Lisp. El terminal lisp podria ser definido asi:

(defun lisp ()

   (loop

      (print '>)

      (print (eval (read)))))

El terminal del sistema lisp historicamente ha sido llamado como el bucle "read-eval-print". La mayoria de los Lisp modernos imprimen un prompt antes de leer la entrada, de esta manera deberia ser realmente llamado el bucle "prompt-read-eval-ptint", pero no habia prompt en algunos sistemas anteriores como MacLisp, y entonces el nombre quedaba mucho mas corto. Si no queremos usar el prompt, podriamos escribir un interprete lisp completo usando solo cuatro simbolos:

(loop (print (eval (read))))

Puede parecer gracioso decir que esos cuatro simbolos y ocho parentesis constituyen un interprete lisp. Cuando escribimos esa linea ¿realmente hemos cumplido con todo? Una respuesta a esa cuestion es considerar que podriamos tener que escribir un interprete lisp (o Pascal) en Pascal. Podriamos necesitar un analizador lexico y un administrador de tabla de simbolos. Esto es una considerable cantidad de trabajo, pero todo es manejado por read. Necesitariamos un analizador sintactico para ensamblar los simbolos lexicos dentro de las declaraciones. read tambien maneja esto, pero solo porque las declaraciones Lisp tienen una sintaxis trivial: la sintaxis de listas y atomos. De esta manera read sirve bien como un analizador sintactico para lisp, pero fallaria para Pascal. Luego necesitaremos la parte de evaluacion o interṕretacion del interprete; eval hace esto de manera amigable, y podria manejar Pascal solo como si interpretaramos sintaxis Pascal dentro de sentencias Lisp. print hace mucho menos trabajo que read o eval, pero sigue siendo practica. 

El punto importante no es que una linea de codigo pueda ser considereda una implementacion de Lisp, sino reconocer patrones comunes de computacion. Tanto Eliza como Lisp pueden ser vistos como interpretes interactivos, que leen una entrada, evaluan o tansforman la entrada de alguna manera, imprimen el resultado y luego vuelven a pedir otra entrada. Podemos extraer los siguientea patrones comunes:

(defun programa

   (loop 

         (print prompt)

         (print (transformar (read)))))

Hay dos naneras de hacer uso de los patrones recursivos: formalmente e informalmente. La alternativa informal es tratar los patrones como un cliche o idioma que ocurre frecuentemente en nuestra escritura de programas pero que variara de uso en uso. Cuando queremos escribir un nuevo programa, recordamos escribir o leer uno similar, vamos para atras y miramos el primer programa, copiamos las secciones relevantes y luego las modificamos para el nuevo programa. Si el borrador es extenso, seria una buena idea insertar comentarios en el nuevo programa, citando al original, pero no habria una conexion "oficial" entre el programa original y su derivado.

La alternativa formal es crear una abstraccion en la forma de funciones y tal vez esrtructuras, y nos referimos explicitamente a esa abstraccion en cada nueva aplicacion -en otras palabras capturamos la abstraccion en la forma de una herramienta de software. El patron interprete puede ser abstraido en una funcion asi:

(defun interprete-interactivo (prompt transformacion)

  "Lee una expresion, la transforma e imprime el resultado"

  (loop

     (print prompt)

     (print (funcall transformacion (read)))))

Esta funcion podria ser usada luego en la escritura de cada nuevo interprete:

(defun lisp()

   (interprete-interactivo '> #'eval))   

(defun eliza ()  

   (interprete-interactivo 'eliza> #'(lambda(x) (aplanar (usar-reglas-eliza x)))))

O con la ayuda de la funcion de alto nivel "compuesta":

(defun compuesta (f g)

  "Devuelve la funcion que calcula (f (g x))"

  #'(lambda(x) (funcall f (funcall g x))))

(defun eliza ()  

   (interprete-interactivo 'eliza> (compuesta #'aplanar #'usar-reglas-eliza)))

Nota del T: vaya despacio...!, pasar funciones como argumentos y escribir funciones que devuelven funciones, son algunas de las caracteristicas potentes de lisp, pero no estamos acostumbrados generalmente a programar de esa manera.

Hay dos diferencias entre los enfoques formal e informal. En primer lugar lucen diferente. Si la abstraccion es simple, como esta, es probablemente mas facil leer una expresion que tuvo el bucle (loop) explicitamente escrito que leer una que llama a interprete-interactivo, ya que requiere buscar la definicion de interprete-interactivo y entenderla. La otra diferencia nos muestra lo que denominamos el mantenimiento. Suponga que buscamos una caracteristica perdida en la definicion del interprete interactivo. Una cuya omision haga que el bucle (loop) no termine. Tengo asumido que el usuario puede terminar el bucle provocando alguna tecla de interrupcion (break o abort). Una implementacion simple permitiria al usuario dar un comando de finalizacion explicito. Otra caracteristica util seria el manejo de errores dentro del interprete. Si usamos el enfoque informal, agregar una caracteristica a un programa no tendria efecto sobre los otros. Pero si usamos el enfoque formal, perfeccionar interprete-interactivo automaticamente traeria las nuevas caracteristicas para todos los programas que lo usan. La siguiente version de interprete-interactivo agrega dos nuevas caracteristicas. Primero utiliza la macro handler-case para manejar errores. Esta macro evalua su primer argumento, y normalmente solo devuelve ese valor. Sin embargo, si ocurre un error, los argumentos posteriores son chequeados por una condicion de error que coincide con el error ocurrido. En este uso, el caso error coincide con todos los errores, y la accion tomada es imprimir la condicion de error y continuar. Esta version tambien permite al prompt ser tanto una cadena de caracteres como una funcion sin argumentos que sera llamada para imprimir el prompt. La funcion prompt-generador, por ejemplo, devuelve una funcion que imprimira el prompt de la forma [1], [2], etcetera.

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