domingo, 20 de diciembre de 2009

Haciendo un intérprete de LISP (IX)

Hasta ahora hemos usado los entornos sin definir claramente cómo son. Ahora lo haremos.

Entornos

Un entorno no es más que un mapa de las cadenas (nombres) a las celdas de un montículo. Adicionalmente, los entornos deben poder usar nombres de entornos ya creados. Entornos padres.

class Environment
{
public:
Environment(Cell* parent) : m_Parent(parent) {}

Cell& FindBond(STRING name)const;
Cell& Bind(Heap& heap, std::wstring const& name, NATIVE native);
Cell& Bind(Heap& heap, std::wstring const& name, Cell& cell);

void Print(std::wostream& o, std::wstring const& indent, int depth=10)const;

public:
Cell* m_Parent;
typedef std::map<string, Cell*> BONDMAP;
BONDMAP m_Bonds;
};

Hemos usado un pequeño atajo para incluir funciones nativas.

Cell& Environment::Bind(Heap& heap, std::wstring const& name, NATIVE native)
{
Cell& r=heap.CreateNative(native);
m_Bonds[heap.GetStringFromPool(name)]=&r;
return r;
}

Cell& Environment::Bind(Heap& heap, std::wstring const& name, Cell& cell)
{
m_Bonds[heap.GetStringFromPool(name)]=&cell;
return cell;
}

Buscando en el entorno padre

La búsqueda en un entorno no debe fallar si no se encuentra el nombre deseado. En ese caso hemos de recurrir al entorno padre. Esta es una forma de extender el entorno padre de manera sencilla.

Cell& Environment::FindBond(STRING name)const
{
BONDMAP::const_iterator i=m_Bonds.find(name);
if(i==m_Bonds.end() || i->second==NULL)
{
if(m_Parent==NULL)
throw std::runtime_error("Unknown symbol");

return m_Parent->GetEnvironment().FindBond(name);
}

return *i->second;
}

El resultado es una función de búsqueda recursiva, pero sin mayor dificultad.

miércoles, 16 de diciembre de 2009

Haciendo un intérprete de LISP (VIII)

En este mensaje vamos a ver cómo funciona la aplicación de una función lambda.

Creación del entorno local

El primer paso en la aplicación de una función lambda es crear un entorno local. Esto es necesario para dos cosas. La primera es aislar la evaluación de la función del entorno de uso de la función. Si lo lo aisláramos, se podría definir un símbolo en el entorno de uso. Lo que es antihigiénico. También usamos el entorno local para vincular el resultado de la evaluación de los argumentos a los nombres de los parámetros.

Cell& Lambda::Apply(Heap& heap, Cell& args, Cell& envir)const
{
Cell& local_cell=heap.CreateEnvironment(&m_Closure);
Environment& local=local_cell.GetEnvironment();

La creación de un entorno ha de estar sujeta a la gestión de memoria. Por esa razón lo creamos en una celda y, dentro de la celda, tenemos el objeto Environment que es realmente el entorno. Para simplificar futuros uso en la aplicación, le damos el nombre "local" al propio entorno.

Vinculación de los resultados de los argumentos

Ahora debemos ir argumento por argumento evaluándolos en el entorno de uso. El resultado de cada evaluación debe ser vinculada a cada parámetro. Así pues, necesitamos dos listas: la de los argumentos y la de los parámetros.

 Cell const *a, *p;

Las iremos recorriendo a la vez. Desde el principio hasta que una de las dos no sea un CT_PAIR. En ese momento terminaremos. Si no hemos terminado, avanzamos en ambas a la vez.

 for(a=&args, p=&m_Params; a->IsPair() && p->IsPair(); a=&a->GetTail(), p=&p->GetTail())

El interior del bucle debe primero evaluar el argumento y luego vincularlo. Es importante recordar aquí que estamos apuntando a una lista y para obtener el elemento que hay en cabeza de la lista hay que ir a su cabeza.

 local.Bind(heap, *p->GetHead().GetName(), heap.Evaluate(a->GetHead(),envir));

Los parámetros han de ser nombres así que si no lo son GetName() fallará con una excepción. La evaluación es en "envir". Este es el entorno de uso desde el que se llama a la función. El método "Bind" queda por ser definido pero lo que hace es relacionar el nombre pasado con el valor pasado (celda pasada).

Una comprobación de aridad

En este punto puede ocurrir que haya más argumentos que parámetros o más parámetros que argumentos. En ambos casos es un error y debemos lanzarlo.


if((a->IsEmpty())!=(p->IsEmpty()))
throw std::runtime_error("Incorrect arity");

Como vemos, es fácil de detectar ya que basta con que una de las dos listas no esté vacía. Como sabemos que una de las dos no es un CT_PAIR y que ambas son listas, la comprobación se simplifica a lo puesto arriba.

La evaluación del cuerpo

Ya tenemos el entorno local con los parámetros vinculados a los valores de los argumentos correspondientes. Eso significa que si evaluamos ahora el cuerpo y nos encontramos con un nombre de parámetro, al estar vinculado al valor del argumento, se evaluará a dicho valor.


return heap.Evaluate(m_Body, local_cell);
}

