Arboles con múltiples nodos

Desarrollaremos un árbol múltiple y veremos como recorrerlo y guardarlo. El ejemplo que seguiremos es una estructura en forma de árbol que vi en algún libro, alguna vez y que se utilizaba para ejemplificar un árbol de decisiones que trataba sobre si era conveniente o no ir a jugar al tenis. Le aconsejo que vaya guardando las funciones en un archivo de texto con extensión .lisp, por ejemplo: "arbol.lisp". Cada vez que modifica el archivo fuente, cargue en el interprete la nueva versión con su archivo modificado:

> (load "arbol.lisp")

El árbol de decisión establece que alguien va a jugar tenis, según el clima.

En primer lugar debemos crear una función para guardar los nodos (en un archivo de texto con extension .lisp), sería así:

(defun agregar-nodo (nodo)
  (push nodo *arbol*)) ;vamos metiendo cada nodo en *arbol*

Lo guardamos en la lista global *arbol*. Debemos declararla al principio:

(defvar *arbol* nil) ; y le asignamos a nil

Debemos generar el nodo con una función, es muy fácil:

(defun hacer-nodo(nombre &rest valores)
   (list :nombre nombre :valores valores))

"nombre" es el nombre del nodo, al que se hará referencia. En valores se guarda una lista con los valores del árbol. El primer elemento va a ser la raíz y los demás serán sus ramas. Veamos como cargamos el árbol generando los nodos, a través del interprete:

