Lisp, por fin algo útil y potente como la recursividad

¿Que es la recursión, o recursividad?

Podemos decir que es una forma de resolver problemas.

Si analizamos un problema, y descubrimos que se puede resolver por partes en las que se vuelve a plantear el problema original pero de forma más "reducida", entonces podemos resolver por recursión.

Ya veis que es algo dificil de explicar, pero se puede ver muy fácilmente.

El ejemplo típico es la función factorial.

El factorial de 6 se representa: 6! y es igual a 6 x 5 x 4 x3 x 2 x 1. Por lo tanto 6! = 720.

Si nos fijamos un poco podemos ver que el factorial de 5 es igual a 5 x 4 x 3 x 2 x 1.

Por lo tanto el factorial de 6 es igual a 6 x el factorial de 5.
Y el factorial de 5 es igual a 5 x el factorial de 4.
etc. etc.

Por convenio en matemáticas el factorial de 0 es igual a 1.

Vemos que podemos usar la función factorial al intentar calcular el factorial de un número.

Función factorial recursiva:

(defun factorial (n)
         (if   (zerop  n)   1
                    (*   n  (factorial (1-   n)))
          )

)

Explicación de la función:

El factorial de un número n es:
1-Si n = 0 entonces el factorial es 1.
2-Si n no es 0, entonces el factorial es n x factorial(n-1)

Avisos:
La función (1- n) devuelve el número n menos 1.
Existe la función (1+ n) que devuelve el número n más 1.

Lisp, carga de programas .lsp

Se que os recomendé un interprete lisp llamado clisp.

Bueno pues hoy si queréis podéis probar este otro, que al menos tiene más logrado el interfaz gráfico para windows. Probarlo y me entenderéis...

Se llama XLisp-Plus y se encuentra en http://almy.us/xlisp.html.

XLisp es un Lisp basado en Scheme (uno de los dialectos de Lisp). Lo que ocurre es que no se distribuye XLisp en formato ejecutable, por lo que he preferido bajarme el XLisp-Plus.

Bueno, bajamos el intérprete y la documentación.

Los descomprimimos y colocamos los ficheros resultantes donde más nos interese tenerlos.

Vamos a la carpeta donde se encuentra el ejecutable xlwin32 y creamos un fichero que llamaremos hola-mundo.lsp. Editamos el fichero y escribimos:

(print ‘”Hola mundo”)

Cerramos y guardamos el fichero.

Ahora entramos en el interprete Lisp haciendo doble clic en xlwin32.exe.

Para cargar y ejecutar un fichero lisp (tiene extensiones .lsp) hacemos lo siguiente:

(load ‘hola-mundo.lsp)

> “Hola mundo”
> “Hola mundo”

La función print muestra en pantalla el string que le hemos pasado como argumento, pero a su vez devuelve un valor que es la evaluación del argumento. Por eso el mismo string aparece dos veces.

Bueno, pues ya estamos preparados para escribir programas LISP.

Saludos a tod@s,

Lisp, quinta lección

Bueno, por fin tenemos elementos suficientes para empezar a utilizar Lisp.

De todas formas, vamos a ver primero las funciones CONDICIONALES.

IF

(if expresion expresion)
Es el típico if...then de otros lenguajes.

En este caso se evalúa el primer argumento. Si el valor es distinto a NIL entonces se evalua el segundo argumento y el valor devuelto es lo que devuelve la función IF.

