Pony Solution to the Expression Problem Using Object Algebras see http://i.cs.hku.hk/~bruno/oa/ for more info

oa.pony

// Initial object algebra interface for expressions: integers and addition
interface ExpAlg[E]
  fun lit(x: I32): E
  fun add(e1: E, e2: E): E

// An object algebra implementing that interface (evaluation)

// The evaluation interface
interface Eval
  fun eval(): I32

// The object algebra
interface EvalExpAlg
  fun lit(x: I32): Eval val =>
    recover
      object
        let x: I32 = x
        fun eval(): I32 => x
      end
    end

  fun add(e1: Eval val, e2: Eval val): Eval val =>
    recover
      object
        let e1: Eval val = e1
        let e2: Eval val = e2
        fun eval(): I32 => e1.eval() + e2.eval()
      end
    end

// Evolution 1: Adding subtraction
interface SubExpAlg[E] is ExpAlg[E]
  fun sub(e1: E, e2: E): E

// Updating evaluation:
interface EvalSubExpAlg
  fun sub(e1: Eval val, e2: Eval val): Eval val =>
    recover
      object
        let e1: Eval val = e1
        let e2: Eval val = e2
        fun eval(): I32 => e1.eval() - e2.eval()
      end
    end

// Evolution 2: Adding pretty printing
interface PPrint
  fun print(): String

interface PrintExpAlg
  fun lit(x: I32): PPrint val =>
    recover
      object
        let x: I32 = x
        fun print(): String =>
          x.string()
      end
    end

  fun add(e1: PPrint val, e2: PPrint val): PPrint val =>
    recover
      object
        let e1: PPrint val = e1
        let e2: PPrint val = e2
        fun print(): String =>
          e1.print() + " + " + e2.print()
      end
    end

  fun sub(e1: PPrint val, e2: PPrint val): PPrint val =>
    recover
      object
        let e1: PPrint val = e1
        let e2: PPrint val = e2
        fun print(): String =>
          e1.print() + " - " + e2.print()
      end
    end

// An alternative object algebra for pretty printing:

// Often, when precise control over the invocation of
// methods is not needed, we can simplify object algebras.
// For example, here's an alternative implementation
// of pretty printing that directly computes a string:

interface PrintExpAlg2
  fun lit(x: I32): String =>
    x.string()

  fun add(e1: String, e2: String): String =>
    e1 + " + " +  e2

  fun sub(e1: String, e2: String): String =>
    e1 + " - " +  e2

// Testing
actor Main
  new create(env: Env) =>
    // Some object algebras:
    let ea = object is EvalExpAlg end
    let esa = object is (EvalSubExpAlg & EvalExpAlg) end
    let pa = object is PrintExpAlg end
    let pa2 = object is PrintExpAlg2 end

    // We can call esa with exp1
    let ev = exp1[Eval val](esa)

    // But calling ea with exp2 is an error
    // let ev_bad = exp2[Eval val](ea)

    // Testing the actual algebras
    env.out.print("Evaluation of exp1 \"" + exp1[PPrint val](pa).print() + "\" is: " + ev.eval().string())
    env.out.print("Evaluation of exp2 \"" + exp2[PPrint val](pa).print() + "\" is: " + exp2[Eval val](esa).eval().string())
    env.out.print("The alternative pretty printer works nicely too!\nexp1: " + exp1[String](pa2) + "\nexp2: " + exp2[String](pa2))

  // An expression using the basic ExpAlg
  fun exp1[E: Any #read](alg: ExpAlg[E] box): E =>
    alg.add(alg.lit(3), alg.lit(4))

  // An expression using subtraction too
  fun exp2[E: Any #read](alg: SubExpAlg[E] box): E =>
    alg.sub(exp1[E](alg), alg.lit(4))

And here are the results of running this program:

Evaluation of exp1 "3 + 4" is: 7
Evaluation of exp2 "3 + 4 - 4" is: 3
The alternative pretty printer works nicely too!
exp1: 3 + 4
exp2: 3 + 4 - 4