# Abstract syntax tree for simple Lisp-like interpreter

A week or so ago, I wrote a binary expression calculator with the hope of better understanding how interpreters and compilers work. In the same vein, I've tried to write a lisp like language interpreter in C#. So far, I've only written code to represent the abstract syntax tree, and haven't written code to parse string text.

# Values and Expressions

Everything in the tree is an IExpression. Classes that implement this interface must provide an implementation for Evaluate (i.e. know how to turn themselves into a Value, another type of IExpression), within the context of an environment.

/// <summary>
/// Interface for all expressions (objects
/// that evaluate to a Value).
/// </summary>
public interface IExpression
{
Value Evaluate(Dictionary<string, Value> env);
}

/// <summary>
/// Base class for all Value types (types that
/// evaluate to self)
/// </summary>
public abstract class Value : IExpression
{
public Value Evaluate(Dictionary<string, Value> env)
{
return this;
}
}


Here are the values I define:

/// <summary>
/// Represents a constant literal (float/int) implemented as C# double)
/// </summary>
[DebuggerDisplay("[Number: Value={Value}]")]
public class Number : Value
{
public Number(double value)
{
Value = value;
}

public override string ToString()
{
return Value.ToString();
}

}

/// <summary>
/// Represents a boolean (true/false)
/// </summary>
[DebuggerDisplay("[Bool: Value={Value}]")]
public class Bool : Value
{
public Bool(bool value)
{
Value = value;
}

public override string ToString()
{
return Value.ToString();
}

}

/// <summary>
/// Represents a function closure (what functions
/// evaluate to). Closures make local environments
/// (lexical scoping) possible. Without closures,
/// we wouldn't be able to use the same parameter
/// name in other parts of our program.
/// </summary>
[DebuggerDisplay("[Closure: Func={Func.Name}]")]
public class Closure : Value
{
public Closure(Function func,
Dictionary<string, Value> env)
{
Func = func; Env = env;
}

}


And here are the expressions I define:

/// <summary>
/// Represents a Variable
/// </summary>
[DebuggerDisplay("[Variable: Name={Name}]")]
public class Variable : IExpression
{
public Variable(string name)
{
Name = name;
}

// Variables evaluate to the Name
// mapping in the current environment.
public Value Evaluate(Dictionary<string, Value> env)
{
return env[Name];
}

}

/// <summary>
/// Represents a function with an arbitrary number of parameters.
/// A Function is an expression with string parameters (to
/// be assigned at evaluation time from the available variables).
/// </summary>
[DebuggerDisplay("[Function: Name={Name}]")]
public class Function : IExpression
{
public Function(string name, IExpression body, params string[] parameters)
{
Name = name; Body = body; Parameters = parameters;
}

// Functions only evaluate to Closures
public Value Evaluate(Dictionary<string, Value> env)
{
return new Closure(this, env);
}

}

/// <summary>
/// Represents a Function "Call"
/// </summary>
[DebuggerDisplay("[Call: Exp={Exp}, Arg={Arg}]")]
public class Call : IExpression
{
public Call(IExpression exp, params IExpression[] args)
{
Exp = exp; Args = args;
}

// To evaluate, evaluate the IExpression (the Function) to a
// Closure. Then populate the Closure's environment
// with the evaluation time arguments. Finally map the Closure to itself,
// so that recursion will remember the inner environment. The Function's
// body can then be evaluated to a Value.
public Value Evaluate(Dictionary<string, Value> outer)
{
var clo = Exp.Evaluate(outer) as Closure;
var env = new Dictionary<string, Value>(clo.Env);

foreach (var p in clo.Func.Parameters.Zip(Args, (x, y) => Tuple.Create(x, y)))
env[p.Item1] = p.Item2.Evaluate(outer);

env[clo.Func.Name] = clo;
return clo.Func.Body.Evaluate(env);
}

}

