Object algebra examples for mleduc.xyz

OA.scala

object OA {

  // based on http://lambda-the-ultimate.org/node/4572
  // read : https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/
  def test(): Unit = {
    val pa = new PrintExpAlg() {}
    val pa2 = new PrintExpAlgBis() {}

    // But calling ea with exp2 is an error
    // val ev_bad = exp2(ea)

    println(s"""Evaluation of exp1 "${program1(pa).print()}" is: ${program1(new EvalSubExpAlg() {}).eval()} / ${program1(new EvalExpAlg() {}).eval()}""")
    println(s"""Evaluation of exp2 "${program2(pa).print()}" is: ${program2(new EvalSubExpAlg() {}).eval()}""")
    println(
      s"""The alternative pretty printer works nicely too!
          |exp1: ${program1(pa2)}
          |exp2: ${program2(pa2)}""".stripMargin)

    val printB: PrintExpBoolAlg with Object = new PrintExpBoolAlg() {}
    val evalB: EvalBoolExpAlg with Object = new EvalBoolExpAlg() {}
    println(s"""${program3(printB).print()} ---> ${program3(evalB).eval()}""")
    val printIB: PrintExpBoolAlg with PrintExpAlg with Object = new PrintExpBoolAlg() with PrintExpAlg {}
    val evalIB: EvalBoolExpAlg with EvalSubExpAlg with Object = new EvalBoolExpAlg() with EvalSubExpAlg {}
    println(s"""${program4(printIB).print()} ---> ${program4(evalIB).eval()}""")
  }

  // An object algebra implementing that interface (evaluation)
  def program1[E](alg: ExpAlg[E]): E = {
    import alg._
    add(lit(3), lit(4))
  }

  // An expression using subtraction too
  def program2[E](alg: SubExpAlg[E]) = {
    import alg._
    sub(program1(alg), lit(4))
  }

  def program3[F, E <: F](alg: BoolExpAlg[F, E]): E = {
    import alg._

    equal(trueE(), falseE())
  }

  def program4[F, E <: F, G <: F](alg: BoolExpAlg[F, E] with SubExpAlg[G]): E = {
    import alg._
    equal(lit(1), sub(lit(2), lit(1)))
  }


  // Initial object algebra interface for expressions: integers and addition
  trait ExpAlg[E] {
    def lit(x: Int): E

    def add(e1: E, e2: E): E
  }

  // The evaluation interface
  trait BoolExpAlg[A, E <: A] {
    def trueE(): E

    def falseE(): E

    def and(left: E, right: E): E

    def or(left: E, right: E): E

    def not(exp: E): E

    def equal[F1 <: A, F2 <: A](left: F1, right: F2)(implicit ev: F1 =:= F2): E
  }

  trait Eval[X] {
    def eval(): X
  }

  trait PPrint {
    def print(): String
  }


  trait EvalBoolExpAlg extends BoolExpAlg[Eval[_], Eval[Boolean]] {
    override def falseE(): Eval[Boolean] = new Eval[Boolean] {
      override def eval(): Boolean = false
    }

    override def trueE(): Eval[Boolean] = new Eval[Boolean] {
      override def eval(): Boolean = true
    }

    override def and(left: Eval[Boolean], right: Eval[Boolean]) = new Eval[Boolean] {
      override def eval(): Boolean = left.eval() && right.eval()
    }

    override def equal[F1 <: Eval[_], F2 <: Eval[_]](left: F1, right: F2)(implicit ev: =:=[F1, F2]): Eval[Boolean] = new Eval[Boolean] {
      override def eval(): Boolean = left.eval() == right.eval()
    }

    override def not(exp: Eval[Boolean]): Eval[Boolean] = new Eval[Boolean] {
      override def eval(): Boolean = !exp.eval()
    }

    override def or(left: Eval[Boolean], right: Eval[Boolean]): Eval[Boolean] = new Eval[Boolean] {
      override def eval(): Boolean = left.eval() || right.eval()
    }
  }

  // The object algebra
  trait EvalExpAlg extends ExpAlg[Eval[Int]] {
    def lit(x: Int): Eval[Int] = new Eval[Int]() {
      def eval() = x
    }

    def add(e1: Eval[Int], e2: Eval[Int]): Eval[Int] = new Eval[Int]() {
      def eval() = e1.eval() + e2.eval()
    }
  }

  trait SubExpAlg[E] extends ExpAlg[E] {
    def sub(e1: E, e2: E): E
  }

  trait EvalSubExpAlg extends EvalExpAlg with SubExpAlg[Eval[Int]] {
    def sub(e1: Eval[Int], e2: Eval[Int]): Eval[Int] = new Eval[Int]() {
      def eval(): Int = e1.eval() - e2.eval()
    }
  }

  // Evolution 2: Adding pretty printing

  trait PrintExpAlg extends SubExpAlg[PPrint] {
    def lit(x: Int): PPrint = new PPrint() {
      def print() = x.toString()
    }

    def add(e1: PPrint, e2: PPrint): PPrint = new PPrint() {
      def print() = e1.print() + " + " + e2.print()
    }

    def sub(e1: PPrint, e2: PPrint): PPrint = new PPrint() {
      def print() = e1.print() + " - " + e2.print();
    }
  }

  trait PrintExpBoolAlg extends BoolExpAlg[PPrint, PPrint] {
    override def trueE(): PPrint = new PPrint {
      override def print(): String = true.toString
    }

    override def falseE(): PPrint = new PPrint {
      override def print(): String = false.toString
    }

    override def and(left: PPrint, right: PPrint): PPrint = new PPrint {
      override def print(): String = s"(${left.print()} and ${right.print()})"
    }

    override def equal[F1 <: PPrint, F2 <: PPrint](left: F1, right: F2)(implicit ev: =:=[F1, F2]): PPrint = new PPrint {
      override def print(): String = s"(${left.print()} == ${right.print()})"
    }

    override def not(exp: PPrint): PPrint = new PPrint {
      override def print(): String = s"!(${exp.print()})"
    }

    override def or(left: PPrint, right: PPrint): PPrint = new PPrint {
      override def print(): String = s"(${left.print()} or ${right.print()})"
    }
  }

  trait PrintExpAlgBis extends SubExpAlg[String] {
    def lit(x: Int) = x.toString()

    def add(e1: String, e2: String) = e1 + " + " + e2

    def sub(e1: String, e2: String) = e1 + " - " + e2
  }

}

object TestOA extends App {

  import OA.test

  test()
}