Haciendo un intérprete de LISP (X)

Después del descanso navideño continuamos con nuestro intérprete LISP. Hoy vamos a probar las funciones lambda desde el REPL (Read-Eval-Print Loop).

La nativa que hace lambdas

Las funciones lambdas son objetos que hemos de crear. Ya vimos cómo hacerlo en la parte séptima. Sin embargo, hemos de poder crear objetos lambda desde el evaluador. La forma de conseguirlo es mediante una función nativa.

El código es el siguiente:

Cell& FOL_Lambda(Heap& heap, Cell& args, Cell& envir)
{
if(args.IsEmpty() || args.GetTail().IsEmpty())
throw std::runtime_error("Lambda needs two arguments at least");

Cell* params=&args.GetHead();
Cell* p;
for(p=params; p->IsPair(); p=&p->GetTail())
if(!p->GetHead().IsName())
 throw std::runtime_error("Binding a non-name");

if(!p->IsEmpty())
throw std::runtime_error("Lambda need a list as first argument");

return heap.CreateLambda(*new Lambda(*params, args.GetTail(), envir));
}

Primero comprobamos que nos han pasado dos argumentos. El primero va a ser la lista de parámetros y el segundo (y restantes) el cuerpo de la función lambda. Los parámetros han de estar en una lista de nombres. Eso lo comprobamos en el bucle y el consiguiente if. Finalmente, creamos el objeto lambda donde almacenaremos la función lambda.

Esto se hace en dos pasos. El primero es crear el objeto. Realmente esto sólo almacena tres referencias: a los parámetros, al cuerpo de la función y al entorno (para la clausura léxica). A continuación, creamos una celda CT_LAMBDA que contendrá ese objeto recién creado. Esta segunda parte la hace CreateLambda().

Se retorna la celda.

Probando las funciones lambda

Usamos el intérprete interactivo para probar las funciones lambda. Primero crearemos una. Como ya teníamos hecha una función de suma, la utilizaremos para hacer la función doble. Escribimos que queremos una función que toma un argumento x y devuelve la suma de x con x.

> (lambda (x) (add x x))

El resultado de evaluar esta expresión S será un valor de tipo CT_LAMBDA. Un objeto lambda que no es más que la función lambda que toma un x y devuelve la suma de x con x. Dependiendo de cómo hayamos hecho la impresión, la visualización de este valor podría ser

<lambda 003A7460 <envir 003A6950> (x) ((add x x))>

Lo interesante de las funciones lambda no es crearlas, es aplicarlas. Calculemos el doble de siete.

> ( (lambda (x) (add x x)) 7 )

14

Vistas así las funciones lambda no son más que una substitución (la regla beta o beta reduccción). Sustituimos x por 7 en (add x x). El resultado es (add 7 7) que evalúa a 14.

Las funciones lambda son muy interesantes porque tienen gran expresividad. Entre otras cosas son Turing completas y podemos expresar algoritmos no decidibles con ellas. Por ejemplo, la forma más rápida de colgar el ordenador es el siguiente bucle infinito.

> ( (lambda (x) (x x)) (lambda (x) (x x)) )