Skip to content

Instantly share code, notes, and snippets.

@manuelleduc
Created October 20, 2016 15:11
Show Gist options
  • Save manuelleduc/2607f15407017daf0d6ae9a987ece243 to your computer and use it in GitHub Desktop.
Save manuelleduc/2607f15407017daf0d6ae9a987ece243 to your computer and use it in GitHub Desktop.
Object algebra examples for mleduc.xyz
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()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment