Angel \”Java\” Lopez on Blog

July 30, 2008

AjLisp: a Lisp interpreter in .NET

Filed under: .NET, AjLisp — ajlopez @ 11:52 am

I’m a fan of writing interpreters, specially Lisp ones. My first Lisp interpreter was wrote in early 80s, using 808x Intel assembler language. Yes, it was a very geek work. Once of the tricky things to implement in such interpreter is the garbage collector. Since mid 90s, we have Java language and class library, as a main stream technology with a decent garbage collector. This century, .NET is the new language platform to use with GC.

In 2005, Martin Salias and me gave a TechNight session,  here, at Buenos Aires, Argentina, at Microsoft local office, about languages written using .NET. It was the first time I presented F#, P# and other interesting language implemented using the .NET framework. After that session, I traveled to Mar del Plata, to give another session about ASP.NET. It’s a beatiful city, in front of the Atlantic ocean, a city I arrange to visit every year. During the trip, AjLisp was born.

It was an Lisp-like interpreter written in VB.NET. This last weekend, I ported it to C# (I use a SharpDevelop menu option to translate VB.NET to C# code, do you know another tool?). The original code was used some weeks ago at my post about VPL:

Lisp-like interpreter using DSS and VPL

The new C# version is published in Google Code at:

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

I like Google Code: it has support for SVN, then I’m using my local TortoiseSVN client to commit the change to the project.

The solution

It has three project:

AjLisp: the core project, a library, that can be invoked from your application.

AjLisp.Tests: all test fixtures, using NUnit 2.2.8. If you don’t use NUnit, you can remove this project from the solution.

AjLisp.Console: a simple console interface.

The types

The base interface are IAtom:

public interface IAtom { bool IsAtom(); }

and IList:

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

All types then derive from SymbolicExpression:

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

I implemented the common types used in Lisp, like List, Atom, Identifier, Function (to invoke primitives or lambdas), True, Nil…:

An Environment class is provided to keep values under names. Each environment can have a parent environment, so we have a chain of them.

The Interpreter class is the main one: it has an Environment and defines some names for initial primitives:

 

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()); } ....

You can write your own primitives and add them to this constructor.

The primitives

The interpreter has the usual primitives:

There are primitives that, before evaluation, evaluate their arguments. They are classes deriving from 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 is the function, and form.Rest is the list of arguments. To evaluate the form, Function uses an environment object.

Other primitives don’t evaluate the received arguments, they are 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); } }

One of the most interesting primitives, is lambda implementation, named FSubrLambda:

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

It creates a Closure, a way to have to remember the current environment in a future invocation of the lambda expression. I implemented NLambda, FLambda, MLambda behavior: N stands for NonSpread (it manages the list of arguments as one argument), F means the arguments are not evaluated prior to invocation, and M is for Macro (I have to test and rewrite this functionality).

The tests

All functionality is covered by test. I configured the AjLisp.Tests library project to run NUnit GUI:

The console

AjLisp.Console is a simple console program. You can enter and evaluate sexpressions:

It is so simple, that you must close it using Control-C ;-).

Next steps

I want to improve some points:

  • Rewrite some classes and base interface
  • Manage and invocation of .NET native objects
  • Real and Integer treatment (using double dispatch to evaluate arithmetic ops, now they are used as double values)
  • Macro expansion
  • Better console
  • Some library examples
  • A minimal manual

The idea is to extends this mini language to be used as the basis for a distributed agent programming language. It should be nice to port to Java. Then, the agents behavior and state could be written in this language, and it could travel to other nodes in a grid.

But I’m dreaming. For now, this is current status: it’s working, and I had fun written this stuff. Enjoy it!

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

13 Comments »

  1. [...] AjLisp: a Lisp interpreter in .NET [...]

    Pingback by Closures in F# « Angel “Java” Lopez on Blog — August 13, 2008 @ 11:33 am

  2. [...] AjLisp- a Lisp interpreter in .NETAjTalk- a Smalltalk-like interpreter [...]

    Pingback by AjBasic: an open source Basic-like interpreter « Angel “Java” Lopez on Blog — August 19, 2008 @ 12:08 am

  3. [...] AjLisp: a Lisp interpreter in .NET Más sobre closures y C# en: [...]

    Pingback by Closures en F# | Buanzolandia — August 23, 2008 @ 11:19 pm

  4. [...] AjLisp: a Lisp interpreter in .NET [...]

    Pingback by Closures en F# - Angel "Java" Lopez — September 14, 2008 @ 6:12 pm

  5. [...] AjLisp- a Lisp interpreter in .NET [...]

    Pingback by La inteligencia artificial y yo | Buanzolandia — December 9, 2008 @ 12:23 am

  6. [...] I’m working on a Lisp interpreter, see AjLisp- a Lisp interpreter in .NET. [...]

    Pingback by Artificial Intelligence links and resources « Angel “Java” Lopez on Blog — February 11, 2009 @ 10:17 am

  7. [...] year I wrote a Lisp interpreter AjLisp- a Lisp interpreter in .NET, that I should improve, but past weeks, I started to write an Scheme-like [...]

    Pingback by Lord of the REPLs (Read Eval Print Loops) and CodePad « Angel “Java” Lopez on Blog — September 15, 2009 @ 9:27 am

  8. [...] año pasado escribí un intérprete Lisp AjLisp- a Lisp interpreter in .NET, AjLisp – un intérprete Lisp en .NET, que quiero mejorar, pero en las últimas semanas me [...]

    Pingback by Lord of the REPLs (Read Eval Print Loops) y CodePad - Angel "Java" Lopez — September 16, 2009 @ 9:34 am

  9. [...] AjLisp: a Lisp interpreter in .NET [...]

    Pingback by AjLisp family: implementing lisp interpreters in C# « Angel “Java” Lopez on Blog — January 4, 2010 @ 3:23 am

  10. [...] AjLisp: a Lisp interpreter in .NET AjLisp: un intérprete Lisp en .NET [...]

    Pingback by La familia AjLisp: implementado intérpretes Lisp en C# - Angel "Java" Lopez — January 5, 2010 @ 10:15 am

  11. [...] AjLisp: a Lisp interpreter in .NET AjLisp: un intérprete Lisp en .NET [...]

    Pingback by Refactoreando AjLisp: un intérprete Lisp escrito en C# - Angel "Java" Lopez — January 10, 2010 @ 11:50 am

  12. I’ve been browsing online more than 2 hours today, yet I never found any interesting article like yours. It is pretty worth enough for me. In my opinion, if all webmasters and bloggers made good content as you did, the net will be a lot more useful than ever before.

    Comment by Meghan — November 11, 2012 @ 5:26 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 56 other followers

%d bloggers like this: