reflect/reify quasi-quotes

FixingQuasiquotes.scala

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 }
*/

}