Ni que decir tiene que al evaluar dentro de una aplicación abrimos la puerta a la recursividad. Esto es deseable.

Esto es el núcleo de cualquier LISP. En los siguientes posts veremos algunos detalles menores: la implementación de los entornos (y el método Bind), evaluación de secuencias y poco más.

domingo, 13 de diciembre de 2009

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.

jueves, 10 de diciembre de 2009

Haciendo un intérprete de LISP (VI)

El resultado de una evaluación era o bien un valor muy fácilmente calculable (literal, error, nombre) o bien una aplicación de una función (nativa o lambda) a unos argumentos. En este post veremos cómo realizar una función nativa.

La interfaz de la función nativa

Si recordamos del último post, había tres cosas que pasábamos con la aplicación de la función nativa: El montículo por si queríamos reservar más celdas; la lista de argumentos y el entorno por si necesitamos calcular el valor de un nombre. Así que la interfaz de una función nativa debe ser:

typedef Cell& (*NATIVE)(Heap& heap, Cell& args, Cell& envir);

Es importante recordar aquí que los argumentos no están evaluados. Se pasaban directamente (ver en el último post). Será un detalle a tener en cuenta.

Una función para sumar enteros

Como uno de los tipos de literales que tenemos son los enteros, hagamos una pequeña función nativa que sume enteros. Sabemos empezarla con la interfaz de arriba.

Cell& FOL_Add(Heap& heap, Cell& args, Cell& envir)
{

Luego hemos de pensar en evaluar los argumentos. Si son literales no hay problemas (se evalúan a ellos mismos), pero si tenemos dos sumas anidadas hay que evaluar. Así pues necesitamos dos cosas: los argumentos y el resultado parcial de la suma.

 Cell* qa=&args;
INTEGER result=0;

Lo que vamos a hacer es ir recorriendo la lista de argumentos sin evaluar (qa) e ir añadiendo los resultados de la evaluación de los argumentos a result. Como una lista es una cadena de pares, el código sería así:

 while(qa->IsPair())
{
result+=heap.Evaluate(qa->GetHead(), envir).GetInteger();
qa=&qa->GetTail();
}

Finalmente, el resultado es un entero pero lo tenemos en una variable, no en una celda. Hay que crear la celda y retornarla. Usamos el montículo para eso.

 return heap.CreateInteger(result);
}

Con lo que sólo faltaría probar la función nativa.

El bucle de lectura-evaluación-impresión

Un intérprete LISP hace tres cosas en ciclo y de forma indefinida. Primero, lee una expresión S. Luego, la evalúa obteniendo un resultado. Finalmente, la imprime. Hasta ahora sólo hemos hablado de la evaluación. La lectura y la impresión son asuntos menores.

Otro aspecto importante es que no podemos usar la función nativa directamente. Hay que darle primero un nombre. Para eso necesitamos manipular entornos. Tampoco es excesivamente difícil y lo veremos algo más adelante. Si le damos el nombre "add" a la función nativa de arriba, interactuamos con el intérprete de la siguiente manera:

> (add 13 72)

85

>

En los siguientes posts hablaré de qué es una celda CT_LAMBDA, cómo generarlas y cómo usarlas. Esto nos deparará algunas interesantes sorpresas como las clausuras léxicas.

lunes, 7 de diciembre de 2009

Haciendo un intérprete de LISP (V)

En los posts anteriores vimos unas estructuras muy simples para almacenar valores de nuestro LISP. Estas estructuras son las celdas. Las celdas estaban gestionadas por un montículo (heap) con el cual podíamos crear nuevas celdas. También recordamos que las expresiones S en las que escribíamos nuestro código eran parte de los valores. Esto es lo que se denomina homoiconicidad.

En este post vamos a ir al núcleo del asunto: crear una celda resultado de una expresión. 

Evaluación

Las reglas de evaluación del LISP son muy sencillas y ya las vimos. Según el tipo de celda, se evalúa de una u otra manera. Eso significa que nuestra función de evaluación va a ser un switch.

Debido a que la evaluación va a crear nuevas celdas con el resultado de los cálculos, voy a incluirla en el montículo.

Además, y debido a que vamos a tener nombre cuyo valor dependerá del contexto en el que los evaluemos, vamos a requerir el paso de un argumento extra con ese contexto. El contexto estará guardado en un entorno que es otro tipo de celda.

Con todas estas cosas en mente, empezamos la implementación así:

