Transformation

This chapter will explain how the @staged-annotated code is transformed to code that forms the intermediate representation necessary for staging.

The key insight is that direct and staged values are two representations of ultimately the same language-level entity. Therefore, exactly like the other data representation transformations, such as unboxing primitive types, miniboxing or value classes, staging requires the explicit introduction of coercions between the "direct" and "staged" representations. This is done using the Unified Data Representation Transformation Mechanism.

The Data Representation Mechanism is comprised of three transformation that each individual data representation transformation can adapt to its exact needs. In the case of staging, these are:

• injection - adding the annotations that guide the introduction of coercions - is done by the programmer, by adding the @staged annotations
• coercion - the coercions are introduced as part of the staging plugin
• committing to the final representation - very simple transformation, only requires transforming T @staged to Exp[T]

Let us now see how the coerce and commit phases transform the example in the introduction, pow.scala:

$ st-scalac pow.scala -Xprint:stagium -Xprint:stagium-prepare
[[syntax trees at end of           stagium-prepare]] // pow.scala
...
  def main(args: Array[String]): Unit = {
    def pow(e: Double @staged, p: Int): Double @staged = if (p.==(0))
      1.0
    else
      if (p.%(2).==(1))
        e.*(pow(e, p.-(1)))
      else
        {
          val x: Double @staged = pow(e, p./(2));
          x.*(x)
        };

    println("execute: ".+(execute[Double](pow(3.0, 5))).+("\n"));

    val fun1: Double => Double = function1[Double, Double](((e: Double @staged) => pow(e, 5)));
    println("fun1(3): ".+(fun1.apply(3.0)).+("\n"));

    val fun2: (Double, Double) => Double = function2[Double, Double, Double](((e1: Double @staged, e2: Double @staged) => pow(e1, 5).*(pow(e2, 5))));
    println("fun2(3, 1): ".+(fun2.apply(3.0, 1.0)).+("\n"))
  }
...

The stagium-inject phase has a very important purpose in the case of staging: in the staged program, programmers use the @staged annotation to signal next-stage values. On the other hand, the methods in the __staged object use the target notation, Exp[T] for next-stage values. The stagium-inject phase transforms all signatures to T @staged, such that the coerce phase can rewire method calls to __staged with the types matching as expected:

$ st-scalac pow.scala -Xprint:stagium -Xprint:stagium-coerce
[[syntax trees at end of            stagium-coerce]] // pow.scala
...
  def main(args: Array[String]): Unit = {
    def pow(e: Double @staged, p: Int): Double @staged = if (p.==(0))
      scala.this.direct2staged[Double](1.0)
    else
      if (p.%(2).==(1))
        __staged.infix_*(e, pow(e, p.-(1)))
      else
        {
          val x: Double @staged = pow(e, p./(2));
          __staged.infix_*(x, x)
        };

    println("execute: ".+(execute[Double](pow(scala.this.direct2staged[Double](3.0), 5))).+("\n"));

    val fun1: Double => Double = function1[Double, Double](((e: Double @staged) => pow(e, 5)));
    println("fun1(3): ".+(fun1.apply(3.0)).+("\n"));

    val fun2: (Double, Double) => Double = function2[Double, Double, Double](((e1: Double @staged, e2: Double @staged) => __staged.infix_*(pow(e1, 5), pow(e2, 5))));
    println("fun2(3, 1): ".+(fun2.apply(3.0, 1.0)).+("\n"))
  }
...

The stagium-coerce phase introduces the direct2staged and staged2direct coercions based on the @staged annotation. Il also rewrites method calls where the receiver is staged to the __staged object. The semantics of coercions is well defined: direct2staged means a staging-time constant, while staged2direct calls are only allowed to happen through the "gateway methods", such as execute and functionN. Any direct occurrence of staged2direct will be rejected by the plugin. Finally, the stagium-commit phase transforms the tree:

$ st-scalac pow.scala -Xprint:stagium -Xprint:stagium-commit
[[syntax trees at end of            stagium-commit]] // pow.scala
...
  def main(args: Array[String]): Unit = {
    def pow(e: stagium.Exp[Double], p: Int): stagium.Exp[Double] = if (p.==(0))
      Con.apply[Double](1.0)((scala.reflect.runtime.`package`.universe.TypeTag.Double: reflect.runtime.universe.TypeTag[Double]))
    else
      if (p.%(2).==(1))
        __staged.infix_*(e, pow(e, p.-(1)))
      else
        {
          val x: stagium.Exp[Double] = pow(e, p./(2));
          __staged.infix_*(x, x)
        };

    println("execute: ".+(execute_impl[Double](pow(Con.apply[Double](3.0), 5))).+("\n"));

    val fun1: Double => Double = function1_impl[Double, Double](((e: stagium.Exp[Double]) => pow(e, 5)));
    println("fun1(3): ".+(fun1.apply(3.0)).+("\n"));

    val fun2: (Double, Double) => Double = function2_impl[Double, Double, Double](((e1: stagium.Exp[Double], e2: stagium.Exp[Double]) => __staged.infix_*(pow(e1, 5), pow(e2, 5))));
    println("fun2(3, 1): ".+(fun2.apply(3.0, 1.0)).+("\n"))
  }
...

The stagium-commit phase undoes the transformation done in stagium-prepare: all occurences of T @staged are replaced by Exp[T]. This makes staging explicit. The coercions are also given their final semantics: direct2staged corresponds to wrapping the value in a constant node (Con) while staged2direct leads to the program being rejected. It also rewrites execute and functionN to their implementations, which trigger the generation and compilation of the new code.

The resulting AST is then compiled down to bytecode, which, when executed, produces the intermediate representation, generates code for it, compiles the code and executes it, thus performing multi-stage execution.

We encourage our reviewers to play around with the staging plugin, but to keep in mind that, due to limitations in the annotation inference, you need to explicitly mention the annotation in all interactions with generics. Please see this discussion for more background. Also please keep in mind that the staging plugin is highly experimental, nowhere near the quality of the miniboxing and value class plugin.

See the next chapter for a larger example that we can stage.