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.

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

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

Here are the values I define:

```
///
/// Represents a constant literal (float/int) implemented as C# double)
///
[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;
}

///
/// Represents a boolean (true/false)
///
[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;
}

///
/// 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.
///
[DebuggerDisplay("[Closure: Func={Func.Name}]")]
public class Closure : Value
{
public Closure

[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 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 - 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;
public readonly IExpression Conseq;
public readonly IExpression Alt;

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; } }

private readonly IExpression _conseq;
public IExpression Conseq { get { return _test; } }

private readonly IExpression _alt;
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 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()
    {
        { "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), "-")

StackExchange Code Review Q#95269, answer score: 7