domingo, 10 de enero de 2010

Haciendo un intérprete de LISP (XI)

Hasta ahora hemos probado nuestro intérprete de una forma ficticia. Hemos dicho que había un bucle de lectura, evaluación e impresión (llamado REPL de read-evaluate-print loop) pero nunca lo hemos implementado. Es hora de hacerlo.

Inicialización

La inicialización del bucle principal es bien sencilla: crear el montículo, crear el entorno inicial para darles nombre a las funciones nativas y empezar con el bucle.

En nuestro modelo de celdas hay que crear una celda para crear el entorno y luego poder acceder al objeto Environment directamente.

int main()
{
Heap h;
Cell& envir=h.CreateEnvironment(NULL);
Environment& env=envir.GetEnvironment();

Las funciones nativas que tenemos son dos: sumar enteros y creación de funciones lambdas. Las hemos llamado ya "add" y "lambda".

 env.Bind(h, L"add", &FOL_Add);
env.Bind(h, L"lambda", &FOL_Lambda);

A partir de este punto, y mientras este entorno esté accesible por la evaluación, podremos usar estas funciones nativas.

El bucle principal

En principio no queremos salir del bucle. Usaremos "for(;;)" que es lo mismo que escribir "while(true)".


for(;;)
{

A continuación vamos a leer una línea de texto del usuario. Como no queremos calentarnos la cabeza reservando buffers, tentemos a la suerte con un buffer en la pila (podríamos tener desbordamiento). Para que quede más bonito le ponemos un prompt ">" y saltos de línea "\n" que separen la entrada del usuario de la salida del evaluador.


wchar_t buffer[8192];
std::wcout << L"\n> ";
std::wcin.getline(buffer, 8192);
std::wcout << L"\n";

El hecho de que hasta ahora sólo hayamos trabajado con la evaluación significa que llamaremos a funciones que aún no tenemos preparadas. Concretamente la impresión y la lectura de expresiones S. La impresión es sencilla, pero la lectura requiere un pequeño parser así que he decidido encapsularla en otra clase que he llamado Exp (expresión). Esta clase lanza excepciones si el usuario introdujo una expresión S incorrecta.

  try
{
Exp e(h, buffer);

Es importante ver que Exp necesita el montículo (heap) como argumento ya que va a crear expresiones con celdas y el único objeto que puede crear celdas es el montículo. De esta forma las celdas creadas están controladas lo que será muy importante más adelante.

Debido a que el usuario puede introducir varias expresiones -por ejemplo "(add 1 1) (add 2 2)"- la clase Exp las mete en una lista. Queremos evaluar lo que ocurra en esa lista expresión a expresión. Nos quedaremos con el último resultado para simplificar. Todo esto lo hará la función EvaluateInSequence().


try
{
Exp v=e.EvaluateInSequence(envir);

De alguna mágica manera, imprimiremos.


v.Print(std::wcout);
std::wcout << std::endl;
}

Y capturamos las excepciones tanto en evaluación como en lectura.


catch(std::exception& e)
{
std::wcout << L"Exception evaluating: ";
std::cout << e.what() << std::endl;
}
}
catch(std::exception& e)
{
std::wcout << L"Exception parsing: ";
std::cout << e.what() << std::endl;
}
}
}


Evaluando en secuencia

Será más sencillo si en vez de hacerlo en Exp lo hacemos en Heap. De esta forma Exp se queda sólo como un envoltorio que únicamente se dedica a leer expresiones.

Exp Exp::EvaluateInSequence(Cell& envir)
{
return Exp(*m_Heap, m_Heap->EvaluateInSequence(*m_Cell, envir));
}

Para evaluar en secuencia empezamos por la primera expresión de la lista y continuamos cada vez con la siguiente hasta llegar al final. Una vez ahí, paramos. 

Cell& Heap::EvaluateInSequence(Cell& cell, Cell& envir)
{
Cell* c=&cell;
Cell* r=&CreateEmpty();
while(c->IsPair())
{
r=&Evaluate(c->GetHead(), envir);
c=&c->GetTail();
}
return *r;
}

Esta evaluación en secuencia también me va a servir para que "lambda" pueda trabajar con una secuencia de expresiones. Es decir, podremos hacer cosas como "(lambda (x) (add 1 1) (add x x))" y calculará primero la parte "(add 1 1)" y luego "(add x x)" retornando este último valor. Basta cambiar la última línea en Lambda::Apply (lo vimos en la parte VIII)

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

 Cell const *a, *p;
for(a=&args, p=&m_Params; a->IsPair() && p->IsPair(); a=&a->GetTail(), p=&p->GetTail())
local.Bind(heap, *p->GetHead().GetName(), heap.Evaluate(a->GetHead(),envir));

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

 return heap.EvaluateInSequence(m_Body, local_cell);
}

El cambio es en la última línea. De hecho, el llamar a Evaluate() era incorrecto ya que m_Body era una lista (ver parte X). Ahora sí que todo queda consistente.

En la siguiente parte sacaremos provecho a esta habilidad de evaluar varias expresiones en secuencia. Además, introduciremos una función nativa que nos saca del bucle (infinito) de lectura evaluación e impresión.

0 comentarios:

Publicar un comentario en la entrada