> (agregar-nodo (hacer-nodo 'clima '("clima" . nil) '("soleado" . humedad) '("nublado" . T) '("lluvioso" . viento)))
(("clima") ("soleado" . HUMEDAD) ("nublado" . T) ("lluvioso" . VIENTO))

CLIMA es el nombre del nodo. Los símbolos HUMEDAD y VIENTO son símbolos a los que daremos los valores correspondientes. En el caso de generar el primer elemento "raíz" del árbol, el primer valor de la lista de valores es la cadena "clima" que es el dato asignado al nodo principal, los valores que siguen son los nodos múltiples.

Ahora creamos el resto de los nodos:

> (agregar-nodo (hacer-nodo 'humedad '("humedad" .  nil) '("normal" . T) '("alta" . nil)))
(("humedad") ("normal" . T) ("alta"))

> (agregar-nodo (hacer-nodo 'viento '("viento" . nil) '("fuerte" . nil) '("debil" . T)))
(("viento") ("fuerte") ("debil" . T))

En este caso va el símbolo y luego los nodos múltiples.
¿Como hacemos para asignar o enlazar a HUMEDAD y VIENTO, los símbolos, con sus respectivos valores...?

Si consultamos estos símbolos veremos que aun no contienen nada y nos dará un error. Incluso debemos tener un símbolo que apunte a la raíz y a sus valores. Para eso les dimos los nombres en :NOMBRE a cada nodo. Debemos crear una función para asignar o enlazar a cada símbolo ":NOMBRE" sus respectivos valores, tanto el de la raíz como sus nodos. De esta manera cada nodo quedará en memoria "en forma de árbol", es decir el símbolo del mismo nombre, por ejemplo HUMEDAD, dentro de la lista de valores, tendrá los nodos asignados como una lista, ya que se le da el mismo nombre ":NOMBRE" cuando se crea el nodo. Parece complicado, pero es fácil, por ejemplo el símbolo VIENTO que se crea en el nodo de nombre CLIMA va a ser el mismo que el símbolo VIENTO cuando se crea el nodo del mismo nombre. Solo que aun estos símbolos no contienen valores. Entonces, creamos la función que realiza dicha asignación:

(defun transforma-nodo-x(nodo) ;Función que transforma un registro de nodo en un nodo en memoria
  (set (getf nodo :nombre) (getf nodo :valores)))

Esta función asigna a cada símbolo en :nombre su lista de valores o nodos múltiples. Ahora bien, tenemos varios nodos, y por lo tanto necesitamos cargar a memoria toda la lista de registros nodos que guardamos en *arbol*, para ello, barrilete cósmico, usamos la siguiente función:

(defun transforma-nodos() ; Función que transforma todos los nodos del árbol y los carga en memoria
  (dolist (nodo *arbol*)
    (transforma-nodo-x nodo)))

Hacemos un (transforma-nodos), y ya podemos constatar que los valores se han cargado:

> clima
(("clima") ("soleado" . HUMEDAD) ("nublado" . T) ("lluvioso" . VIENTO))

> humedad
(("humedad") ("normal" . T) ("alta"))

Debemos modificar la función agregar-registro agregándole la función para cargar un nodo, para que cada vez que creamos un registro nodo, lo cargue en memoria, es decir que le asigne a su nombre los valores correspondientes:

(defun agregar-nodo(nodo) ; Función que agrega un nodo a la lista *arbol*; y a la memoria "nodo-x"
   (push nodo *arbol*)
   (transforma-nodo-x nodo))

Para recorrer el árbol, podemos usar recursividad. Primero accedemos al dato del primer nodo con (first (car ...)), luego aplicando la función recursivamente accedemos al primer elemento de la lista con un first "la raíz", luego con otra llamada recursiva al resto, "los valores", usando un rest. Bueno, menos palabras y mas acción:

(defun mostrar (lista) ;función que muestra todos los nodos
  (when (not (null lista))
    (when (not (equal T lista))
    (format t "~%~5t~s" (car (first lista)))
    (mostrar (eval (cdr (first lista))))
    (mostrar (rest lista)))))

El argumento lista no trata sobre una señorita inteligente, mas bien trata sobre la lista de valores que contiene cada símbolo :NOMBRE, como vimos anteriormente, por ejemplo los símbolos CLIMA, HUMEDAD y VIENTO, los que ya cuentan con valores asignados.

Entonces llamamos a nuestra función para ver los nodos:

> (mostrar clima)

     "clima"
     "soleado"
     "humedad"
     "normal"
     "alta"
     "nublado"
     "lluvioso"
     "viento"
     "fuerte"
     "debil"

Ahí están todos los datos de los nodos. Te preguntarás por que se muestra el árbol sin diferenciar la raíz de sus nodos con alguna especie de dentado o tabulación, es verdad, llevaría mas programación.

¡Ah! ...

¿te habrás dado cuenta que si sales del interprete se borran los nodos cargados en *arbol* y las listas de valores que se cargaron en los símbolos...?

Entonces, antes de salir vamos a crear una función para guardar el árbol en un archivo:

(defun guardar-arbol(archivo) ;Función para guardar los registros nodos de *arbol* en un archivo de salida
  (with-open-file (salida archivo
 :direction :output
 :if-exists :supersede)
    (with-standard-io-syntax
      (print *arbol* salida))))

Pasemos a guardar el archivo con los datos cargados a través del interprete:

> (guardar-arbol "arbol.tree") ;en arbol.tree quedan los datos cargados

Ahora queda cargar esos nodos registro cuando iniciamos:

(defun cargar-arbol (archivo) ;Función para recuperar los nodos de *arbol* desde un archivo de entrada
  (with-open-file (entrada archivo)
    (with-standard-io-syntax
      (setf *arbol* (read entrada)))))

Para cargar hacemos:

> (cargar-arbol "arbol.tree")

Entonces en nuestro archivo "arbol.lisp" agregamos al final:

(cargar-arbol "arbol.tree") ;para cargar los nodos registro al inicio
(transforma-nodos) ;para asignar a los símbolos con los nombres correspondientes sus valores respectivos.
A todo esto le estaría faltando una función que recorra el árbol y haga las preguntas para decidir si voy a jugar al tenis. Así que agregamos estas funciones a nuestro archivo "arbol.lisp", que nos ayudarán a decidir:

(defun leer-mensaje(mensaje) ;función que muestra un msj en pantalla y devuelve un valor ingresado
(format *query-io* "~%~%~a: " mensaje)
(force-output *query-io*)
(read-line *query-io*))

(defun pregunta (lista) ;función que recorre el árbol preguntando al usuario
  (when (not (null lista))
    (if (not (equal T lista))
(progn
 (format t "~%¿Cual es la condición de el/la ~s?" (car (first lista)))
       (set 'opcion 1)
 (set 'valores (rest lista))
 (format t "~%")
 (dolist (valor valores)
   (format t "~%~5t~s. ~s" opcion (car valor))
   (set 'opcion (+ 1 opcion)))
 (set 'elegir (- (parse-integer (leer-mensaje "Elija una opcion: ") :junk-allowed t) 1))

 (pregunta (eval (cdr (nth elegir valores))))) ;vuelve a preguntar con recursividad segun opcion

(format t"~%Entonces voy a jugar al tenis"))))

Para hacer la pregunta obvia:

> (pregunta clima)

En este link está el archivo "arbol.lisp" que contiene las funciones descritas arriba. También otro link donde se guardaron en disco los datos del árbol: "arbol.tree".

Mas tipos de datos lisp

Listas de Propiedades

Las listas de propiedades (‘plistas’) proporcionan una vía simple pero poderosa de manejar pares de palabras-clave/valores. Una plista es simplemente una lista, con un número par de elementos, donde cada pareja de elementos representa un valor con nombre. Este es un ejemplo de plista:

   > '(:nombre "Gloria" :domicilio "Calle Urquiza 1222, Formosa" :celular "111-111111" :edad 35)

En esta plista, las claves son símbolos de palabras clave, y los valores son cadenas. Las claves en una plista son con mucha frecuencia símbolos de palabras clave. Los símbolos de palabras clave son símbolos cuyos nombres van precedidos por un signo de dos puntos (‘:’), y que son usadas generalmente justo para comparar el símbolo en sí (típicamente no se usan por su valor del símbolo o función del símbolo). Para acceder a los miembros de una plista, CL proporciona la función getf, que toma una plista y una clave:

   > (getf '(:nombre "Gloria" :domicilio "Calle Urquiza 1222, Formosa" :celular "111-111111" :edad 35) :nombre)
   "Gloria"

Es mas cómodo guardar la lista de propiedad en una variable:

   > (set 'registro '(:nombre "Gloria" :domicilio "Calle Urquiza 1222, Formosa" :celular "111-111111" :edad 35))

   > (getf registro :edad)
   35

 

 

 

 

 

 

 

 

 "Oh, Lisp me vuelve tan loca..." (Ai Sayama)

 

 

 

Arrays (Arreglos)

Los arreglos son estructuras de datos que pueden albergar "rejillas" simples (o multi-dimensionales) llenas de valores, que son indexadas por uno o más enteros. Los arreglos soportan un acceso muy rápido a los datos basado en índices de enteros. Se crean arreglos empleando la función constructora make-array y los elementos del arreglo se refieren usando la función de acceso aref. Se pueden establecer elementos individuales en el arreglo usando setf:

     > (set 'array (make-array (list 3 3)))
     #2A((NIL NIL NIL) (NIL NIL NIL) (NIL NIL NIL))
    
     > (setf (aref array 0 0) "David")
     "David"
    
     > (setf (aref array 0 1) "José")
     "José"
    
     > (aref array 0 0)
     "David"
    
     > (aref array 0 1)
     "José"

Observe que luego de la función va el argumento requerido de las dimensiones del array, que debe ser una lista. En el ejemplo anterior se trata de un array de 3 * 3. La función make-array también admite varios argumentos de palabras clave optativos para inicializar el arreglo en el momento de su creación. Uno de ellos es :initial-contents que permite establecer los valores iniciales:

    > (make-array '(4 2 3)
            :initial-contents
            '(((a b c) (1 2 3))
              ((d e f) (3 1 2))
              ((g h i) (2 3 1))
              ((j k l) (0 0 0))))
    #3A(((A B C) (1 2 3)) ((D E F) (3 1 2)) ((G H I) (2 3 1)) ((J K L) (0 0 0)))

Se trata de un array de tres dimensiones: 4 * 2 * 3.
Observe la respuesta del intérprete al crear el array: Comienza con las dimensiones #3A (A es el tipo del array) y luego los elementos como listas anidadas. De esta manera podríamos definir al array sin usar la función make-array:

   > (set 'nuevo-array #3A(((a b c) (1 2 3)) ((d e f) (3 1 2)) ((g h i) (2 3 1)) ((j k l) (0 0 0))))

   > (aref nuevo-array 2 0 1)
   H

   > (setf (aref nuevo-array 3 1 1) "sapo pepe")
   "sapo pepe"

   > nuevo-array
   #3A(((A B C) (1 2 3)) ((D E F) (3 1 2)) ((G H I) (2 3 1)) ((J K L) (0 "sapo pepe" 0)))

Tablas Hash

Una tabla hash es similar a lo que en otros lenguajes es conocido como arreglo asociativo. Es comparable a un array de una dimensión que admite claves que son cualquier objeto CL arbitrario, que serán comparados usando eql. Las tablas hash soportan un rastreo de  datos de tiempo constante, lo que significa que el tiempo que se toma en buscar un elemento en la tabla hash permanecerá estable, incluso si el número de entradas en la tabla se incrementa.
Para trabajar con tablas hash, CL proporciona la función constructora make-hash-table y la función de acceso gethash. Para establecer entradas en una tabla hash se usa el operador setf en conjunción con la función de acceso gethash. setf es una generalización de setq que puede usarse en sitios resultantes de una llamada a función, además de exclusivamente con símbolos como con setq. Este es un ejemplo de creación de una tabla hash, que pone un valor en ella y que recupera un valor de ella:

   > (setq so-clasif (make-hash-table))
   #S(HASH-TABLE :TEST FASTHASH-EQL)

   > (setf (gethash :windows so-clasif) "sin comentarios")
     "sin comentarios"
    
   > (gethash :windows so-clasif)
     "sin comentarios" ;
     T

Observe que la función gethash devuelve dos valores. El primer valor de retorno es el valor correspondiente a la entrada encontrada en la tabla hash, si existiera. El segundo valor de retorno es un valor booleano (T o NIL), que indica si el valor se se encontró de hecho en la tabla hash. Si el valor no se encuentra, el primer valor de retorno será NIL y el segundo será también NIL. Este segundo valor es necesario para distinguir los casos en los que la entrada sí se encuentra en la tabla hash, pero sucede que su valor es precisamente NIL. Existen varias vías para acceder a múltiples valores de retorno de una función, empleando multiple-value-bind y multiple-value-list.

En proximas entregas veremos como trabajar con tablas hash, eliminar registros, guardarla en un archivo, etc.

Mi mujer me dijo que si no llevo dinero a casa, me echa y que va a salir con el carnicero de la esquina. :-(

Parámetros de funciones

Parámetros requeridos

Los parámetros declarados al momento de escribir una función son guardados como una lista. El propósito básico de una lista de parámetros es, por supuesto, declarar las variables que van a recibir los argumentos pasados a la función. Cuando una lista de parámetros es una simple lista de nombres de variables - como en de suma-detallada - los parámetros se llaman parámetros requeridos. Cuando una función se llama, deben ser abastecida con un argumento para todos los parámetros requeridos. Cada parámetro es asignado al argumento correspondiente. Si una función es llamada con pocos o demasiados argumentos, Lisp dará una señal de error.

    (defun media (valor-1 valor-2 valor-3)
          (set 'resultado (/ (+ valor-1 valor-2 valor-3)))
          (format t "La media de los tres valores es: ~s" (float resultado)))

 Parametros Opcionales

En Common Lisp puedes utilizar parámetros opcionales, que para los usuarios que llaman a tu función y no especifican los valores para esos parámetros, obtienen un valor predeterminado razonable, y otros pueden proporcionar un valor específico.

Para definir una función con parámetros opcionales, después de los nombres de los parámetros requeridos, coloque el símbolo &optional seguidos por los nombres de los parámetros opcionales. Un ejemplo simple es el siguiente:

   (defun opt (a b &optional c d) (list a b c d))

Cuando se invoca la función, los primeros argumentos son asignados a los parámetros requeridos. Después de que todos los parámetros requeridos han obtenido sus valores, los valores se asignan a los parámetros opcionales. Si los argumentos pasados a la función se agotan antes que los parámetros opcionales, el resto de parámetros opcionales serán asignados a NIL. Por lo tanto, la función definida anteriormente da el siguiente resultado:

   (opt 1 2) ==> (1 2 NIL NIL)
   (opt 1 2 3) ==> (1 2 3 NIL)
   (opt 1 2 3 4) ==> (1 2 3 4)

Lisp todavía comprueba que la cantidad de argumentos apropiados sean pasados a la función - en este caso entre dos y cuatro, ambos inclusive - y dará una señal de error si la función se llama con muy pocos o demasiados.

Por supuesto, a menudo se desea un valor predeterminado distinto de NIL. Usted puede especificar el valor predeterminado mediante la sustitución del nombre del parámetro con una lista que contiene un nombre y una expresión. La expresión se evalúa solamente si el usuario que llama no pasa argumentos suficientes para proporcionar un valor para el parámetro opcional. El caso común es simplemente para proporcionar un valor en la expresión.

   (defun opt (a &optional (b 10)) (list a b))

Esta función requiere un argumento que será asignado al parámetro a. El segundo parámetro b, tomará el valor del segundo argumento, si es que existe, o 10.

   (opt 1 2) ==> (1 2)
   (opt 1) ==> (1 10)

A veces, sin embargo, es posible que tenga más flexibilidad para elegir el valor por defecto. Es posible que desee calcular un valor predeterminado basado en otros parámetros. Y se puede – el valor predeterminado puede referirse a parámetros que se guardan antes en la lista de parámetros. Si estuviera escribiendo una función que devuelve una especie de representación de un rectángulo y que ha querido dejar muy conveniente para hacer plazas, se puede utilizar una lista de argumentos como este:

   (defun hacer-rectángulo (ancho &optional (alto ancho)) ...)

lo que causaría la altura de los parámetros tengan el mismo valor que el ancho a menos que estén explícitamente especificados.

O hacer operaciones entre argumentos pasados a la función:

   (defun hacer-rectangulo (ancho &optional (alto (* 2 ancho)) ... )

Con lo que el alto sería igual al doble del ancho en caso de omitir el argumento.

De vez en cuando, es útil saber si el valor de un argumento opcional fue suministrado por el usuario o es el valor predeterminado. En lugar de escribir código para comprobar si el valor del parámetro es el valor predeterminado (que no funciona de todos modos, si el usuario le pasa de forma explícita el valor predeterminado), puede agregar otro nombre de variable para especificar la falta de valor del parámetro. A esta variable se le asigna true si la persona que llama en realidad suministra un argumento para este parámetro y NIL lo contrario. Por convención, estas variables tienen usualmente el mismo nombre que el parámetro actual con una "-p" agregada al final. Por ejemplo:

   (defun opt (a b &optional (c 3 c-p)) (list a b c c-p))

Esto da resultados como este:

   (opt 1 2) ==> (1 2 3 NIL)
   (opt 1 2 3) ==> (1 2 3 T)
   (opt 1 2 4) ==> (1 2 4 T)

Parámetros rest

Los parámetros opcionales sirven cuando se tienen parámetros discretos para los cuales el usuario puede o no desea proporcionar los valores. Sin embargo, algunas funciones toman un número variable de argumentos. La función FORMAT, por ejemplo, tiene dos argumentos requeridos, el medio y la cadena de control. Pero después de eso se necesita un número variable de argumentos en función de valores que deben ser interpolados en la cadena de control. La función + también tiene un número variable de argumentos - no hay ninguna razón particular para limitar la suma a sólo dos números, sino que se suma un número de valores. (También funciona con cero argumentos, devolviendo un 0, la identidad con la adición.) Las siguientes son todas las llamadas legales de esas dos funciones:

   (format t "hola, mundo")
   (format t "hola, ~a" nombre)
   (format t "x: ~d y:~d" x y)
   (+)
   (+ 1)
   (+ 1 2)
   (+ 1 2 3)

Obviamente, usted puede escribir funciones que toman un número variable de argumentos, simplemente les da un montón de parámetros opcionales. Pero eso sería increíblemente costoso - sólo escribir la lista de parámetros sería bastante malo, y ni que hablar en tratar con todos los parámetros en el cuerpo de la función. Para hacerlo correctamente, usted tendría que tener parámetros opcionales tantos como el número de argumentos que legalmente se puede pasar en una llamada a la función. Este número depende de la implementación, pero se garantiza que al menos 50. Y en las implementaciones actuales que van desde 4096 a 536.870.911.

En cambio, Lisp permite incluir un parámetro comodín después del símbolo &rest. Si una función incluye un parámetro &rest, cualquier argumento restante después de que los valores han sido distribuidos a todos los parámetros requeridos y opcionales es recogido en una lista que se convierte en el valor del parámetro &rest. Por lo tanto, las listas de parámetros de FORMAT y + probablemente lucen como esto:

   (defun format (medio cadena &rest valores) ...)
   (defun + (&rest números) ...)

En el ejemplo para el cálculo de la media en valores requeridos, vemos que solo podemos obtener una media para tres valores nada mas, si quisiéramos calcular la media para una cantidad indefinida de valores:

   (defun media (&rest valores)
       (set 'suma 0)
       (dolist (num valores)
            (set 'suma (+ num suma)))
       (set 'resultado (/ suma (length valores)))
       (format t "El valor de la media es: ~s" (float resultado)))

Parámetros de palabras clave

Los parámetros opcionales e &rest te dan un poco de flexibilidad, pero tampoco te van a ayudar mucho en la siguiente situación: Supongamos que tenemos una función que toma cuatro parámetros opcionales. Ahora bien, supongamos que la mayoría de los lugares en que se llama a la función, el usuario desea proporcionar un valor para sólo uno de los cuatro parámetros y, además, que los usuarios están divididos en cuanto a qué parámetros van a utilizar.

Los usuarios que quieren proporcionar un valor para el primer parámetro están bien – solo pasan el único argumento opcional y dejan en blanco el resto. Pero los otros usuarios que tienen que pasar un valor de entre uno y tres argumentos cualesquiera de ellos. ¿No es exactamente el problema que los parámetros opcionales fueron diseñados para resolver?

Por supuesto que sí. El problema es que los parámetros opcionales son todavía de posición - si el usuario quiere pasar un valor explícito para el cuarto parámetro opcional, resulta que los tres primeros parámetros opcionales son requeridos para él. Por suerte, existe otro sabor de parámetros, los parámetros de palabra clave, que permiten al usuario especificar que valores van con qué parámetros.

Para dar a una función parámetros de palabras clave, después de cualquier parámetro requerido, &optional, y &rest se incluye el símbolo &key y cualquier número de especificadores de parámetro de palabra clave, que funcionan como especificadores de parámetros opcionales. He aquí una función que tiene sólo parámetros de palabra clave:

  (defun clave (&key a b c) (list a b c))

Cuando esta función se llama, cada uno de los parámetros clave está ligado al valor inmediatamente después de una palabra clave del mismo nombre.
Si una palabra clave determinada no aparece en la lista de parámetros, al parámetro correspondiente se le asigna su valor por defecto, al igual que un parámetro opcional. Debido a que los argumentos de palabras clave están etiquetados, que se pueden pasar en cualquier orden, siempre y cuando sigan los argumentos necesarios. Por ejemplo, clave se puede invocar como sigue:

   (clave) ==> (NIL NIL NIL)
   (clave :a 1) ==> (1 NIL NIL)
   (clave :b 1) ==> (NIL 1 NIL)
   (clave :c 1) ==> (NIL NIL 1)
   (clave :a 1 :c 3) ==> (1 NIL 3)
   (clave :a 1 :b 2 :c 3) ==> (1 2 3)
   (clave :a 1 :c 3 :b 2) ==> (1 2 3)

Al igual que con los parámetros opcionales, los parámetros de palabra clave puede proporcionar una forma de valor por defecto y el nombre de una variable con -p agregada. Asimismo, la forma de valor por defecto puede hacer referencia a los parámetros que aparecen anteriormente en la lista de parámetros.

   (defun clave (&key (a 0) (b 0 b-p) (c (+ a b)))
      (list a b c b-p))

   (clave :a 1) ==> (1 0 1 NIL)
   (clave :b 1) ==> (0 1 1 T)
   (clave :a 3 :b 5) ==> (3 5 8 T)
   (clave :b 1 :c 4) ==> (0 1 4 T)
   (clave :a 2 :b 1 :c 4) ==> (2 1 4 T)

Además, si por alguna razón, desea que la palabra clave que el usuario use un parámetro diferente del nombre del parámetro real, puede reemplazar el nombre del parámetro con otra lista que contiene la palabra clave que se utiliza al llamar a la función y el nombre para ser utilizado por el parámetro. La siguiente definición de clave lo muestra:

   (defun clave (&key ((:arbol a)) ((:bombon b) 0) ((:cereza c) 0 c-p)) (list a b c c-p))

permite que el usuario lo llame así:

   (clave :arbol 10 :bombon 20 :cereza 30) ==> (10 20 30 T)

Este estilo es útil sobre todo si se quiere desvincular por completo a la API pública de la función de los detalles internos, por lo general debido a que desea utilizar los nombres de variable cortas, en lugar de palabras descriptivas en el API. Sin embargo, esto no es utilizado con frecuencia.

Fuente consultada:

Seibel Peter (2005). Practical Common Lisp.  EE.UU.: Apress

Llevar adelante este blogg cuesta tiempo, esfuerzo, dinero, y los palazos que me da mi esposa por estar todo el día frente al ordenador...

Árboles binarios en Lisp

En lisp, todos los datos en memoria se estructuran de a pares, conocidos como nodos:

En la notación antigua de lisp, se escribía con puntos así:

> '(23 . 99)
> (23 . 99)

23 es el elemento de la izquierda y 99 el de la derecha

Para acceder al elemento de la izquierda usamos CAR, y para acceder al elemento de la derecha usamos CDR.

> (car '(23 . 99))
23

> (cdr '(23 . 99))
99

De esta manera todos los tipos de datos se estructuran a partir de nodos, solo que actualmente se omite el punto. Así las listas son nodos encadenados:

Del mismo modo las funciones, tienen estructura de lista, solo que estas se evalúan.

Revista Mundo Linux n° 85 - Articulo sobre lisp

Arboles binarios

Para crear árboles usamos los nodos. La figura siguiente es un árbol binario:

Para hacerlo mediante nodos:

Es fácil construirlo en Lisp, (voy a usar la notacion con puntos, pues me resulta mas cómodo)

Las ramas van separadas por puntos y entre paréntesis

> (set 'arbol '(1 . ((2 . nil) . (3 . nil))))
(1 (2) 3)

;;; a la variable arbol le asignamos el arbol binario

Por convención el elemento de la izquierda del nodo tendrá el valor y el elemento de la derecha apuntará hacia otro nodo, o bien apunta a NIL.

Para acceder a la raíz usamos CAR:

> (car arbol)
1

Para acceder al nodo 2, por ejemplo, primero usamos un (CDR arbol), que nos situa en el nodo que contiene las direcciones de los nodos (2 . nil) y (3 . nil). Luego un CAR (que lo envuelve) nos lleva al nodo (2 . nil). Por último un CAR devolverá el elemento 2, si usáramos CDR aca, nos devolvería NIL.

> (car (car (cdr arbol)))
2

Dejo al lector como ejercicio, que intente acceder al elemento 3.

Debido a que los valores están a la izquierda, siempre que queramos acceder un dato, habrá un CAR que envuelva a toda la expresión.

Veamos un árbol con mas hojas:

En Lisp, se ve así:

Se guarda así:

> (set 'arbol '(1  .  ((2 . ((4 . nil) . (5 . nil)))  .  (3 . ((6 . nil) . (7 . nil))))))
(1 (2 (4) 5) 3 (6) 7)

Para recorrer este árbol usamos CAR y CDR, como vimos anteriormente.
Para acceder a 5 sería asi:

> (car (cdr (cdr (car (cdr arbol)))))
5

Dejo al lector que intente acceder a los demás elementos.

Bien de esta manera, podemos crear cualquier tipo de estructura que se nos ocurra. Las funciones para recorrerlas y agregar elementos no serían muy complicadas. Nos evitamos el hecho de tener que manejar punteros y/o variables de tipo puntero.

"Dona lo que quieras, y ayuda a mantener este blogg en funcionamiento, eso eso eso!!!"

Estructura de Control de Programa (Tercera parte)

Progn y Let

Son estructuras que sirven para organizar los programas. Antes de comenzar veamos la manera de organizar un programa lisp (archivo de texto con la extensión .lisp o .lsp) , sería asi:

;;;; -----------------------------------------------------------------------------------------------------------------------

;;;; Cargo los archivos que tengan funciones externas con load

(load "archivo-a-cargar.fas")

;;;; Ingreso en el paquete a utilizar

(use-package :paquete-a-utilizar

;;;; Defino e inicializo las variables globales:

(defvar *valor* 8)

(defvar *cadena* "holaaaa")

(defvar *variable* nil)

;;;; Por convención, las variables globales van entre asteriscos
;;;; Defino ahora las funciones internas

(defun mi-funcion (argumentos) (cuerpo-expresiones))
(defun otra-funcion (argumentos (cuerpo-expresiones))


;;;; Ahora comienza el cuerpo del programa:

(expresión-1)
(expresión-2)
     ...........

(expresión-n)

;;;; -----------------------------------------------------------------------------------------------------------------------------

Prog1, Prog 2, Progn

Sirven para agrupar varias expresiones, dentro de un if por ejemplo o dentro de un when. Su sintaxis es la siguiente:

(prog1
       (exprexion-1)
       (expresion-2)
             ..........
       (expresion-n))

Las prog evaluaran cada una de las expresiones, a menos que se desactive la evaluación con comilla simple ('). Prog1 evaluará todas las expresiones y devolverá (expresion-1) evaluada cuando termina. Prog2 hará lo mismo y devolverá la evaluación de (expresion-2) cuando acaba. De la misma manera Progn irá evaluando las expresiones y devolverá la evaluación de la última.

Veamos unos ejemplos de prog:

> (prog1 (set 'x 4) (set 'y 9) (set 'z (* x y)) (format t "~s * ~s  = ~s" x y z))
4 * 9 = 36
4

> (prog2 (set 'x 4) (set 'y 9) (set 'z (* x y)) (format t "~s * ~s  = ~s" x y z))
4 * 9 = 36
9

> (progn (set 'x 4) (set 'y 9) (set 'z (* x y)) (format t "~s * ~s  = ~s" x y z))
4 * 9 = 36
NIL

 let

 Let sirve para organizar el programa, se puede vivir sin let, pero es mas cómodo usarlo, lo mismo sucede con una almohada :-D. Consta de dos partes, una de asignación de valores a símbolos y un cuerpo de expresiones.

Su sintaxis es:

(let ((simbolo-1 valor-1)
     (simbolo-2 valor-2)
                ...............
     (simbolo-n valor-n))

    (expresion-1)
    (expresion-2)
       ...............
    (expresion-m))

Es simple lo que hace let, cuando comienza asigna a cada símbolo el valor que se escribe al lado. Es decir, a simbolo-1 asignará el valor-1, a símbolo-2 el valor-2, y así sucesivamente, hasta simbolo-n. Luego evaluará el cuerpo de expresiones: (expresion-1) (expresion-2) .... (expresion-n).

Ejemplo:

(let ((x 76)
      (y 423)
      (z (* x y)))

   (format t "~s * ~s = ~s" x y z))


76 * 423 = 36
NIL

Algo que hay que tener en cuenta es que las variables usadas dentro de let tienen un alcance local. Es decir los valores dados dentro del mismo let no afectarán a las variables x, y, z del mismo nombre que estén afuera y que seguirán teniendo los mismos valores. Si lo hemos hecho todo desde el interprete, podemos consultar los valores de esas variables:

> x
4

> y
9

> z
36

Estructuras de Control de Programa (Segunda parte)

Iteraciones o bucles de programa

dolist

Sintaxis

(dolist (lista-inicializacion) (cuerpo))

dolist toma una lista de inicialización y un cuerpo.La lista de inicialización contendrá una variable que tomara los elementos de una lista para cada iteración, la lista de elementos, y una variable que se devolverá como resultado.

(elemento lista-elementos resultado)

En el cuerpo se iterará para cada elemento de la lista, y se irá almacenando cada uno de esos valores en la variable elemento.

Un ejemplo:

> (set 'resultado 1)
1

> (set 'lista-elementos '(2 3 5 7 11 13 17 19 23))

> (dolist (elemento lista-elementos resultado)
            (set 'resultado (* elemento resultado))) ;multiplica cada elemento de la lista y acumula en resultado

Hay que tener en cuenta que "resultado", contendrá el valor devuelto al finalizar el bucle. Si se omite el argumento "resultado" se devolverá NIL al terminar el proceso.

dotimes

Es similar a dolist, solo que la variable iteradora sera siempre un numero natural, comenzando por cero (naturales incluido el cero).

La sintaxis es:

(dotimes (lista-inicializacion) (cuerpo))

Donde (lista-inicializacion) tiene la forma:

(variable-iteradora valor-maximo resultado)

El cuerpo se evaluara sucesivamente, comenzando la variable iteradora con un valor de 0 (cero), hasta alcanzar a valor-maximo menos uno. Como en el caso anterior, si se omite el argumento "resultado" se devolverá NIL al finalizar el bucle.

Ejemplo:

> (dotimes (i 10) (format t "~s" i))
0123456789
NIL

Format imprime el valor de la variable cada vez que se evalúa el cuerpo: "~s" toma el valor de la variable y lo imprime en pantalla.

Para que quede mas lindo, imprimimos uno debajo del otro y con tabulación:

> (dotimes (i 10) (format t "~% ~14t ~s" i))

"~%" equivale a "enter"
"~14t" es la tabulacion
"~s" es la variable que se imprime

Supongamos que deseamos obtener la sumatoria de (2 * i) desde 6 hasta 23 inclusive,

hacemos asi:

> (set 'sumatoria 0)

> (dotimes (i 18 sumatoria) (set 'sumatoria (+ sumatoria (* 2 (+ i 6)))))
522

loop

La forma mas facil de hacer un bucle es haciendo un loop. Para poder salir del bucle es necesario usar un (return). (return) me sirve para salir de cualquier iteraccion, obviamente hay que usarlo siempre y cuando se cumpla una determinada condicion, usando un "if" o "when", por ejemplo.

(set 'x 2)

(loop
   (set 'funcion (expt (+ 1 (/ 1 x)) x))                                ;aplica la funcion
   (format t "~8t x: ~s ~% ~8t y: ~s" x funcion)                ;muestra el valor de funcion
   (set 'x (+ x 1))                                                            ;incrementa x en uno
   (when (not (y-or-n-p "¿Desea calcular un nuevo valor?")) (return)))

La función "y-or-n-p" devuelve T (verdadero) cuando se presiona la tecla "y" y NIL (falso) cuando se presiona "n". En nuestro caso, sale del bucle, aplicando "return" cuando se presiona "n", pues esta precedido de la funcion "not" que niega el valor lógico.

do

Es la iteración mas complicada. Sirve para poder utilizar varias variables iteradoras a la vez, cada una con su propio incremento.

Su sintaxis es:

(do ((lista-inicializacion-1)
     (lista-inicializacion-2)
         ...........
     (lista-inicializacion-n))

    (condicion (expresiones-verdad))

    (expresiones-falso))

Cada lista-inicializacion-i contiene una variable-iteradora, el valor-inicial para esta variable y una funcion que incrementará ese valor:

    (variable-iteradora-i  valor-inicial  funcion-incremento)

Ejemplos de lista-inicializacion-i:

(i 1 (+ i 1))                          ;i comienza en 1 y se va incrementando en 1
(valor 7 (+ valor 4))             ;valor comienza en 7 y se va incrementando en 4
(colores '("azul" "verde" "rojo" "amarillo" "marron" "naranja") (rest colores))
                                              ;mi-lista comienza con una lista de colores
                                              ;rest va eliminando con cada iteración el primer elemento de la lista

En la primera iteracion las variables-iteradoras toman el valor-inicial. Luego se evalúa la "condicion". Si la condicion es T (verdadera) evalua las "expresiones-verdad" y termina el bucle. Si la condicion es NIL (falso), evalua las "expresiones-falso" e incrementa cada una de las variables-iteradoras, y se vuelve a evaluar "condicion".

Ejemplo de do:

(do
 ((i 1 (+ i 1))
  (colores '("azul" "verde" "rojo" "amarillo" "marron" "naranja") (rest colores)))

 ((null colores) (format t "~% ~%¡Listo, barrilete cósmico!"))

 (format t "~% ~10t El color ~s es ~10t ~s" i (first colores)))

Si la lista aun no esta vacía, se imprime el primer elemento de la lista que aun queda. :-)