(if (listp '(a)) 'LISTA)
> LISTA

(if (listp 'a) 'LISTA)
> NIL

(if expresion expresion expresion)
Es el típico if...then...else de otros lenguajes.

Si el valor del primer argumento es T entonces se evalúa el segundo argumento. Si no es así se evalúa el tercer argumento.

(if (listp '(a)) 'LISTA 'NO-LISTA)
> LISTA

(if (listp 'a) 'LISTA 'NO-LISTA)
> NO-LISTA

WHEN

Es igual que la función IF.

(when expresion expresion) es equivalente a (if expresion expresion).

UNLESS

Esta función es un poco dudosa y también prescindible igual que WHEN.

(unless expresion expresion)
Si el valor del primer argumento es falso se devuelve el valor del segundo argumento.
Si el valor del primer argumento es verdadero devuelve NIL.

Es totalmente equivalente a (if expresion NIL expresion).

COND

Parecido a la instrucción SELECT CASE de otros lenguajes.
Es como un montón de if...then...else.

(cond (expresion-test1 expresion-consecuencia1 expresion-consecuencia2...)
(expresion-test1 expresion-consecuencia2 expresion-consecuencia2...)
....
(t expresion-consecuenciaN expresionconsecuenciaN+1........)
)

La última claúsula (la de t) no es obligatoria.
Si no se cumple ninguna expresion-test de cond se devuelve NIL.

Lisp, 5ª lección

Funciones predicado

Me imagino (no tengo mis apuntes a mano) que se llaman así porque sirven para obtener información de los predicados, o sea, de sus argumentos.

Creo que esta es la última lección que necesitamos antes de empezar a resolver problemas. Bueno, esto no es del todo exacto. Necesitamos también funciones para el control de flujo (for, while y esas cosas).

¿Qué devuelven las funciones predicado?

Devuelven el símbolo t para indicar que se cumple la condición (t de true).

Devuelven el símbolo NIL para indicar que la condición no se cumple. NIL es un símbolo y una lista a la vez: la lista vacía.

NIL = ()

Por eso (rest ‘(a)) devuelve NIL, o sea la lista vacía.

Por cierto, la mayoría de las funciones predicado terminan con la letra P (de predicado).

Función SYMBOLP

Sirve para saber si el valor del argumento es un símbolo o no.

(symbolp NIL)
> t

(symbolp t)
> t

(symbolp (first '(a b)))
> t

Función LISTP

Indica si el valor del argumento es una lista.

(listp ‘(a b c))
> t

(listp NIL)
> t

Función NUMBERP

(numberp 5)
> t

Función ATOM

Los símbolos y números son átomos.

(atom 'a)
> t

(atom 5)
> t

(atom '(a))
> NIL

Función ZEROP

Indica si el valor del argumento es cero o no.

Función MINUSP

Para saber si el valor del argumento es negativo.

Función PLUSP

Para saber si el valor del argumento es positivo.

Función EVENP

Nos dice si es par.

Función ODDP

Para saber si es impar.

Función "<" (menor)

(<>
> NIL

(<>
> t

Función ">" (mayor)

(> 7 6 5)
> t

Función "=" (igualdad)

(= 4 4)
> t

(= 4 4.0)
> t

(= 4 (first '(4 2)))
> t

Función EQ

Similar a la función "igualdad", pero los valores de los argumentos tienen que ser símbolos.

(eq 'a (first '(a b)))
> t

(eq 'a (rest '(a b)))
> ERROR.

Función EQL

Similar a los 2 anteriores, pero los valores de los argumentos tienen que ser números o símbolos.

(eql 'a (first '(a)))
> t

(eql 4 4.0)
> NIL por ser diferentes números (uno entero y otro decimal).

Función EQUAL

Sirve para números, símbolos y listas. En el caso de los números el comportamiento es igual que en la función EQL.

(equal '(a b 4) (list 'a 'b 4.0))
> NIL

Bueno, ya está bien por hoy.
Saludos...

Otra vez salvado por Perl

Si, hoy no voy a continuar con el tema de Lisp.

Resulta que me han solicitado ayuda por un tema:

Un programa comercial genera un fichero de texto como salida, pero luego resulta que el organismo oficial que lo requiere nos solicita un formato diferente.

Para un tema así de conversión de formatos LISP no es el lenguaje más adecuado. Perl en cambio está especializado en estas tareas aburridas y pesadas.

Hay va mi programita Perl. Si alguien tiene dudas de lo que hace que me deje un comentario...

$fichero="origen.txt";
open(FICH, $fichero) or die("Error al abrir el fichero");

open(SALIDA, ">destino.txt");

while(){
  ($texto, $cae, $fecha, $hora, $matricula, $carburante, $litros) = split(';',$_);
  $anyo=substr($texto, 0, 4);
  $periodo=substr($texto, 4, 2);
  $numeracion=substr($texto, 6, 12);
  $litros=$litros*100;
  printf SALIDA "A11025131%4s%2GAST%12s%s%-12s%s%s%7d%s\n",$anyo,$periodo,$numeracion,$cae,$matricula,$fecha,$hora,$litros,$carburante;
}

close FICH;
close SALIDA;

Lisp, 4ª lección, segunda parte

Bueno, y ahora hablemos un poco de funciones superfluas.

LET*

Si nos fijamos un poquito nos damos cuenta de que...
Se puede sustituir LET* por un LET dentro de otro LET:

Si hacemos

(let ( (x 100)
     )
     (let ( (y (+ x 200)))
     )
)

Comprobamos que es totalmente equivalente a...

(let* ( (x 100)
        (y (+ x 200))
      )

)

¡Ja! así que podemos prescindir de LET* tranquilamente.

Hay muchas otras funciones prescindibles.

Por ejemplo la función SECOND.

Second sirve para elegir el segundo elemento de una lista.

(second '(a b c)
> b

En la primera lección de Lisp vimos las funciones FIRST y REST.

Podemos definir una nueva función llamada SEGUNDO.

(defun segundo (lista)
     (first (rest lista))
)

(segundo '(a b c))
> b 

De esta forma podemos hacer nuestro propio LISP fácilmente.

4ª Lección de Lisp

Bueno, hoy toca intensivo,

Primero 2 funciones que pueden venir bien en cualquier situación:

LENGTH

(length lista)
Devuelve el número de elementos de la lista.

(length ‘(a b c))
> 3

REVERSE

(reverse lista)
Devuelve la misma lista pero invierte el orden.

(reverse ‘(a b c))
> (c b a)

Y dos funciones muy importantes en lisp:

LET

Esta función permite hacer asignación de variables de forma local.
Se ve claro en el siguiente ejemplo.

(setf a ‘HOLA)
(setf b ‘ADIOS)
(let ( (a 6)
       (b 9)
     )
     (+ a b)
)
> 15
a
> HOLA
b
> ADIOS

Esto es, dentro del cuerpo del LET las variables tienen el valor que se ha preasignado, y no tiene que ver con el valor que tenían fuera de ese ámbito.

LET*

Es muy similar a LET, pero con el asterisco la asignación es dinámica. ¿Que significa esto? Veámoslo con otro ejemplo:

(let (
      (x 100)
      (y (+ x 200))
     )
)

Esto devuelve un error si se hace con la función LET. Es porque cuando intenta asignar un valor a “y”, “x” todavía no tiene un valor válido.
En cambio si utilizamos LET*, primero asigna el valor a “x” y luego a “y”, de forma que no se produce un error.

Lisp, 3ª lección

Hoy voy a improvisar un poco porque no tengo los apuntes a mano.

Para empezar a hacer algo con Lisp vamos a necesitar un mínimo de operaciones aritméticas.

Funciones matemáticas básicas en Lisp:

La útil suma:

(+ 7 37 39 2)
Devuelve 85.

La imprescindible resta:
(- 7 37 39 2)
Devuelve -71.

¡Ah!, entonces como habréis imaginado...

La multiplicación:
(* 6 6)
Devuelve 36.

Y
(/ 36 6)
Devuelve 6.

Ahora otras funciones algo más complejas (pero poco):

(mod 36 6)
Devuelve 0 por ser el resto de la división.

Entonces,
(mod 37 6)
Devuelve 1.

La raiz cuadrada:

(sqrt 25)
Devuelve 5.

Y por si alguien tiene dudas:
(sqrt 91)
Devuelve 9.539392.

Ahora unas funciones de lo más prescindibles:
(max 7 37 39 2) devuelve el máximo valor.
Por lo tanto devuelve 39.

(min 7 37 39 2) devuelve el mínimo valor.
Por lo tanto devuelve 2.

(abs -2) devuelve el valor absoluto.
Por lo tanto devuelve 2.

¿Por qué digo que son funciones prescindibles?
Porque son fácilmente implementables en Lisp.

Veamos como...

Para definir funciones en lisp utilizamos la función defun.

Voy a crear una función con el nombre suma que servirá para sumar 2 argumentos.
(defun suma (argumento1 argumento2)
(+ argumento1 argumento2)
)

Cuando terminemos de meter las 3 líneas en el interprete nos devolverá el prompt de Lisp. Ahora la función se encuentra cargada en memoria y podemos utilizarla.

(suma 45 5)
Devolverá 50.

¡Que útil!
Ya podemos ampliar Lisp con nuevas funciones.

Lisp. 2ª lección

FUNCIONES CONSTRUCTORAS: Cons, List, Append

Son las funciones para creación de listas.


CONS

(cons expresion lista)
Devuelve una lista que contiene como primer elemento el valor de la expresión, y los siguientes elementos son los de la lista.

(cons 'a '(b c))
Devuelve (a b c)

LIST

(list expresion expresion ...)
Devuelve una lista que contiene los valores de las expresiones.

(list 5 7 9)
Devuelve (5 7 9)

APPEND

(append lista1 lista2 ...)
Coge los elementos de las listas y los fusiona en una sola lista.

(append '(a) (list 2 (cons 'b '(3)) 4) '(5))
Devuelve (a 2 (b 3) 4 5)

OTRAS FUNCIONES:

LENGTH

(length lista)
Devuelve un número que indica los elementos de la lista.

(lenght '(a b c (d e))
Devuelve 4.

REVERSE

(reverse lista)
Devuelve una lista con los elementos en orden inverso.

(reverse '(a b c d))
Devuelve (d c b a)

Todavía es un poco pronto para empezar con resolución de problemas, pero en los próximos días cuando veamos la definición de funciones, algunas funciones matemáticas y las funciones predicado podremos empezar con las funciones recursivas y toda su potencia.