Advanced Topics on Quasiquotes and Rewriting

Definitions and Recursive Functions

Squid quasiquotes are for expressions; they do not directly support definitions. However, quasiquotes can very well refer to definitions defined outside of them (as long as these can be accessed via a static path).

For example, this is invalid and triggers an embedding error:

scala> code {
     |   def f(i: Int) = 2 * i; // NOT SUPPORTED!
     |   f(42)
     | }
<console>:20: error: Embedding Error: Statement in expression position: def f(i: Int): Int = 2.*(i)
       code {
            ^

However, this works:

scala> code {
     |   val f = (i: Int) => 2 * i;
     |   f(42)
     | }
res1: example.doc.IR.ClosedCode[Int] = code"(2).*(42)"

Recursive functions and lazy values are not supported, but you can emulate them using a fixpoint combinator and the squid.utils.Lazy data type. As an example, we will define the factorial function. We first define a Y combinator.

package example.doc
object FixPoint {
  def Y[S,T](f: (S => T) => (S => T)): (S => T) = f(Y(f))(_:S)
}

(Again, object FixPoint needs a static path to be accessible from quasiquotes, so it has to be defined in a file of its own, not in the REPL.)
Now we can define a factorial function in a quasiquote:

val factorial = code {
  FixPoint.Y[Int, Int] {
    (f: (Int => Int)) =>
      (n: Int) =>
        if (n <= 1) 1
        else n * f(n - 1)
  }
}

In addition, method definitions that live in an object or a class annotated with @embed have automatic support for inlining, as explained in the documentation on lowering transformers.

Speculative Rewrite Rules

It is possible to define rewrite rules that try to apply some transformations, but abort in the middle if it turns out that these transformations cannot be carry out completely.

For this, one uses the Abort() construct, which throws an exception that will be caught by the innermost rewriting.

A typical application of speculative rewrite rules is the rewriting of some let-bound construct that is used in a specific way, aborting if the construct is used in unexpected ways. For example, the following tries to rewrite any Array[(Int,Int)] into two Array[Int], assuming that the original array arr is only used in expressions of the form arr.length, arr(i)._1, arr(i)._2 and arr(i) = (x,y).

def rewriteArrayOfTuples[T,C](pgrm: Code[T,C]) = pgrm rewrite {
    case code"val $arr = new Array[(Int,Int)]($len); $body: $bt" =>
      val a, b = Variable[Array[Int]]
      
      val body0 = body rewrite {
        case code"$$arr.length" => len
        //        ^ double dollar inserts an existing term into a pattern
        case code"$$arr($i)._1" => code"$a($i)"
        case code"$$arr($i)._2" => code"$b($i)"
        case code"$$arr($i) = ($x:Int,$y:Int)" => code"$a($i) = $x; $b($i) = $y"
      }
      
      // abort if there are still `arr` free variables left in `body0`:
      val body1 = body0.subs(arr) ~> Abort()
      // note that 'subs' lazily evaluates its right-hand side argument!
      
      // reconstruct the final program:
      code"val $a = new Array[Int]($len); val $b = new Array[Int]($len); $body1"
}

And here is a transformation example:

scala> rewriteArrayOfTuples(code{
     |   val l = readInt
     |   val xs = new Array[(Int,Int)](l)
     |   var i = 0
     |   while(i < xs.length) {
     |     xs(i) = (i,i+1)
     |     i += 1
     |   }
     |   val idx = new scala.util.Random().nextInt(xs.length)
     |   xs(idx)._1 + xs(idx)._2
     | })
res2: example.doc.IR.Code[Int,Any] =
code"""{
  val l_0 = scala.Predef.readInt();
  val xs_1 = new scala.Array[scala.Tuple2[scala.Int, scala.Int]](l_0);
  var i_2: scala.Int = 0;
  while ({
    val x_3 = i_2;
    val x_4 = xs_1.length;
    x_3.<(x_4)
  })
    {
      val x_5 = i_2;
      val x_6 = i_2;
      val x_7 = i_2;
      xs_1.update(x_5, scala.Tuple2.apply[scala.Int, scala.Int](x_6, x_7.+(1)));
      val x_8 = i_2;
      i_2 = x_8.+(1)
    }
  ;
  val x_9 = new scala.util.Random();
  val x_10 = xs_1.length;
  val x_11 = x_9.nextInt(x_10);
  val x_12 = xs_1.apply(x_11);
  val x_13 = xs_1.apply(x_11);
  x_12._1.+(x_13._2)
}"""

Nested Code Quotations

As an interesting aside, note that quasiquotes and quasicode can be nested:

scala> val a = code{code{1.toDouble}}  // also written:  code""" code"1.toDouble" """
a: example.doc.IR.ClosedCode[example.doc.IR.ClosedCode[Double]] =
code"""{
  val x_1 = example.doc.IR.Quasicodes.qcbase.wrapConstruct({
    val x_0 = example.doc.IR.Quasicodes.qcbase.const(1);
    example.doc.IR.Quasicodes.qcbase.methodApp(x_0, example.doc.IR.Quasicodes.qcbase.`scala.Int`.`method toDouble`.value, scala.collection.immutable.Nil, scala.collection.immutable.Nil, example.doc.IR.Quasicodes.qcbase.`scala.Double`.asStaticallyAppliedType.value)
  });
  example.doc.IR.Quasicodes.qcbase.`internal Code`[scala.Double, scala.Any](x_1)
}"""

scala> val b = a.compile
b: example.doc.IR.ClosedCode[Double] = code"1.toDouble"

scala> val c = b.compile
c: Double = 1.0

Notice how the printing of result a exposes Squid internals ― what is shown there corresponds to the code generated by the inner Squid quasiquote in order to build a runtime term representation for 1.toDouble. This code is captured and embedded by the outer quotation.

Note: In order to make the code above work, your IR object cannot be a local value, such as one defined within the REPL. To run the code above in the REPL, define that object (object IR extends SimpleAST) in a Scala file first and then run the REPL from an SBT prompt.

More generally, if you want to be able to refer to a definition (class, method or object) from within a quasiquote, this definition needs to be accessible via a static path (such as my.package.MyObject.MyClass.foo).