Interpreter Pattern and Structural Recursion

I have previously discussed the flaws and limitations of the Visitor Pattern; criticised the Singleton Patterm as a global variable in disguise; and dismissed all but one of the rest as kludges to work around the GoF's languages-of-choice. That leaves the Interpreter.

This is a critically important pattern, if you only learn one pattern, make it this one! It is so fundamental to what we do to be different in kind from the other patterns in the book. In fact it is so critical that Gamma et al would probably have been better off ignoring the other patterns and writing their book exclusively on the Interpreter. In a very real sense this is exactly what Daniel Friedman did in "Essentials of Programming Languages" (EoPL).

If nothing else, the fact that you can comfortably write an entire book introducing the basics of the Interpreter Pattern is a good sign we're dealing with a different beast here to the rest of the GoF. Can you imagine writing a 300 page book introducing the basics of the factory-method?

The reason why the interpreter pattern is so important is that it amounts to designing a language, and language is our primary tool as programmers. We solve problems with computers, ultimately we do so with sequences of opcodes passed to the execution unit of our cpus; but the number of concepts we can express in a single sentence in machine code is limited, and the amount of detail we can choose to ignore when it is irrelevant to our solution is minimal. The act of climbing the language stack, (machine code -> symbolic assembly -> macro assembly -> C -> libc -> [java, Scheme, ML, etc]) is an exercise in increasing these two measures. Note I included libc in that list. I did that because language is the core abstraction being invoked in library, module, and macro systems as Kernighan and Pike discuss in "The Practice of Programming".

Now for the bad news. Yes the interpreter pattern is all goodness and light, but the unfortunately the sample implementation provided by GoF is crap. It's crap for exactly the same reason the visitor pattern is an inappropriate approach for parse-tree manipulation. This is a symbolic transformation, and as a problem is decidedly non-object-oriented. I'll go into exactly what an object-oriented problem looks like another time, but suffice to say that there is a good reason why LISP has survived 50 years, and the applicability of functional programming techniques to symbolic programming is a major part of it.

The solution offered in Design Patterns is an excelent piece of OO design. The problem: You have an AST you wish to execute. The solution: encapsulate the knowledge of how each different node-type should be evaluated in an 'evaluate' method on each node-type's associated class. Below is an example calculator implemented in Java using this exact design:

$cat test/*.java

/**
 * test/Add.java
 */
package test;

public class Add implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Add(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() + this.rhs.calc();
  }
}

/**
 * test/Div.java
 */
package test;

public class Div implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Div(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() / this.rhs.calc();
  }
}

/**
 * test/Expression.java
 */
package test;

public interface Expression {
  public int calc();
}

/**
 * test/Main.java
 */
package test;

public class Main {
  public static void main(String[] args) {
    System.out.println(Integer.toString(
        new Mul(
          new Sub(new Num(6), new Num(2)),
          new Add(new Num(2), new Num(3))).calc()));
  }
}

/**
 * test/Mul.java
 */
package test;

public class Mul implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Mul(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() * this.rhs.calc();
  }
}

/**
 * test/Num.java
 */
package test;

public class Num implements Expression {
  private int num;

  public Num(int num) {
    this.num = num;
  }

  public int calc() {
    return this.num;
  }
}

/**
 * test/Sub.java
 */
package test;

public class Sub implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Sub(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() - this.rhs.calc();
  }
}

and indeed this does print '20' as expected.

Compare this with the ML code below, or the far more complex interpreter on page 74 of EoPL, and the problem is immedately clear. With symbolic transformation we are invariably performing 'structual recursion'. We have a data-structure, that is indeed a structure, defined recursively that is then processed by following the structure of the data, possibly performing an operation at each step. Consequently it is the structure that is important in comprehending the code, and ensuring a perfect match between data-structure and code-structure that is required to get it right. By scattering the code across multiple files, it makes it much more difficult to understand the structure of the code, and impossible to verify that this matches the structure of the data without signifigant effort.

$cat calc.ml

(* Calculator *)

type expression =
  | Num of int
  | Add of expression * expression
  | Sub of expression * expression
  | Mul of expression * expression
  | Div of expression * expression ;;

let rec calc expr =
  match expr with
    | Num n -> n
    | Add (e1, e2) -> calc e1 + calc e2
    | Sub (e1, e2) -> calc e1 - calc e2
    | Mul (e1, e2) -> calc e1 * calc e2
    | Div (e1, e2) -> calc e1 / calc e2

let main () =
  print_int(calc(Mul(Sub(Num 6, Num 2), Add(Num 2, Num 3))));
  print_newline();
  exit 0 ;;
main() ;;

and it is now trivial to inspect the code and the data and verify that the structures are identical. In fact it is so trivial the compiler will warn us of our mistake.

$ diff calc.ml calc-broken.ml 15c15
<     | Mul (e1, e2) -> calc e1 * calc e2
---
> (*    | Mul (e1, e2) -> calc e1 * calc e2 *)
$ ocamlc -o calc-broken calc-broken.ml 
File "calc-broken.ml", line 11, characters 2-199:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Mul (_, _)
$ ./calc-broken
Fatal error: exception Match_failure("calc-broken.ml", 11, 2)

Now if you are stuck in an OO-world then the closest you can get to the above is to use either the visitor pattern or dynamic double dispatch. Not as neat, and a scary amount of boilerplate, but it works, and it is definately preferable to the example given in GoF; and when the time comes that you are not compelled to consign yourself to the OOP-only gulag you now know that there is something worth escaping to.