Cell& Heap::Evaluate(Cell& c, Cell& envir)
{
if(envir.CellType()!=Cell::CT_ENVIR)
throw std::runtime_error("Environment cell is not an environment");

switch(c.CellType())
{

Empecemos por el caso más fácil. Si la celda no es de un tipo evaluable, emitimos un error.

 default:
case Cell::CT_UNUSED:
case Cell::CT_ENVIR:
case Cell::CT_LAMBDA:
throw std::runtime_error("Evaluating a non-evaluable cell");

El siguiente caso más fácil son los literales. El resultado del literal es él mismo aquí tenemos dos opciones. La primera es crear otra celda con el mismo valor, la segunda es reutilizar la celda de la propia expresión como valor del resultado. Generalmente se usa esta última opción ya que nos ahorramos una reserva de celda.


case Cell::CT_EMPTY:
case Cell::CT_INTEGER:
case Cell::CT_REAL:
case Cell::CT_STRING:
case Cell::CT_BOOLEAN:
return c;

Destacamos aquí que la lista vacía se evalúa también como un literal. Es decir, el resultado de una lista vacía es la propia lista vacía.

El siguiente caso más fácil es el de los nombres. Los nombres se evalúan a lo que diga el entorno en el que estamos. Como ese entorno ya se nos ha pasado en un argumento, delegamos esa búsqueda al entorno. Habrá que programarla más adelante.

 case Cell::CT_NAME:
return envir.GetEnvironment().FindBond(c.GetName());

Finalmente, queda la evaluación de una lista compuesta por una cadena de pares. Es algo más complejo así que le dedicaremos un apartado especial.

Aplicación de argumentos

Hay una distinción que es clave. Una función no es lo mismo que el nombre de la función. De hecho, una misma función puede tener varios nombres. Eso dependerá del entorno.

Así pues, no es lo mismo evaluar el nombre de una función a evaluar la función. En el primer caso usamos el entorno, en el segundo caso necesitamos unos argumentos que pasarle a la función para que ésta calcule su resultado. A esta última operación se la llama aplicación.

Debido a que a las funciones se les pasa los argumentos en una lista (ya que las expresiones S son listas) hemos de requerir que realmente sea una lista. Es decir, una cadena de pares (celdas CT_PAIR) acabada en CT_EMPTY. Algo como (f a b c d) que realmente es [f [a [b [c [d ()]]]]].

 case Cell::CT_PAIR:
if(c.IsList())
{

Ya veremos qué ocurre si no es una lista. En este caso, sabemos que el primer elemento de la lista es el nombre de la función y hay que evaluarlo para realmente obtener la función en sí.


Cell& f=Evaluate(c.GetHead(), envir);

Dijimos que íbamos a tener dos tipos de funciones. Las funciones nativas (las predefinidas) y las lambda (definidas por el usuario). El primer caso es muy sencillo. Le pasamos a la nativa el montículo (para que pueda reservar sus celdas), los argumentos (para que pueda usarlos al evaluar) y el entorno (por si necesita usar o crear nombres). El resultado de la evaluación será lo que la función nativa nos diga.


if(f.IsNative())
return f.GetNative()(*this, c.GetTail(), envir);

Ya tendremos tiempo de implementar algunas funciones nativas más adelante. Ahora nos conformaremos con echarle toda la carga de trabajo a la nativa.

En este momento comprobamos que la celda que tenemos o es una función lambda o estamos intentando aplicar algo que no es una función.


if(f.CellType()!=Cell::CT_LAMBDA)
throw std::runtime_error("Applying non-lambda");

Finalmente, como lo que tengo es una CT_LAMBDA, usaré el objeto Lambda para aplicar los argumentos. Como hicimos con las funciones nativas, no vamos a definir ahora cómo se aplica una lambda. De hecho, primero hemos de saber cómo construir una función lambda y para eso vamos a necesitar una función nativa. Así que ni nos preocupamos, de nuevo le pasamos el montículo, los argumentos, el entorno y lo que retorne el método Apply del objeto Lambda será el resultado de la evaluación.


return f.GetLambda().Apply(*this, c.GetTail(), envir);
}

Para acabar tenemos el caso de qué hacer si estamos evaluando un CT_PAIR que no es una lista. La opción más fácil sería abortarlo emitiendo un error pero, por hacer algo distinto, vamos a evaluar cada uno de los dos componentes del par y retornamos un nuevo par (habrá que crearlo) con cada resultado en el componente correspondiente.


else
{
//Create pair
return CreatePair(Evaluate(c.GetHead(), envir), Evaluate(c.GetTail(), envir));
}

Cerramos switch y la función de evaluación.


}
}

Resumiendo

No se ha hecho mucho en la evaluación realmente. Hemos comprobado el tipo de celda. Según ese tipo o emitíamos un error o devolvíamos la propia celda o buscábamos el nombre en el entorno o aplicábamos argumentos si era nativa o lambda.

