BFS con Lisp

Esta es la primera entrada con Lisp. Lisp es una familia de lenguajes multiparadigma que tiene muchos usos, matemáticos, de IA, entre otros. Una versión de Lisp es, además, el lenguaje en el que se programan las extensiones del popular editor de texto Emacs, creado por Richard Stallman. Tiene una sintáxis que usa millones de paréntesis y tiene facilidades para crear programas del tipo funcional.

Para hacer una pequeña demostración del lenguaje, vamos a implementar un pequeño algoritmo BFS en Lisp. Primero, hacemos algunas definiciones básicas:

(defvar *nodes* '(A B C D E F G H I J))
(defvar *aristas* '((A B) (A C) (B D) (B E) (C F) (C G) (D H) (E H) (F I) (G I) (H J) (I J)))
(defvar *start-point* 'A)
(defvar *end-point* 'J)

(defun bfs (nodepath) nodepath)

(print (bfs '(A)))

¿Qué hicimos acá? Primero, definimos algunas variables arbitrarias que configuran un grafo. La primera, nodos, está sólo a modo decorativo. La segunda, aristas, contiene el grafo en sí. El tercero y el cuarto son los dos puntos entre los cuáles queremos obtener el camino mas corto. Finalmente definimos una función llamada bfs que, en principio, no hace nada, sólo nos devuelve lo que le pasemos. El en último renglón, imprimimos el resultado de la función, que por ahora no hace mas que pasarnos lo que le pasamos (en este caso, una lista que contiene el elemento A).

Modifiquemos un poco la función bfs:

(defun bfs (nodepath) (cond
 ((= (length nodepath) 0) 'ninguno)
 ((= (length nodepath) 1) 'uno)
 (t 'muchos)
))

(print (bfs '(A B)))

Lo que hace ahora la función BFS es, simlemente, si me pasan una lista vacía devuelvo NINGUNO. Si la lista tiene sólo un parámetro devuelvo UNO. Sino, devuelvo MUCHOS. La función t es el else de la función cond (una especie de switch-case en Lisp).

Si lo pensamos un poco, no tiene ningún sentido que le pasemos una lista vacía de nodos a la función BFS, ya que por lo menos tenemos que tener el primer nodo, el start-point. ¡Tenés razón! Modificamos la función:

(defun bfs (nodepath) (cond
 ((= (length nodepath) 1) 'uno)
 (t 'muchos)
))
(trace bfs)
(print (bfs (list *start-point*)))

Usamos trace para depurar la función bfs y ver cómo funciona.

Ahora bien, el BFS funciona agregando a todos los nodos «vecinos» a una cola de procesamiento, en la que primero se procesan los mas próximos. Hacer esto de una manera estructurada es fácil, pero nosotros vamos a intentarlo por la manera recursiva, que debe ser mas sencilla todavía aunque mas difícil de pensar. A priori, tenemos que llamar a la función bfs con el start-point mas el punto vecino, tantas veces como vecinos tenga. ¡Pero entonces tenemos que modificar la función! Empecemos con un caso ideal:

(defun bfs (nodepath) (cond
 ((member *end-point* nodepath) nodepath)
))
(trace bfs)
(print (bfs (list *start-point* *end-point*)))

Es decir, si el *end-point* es parte de la lista nodepath, lo devolvemos. Sino, no hacemos nada. Esta función devuelve el camino mas corto sólo si el end-point está presente la primera vez que lo llamamos. Acá empieza a ponerse confuso, así que vamos de a poquito:

(defun bfs (nodepath) (cond
 ((member *end-point* nodepath) nodepath)
 (t (dolist (item *aristas*)
 (cond
 ((eq (first item) (first (last nodepath)))
 (print item))
 )))
))
(trace bfs)
(print (bfs (list *start-point*)))

Si que cambió, ¿eh? Lo que hace esta función es, simplemente, imprimir las aristas relacionadas con el último nodo que le pasemos como parámetro. Como le estamos pasando uno sólo, la salida de esta función es:

(A B)
(A C)

Perfecto, ya tenemos entonces los nodos relacionados. Ahora apliquemos la magia de la recursividad:

(defun bfs (nodepath) (cond
 ((member *end-point* nodepath) nodepath)
 (t (dolist (item *aristas*)
 (cond
 ((eq (first item) (first (last nodepath)))
 (bfs (append nodepath (last item))))
 (t nodepath)
 )))

; (t (assoc (first (last nodepath)) *aristas*))
))
(trace bfs)
(print (bfs (list *start-point*)))

¿Y qué obtenemos… ?

1. Trace: (BFS ‘(A))
2. Trace: (BFS ‘(A B))
3. Trace: (BFS ‘(A B D))
4. Trace: (BFS ‘(A B D H))
5. Trace: (BFS ‘(A B D H J))
5. Trace: BFS ==> (A B D H J)
4. Trace: BFS ==> NIL
3. Trace: BFS ==> NIL
3. Trace: (BFS ‘(A B E))
4. Trace: (BFS ‘(A B E H))
5. Trace: (BFS ‘(A B E H J))
5. Trace: BFS ==> (A B E H J)
4. Trace: BFS ==> NIL
3. Trace: BFS ==> NIL
2. Trace: BFS ==> NIL
2. Trace: (BFS ‘(A C))
3. Trace: (BFS ‘(A C F))
4. Trace: (BFS ‘(A C F I))
5. Trace: (BFS ‘(A C F I J))
5. Trace: BFS ==> (A C F I J)
4. Trace: BFS ==> NIL
3. Trace: BFS ==> NIL
3. Trace: (BFS ‘(A C G))
4. Trace: (BFS ‘(A C G I))
5. Trace: (BFS ‘(A C G I J))
5. Trace: BFS ==> (A C G I J)
4. Trace: BFS ==> NIL
3. Trace: BFS ==> NIL
2. Trace: BFS ==> NIL
1. Trace: BFS ==> NIL
NIL

¿Algo no está funcionando no? Sin embargo estamos llegando a resultados correctos -> (A B E H J). ¿Como que no estamos cortando donde debiéramos, no? ¡Es exactamente eso! Ni bien llegamos a un resultado correcto (cuando se cumple (member *end-point* nodepath) ) tendríamos que simplemente detenernos ahí. Podemos hacerlo de esta forma:

(defun bfs (nodepath) (cond
; ((member *end-point* nodepath) nodepath)
 ((member *end-point* nodepath) (print nodepath))
 (t (dolist (item *aristas*)
 (cond
 ((eq (first item) (first (last nodepath)))
 (bfs (append nodepath (last item))))
 (t nodepath)
 )))
))
;(trace bfs)
;(print (bfs (list *start-point*)))
(bfs (list *start-point*))

Resultado:

(A B D H J)
(A B E H J)
(A C F I J)
(A C G I J)

¡Perfecto! Ya tenemos un BFS andando. Sin embargo, deberíamos obtener como resultado sólo un camino, no cuatro. Aunque los cuatro sean correctos, el algoritmo debería detenerse en el primer camino correcto. Por otro lado, estaría bueno que la función devolviera el resultado, y no tener que imprimirlo desde adentro. De esta forma podríamos manipular el resultado. Estas cosas trataré de solucionarlas en el siguiente script.

Versión completa del script:

defvar *nodes* '(A B C D E F G H I J))
(defvar *aristas* '((A B) (A C) (B D) (B E) (C F) (C G) (D H) (E H) (F I) (G I) (H J) (I J)))
(defvar *start-point* 'A)
(defvar *end-point* 'J)

(defun bfs (nodepath) (cond
 ((member *end-point* nodepath) (print nodepath))
 (t (dolist (item *aristas*)
 (cond
 ((eq (first item) (first (last nodepath)))
 (bfs (append nodepath (last item))))
 (t nodepath)
 )))
))
(bfs (list *start-point*))

Conclusión: los grafos son algo divertido y emocionante. Lisp es un lenguaje cuya sintáxis es extraña, pero permite realizar cosas complejas en pocas líneas, y de una forma satisfactoria. En el siguiente artículo trataremos de ver si es posible realizar este algoritmo de un modo funcional y que la función se comporte exactamente como queremos.