/// <summary>
/// Represents an if, else conditional execution.
/// </summary>
[DebuggerDisplay("[Conditional: Exp={Exp}, Arg={Arg}]")]
public class Conditional : IExpression
{
public Conditional(IExpression test, IExpression conseq, IExpression alt)
{
Test = test; Conseq = conseq; Alt = alt;
}

// The Conditional's Test argument must first
// evaluate to a Bool. Then Conseq/Alt can
// be chosen based on the Value of Test.
public Value Evaluate(Dictionary<string, Value> env)
{
var test = Test.Evaluate(env) as Bool;
return test.Value ? Conseq.Evaluate(env)
: Alt.Evaluate(env);
}

}


# Evaluating an IExpression

Evaluation is pretty straightforward in most cases. If an IExpression contains sub-expressions, evaluate those to Value types first, and then perform the required operations. The most complicated (and interesting!) evaluation is that of function calls. Functions evaluate to Closures (a Function and an environment). Evaluation of a Call evaluates an IExpression to a Closure, and extends the environment of the Closure with the evaluation-time arguments, as well as a mapping to the Closure itself (for recursion). If you think about it, this is exactly what we need in order to be able to define a variable x in both the parameters of a Function and a global environment that sits atop the Function definition.

# Extending the language with more variants of IExpression

I've written an auxiliary factory class to help with the creation and evaluation of binary expressions:

/// <summary>
/// Factory class for evaluating two expressions
/// </summary>
[DebuggerDisplay("[BinaryOperation: X={X}, Y={Y}, Op={Op}]")]
public class BinaryOperation : IExpression
{
public BinaryOperation(IExpression x, IExpression y, string op)
{
X = x; Y = y; Op = op;
}

// All BinaryOperations must evaluate to a Number
// before they can be combined with the operation
// implemented for Op.
public Value Evaluate(Dictionary<string, Value> env)
{
var x = X.Evaluate(env) as Number;
var y = Y.Evaluate(env) as Number;

switch (Op)
{
case "+" : return new Number(x.Value + y.Value);
case "-" : return new Number(x.Value - y.Value);
case "*" : return new Number(x.Value * y.Value);
case "/" : return new Number(x.Value / y.Value);
case "<=": return new Bool(x.Value <= y.Value);
default:
throw new NotImplementedException();
}
}

}


I've done something similar for ListExpressions, where List is the target Value type that evaluation must resolve to before applying the operation (omitted here for brevity). I don't really like this (I have to do something, though, since everything in the tree is an IExpression). It makes things convenient, but I'm hoping someone can offer a better solution.

# Using the language

Here's an example of the language in action:

class Program
{
public static void Main(string[] args)
{
var env = new Dictionary<string, Value>()
{
{ "x", new Number(100) }
};

var x = new Variable("x"); // for convenience
var fac = new Function("fac", new Conditional(
new BinaryOperation(x, new Number(1), "<="),
new Number(1),
new BinaryOperation(x, new Call(new Variable("fac"),
new BinaryOperation(x, new Number(1), "-")),  "*")), "x");

var fib = new Function("fib", new Conditional(
new BinaryOperation(x, new Number(1), "<="),
new Number(1),
new BinaryOperation(new Call(new Variable("fib"), new BinaryOperation(x, new Number(1), "-")),
new Call(new Variable("fib"), new BinaryOperation(x, new Number(2), "-")), "+")), "x");
}
}


I define the mapping x -> 100 here to demonstrate why lexical scoping is so important in the implementation of closures. You can call fib or fac like this:

IExpression exp = new Call(fib, new Number(10));
Value result = exp.Evaluate(env);


# Code to review

The general points I'm hoping to have reviewed are as follows

• General structure and class design
• Improved method of creation/evaluation of binary and list operations
• Use of access modifiers

Of course, any general comments are welcomed.

# References

My implementation more or less follows the guidelines presented in a programming languages course at the University of Washington. I should add that there's an excellent version of this course offered on Coursera.

