AjLisp: a Lisp interpreter in .NET

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

Lisp-like interpreter using DSS and VPL

My sunday project was to write some primitives of a Lisp-like interpreter using DSS Service Components. The core interpreter was derived from my previous work on AjLisp, a Lisp interpreter (I had never published the code before). I write it using Visual Studio 2008 and the CTP v2.0 of Microsoft Robotics Developer Studio. I published the code on my Skydrive space as DssLisp.zip.

The solution

It has two projects: a class library named AjLisp (a revamped version of my original interpreter in VB.NET):

and a C# Dss Service project, with has many implemented service components:

It has no manifest. It is designed to use from VPL diagrams.

Most of these components receive or return SymbolicExpression, the base type of my interpreter. See the messages for Rest service Execute operation:

[DataContract()] public class ExecuteRequest { [DataMember] public SymbolicExpression Expression; } [DataContract] public class ExecuteResponse { [DataMember] public SymbolicExpression Result; }

To use this components, you must adjust the references and directories in the DSS project (it points to my local directories, and to my local Microsoft Robotics Developer Studio install).

Using VPL

There are three VPL programs included in the examples. They use the compiled components of the solution. I had a problem with these VPL programs. I couldn’t run them from the menu option Run. You must use Build -> Compile as a Service, and then, use the option Run -> Run Compiled Services. I guess the origin of the problem is that the diagrams maps special messages, not only primitive types or Strings. In order to successful compile, you must adjust the properties of diagrams in each VPL project:

The first one DssLispVpl1 calculate (first ‘(a b c)):

 

There are two components LispParser and LispToString, that help to convert from string to SymbolicExpression and from SymbolicExpression to string.

The second one is DssLispVpl2:

It uses LispAppend component to append two predefined lists.

The third one is a mini-interpreter DsspLispInterpreter:

I must improve the error treatment. Now, if an exception occurs inside the service process, no Fault response is generated, and a causality is raised.

I could implement some generic contracts, and reuse it in many components, for example, a GenericBinaryOperation component.

Problems

I failed to write an Activity, to implement a Reverse function. The activity called itself recursively, but the generated code returns at the last recursive invocation. The problem is caused by my use of a merge to return a value. It’s weird to explain clearly, after some hours trying to do the job, I abandoned the code. Another stone in the way was the fact that activities only accept predefined types in its messages and results. But in this case, I found a solution: generate the code, and modified the generated solution to accept my SymbolicExpression type as inputs and outputs.

One interesting thing I wrote, is the component Uncons, that has TWO expressions in its result response: it takes a list, and returns the first and the rest of that list. Having two members in the response, you can processes each one in parallel branchs of the diagram.

Conclusion

As in previous posts, I found the VPL orchestration as very powerful and interesting, but lacks the support of a generic object, and has problems to manage custom types. I think you can implements any functional languages primitives and make a VPL diagram for each program you want. VPL would have problems with recursion (or I didn’t found a workable solution to manage it). This exercise could be expanded to other ideas:

- Manage a pipeline processing a generic message (I discovered that we can have a generic object as a DataMember)
- Have load balance as a component
- Serialize/Deserialize objects between nodes
- Implement some workflow or application intergration patterns in VPL

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