Object algebras example in scala

gistfile1.scala

#!/bin/bash
exec ~/src/scala/bin/scala -savecompiled "$0" "$@"
!#

// Example of object algebras, based on the scala example at http://ropas.snu.ac.kr/~bruno/oa/

// type Term = ∀A,O. O[A] -> A
trait Term[O[_]] {
  def apply[A](o: O[A]): A
}

// Data: Lit | Add
trait Lit[A] { def Lit(x: Int): A }
trait Add[A] { def Add(x: A, y: A): A }
trait Ops[A] extends Lit[A] with Add[A]

// More data: ... | Sub | Mul
trait Mul[A] { def Mul(x: A, y: A): A }
trait Sub[A] { def Sub(x: A, y: A): A }
trait Ops2[A] extends Ops[A] with Sub[A] with Mul[A]

// Behavior: eval

trait Eval extends Ops[Int] {
  def Lit(x: Int)         = x
  def Add(x: Int, y: Int) = x + y
}

trait Eval2 extends Ops2[Int] with Eval {
  def Sub(x: Int, y: Int) = x - y
  def Mul(x: Int, y: Int) = x * y
}

// Behavior: show

trait Show extends Ops[String] {
  def Lit(x: Int)               = "%s"        format x
  def Add(x: String, y: String) = "(%s + %s)" format (x,y)
}

trait Show2 extends Ops2[String] with Show {
  def Sub(x: String, y: String) = "(%s - %s)" format (x,y)
  def Mul(x: String, y: String) = "(%s * %s)" format (x,y)
}

//
// Examples:
//

{

  val x = new Term[Ops]  { def apply[A](o: Ops[A]):  A = o.Add(o.Lit(3), o.Lit(4)) }
  val y = new Term[Ops2] { def apply[A](o: Ops2[A]): A = o.Sub(o.Lit(8), o.Add(x(o), o.Lit(1))) }

  def identity [O[A] <: Ops[A]]  (z: Term[O]) = new Term[O] { def apply[A](o: O[A]): A = z(o) }
  def double   [O[A] <: Ops[A]]  (z: Term[O]) = new Term[O] { def apply[A](o: O[A]): A = o.Add(z(o), z(o)) }
  def square   [O[A] <: Ops2[A]] (z: Term[O]) = new Term[O] { def apply[A](o: O[A]): A = o.Mul(z(o), z(o)) }

  def test[X](x:X, y:X) = assert(x == y, "%s != %s" format (x,y))

  test(x(new Eval {}), 7)
  test(x(new Show {}), "(3 + 4)")

  test(y(new Eval2 {}), 0)
  test(y(new Show2 {}), "(8 - ((3 + 4) + 1))")

}

//
// Examples redux:
//

{

  def Lit[O[A] <: Lit[A]] (n: Int)                 = new Term[O] { def apply[A](o: O[A]): A = o.Lit(n) }
  def Add[O[A] <: Add[A]] (z: Term[O], w: Term[O]) = new Term[O] { def apply[A](o: O[A]): A = o.Add(z(o), w(o)) }
  def Sub[O[A] <: Sub[A]] (z: Term[O], w: Term[O]) = new Term[O] { def apply[A](o: O[A]): A = o.Sub(z(o), w(o)) }
  def Mul[O[A] <: Mul[A]] (z: Term[O], w: Term[O]) = new Term[O] { def apply[A](o: O[A]): A = o.Mul(z(o), w(o)) }

  def x[O[A] <: Ops[A]]  = Add[O](Lit[O](3), Lit[O](4))
  def y[O[A] <: Ops2[A]] = Sub[O](Lit[O](8), Add[O](x, Lit[O](1)))

  def double       [O[A] <: Ops[A]]  (z: Term[O]) = Add(z,z)
  def square       [O[A] <: Ops2[A]] (z: Term[O]) = Mul(z,z)
  def squareDouble [O[A] <: Ops2[A]] (z: Term[O]) = square(double(z))

  def test[X](x:X, y:X) = assert(x == y, "%s != %s" format (x,y))

  test(x[Ops](new Eval {}), 7)
  test(x[Ops](new Show {}), "(3 + 4)")

  test(y[Ops2](new Eval2 {}), 0)
  test(y[Ops2](new Show2 {}), "(8 - ((3 + 4) + 1))")

}

//
// How could we express these more concisely?
//

// scala:
// trait Term[O[_]] { def apply[A](o: O[A]): A }
// def x[O[A] <: Ops[A]]: Term = Add[O](Lit[O](3), Lit[O](4))

// haskell (vaguely):
// type Term = forall A :: *, O :: * -> *. O[A] -> A
// x o = o.Add(o.Lit(3), o.Lit(4)) :: Term

// type theory (vaguely):
// type Term = ∀A,O. O[A] -> A