An Alpha Interpreter

Alpha is a simple expression-oriented language with LISP-like syntax.

Here's an EBNF for Alpha:

<Expression> ::= <Literal> | <FunCall>
<FunCall> ::= ( <Operator> <Expression>+ )
<Operator> ::= + | *
<Literal> ::= <Digit>*(.<Digit>+)?
<Digit> ::= 0 .. 9

Here's a sample session with the Alpha interpreter:

-> -3.1416
value = -3.1416
-> ( + 2 3 )
value = 5.0
-> ( + ( * 2 3 ) ( * 4 ( + 5 3.1416 ) ) )
value = 38.5664
-> quit
bye

Design Model

The design of Alpha uses three patterns:

Composite
Interpreter
Visitor

We use the Composite Pattern to represent Alpha expressions:

Each node knows how to parse itself.

Each node knows how to evaluate itself. (Interpreter Pattern)

Each node has a method that accepts an object implementing a visitor interface:

Implementation

Expressions

abstract class Expression {

   public static Expression parse(Scanner tokens) throws Exception {
      if (tokens.hasNext("\\(")) {     // if next token is a left paren
         return FunCall.parse(tokens); // then it must be a FunCall
      } else {
         return Literal.parse(tokens); // else it must be a Literal
      }
   }

   abstract public double eval() throws Exception;
   public void accept(ExpVisitor v) { }
}

class Literal

class Literal extends Expression {
   private Double token;
   public static Expression parse(Scanner tokens) throws Exception {
      Literal result = new Literal();
      result.token = tokens.nextDouble();
      return result;
   }
   public String toString() { return "" + token; }
   public double eval() throws Exception { return token; }
   public void accept(ExpVisitor v) { v.visit(this); }
}

class FunCall

class FunCall extends Expression {
   private List<Expression> operands = new ArrayList<Expression>();
   private String operator = "?";
   public String getOperator() { return operator; }
   public static Expression parse(Scanner tokens) throws Exception {
      FunCall result = new FunCall();
      tokens.next(); // toss left paren
      result.operator = tokens.next();
      while (!tokens.hasNext("\\)")) { // parse operands until closing right paren encountered
         result.operands.add(Expression.parse(tokens));
      }
      tokens.next(); // toss right paren
      return result;
   }

   public void accept(ExpVisitor v) { v.visit(this); }

   public Iterator<Expression> iterator() {
      return operands.iterator();
   }
   public String toString() {
      String result = "(";
      for(Expression node: operands) {
         result = result + node + " ";
      }
      return result + ")";
   }

   public double eval() throws Exception {
      double result = 0;
      List<Double> args = new ArrayList<Double>();
      for(Expression operand: operands) {
         args.add(operand.eval());
      }
      if (operator.equals("+")) {
         for(Double arg: args) {
            result += arg;
         }
      } else if (operator.equals("*")) {
         result = 1;
         for(Double arg: args) {
            result *= arg;
         }
      } else {
         throw new Exception("unrecognized operator: " + operator);
      }
      return result;
   }
}

Visitors

An expression visitor is anything that implements the ExpVisitor interface:

interface ExpVisitor {
void visit(Literal node);
void visit(FunCall node);
}

For example, a tree print visitor displays each token on a separate line preceded by N spaces, where N is the depth of nesting of the token:

class TreePrintVisitor implements ExpVisitor {
   private String indent = " ";
   public void visit(Literal node) {
      System.out.println(indent + node);
   }
   public void visit(FunCall node) {
      System.out.println(indent + node.getOperator());
      Iterator<Expression> p = node.iterator();
      indent += " "; // add a space
      while(p.hasNext()) {
         p.next().accept(this);
      }
      indent = indent.substring(1); // remove a space
   }
}

A tree seach visitor compares each node to a given token, incrementing a counter each time a match is found:

class TreeSearchVisitor implements ExpVisitor {
   private String target;
   private int occurrences = 0;
   public int getOccurrences () { return occurrences; }
   public TreeSearchVisitor(String t) { target = t; }
   public void visit(Literal node) {
      if (target.equals(node.toString()))occurrences++;
   }
   public void visit(FunCall node) {
      if (target.equals(node.getOperator())) occurrences++;
      Iterator<Expression> p = node.iterator();
      while(p.hasNext()) {
         p.next().accept(this);
      }
   }
}

Notice that visiting a composite node (FunCall) requires us to visit each child. The type of the child (simple or composite) will polymorphically determine which variant of visit is called.

The Interpreter

We implement a REPL-style interpreter (Read-Evaluate-Print Loop).

To demonstrate visitors, we ask a tree print visitor to visit the parse tree as well as a search visitor that counts the number of occurrences of pi in the expression:

public class Interpreter {

   public static void main(String[] args) {
      while(true) {
         try {
            System.out.print("-> ");
            Scanner kbd = new Scanner(System.in);
            if (kbd.hasNext("quit")) break;
            Expression exp = Expression.parse(kbd);
            System.out.println("value = " + exp.eval());

            TreePrintVisitor v1 = new TreePrintVisitor();
            exp.accept(v1);

            TreeSearchVisitor v2 = new TreeSearchVisitor("3.1416");
            exp.accept(v2);
            System.out.println("#pi = " + v2.getOccurrences());

         } catch(Exception e) {
            System.err.println(e.getMessage());
         }
      }
      System.out.println("bye");
   }
}

A Session

Here's a sample session:

-> -3.1416
value = -3.1416
expression tree:
-3.1416
#pi = 0
-> ( * 2 3 4 )
value = 24.0
expression tree:
*
2.0
3.0
4.0
#pi = 0
-> ( * ( + 4 5 ) ( + 2 ( * 6 3.1416 ) ) )
value = 187.6464
expression tree:
*
+
   4.0
   5.0
+
   2.0
   *
    6.0
    3.1416
#pi = 1
->

Question

Note that the implementation of accept is the same for Literal.accept(Visitor v) and FunCall.accept(Visitor v). Namely:

v.visit(this);

Why not simply pull this implementation up to Expression.accept(Visitor v) and get rid of the subclass overrides?

Project

Beta extends Alpha by adding symbols and definitions:

Here's a sample session:

-> [ define pi 3.14 ]
done
-> ( + 2 pi )
value = 5.14
->

Design and write an interpreter for Beta. Hint: eval now needs a symbol table parameter:

abstract class Phrase {
abstract double eval(Map<Symbol, Double> env);
// etc.
}