• Have you looked at the Roslyn source code or the parser/lexers generated by ANTLR? Studying those codes could be enlightening for you. – RubberDuck Jul 4 '15 at 0:20

[DebuggerDisplay("[Number: Value={Value}]")]


I have a new favorite attribute :)

First time I encounter C# code using a DebuggerDisplayAttribute - and I must say it makes an awesome feature, especially for that kind of code.

// Variables evaluate to the Name
// mapping in the current environment.
public Value Evaluate(Dictionary<string, Value> env)
{
return env[Name];
}


Regular comments on public members should be XML comments instead, for documentation purposes. And you'll want documentation for this.

Now, having spent the last couple of weeks implementing an identifier reference resolver for a VBA parse tree, one thing strikes me here, and it's not the fact that you're depending on a specific implementation of IDictionary<TKey,TValue> - maybe I'm missing something, but that "environment" better correspond to everything that's in-scope, and your language wouldn't support ambiguous identifiers.

I realize your language has nothing to do with VBA, but picture this [legal] code:

Sub Foo()
Dim Foo As New Foo
With Foo
With .Foo
.Foo = 42
End With
Bar .Foo.Foo
End With
End Sub


Having a dictionary keyed with identifier names wouldn't work here, but I'm just raising a flag - it's not exactly something that's, well, in-scope for this review ;-)

There are more readable ways to write this ternary:

    return test.Value ? Conseq.Evaluate(env)
: Alt.Evaluate(env);


Consider:

    return test.Value
? Conseq.Evaluate(env)
: Alt.Evaluate(env);


I don't like how you're exposing public fields all over the place:

public readonly IExpression Test;


Don't get me wrong - making them readonly is awesome! But in a properly OOP setup, fields should not be public, because that breaks encapsulation by exposing internal class implementation details, and later changing them to get-accessors is a breaking change; fields shouldn't impact an object's interface.

I'd much rather see get-only properties:

private readonly IExpression _test;
public IExpression Test { get { return _test; } }

public IExpression Conseq { get { return _test; } }

public IExpression Alt { get { return _alt; } }


Not sure about these names either - maybe it's the abbreviated words, but wouldn't Condition, ValueWhenTrue and ValueWhenFalse (or something similar) be better? The idea being to better antagonize the Conseq and Alt properties.

I'm surprised with the code you've written for using the language - pretty much the last thing I would have expected was a void Main in a Program class. What did I expect then? A grammar, a lexer, a parser, and that code included as part of an interpreter. Or is that your next Code Review post? ;-)

The soft casts in BinaryOperation.Evaluate don't look right:

