AjLisp: un intérprete Lisp en .NET

Soy un entusiasta de escribir intérpretes, especialmente del tipo Lisp. Mi primer intérprete Lisp fue escrito al principio de los 80, usando el lenguaje assembler de un Intel 808x. Era un trabajo muy “geek”. Una de las características más “tricky” de implementar es un recolector de basura (garbage collector). Por suerte, desde mediados de los 90 tenemos Java y su  librería de clases como una tecnología ampliamente disponible con un garbage collector decente. En este siglo, .NET es la nueva plataforma de lenguajes con GC..

En el 2005, Martin Salias y yo dimos un TechNight, aquí en Buenos Aires, Argentina, para la oficina local de Microsoft. Trató sobre lenguajes implementados en .NET. Fue la primera vez que presenté F#, así como P# y otros. Despues de esa charla, la misma noche viajé a Mar del Plata, para dar otra charla sobre ASP.NET. Mar del Plata es una bella ciudad, en frente del océano Atlántico, a la que trato de volver cada año. Entonces, era mi primer visita luego de treinta años. En el viaje, “nació″ AjLisp.

Esa versión era un intérprete Lisp escrito en Visual Basic .NET. El pasado domingo, lo porté a C# (usando alguna opción de menú de SharpDevelop, ¿alguna otra herramienta que conozcan?). El código original fue usado hace unas semanas en mi post sobre VPL:

Lisp-like interpreter using DSS and VPL
Intérprete tipo Lisp usando DSS y VPL

La nueva versión C# version está publicada en Google Code en:

http://code.google.com/p/ajlisp/

Me gusta Google Code: tiene soporte de SVN, asi que uso mi cliente local TortoiseSVN para enviar los cambios en el proyecto.

La solución

Tiene tres proyectos:

AjLisp: el proyecto núcleo, una librería, que puede ser invocada desde otra aplicación.

AjLisp.Tests: Todos los tests, usando NUnit 2.2.8. Si no tienen NUnit, pueden remover el proyecto de la solución.

AjLisp.Console: un simple programa de consola.

Los tipos

Una interfaz base es IAtom:

public interface IAtom { bool IsAtom(); }

Otra es IList:

public interface IList { SymbolicExpression First { get; set; } SymbolicExpression Rest { get; set; } bool IsList(); }

Todos los tipos derivan de una SymbolicExpression:

namespace AjLisp.Types { public abstract class SymbolicExpression : IList, IAtom { ....

Implementé los tipos comunes a usar en un Lisp, como List, Atom, Identifier, Function (para invocar a primitivas y funciones generadas por lambdas), True, Nil…:

Existe una clase Environment para mantener valores asociados a nombres. Cada Environment tiene un Environment padre, para mantener una lista de ambientes con valores.

La clase Interpreter es la principal a manejar: tiene un Environment y define algunos nombres para las primitivas iniciales:

 

public class Interpreter { private Environment environment = new Environment(); public Interpreter() { Define("nil", Nil.Value); Define("t", True.Value); Define("cons", new SubrCons()); Define("first", new SubrFirst()); Define("car", new SubrFirst()); Define("rest", new SubrRest()); Define("cdr", new SubrRest()); Define("list", new SubrList()); Define("quote", new FSubrQuote()); Define("append", new SubrAppend()); Define("cond", new FSubrCond()); Define("atom", new SubrAtom()); Define("eval", new SubrEval()); Define("null", new SubrNull()); Define("lambda", new FSubrLambda()); Define("progn", new FSubrProgN()); Define("flambda", new FSubrFLambda()); Define("nlambda", new FSubrNLambda()); Define("mlambda", new FSubrMLambda()); Define("numberp", new SubrNumberP()); Define("functionp", new SubrFunctionP()); Define("idp", new SubrIdP()); Define("define", new FSubrDefine()); Define("definef", new FSubrDefineF()); Define("definen", new FSubrDefineN()); Define("definem", new FSubrDefineM()); Define("eq", new SubrEq()); Define("if", new FSubrIf()); Define("let", new FSubrLet()); Define("lets", new FSubrLetS()); Define("set", new SubrSet()); Define("consp", new SubrConsP()); Define("less", new SubrLess()); Define("greater", new SubrGreater()); Define("plus", new SubrPlus()); Define("difference", new SubrDifference()); Define("times", new SubrTimes()); Define("quotient", new SubrQuotient()); Define("remainder", new SubrRemainder()); } ....

Uds. pueden escribir sus propias primitivas y agregarlas a este constructor.

Las primitivas

El intérprete tiene las primitivas usuales:

Hay primitivas, que antes de su invocación, evalúan los argumentos recibidos. Son las que derivan de Subr:

public abstract class Subr : Function { public abstract SymbolicExpression Execute(SymbolicExpression args, Environment env); public override SymbolicExpression Apply(SymbolicExpression form, Environment env) { return Execute(form.Rest.Evaluate(env), env); } }

form.First es la función, y form.Rest es la lista de argumentos. Para evaluar el form, Function usa un objeto Environment.

Otras primitivas no evalúan sus argumentos, derivan de FSubr:

public abstract class FSubr : Function { public abstract SymbolicExpression Execute(SymbolicExpression args, Environment env); public override SymbolicExpression Apply(SymbolicExpression form, Environment env) { return Execute(form.Rest, env); } }

Una de las primitivas más interesantes, es la implementación de lambda, llamada FSubrLambda:

public class FSubrLambda : FSubr { public override SymbolicExpression Execute(SymbolicExpression args, Environment env) { return new SubrClosure(args.First, env, args.Rest); } }


Crea un Closure, una manera de recordar el Environment actual para usarlo en una futura invocación de la expresión lambda. Implementé también NLambda, FLambda, MLambda: N es por NonSpread (maneja su lista de argumentos como si fuera un solo argumento), F es cuando no son evaluados los argumentos antes de la invocación, y M es por Macro (tengo que revisar hasta donde implementé esta “feature”).


Los tests


Toda la funcionaliad está cubierta por tests. Configuré el proyecto AjLisp.Test para ejecuter NUnit GUI:



La consola


AjLisp.Console es un simple programa de consola. Pueden ingresar una expresión y la evalúa:



Es tan simple, que hay que usar Control-C para salir… ;-).


Próximos pasos


Hay tanto para hacer. Quiero mejorar algunos puntos:


  • Reescribir interfaces y clases de base
  • Manejar e invocar objetos .NET nativos
  • Tratar a Reales y Enteros por separado (hoy a ambos, al operar, los trata como valores double)
  • Revisar Macro expansion
  • Mejor consola
  • Librería de ejemplos
  • Un manual mínimo

La idea es llegar a extender este mini lenguaje para ser usado como la base programación de agentes distribuidos. Sería bueno portarlo a Java. Entonces, la conducta de los agentes y su estado puede ser escrito en este lenguaje, y viajar a distintos nodos de la grilla, de forma independiente a la plataforma.


Bueno, son sueños. Ahora, el estado actual: está funcionando, y me divertí escribiéndolo. Disfruten!


(Este artículo es una traducción a Spanish, desde el Anglish (Angel’s English) original:
AjLisp- a Lisp interpreter in .NET


)


Angel “Java” Lopez
http://www.ajlopez.com/en

This entry was posted in 1389, 3036, 5374, 8313, 8870. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>