Solving the expression problem in Java with Object Algebras

Program.java

// The structure of this document:
//  1. 'Define' the initial data type hierarchy
//     (Integer expression trees with literals only initially, so rather a leaf)
//  2. Extend with an evaluation operation
//  3. Extend with a branching Add expression
//  4. Extend the evaluation operation to work on Add expressions

// 1. Define the data type hierarchy, expression trees.
//    The paper's example is more fleshed out,
//    this is the bare minimum.

/**
 * An interface for defining operations on
 * simple expressions trees, only handling
 * literals.
 */
interface LitAlg<A> {
  A lit(int x);
}

class LitExample {
  /**
   * This is a free encoding of our data.
   */
  public static <A> A someLit(LitAlg<A> alg) {
    return alg.lit(42);
  }
}


// 1b. An algebra for producing a plain old
//     expression tree, just as a PoC.

/**
 * This is the type by which we 'materialize'
 * our encoded data. I'll only show this for literals,
 * as a proof of concept that we can reconstruct
 * the actual expression tree from this.
 */
interface Exp {
}


/**
 * An expression carrying an integer literal.
 */
class Lit implements Exp {
  int x;

  public Lit(int x) {
    this.x = x;
  }
}

/**
 * An algebra producing an actual expression tree.
 * That corresponds to the factory pattern.
 */
class LitFactory implements LitAlg<Exp> {
  public Exp lit(int x) {
    return new Lit(x);
  }

  public static void test() {
    Exp e = LitExample.someLit(new LitFactory());
    assert (e instanceof Lit);
  }
}


// 2. Add an evaluation operation via an algebra.

class LitEval implements LitAlg<Integer> {
  public Integer lit(int x) {
    return new Integer(x);
  }
}

// 3. Extend with an add expression.
//    I'll spare the new Add class and the
//    IntFactory, because we don't actually need
//    it to encode our data! Although the Exp
//    could be recovered from the free expression
//    in IntExample.

interface IntAlg<A> extends LitAlg<A> {
  A add(A e1, A e2);
}

class IntExample {
  public static <A> A exp(IntAlg<A> alg) {
    return alg.add(alg.lit(3), alg.lit(5));
  }
}

// 4. Extend LitEval to work with add.

class IntEval extends LitEval implements IntAlg<Integer> {
  public Integer add(Integer v1, Integer v2) {
    return v1 + v2;
  }
}

public class Program {
  public static void main(String[] args) {
    LitFactory.test();
    printAssertion(LitExample.exp(new LitEval()), 42);
    printAssertion(IntExample.exp(new IntEval()), 8);
  }

  private static <T> void printAssertion(T a, T b) {
    String op = a.equals(b) ? " == " : " != ";
    System.out.println(a + op + b);
  }
}