Last active
April 3, 2018 20:02
-
-
Save netanelrabinowitz/237299444c7635a77d5bce31dc8df856 to your computer and use it in GitHub Desktop.
A simple final encoding example with an extension and an applied optimization
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // http://2017.flatmap.no/talks/hauck/ | |
| object SimpleFinalEncodingExample { | |
| sealed trait Expr[A] { | |
| def lit(x: Int): A | |
| def neg(e: A): A | |
| def add(e1: A, e2: A): A | |
| } | |
| sealed trait ExprMul[A] { | |
| def mul(e1: A, e2: A): A | |
| } | |
| def program[A](implicit E: Expr[A]): A = { | |
| import E._ | |
| add(lit(50), | |
| neg(add(lit(6), | |
| lit(2))) | |
| ) | |
| } | |
| def programMul[A](implicit E1: Expr[A], E2: ExprMul[A]): A = { | |
| import E1._, E2._ | |
| // 2 * (1 + (10 + 10)) | |
| mul(lit(2), | |
| add(lit(1), | |
| add(lit(10), | |
| lit(10)))) | |
| } | |
| // interpreter1 | |
| implicit val calc: Expr[Int] = new Expr[Int] { | |
| override def lit(x: Int): Int = x | |
| override def neg(e: Int): Int = -e | |
| override def add(e1: Int, e2: Int): Int = e1 + e2 | |
| } | |
| implicit val calcMul: ExprMul[Int] = new ExprMul[Int] { | |
| override def mul(e1: Int, e2: Int): Int = e1 * e2 | |
| } | |
| //interpreter2 | |
| implicit val pretty: Expr[String] = new Expr[String] { | |
| override def lit(x: Int): String = x.toString | |
| override def neg(e: String): String = s"-$e" | |
| override def add(e1: String, e2: String): String = s"($e1 + $e2)" | |
| } | |
| implicit val prettyMul: ExprMul[String] = new ExprMul[String] { | |
| override def mul(e1: String, e2: String): String = s"($e1 * $e2)" | |
| } | |
| // push down negation optimization | |
| // move all negation into the leaves | |
| // -(1 + 2) -> (-1 + -2) | |
| // (+) (+) | |
| // / \ / \ | |
| // 50 - -> 50 (+) | |
| // | / \ | |
| // (+) - - | |
| // / \ | | | |
| // 6 2 6 2 | |
| // we can change the "AST" we just need to be more explicit about our dependencies | |
| // when we do transformations. | |
| // here we need to know whether the previous operation was negation or not | |
| sealed trait Ctx | |
| case object Pos extends Ctx | |
| case object Neg extends Ctx | |
| // newtype for: Ctx => A | |
| final class Push[A](val run: Ctx => A) extends AnyVal | |
| implicit def pushNeg[A](implicit E: Expr[A]): Expr[Push[A]] = new Expr[Push[A]] { | |
| override def lit(x: Int): Push[A] = new Push[A]({ | |
| case Pos => E.lit(x) | |
| case Neg => E.neg(E.lit(x)) | |
| }) | |
| override def neg(e: Push[A]): Push[A] = new Push[A]({ | |
| case Pos => e.run(Neg) | |
| case Neg => e.run(Pos) | |
| }) | |
| override def add(e1: Push[A], e2: Push[A]): Push[A] = new Push[A](ctx => E.add(e1.run(ctx), e2.run(ctx))) | |
| } | |
| def main(args: Array[String]): Unit = { | |
| println(program[String]) // (50 + -(6 + 2)) | |
| println(programMul[String]) // (2 * (1 + (10 + 10))) | |
| println(program[Push[String]].run(Pos)) // (50 + (-6 + -2)) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment