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
F# is a functional language, created by Microsoft. Implemented under .NET CLR, it’s a typed language, with access to .NET framework. It inherits most of ML/OCaml features. 
