Simple Polymorphic Stack Machine

gistfile1.scala

import scala.util.Random

object PStack {
  type Any = PStack[_, _]
}

sealed trait PStack[A, B <: PStack.Any] {
  def ++[C, D <: PStack.Any](op: Op[A, B, C, D]): PStack[C, D] = op.execute(this)
}

case class EmptyPStack() extends PStack[Unit, EmptyPStack]
case class ConsPStack[A, B <: PStack.Any](top: A, rest: B) extends PStack[A, B]

sealed trait Op[A, B <: PStack.Any, C, D <: PStack.Any] {
  def execute(ctx: PStack[A, B]): PStack[C, D]
}

case class Op0[A, B, C <: PStack.Any](method: () => A) extends Op[B, C, A, PStack[B, C]] {
  def execute(ctx: PStack[B, C]) = ConsPStack(method(), ctx)
}

case class Op1[A, B, C, D <: PStack.Any](method: A => B) extends Op[A, PStack[C, D], B, PStack[C, D]] {
  def execute(ctx: PStack[A, PStack[C, D]]) = ctx match {
    case ConsPStack(a, q) => ConsPStack(method(a), q)
  }
}

case class Op2[A, B, C, E, F <: PStack.Any](method: (A, B) => C) extends Op[A, PStack[B, PStack[E, F]], C, PStack[E, F]] {
  def execute(ctx: PStack[A, PStack[B, PStack[E, F]]]) = ctx match {
    case ConsPStack(a, ConsPStack(b, q)) => ConsPStack(method(a, b), q)
  }
}

object Op {
  implicit def elemToPush[A, B, C <: PStack.Any](elem: A): Op0[A, B, C] = Op0({ () => elem })
  implicit def function0ToOp[A, B, C <: PStack.Any](elem: (() => A)): Op0[A, B, C] = Op0(elem)
  implicit def function1ToOp[A, B, C, D <: PStack.Any](elem: (A => B)): Op1[A, B, C, D] = Op1(elem)
  implicit def function2ToOp[A, B, C, D, E, F <: PStack.Any](elem: (A, B) => C): Op2[A, B, C, E, F] = Op2(elem)
}

object Main extends App {
  import Op._

  val stack = EmptyPStack() ++
      3 ++
      { a: Int => a * a } ++
      { () => new Random().nextInt(10) } ++
      5 ++
      { (a: Int, b: Int) => a + b } ++
      { (a: Int, b: Int) => a + b } ++
      "The result is " ++
      { (a: String, b: Int) => a + ": " + b }

  println(stack)
}