public Value Evaluate(Dictionary<string, Value> env)
{
var x = X.Evaluate(env) as Number;
var y = Y.Evaluate(env) as Number;


If X and Y must evaluate to a Number, then IExpression X and IExpression Y aren't really abstractions - in reality a BinaryOperation can only ever operate with Number objects (or blow up with a NullReferenceException), and looking at the operations:

    switch (Op)
{
case "+" : return new Number(x.Value + y.Value);
case "-" : return new Number(x.Value - y.Value);
case "*" : return new Number(x.Value * y.Value);
case "/" : return new Number(x.Value / y.Value);
case "<=": return new Bool(x.Value <= y.Value);
default:
throw new NotImplementedException();
}


...why not explicitly couple BinaryOperation with Number then? newing up a Number already induces coupling between the two types, so that wouldn't be anything new.

Hard-coding your operators there is probably playing against you, too - if you had started designing your language from the ground up, instead of starting with its mechanics, you would probably have had an OperatorToken of some sort, and wouldn't have hard-coded them there.

As for the general structure and class design - I like how you made everything immutable, and as I said above the only thing that really itches is the public fields, that I would have exposed as properties. The API looks reasonable, although it would have been useful/helpful to have comments in that Main method to illustrate what kind of code is being simulated there.

Let's see...

    var env = new Dictionary<string, Value>()
{
{ "x", new Number(100) }
};


I don't see where/how env is being used...

    var x = new Variable("x"); // for convenience

var fac = new Function("fac", new Conditional(
new BinaryOperation(x, new Number(1), "<="),
new Number(1),
new BinaryOperation(x, new Call(new Variable("fac"),
new BinaryOperation(x, new Number(1), "-")),  "*")), "x");


If I get this right, the language-in-design code for fac could look something like this:

function fac(x) {
return x <= 1 ? 1 : x * fac(x - 1);
}


I'm not sure how a function's body could contain more than a single expression and still adhere to the IExpression interface... unless the language specs don't allow that? I think you might be trying to define the language in a place that's not meant for that - it's the job of the grammar to define the language, and having worked with an AST, I don't think it's right that everything in the tree is an IExpression, at least not from my experience with ANTLR, which builds a syntax tree out of much more than just that.

• "But fields should not be public." Why? – Ben Aaronson Jul 4 '15 at 1:23
• @BenAaronson edited. also: this and this, and given the purpose of OP's code, especialy this comment – Mathieu Guindon Jul 4 '15 at 1:34
• Fair enough. In the case of readonly` fields, the only reason I can think you'd need to change to a property is if you needed to change what it returns from being immutable to mutable. Whether or not a member is immutable seems like something of interest to consumers, not just an implementation detail of the class, so I'd consider it potentially useful to make that guarantee of immutability part of the member's signature. – Ben Aaronson Jul 4 '15 at 1:46
• It is my next Code Review post! (though I have to figure out the algorithm for parsing string input into my AST -- maybe you want to point me in the right direction...) – rookie Jul 4 '15 at 3:28
• Can you please comment on some of the thing's I've explicitly asked to be reviewed? I'd like some feedback on those items before awarding the bounty. – rookie Jul 6 '15 at 0:33

You're mixing responsibilities pretty badly. From the Univeristy of Washington document you linked to:

We can describe a typical workflow for a language implementation as follows. First, we take a string holding the concrete syntax of a program in the language. Typically this string would be the contents of one or more files. The parser gives errors if this string is not syntactically well-formed, meaning the string cannot possibly contain a program in the language due to things like misused keywords, misplaced parentheses, etc. If there are no such errors, the parser produces a tree that represents the program. This is called the abstract-syntax tree, or AST for short. It is a much more convenient representation for the next steps of the language implementation. If our language includes type-checking rules or other reasons that an AST may still not be a legal program, the type-checker will use this AST to either produce error messages or not. The AST is then passed to the rest of the implementation.

There are basically two approaches to this rest-of-the-implementation for implementing some programming language B. First, we could write an interpreter in another language A that takes programs in B and produces answers. Calling such a program in A an “evaluator for B” or an “executor for B” probably makes more sense, but “interpreter for B” has been standard terminology for decades. Second, we could write a compiler in another language A that takes programs in B and produces equivalent programs in some other language C (not the language C necessarily) and then uses some pre-existing implementation for C. For compilation, we call B the source language and C the target language. A better term than “compiler” would be “translator” but again the term compiler is ubiquitous. For either the interpreter approach or the compiler approach, we call A, the language in which we are writing the implementation of B, the metalanguage.

This is typically accomplished by having a lexer that generates a token stream from input text, a parser that produces an abstract syntax tree, and an interpreter (or compiler) that executes the AST. The interpreter will typically use the Visitor pattern to do things like evaluating expressions & conditionals and calling functions.

Currently, your AST and the interpreter are all mixed together. I think you'll find your life easier if you separate the concerns into the traditional areas of responsibility.

As an aside, perhaps writing your own interpreter from scratch isn't the best introduction into language design. Have you considered using a lexer/parser generator and implementing an interpreter from the AST & parser it will generate for you? I think you may be more successful writing your own later if you learn to use one of these tools first. There are lots of them out there to choose from.

• I think what I'm using right now is the interpreter pattern. Can you please provide some explanation for why my approach might not be right in this case? – rookie Jul 9 '15 at 14:58