Ahora todo el meollo está en la aplicación. Como tenemos los enteros como tipos básicos, introduciremos una pequeña función nativa que los sume... pero en el siguiente post.

miércoles, 2 de diciembre de 2009

Coinducción

Estudiando teoría de tipos me he cruzado con el concepto de coinducción. Es un concepto fácil y con interesantes consecuencias.

Inducción

Tanto en la inducción como en la coinducción queremos saber qué elementos de un conjunto universo U cumplen una propiedad P. Llamemos precisamente P al conjunto de elementos que cumplen P. Obviamente

[$$ P\subseteq U $$]

En el caso de la inducción partimos con unos casos base B que son elementos de los que tenemos constancia directa de su propiedad P. De nuevo y obviamente

[$$ B\subseteq P\subseteq U $$]

Ahora necesitamos el paso de inducción. El paso de inducción nos dice que si conocemos que ciertos elementos cumplen la propiedad, entonces otros también la cumplen. El paso clásico es

[$$ P(n)\rightarrow P(n+1) $$]

Sin embargo, generalizamos pensando que si he comprobado que los elementos de X cumplen la propiedad, entonces los elementos de F(X) también la cumplen. F(X) representa a los elementos del siguiente paso. Es decir,

[$$ X\subseteq F(X) $$]

El resultado es que cada vez X se hará más y más grande... hasta encontrar un punto fijo (por el teorema de Kleene es el mínimo punto fijo)

[$$ X=F(X)=\mu F $$]

En ese momento P=X.

Nota adicional: Si hacemos que

[$$ F(\emptyset )=B $$]

Se captura también la idea de caso base en el formalismo de F (llamada función generadora). Una restricción para esta F es que debe ser monótona.

[$$ U\subseteq V \rightarrow F(U)\subseteq F(V) $$]

Esto es lógico porque si hemos probado que un elemento x cumple la propiedad P(x) está claro que debe seguir cumpliéndola conforme avancemos en la demostración.

Coinducción

Algunas propiedades no se pueden demostrar por inducción. Sólo podremos demostrar por inducción aquellas en las que exista una función generadora F cuyo mínimo punto fijo sea P. Como ya hemos escrito,

[$$ \mu F=P $$]

Sin embargo, tenemos otro punto fijo que es el máximo punto fijo. En este punto fijo, empezamos por asumir que todos los elementos de U cumplen la propiedad y luego, con la F, vamos quitándolos. Eso es la coinducción.


Partimos de unos casos bases de los que estamos seguros que fuera de ellos no se cumple P. Luego vamos refinando esos casos quitando poco a poco, usando F otra vez, hasta llegar al máximo punto fijo.

[$$ \nu F=F(X)=X=P $$]

Todo esto está muy bien, ¿pero para qué sirve?

Principalmente para nada si ambos puntos fijos son el mismo, pero si no son el mismo obtenemos propiedades distintas ya usemos la inducción o la coinducción.

Aplicación a los subtipos recursivos

Supongamos que tenemos una lista definida de la manera usual en tipos algebráicos paramétricos.

Lista(X) = vacía | par X Lista(X)

Es decir, una lista es o bien la lista vacía o bien un par de un elemento del contenido de la lista (tipo X) con el resto de la lista.

Ahora tendremos dos tipos, los enteros y los reales. Está claro que un entero es un subtipo de un real de sólo lectura ( Entero <: Real ), pero ¿es una lista de enteros una lista de reales? ( Lista(Entero) <: Lista(Real) ).


Vayamos por partes.


Una lista vacía es una lista vacía así que no vamos a tener problemas ahí.

Si un par X Y es subtipo de otro par S T entonces X ha de ser subtipo de S e Y de T. Es decir

[$$ par\ X\ Y\ <:\ par\ S\ T\ \ \leftrightarrow\ \ X<:S\ \ \wedge\ \ Y<:T $$]


Cuando comparamos las listas de enteros y reales los primeros términos del par son precisamente Entero y Real por lo que todo va bien. Sin embargo, en el segundo término volvemos a tener Lista(Entero) y Lista(Real) que es justo lo que queríamos comprobar.

Estamos usando tipos recursivos y es normal que esto pase.

Si usáramos inducción deberíamos decir "Como no he comprobado que Lista(Entero)<:Lista(Real) entonces lo asumo falso y concluyo que una lista de enteros no es una lista de reales".


Si usáramos coinducción deberíamos decir "Como no he comprobado que Lista(Entero)<:Lista(Real) entonces lo asumo cierto y concluyo que una lista de enteros es una lista de reales".


En los lenguajes de programación que usan tipos recursivos, el uso de la coinducción es necesario ya que de otra forma estos tipos recursivos no cumplirían ninguna propiedad.