Expression problem in Scala

expr.scala

// The expression problem is a new name for an old problem.  The goal is to
// define a datatype by cases, where one can add new cases to the datatype and
// new functions over the datatype, without recompiling existing code, and while
// retaining static type safety (e.g., no casts).
//                                                               (Philip Wadler)

import scala.language.implicitConversions

object ExpressionProblem extends App {

  // class Eval a where
  //   eval :: a -> Int
  trait Eval[A] {
    def eval(expr: A): Int
  }

  //////////////////////////////////////////
  // HERE'S THE MAGIC
  //
  // data Expr = forall t. Eval t => Expr t
  trait Expr {
    type T
    val t: T
    val evalInst: Eval[T]
  }

  object Expr {
    def apply[T0 : Eval](t0: T0) = new Expr {
      type T = T0
      val t = t0
      val evalInst = implicitly[Eval[T]]
    }
  }

  // Default boxing is needed
  implicit def box[T : Eval](t: T) = Expr(t)

  // instance Eval Expr where
  //   eval (Expr e) = eval e
  implicit object exprInstance extends Eval[Expr] {
    def eval(e: Expr) = e.evalInst.eval(e.t)
  }

  // NOTE: Haskell's name lookup makes this unnecessary; however, in order to
  // avoid explicitly specifying `exprInstance.eval` each time when we call it
  // recursively, simply define an alias.
  def evaluate = exprInstance.eval _

  // data BaseExpr = Const Int | Add Expr Expr | Mul Expr Exp
  sealed abstract class BaseExpr
  case class Const(c: Int) extends BaseExpr
  case class Add(lhs: Expr, rhs: Expr) extends BaseExpr
  case class Mul(lhs: Expr, rhs: Expr) extends BaseExpr

  // instance Eval BaseExpr where
  //   eval (Const n) = n
  //   eval (Add a b) = eval a + eval b
  //   eval (Mul a b) = eval a * eval b
  implicit object baseExprInstance extends Eval[BaseExpr] {
    def eval(baseExpr: BaseExpr): Int =
      baseExpr match {
        case Const(c)      => c
        case Add(lhs, rhs) => evaluate(lhs) + evaluate(rhs)
        case Mul(lhs, rhs) => evaluate(lhs) + evaluate(rhs)
      }
  }

  // Implicit conversions for all base expressions
  //
  // NOTE: This is only needed because we created a new hierarchy instead of
  // enrolling each type to `Eval` on its own.  Otherwise, the boxing function
  // would suffice.
  implicit def baseExprToExpr[T <: BaseExpr](t: T): Expr = Expr[BaseExpr](t)

  ///////////////////////////////////////////////
  // Possibly somewhere else (other module/lib).
  ///////////////////////////////////////////////

  // data SubExpr = Sub Expr Exp
  case class SubExpr(val lhs: Expr, val rhs: Expr)

  // instance Eval SubExpr where
  //   eval (Sub a b) = eval a - eval b
  implicit object subExprInstance extends Eval[SubExpr] {
    def eval(subExpr: SubExpr): Int =
      evaluate(subExpr.lhs) - evaluate(subExpr.rhs)
  }

  // NOTE: We don't have to provide an implicit conversion to Expr as the
  // default `box` one suffices.

  object Test {
    val exprs: List[Expr] = List(
      SubExpr(Const(10), Const(3)),
      Add(Const(1), Const(1))
    )
  }

  // Just sanity checking, they are not pretty Show-able.
  println(Test.exprs)

} // ExpressionProblem