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 ExpressionsEverything 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();    }    public readonly double Value;}/// <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();    }    public readonly bool Value;}/// <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;    }    public readonly Function Func;    public readonly Dictionary<string, Value> 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];    }    public readonly string 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);    }    public readonly string Name;    public readonly IExpression Body;    public readonly IEnumerable<string> Parameters;}/// <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);    }    public readonly IExpression Exp;    public readonly IEnumerable<IExpression> Args;}/// <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);    }    public readonly IExpression Test;    public readonly IExpression Conseq;    public readonly IExpression Alt;}Evaluating an IExpressionEvaluation 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 IExpressionI'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();        }    }    public readonly IExpression X;    public readonly IExpression Y;    public readonly string Op;}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 languageHere'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 reviewThe general points I'm hoping to have reviewed are as followsGeneral structure and class design Improved method of creation/evaluation of binary and list operations Use of access modifiersOf course, any general comments are welcomed. ReferencesMy 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. 
Abstract syntax tree for simple Lisp-like interpreter
c#;interpreter;compiler