Angel \”Java\” Lopez on Blog

May 3, 2010

AjCoreLisp and MinimaLisp, a minimal Lisp interpreter implementation

As I mentioned in:

AjLisp family: Implementing Lisp Interpreters in C#

I was working written two Lisp interpreters: AjLisp and AjSharpure (a clojure-like interpreter). But I wanted to explore what is the core of the language, the minimal part that should be implemented, in order to have a Lisp interpreter.

Then, I wrote AjCoreLisp. You can download from my Google project

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjCoreLisp

It is implemented in C#. The solution:

has five projects:

AjCoreLisp: core class library, implementing the language base, but without parser and lexer, only execution runtime.

AjCoreLisp.Tests: as usual, I developed the library using TDD approach. This is the tests project of the core library.

MinimaLisp: A proof-of-concept lexer, parser, and minimal machine, to show how to use the core library to build a minimal Lisp interpreter.

MiminaLisp.Console: the interactive console interpreter.

MiminaLisp.Test: TDD tests written during the development of MinimaLisp.

The root interface is IExpression:

    public interface IExpression
    {
        object Evaluate(IEnvironment environment);
    }

Any Lisp has list support. The IList interface is:

 

    public interface IList : IExpression
    {
        object First { get; }
        object Rest { get; }
        IList Next { get; }
    }

No update of the list are supported. If you want to add such list, you should derive from this interface, and put the implementation in your extending project, as MinimaLisp. Note that I borrowed from Clojure, the idea of having Rest and Next: the former return an object, the latter presumes the rest of the list is a list itselft.

Every form implements the interface IForm:

    public interface IForm
    {
        object Apply(IEnvironment environment, IList arguments);
    }

Then, the Form class implements IForm and IExpression:

    public class Form : IForm, IExpression
    {
        private IList parameters;
        private IIdentifier parameter;
        private IList body;
        private IEnvironment environment;
        public Form(IList parameters, IList body, IEnvironment environment)
        {
            this.parameters = parameters;
            this.body = body;
            this.environment = environment;
        }
        public Form(IIdentifier parameter, IList body, IEnvironment environment)
        {
            this.parameter = parameter;
            this.body = body;
            this.environment = environment;
        }
// ....
        public object Evaluate(IEnvironment environment)
        {
            return this;
        }
        public virtual object Apply(IEnvironment environment, IList arguments)
        {
            IEnvironment newenv;
            
            if (this.parameter != null)
                newenv = this.MakeNewEnvironmentList(arguments);
            else
                newenv = this.MakeNewEnvironment(arguments);
            return Machine.EvaluateBody(this.body, newenv);
        }
// ....
    }

Note that Form does not evaluate its arguments. That is the job of derived Function class:

    public class Function : Form, IExpression
    {
        public Function(IList parameters, IList body, IEnvironment environment)
            : base(parameters, body, environment)
        {
        }
        public Function(IIdentifier parameter, IList body, IEnvironment environment)
            : base(parameter, body, environment)
        {
        }
        public override object Apply(IEnvironment environment, IList arguments)
        {
            return base.Apply(environment, BaseForm.EvaluateList(arguments, environment));
        }
    }

As usual, macros have a twists: they evaluate its body, and then, evaluates the returned value:

    public class Macro : Form, IExpression
    {
// ...
        public override object Apply(IEnvironment environment, IList arguments)
        {
            object value = base.Apply(environment, arguments);
            value = Machine.Resolve(value, environment);
            return Machine.Evaluate(value, environment);
        }
    }

Ok, enough source code. Look the complete code, for more details. The main point is that AjCoreLisp implements few primitives:

The binding to this primitives is the job of MinimaLisp Machine:

        public MinimalMachine()
        {
            this.Environment.SetValue("first", new First());
            this.Environment.SetValue("rest", new Rest());
            this.Environment.SetValue("cons", new Cons());
            this.Environment.SetValue("quote", new Quote());
            this.Environment.SetValue("define", new Define());
            this.Environment.SetValue("lambda", new Lambda());
            this.Environment.SetValue("flambda", new FormLambda());
            this.Environment.SetValue("mlambda", new MacroLambda());
            this.Environment.SetValue("let", new Let());
            this.Environment.SetValue("letrec", new RecursiveLet());
            this.Environment.SetValue("eval", new Evaluate());
            this.Environment.SetValue("if", new If());
            this.Environment.SetValue("do", new Do());
            this.Environment.SetValue("nil?", new IsNil());
            this.Environment.SetValue("list?", new IsList());
            this.Environment.SetValue("equal?", new IsEqual());
        }

Based on that set, I could write a set of core functions:

