Last active
November 30, 2017 16:28
-
-
Save TiarkRompf/7321eec6651287573454 to your computer and use it in GitHub Desktop.
reflect/reify quasi-quotes
This file contains 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
package test1 | |
/* | |
====================================================================== | |
fixing quasi-quotes | |
====================================================================== | |
when writing a program using quasi-quotation: | |
val x = c"foo()" | |
val y = c"bar()" | |
c"$y + $x + $x" | |
the intuition is that the quoted code would produce the same result | |
as this program: | |
val x = foo() | |
val y = bar() | |
y + x + x | |
unfortunately this is not the case. the generated code is this: | |
bar() + foo() + foo() | |
the computation of foo() has been duplicated and reordered with the | |
computation of bar(). with side effects, there are no guarantees | |
that the quoted code computes anything similar to the unquoted program. | |
another problem is passing quoted code through functions, because | |
we lose the familiar call-by-value behavior. let's assume an | |
implementation of foreach: | |
def foreach(self: Code, f: Code) = c""" | |
var i = $self.start | |
val n = $self.end | |
while (i < n) { | |
$f(i) | |
i += 1 | |
} | |
""" | |
who can spot the errors? let's try an example. if this is a macro | |
we can use it like this: | |
computeRange() foreach computeFun() | |
the compiler will auto-lift the arguments: | |
foreach(c"computeRange()", c"computeFun()") | |
and the definition above will produce the following code: | |
var i = computeRange().start | |
val n = computeRange().end | |
while (i < n) { | |
computeFun()(i) | |
i += 1 | |
} | |
however we would expect computeRange/computeFun being called | |
only once each. imagine either of them being effectful and/or | |
expensive: | |
def computeFun() = { | |
println("heavy computing...") | |
(x => ()) | |
} | |
another example (from the quasiquotation SIP): | |
class Queryable[T, Repr](query: Query) { | |
macro def filter(p: T => Boolean): Repr = c””” | |
val b = $this.newBuilder | |
b.query = Filter($this.query, $reify(p)) | |
b.result | |
””” | |
spot the two uses of $this? writing | |
computeQueryable().filter(x => true) | |
will execute computeQueryable() twice. | |
====================================================================== | |
the fix | |
====================================================================== | |
it turns out we can fix this behavior by borrowing a key idea | |
from LMS. there the mechanism to maintain relative execution order | |
is to issue a side effect whenever a staged value is created, and | |
to add a val binding to the enclosing context. executing the bindings | |
in order will execute the statements in the order they were | |
encountered. | |
in this spirit we introduce reflect/reify quotation: | |
q" foo ${ bar } baz " ---> reflect(" foo {" + reify{ bar } + "} baz ") | |
reify{ E[ reflect("str") ] } ---> "val fresh = str; " + reify{ E[ Code("fresh") ] } | |
reify{ Code("str") } ---> "str" | |
now the situation is much improved: | |
reify { | |
val x = q"foo()" | |
val y = q"bar()" | |
q"$y + $x + $x" | |
} | |
// result: "val x1 = foo(); val x2 = bar(); val x3 = {x2} + {x1} + {x1}; x3" | |
no reordering, no duplicated computation. with minor extra work | |
we can generate a cleaner but equivalent result: | |
"val x1 = foo(); val x2 = bar(); x2 + x1 + x1" | |
creating code fragments inside escapes works as expected: | |
reify { | |
val x = q"foo()" | |
val y = q"bar()" | |
q"$y + ${ q"baz()" } + $x" | |
} | |
//result: "val x1 = foo(); val x2 = bar(); | |
val x3 = {x2} + {val x4 = baz(); x4} + {x1}; x3" | |
implementation and foreach use-case are below. | |
*/ | |
// interface: abstracts over reflect/reify implementation | |
trait Q { | |
implicit def richQuote(c: StringContext) = new { | |
def q(args: Thunk[Code]*): Code = { | |
reflect(c.s(args map (a => reify(a.eval())):_*)) | |
} | |
} | |
// args: =>Code* is not allowed so we make thunks explicit | |
case class Thunk[+A](eval: () => A) | |
implicit def toThunk[A](x: =>A) = new Thunk(() => x) | |
// code is abstract | |
type Code | |
def reflect(x: String): Code | |
def reify(block: => Code): String | |
// simple pattern matching | |
def inspect[A](r: => Code)(f: PartialFunction[Code,A]): A = f(reify(r)) | |
object Tokens { def unapplySeq(s: String) = Some(s.split(" ").toSeq) } | |
object ToCode { def unapply(s: String) = Some(reflect) } | |
} | |
// regular string quotation | |
trait Q0 { | |
type Code = String | |
def reflect(x: String): Code = x | |
def reify(block: => Code): String = block | |
} | |
// simple reflect/reify quotation | |
trait Q1 { | |
case class Code(str: String) | |
var count: Int = -1 | |
var defs: String = null | |
def reflect(x: String): Code = { | |
assert(count >= 0, "reflect without enclosing reify") | |
val sym = "x" + count | |
count += 1 | |
defs += "val " + sym + " = " + x + "\n" | |
Code(sym) | |
} | |
def reify(block: => Code): String = { | |
val saveCount = count | |
val saveDefs = defs | |
count = 0 | |
defs = "" | |
val innerRes = block.str | |
val innerDefs = defs | |
count = saveCount | |
defs = saveDefs | |
"{\n" + innerDefs + innerRes + "\n}" | |
} | |
} | |
// slightly extended reflect/reify quotation | |
trait Q2 { | |
case class Code(str: String) | |
var count: Int = -1 | |
var defs: List[(String,String)] = null | |
def reflect(x: String): Code = { | |
assert(count >= 0, "reflect without enclosing reify") | |
val sym = "x" + count | |
count += 1 | |
defs ::= (sym, x) | |
Code(sym) | |
} | |
def reify(block: => Code): String = { | |
val saveCount = count | |
val saveDefs = defs | |
count = 0 | |
defs = Nil | |
val innerRes = block.str | |
val innerDefs = defs | |
count = saveCount | |
defs = saveDefs | |
def formatDefs(defs: List[(String,String)], res: String) = if (defs.isEmpty) res else | |
("{" :: (defs.reverse.map(p => "val "+p._1+" = "+p._2)) ::: res :: "}" :: Nil) mkString "\n" | |
innerDefs match { | |
case (`innerRes`,tailRes)::tailDefs => formatDefs(tailDefs, tailRes) | |
case _ => formatDefs(innerDefs, innerRes) | |
} | |
} | |
} | |
object Test extends App with Q with Q2 { | |
// simple foreach implementation. arguments guaranteed to be values. | |
def foreach1(self: Code, f: Code) = q"var i = $self.start; val n = $self.end; while (i < n) { $f(i); i += 1 }" | |
// if arguments are values we cannot inspect how they are computed, | |
// which is useful for optimizations. to pattern match on computations, | |
// we use by-name parameters. making them explicit reduces surprises. | |
def foreach2(self: => Code, f0: => Code) = { | |
val (start,end) = extractRange(self) | |
val f = extractFunction(f0) | |
q"var i = $start; val n = $end; while (i < n) { ${ f(q"i") }; i += 1 }" | |
} | |
// extractors match on the result of reify, which is the intensional | |
// representation, and reflect their return values. this is done | |
// internally by inspect and ToCode. | |
def extractRange(r: => Code): (Code,Code) = inspect(r) { | |
case Tokens(ToCode(s),"until",ToCode(e)) => (s,e) | |
case ToCode(range) => (q"$range.start", q"$range.end") | |
} | |
def extractFunction(r: => Code): (Code => Code) = inspect(r) { | |
case Tokens(x,"=>",ys @ _*) => | |
{ z: Code => reflect(ys.mkString(" ").replace(x, reify(z))) } // crude substitution... | |
case ToCode(f) => | |
{ z: Code => q"$f($z)" } | |
} | |
// let's try it ... | |
println("=== 1 ===") | |
println { reify { | |
foreach1(q"0 until 10", q"x => println(x)") | |
}} | |
/* | |
val x0 = 0 until 10 | |
val x1 = x => println(x) | |
var i = x0.start; val n = x0.end; while (i < n) { x1(i); i += 1 } | |
*/ | |
println("=== 2.1 ===") | |
println { reify { | |
foreach2(q"0 until 10", q"x => println(x)") | |
}} | |
/* | |
val x0 = 0 | |
val x1 = 10 | |
var i = x0; val n = x1; while (i < n) { { | |
val x0 = i | |
println(x0) | |
}; i += 1 } | |
*/ | |
println("=== 2.2 ===") | |
println { reify { | |
foreach2(q"myrange", q"{ println(boo!); (x => println(x)) }") | |
}} | |
/* | |
val x0 = myrange | |
val x1 = x0.start | |
val x2 = x0.end | |
val x3 = { println(boo!); (x => println(x)) } | |
var i = x1; val n = x2; while (i < n) { { | |
val x0 = i | |
x3(x0) | |
}; i += 1 } | |
*/ | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment