Haciendo un intérprete de LISP (VII)

Hasta ahora hemos hablado de cómo almacenar valores (las celdas), cómo representarlos (las expresiones S), cómo pasar de la representación al valor (la evaluación) y cómo calcular un valor a partir de unos argumentos (la aplicación de una función). Falta un paso fundamental: poder definir las funciones.

En este post y el siguiente nos dedicaremos a esto.

El lambda cálculo

Los modelos de computación trabajan en base a un concepto muy simple: las sustituciones de una cosa por otra. Dependiendo de qué sustituyamos y qué reglas usemos para sustituir obtendremos un tipo de computación u otro. La definición de funciones en LISP se basa en el lambda cálculo. En este cálculo las sustituciones son de una variable por un término.

La sintaxis del lambda cálculo es muy simple:

t ::= x\ |\ t t\ |\ \lambda x.t

La x son las variables. Las dos t son dos términos yuxtapuestos y representan la aplicación. Finalmente la lambda destaca la variable a sustituir en el término que precede. Es decir, el lambda cálculo separa la sustitución en dos partes: abstracción y aplicación.

La regla fundamental del lambda cálculo es la beta reducción. No es más que la sustitución de la variable por el argumento aplicado.

(\lambda x. t) s \rightarrow t[x/s]

En el LISP se usa otra técnica similar. Para empezar se usa el orden aplicativo (primero se calcula el valor de s y luego se aplica). En vez de sustituir, vinculamos la x al valor del argumento recién calculado. Luego, cuando evaluemos t y nos encontremos con el nombre x, usamos ese valor. Realmente es como si sustituyamos con la aparición intermedia del entorno. Veremos más adelante que esto es muy útil.

La clausura léxica

La descripción de arriba deja un pequeño resquicio problemático. Al no sustituir sino vincular los nombres con valores, cabe la posibilidad de hacer referencia a nombres no definidos. Esto ya lo he hablado alguna que otra vez en mensajes previos. La solución es dejar que cada entorno donde se vinculen nombres a valores tenga un entorno padre. El entorno padre de la aplicación de argumentos ha de ser el entorno de definición.

De esta manera cualquier uso de un nombre que no sea un parámetro es capturado y no dará error. Es lo que se denomina la clausura léxica.

El resultado de todo esto es que una vez definamos una función usando una abstracción lambda (lo que he llamado una función lambda) necesitamos tres cosas:

1. El término de la abstracción (que se evalúa tras las vinculaciones)
2. Los nombres de los parámetros a vincular con los valores de los argumentos
3. El entorno padre del entorno que vincula los nombres anteriores (la clausura léxica)

Nuestro objeto Lambda estará compuesto de estas tres cosas.

El objeto Lambda

La estructura de este objeto será:

class Lambda
{
protected:
Cell& m_Params;
Cell& m_Body;
Cell& m_Closure;
}

Y las operaciones que queremos realizar sobre él son dos: crearlo y aplicarlo a unos argumentos.

public:
Lambda(Cell& params, Cell& body, Cell& closure)
: m_Params(params), m_Body(body), m_Closure(closure) {}

Cell& Apply(Heap& heap, Cell& args, Cell& envir)const;

Realmente la creación es muy simple: sólo hay que recordar estas tres cosas. La aplicación tiene algo más de trabajo ya que, al usar un orden aplicativo, hemos de evaluar los argumentos antes de vincularlos. Además, la vinculación requiere la creación de un nuevo entorno y la aplicación requiere una evaluación del cuerpo de la abstracción lambda.