(define list x x)
(define definem 
  (mlambda x 
    (list 
      'define 
      (first x)
      (cons 'mlambda (rest x))
    )
  )
)
(define mapfirst (fn lst)
  (if (nil? lst)
    nil
    (cons 
      (fn (first lst)) 
      (mapfirst fn (rest lst))
    )
  )
)
    
(define mapcond (fn lst)
  (if (nil? lst)
    nil
    (if (fn (first lst))
      (cons 
        (first lst) 
        (mapcond fn (rest lst))
      )
      (mapcond fn (rest lst))
    )
  )
)
(define append (x y) (if (nil? x) y (cons (first x) (append (rest x) y))))
  
(definem cond lst
  (if (nil? lst)
    nil 
    (list 
      'if 
      (first (first lst)) 
      (cons 'do (rest (first lst))) 
      (cons 'cond (rest lst))
    )
  )
)
(define atom? (x)
  (cond 
    ((nil? x) t)
    ((list? x) nil)
    (t t)
  )
)
(definem and lst
  (if (nil? lst)
    t
    (list 
      'if 
      (first lst)
      (cons 'and (rest lst))
      nil
    )
  )
)
(definem or lst
  (if (nil? lst)
    nil
    (list 
      'if 
      (first lst)
      t
      (cons 'or (rest lst))
    )
  )
)
(define not (x)
  (if x
    nil
    t
  )
)
(definem backquote (lst) 
  (cond 
      ((nil? lst) nil)
        ((atom? lst) (list 'quote lst))
        ((equal? (first lst) 'unquote) (first (rest lst)))
        ((and (list? (first lst)) (equal? (first (first lst)) 'unquote-slice)) (list 'append (first (rest (first lst))) (list 'backquote (rest lst))))
        (t (list 'cons (list 'backquote (first lst)) (list 'backquote (rest lst))))
  )
)
(definem while lst
  (list 'if (list 'not (first lst)) nil (cons 'do (rest lst)) (cons 'while lst))
)

I’m very proud of my implementation of backquote (macro expansion). That is, these tests are green (note the use of unquote and unquote-slice):

this.EvaluateAndCompare("(backquote (a b c))", "(a b c)");
this.EvaluateAndCompare("(backquote (a (b c) d))", "(a (b c) d)");
this.Evaluate("(define x '(b b))");
this.EvaluateAndCompare("(backquote (a (unquote x) c))", "(a (b b) c)");
this.EvaluateAndCompare("(backquote (a ((unquote x)) c))", "(a ((b b)) c)");
this.EvaluateAndCompare("(backquote (a (unquote-slice x) c))", "(a b b c)");
this.EvaluateAndCompare("(backquote (a ((unquote-slice x)) c))", "(a (b b) c)");
this.EvaluateAndCompare("(backquote (a (unquote-slice x) (unquote-slice x) c))", "(a b b b b c)");

There is no numeric support, then, I wrote numbers using Peano-like ideas, only for tests:

(define succ (x)
  (cons x nil))
  
(define pred (x)
  (first x))
(define add (x y)
  (if (nil? x)
    y
    (add (pred x) (succ y))
  )
)

I didn’t improve the code for a while, but my next step could be refactor AjLisp to be based on this core interpreter. Now, I have a more clear idea of what is needed and what is accesory in a Lisp interpreter.

And, as usual, I had fun written all this code! 😉

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

January 4, 2010

AjLisp family: implementing lisp interpreters in C#

Filed under: .NET, AjCoreLisp, AjLisp, AjScheme, AjSharpure, Lisp, Programming Languages — ajlopez @ 3:22 am

In the last months, I was active written Lisp interpreters. Since the eighties, I like to write such interpreters. One of my preferred exercises when I study a new programming language, is to write a Lisp interpreter.

In 2008, I published a code written in C#, AjLisp:

AjLisp: a Lisp interpreter in .NET

At mid of 2009, I started to research Clojure. Then, I decide to explore the news ideas of that language, reimplemeting it in C# (original Clojure is written in Java, but there is a version written in .NET, that compiles to .NET using Dynamic Language Runtime). It’s only an interpreter (I should study more about DLR or .NET compilation, to write down a compiler; and about how to do it… ;-). The result is work in progress, named AjSharpure (I named it AjClojure, but I had to change the name). You can see the code, under development:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjSharpure

Initially, my idea was to port “one-to-one” Clojure java code, but I realized that its code is not easily read, no test on code, no spefication about the behavior of dozens of methods, so I stopped, and rethinked my way. I took courage, forget my initial code, and start bottom-up, full TDD, implementing piece by piece, only trying to follow the external behavior of the language, instead of its internal implementation.

I stopped AjSharpure development, to study more about variables in Clojure, Shared Transactional Memory, and other topics. Then I back to 2008 version of AjLisp. I write a new version in 2009, with major refactoring of the previous one. Now, it can manage native objects and values. The trunk is at:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjLisp

There is no “plain vanilla” Lisp, and there are TWO main dialects: Common Lisp and Scheme. I don’t like Common Lisp (I should write a post about my reasons), so, in order to know more about Clojure and current Lisp development, I started AjScheme, an interpreter that implements most of the Scheme reference (I give up to implement macros as in Scheme, I back to mlambdas and alike):

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjScheme

AjLisp was born following an old Christian Queinnec book (I didn’t find the code of that book in the web). He wrote a Lisp interpreter in Lisp itself. Queinnec use a simplified Lisp. But I want to study more about the minimal needed kernel. So, now I’m working on AjCoreLisp:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjCoreLisp

It has no parser or lexer. The idea is implement an minimal interpreter using AjCoreLisp as the basis: the result is named MinimaLisp, and it’s included in the trunk. I’m implementing few primitives, and I’m trying to write the rest of the common forms as functions or macros. A geeky decision: implement backspace macro expansion as a macro! See code at:

http://pastie.org/765371

Once I have AjCoreLisp stabilized, I will refactor AjLisp, AjScheme, to use a more slim kernel, but re-implementing the most used forms as primitives. I should measure the impact of using most used forms as macro. I’m confident on the successful of changes, since all is backed by a battery of test (TDD and tests save my day many times, when I refactored much of this code base).

I will write detailed posts about these different interpreters, variations over a leit motiv: the beautiful ideas of Lisp language.

Keep tuned!

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

Create a free website or blog at WordPress.com.