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