3

I've written a parser for a subset of the LISP programming language and would now like to write an interpreter. I've been told that the visitor pattern is desirable because it helps keep the syntax classes uncluttered with evaluation logic.

I'm having trouble writing the actual "accept" and "visit" methods, and in particular specifying the return type. In my syntax classes, everything is an IExpression. Here are some of the expressions I parse the input to:

public interface IExpression
{
}

public class Number : IExpression
{
    public Number(double x)
    {
        Val = x;
    }

    public readonly double Val;
}

public class Bool : IExpression
{
    public Bool(bool b)
    {
        Val = b;
    }

    public readonly bool Val;
}

public class Definition : IExpression
{
    public Definition(string name, IExpression expr)
    {
        Name = name; Expr = expr;
    }

    public readonly string Name;
    public readonly IExpression Expr;
}

public class Conditional : IExpression
{
    public Conditional(IExpression test,
        IExpression trueBranch, IExpression falseBranch)
    {
        Test = test; TrueBranch = trueBranch; ElseBranch = falseBranch;
    }

    public readonly IExpression Test;
    public readonly IExpression TrueBranch;
    public readonly IExpression ElseBranch;
}

public class Add : NumericExpression
{
    public Add(IExpression x, IExpression y)
    {
        X = x; Y = y;
    }

    public readonly IExpression X;
    public readonly IExpression Y;
}

And here is the visitor interface. 

public interface IVisitor
{
    double Visit(Add add)
}

How should I now "visit" an Add node? If I add public double Accept(IVisitor v) to the IExpression interface, everything has to implement "accept" for doubles, even if the expression can never produce a double (take, for example, the case of my Bool type). This doesn't seem correct, and I'm wondering if I'm missing an opportunity to use generics.

rookie
  • 2,783
  • 5
  • 29
  • 43
  • Usually the visit methods don't return anything. You would basically walk the syntax tree passing in the 'next' node. – user2697817 Jul 16 '15 at 15:36
  • @user2697817: can you maybe give an example of this in the context of my code? – rookie Jul 16 '15 at 15:38
  • It looks to me like `IExpression` should have a `Value` property or member. It also looks like `IExpression` could be generic at that level, so that something like boolean would look like `class Bool : IExpression`, then the definition of `Value` in expression should be `T Value { get; }`. Is there a reason you chose not to use an AST tool like ANTLR (http://www.antlr.org/about.html) ? – Ron Beyer Jul 16 '15 at 15:48
  • @RonBeyer I think what you're describing is the [interpreter pattern](https://en.wikipedia.org/wiki/Interpreter_pattern) -- an expression knows how to evaluate itself. I'd like to stick with the visitor pattern, if possible. I decided against using an AST tool because I wanted to learn the aspects of implementing a programming language on my own. – rookie Jul 16 '15 at 15:52
  • 1
    A common pattern is to avoid return types and store the current value of the evaluation in the *state* of the visitor, see: http://stackoverflow.com/q/10164714/87698 – Heinzi Jul 16 '15 at 15:53
  • @Heinzi: What would my states be, in this case? Can you say more on this? – rookie Jul 16 '15 at 15:54
  • 1
    This is explains the visitor pattern well http://stackoverflow.com/questions/16165640/how-to-write-visitor-pattern-for-a-abstract-syntax-tree-in-c – user2697817 Jul 16 '15 at 15:56
  • 1
    @rookie: By *state* I mean an instance field. Have a look at user2697817's link: Your *expression evaluation* visitor could do the same, storing the *value* of the expression instead of the type. You'll probably need an `object` field, since the current value can be a double or a bool. – Heinzi Jul 16 '15 at 16:08
  • @Heinzi: yes -- that's a great suggestion, although I'd really like to avoid `object` if possible? – rookie Jul 16 '15 at 16:11
  • @rookie: Suggestion: wrap your object into a custom, immutable class `MyLispValue { MyEnum Type; object Value; }` with `GetBoolean` and `GetDouble` methods that do the casting and check the type first. – Heinzi Jul 16 '15 at 18:52

0 Answers0