Details ~ Scope Nesting - miniboxing/ildl-plugin GitHub Wiki

If you haven't read the [[introduction|Tutorial--Introduction]] and [[first example|Tutorial--Example-(Part-1)]] already, it's a good time to do so, as this advanced discussion assumes familiarity with the ildl-plugin.

This page presents the interactions between different adrt transformation scopes. Most of these interactions are exactly what programmers expect, but there are a few corner cases might be surprising. The invariant among these interactions is that they preserve correctness, which would otherwise be difficult to guarantee using manual transformations or implicit conversions.

The scoping rules presented are part of the [[ildl-plugin test suite|Tutorial-~-Running-the-Test-Suite]] and are thus checked with each build of the compiler plugin. For each of the scoping cases, we will point at the corresponding test file, along with the compiler flags that are passed and the expected output.

If you have either the demo vm or a local installation, you can use the ildl-scala and ildl-scalac scripts to run the examples on your own. For example, given this test file with its flags file, we can run:

$ cd ildl-plugin
$ ildl-scalac tests/correctness/resources/tests/scopes-nested.scala -Xprint:ildl-commit
tests/correctness/resources/tests/scopes-nested.scala:23: warning: The new 
operator can be optimized if you define a public, non-overloaded and matching
constructor method for it in object IntPairAsLong, with the name ctor_Tuple2:
      var n1 = (1, 0)
               ^
[[syntax trees at end of               ildl-commit]] // scopes-nested.scala
...

The output should match the one in the check file.

The transformation description objects used to explain the scoping rules are stubs and would not be used as such in real transformations. However, they serve the purpose of demonstrating how the ildl-plugin behaves in different cases. With this long list of disclaimers, let's see those scopes!

A limitation one might think of when seeing the lexically-scoped adrt transformations is that it is impossible to have overlapping scopes without one completely including the other. For example:

 + This code should be transformed using IntPairToLong
 | 
 |     val pair = (1, 0)
 |
 | + This code should be transformed using StringToArrayOfChar
 | |
 | |   val text = pair.toString
   |   text.substring(1,1)
   |   ...
   |

A programmer might want some part of the program (e.g. the first and second statements) to be transformed by a first scope (IntPairToLong) and an overlapping part (e.g. the second and third statements) by a second scope (StringToArrayOfChar).

It is indeed impossible to have overlap without nesting for lexical scopes. However, the lexical scopes can be split in three regions, each with its own set of transformations:

adrt(IntPairToLong) {
  val pair = (1, 0)
} 
adrt(IntPairToLong) {
  adrt(StringToArrayOfChar) {
    val text = pair.toString
  }
}
adrt(StringToArrayOfChar) {
  text.substring(1,1)
  ...
}

This way, the two overlapping scopes have been transformed into 3 disjoint scopes, two with a single transformation and one with two (nested) transformations. Which takes us to the next point, disjoint scopes.

Although disjoint, several scopes may still interact through the values that are being passed from one scope to the next. We will look at two examples.

Values from one scope can be aliased or assigned to values in other scopes, as long as the High type (= semantic meaning) of the two values is the same:

adrt(IntPairAsLong)  {  val n1 = (1, 0)  }
adrt(IntPairAsFloat) {  val n2 = n1      }

The IntPairAsLong and IntPairAsFloat transformation description objects are shown below:

object IntPairAsLong extends RigidTransformationDescription {
  type High = (Int, Int)
  type Repr = Long
  def toRepr(pair: (Int, Int)): Long @high = ...
  def toHigh(l: Long @high): (Int, Int) = ...
}

object IntPairAsFloat extends RigidTransformationDescription {
  type High = (Int, Int)
  type Repr = Float
  def toRepr(pair: (Int, Int)): Float @high = ...
  def toHigh(l: Float @high): (Int, Int) = ...
}

Before the adrt transformation, both values are of high-level type (Int, Int). However, after the transformation, inside the first scope, (Int, Int) is transformed to Long, while in the second it is transformed to Float.

Now, how can the assignment in the second line of code be implemented? Would it be okay to just assign n1, of type Long, to n2, of type Float? Despite the fact that Long values can be assigned to Float, assigning n1 to n2 would be incorrect, as it would lose the high-level program semantic, where both n1 and n2 are encoded pairs of integers. Let us see how the example is transformed by visiting each ildl-plugin transformation phase.

During the inject phase the adrt scope markers are removed and are substituted by the injected @repr annotations, parameterized by the transformation object:

val n1: (Int, Int) @repr(IntPairAsLong) = scala.Tuple2.apply[Int, Int](1, 0);
val n2: (Int, Int) @repr(IntPairAsFloat) = n1;

So far, the assignment is still correct, as both values have the (Int, Int) high-level type. The [[ildl-bridge phase|Details-~-Bridges]] leaves the tree intact, as there are no overrides.

In the coercion phase, the ildl-plugin allows the representation types to take over. Thus, while n1 still has type (Int, Int) @repr(IntPairAsLong), it is no longer compatible with either (Int, Int) or (Int, Int) @repr(IntPairAsFloat). In order to resolve this incompatibility, the toRepr and toHigh methods of the transformation description objects are invoked:

val n1: (Int, Int) @repr(IntPairAsLong) = IntPairAsLong.toRepr(new (Int, Int)(1, 0));
val n2: (Int, Int) @repr(IntPairAsFloat) = IntPairAsFloat.toRepr(IntPairAsLong.toHigh(n1()));

The reason for introducing so many toRepr and toHigh calls in the ildl-coerce phase becomes apparent in the ildl-commit, where the actual representation types are used:

val n1: Long = IntPairAsLong.toRepr(new (Int, Int)(1, 0));
val n2: Float = IntPairAsFloat.toRepr(IntPairAsLong.toHigh(n1()));

As mentioned above, correctness is a primary concern in the ildl transformation. Therefore, the n1 value, meant to be represented as a long integer, could not be directly assigned to a floating-point number, as that would lose its semantic (Int, Int) meaning. Instead, the ildl-coerce phase transformed n1 from Long to (Int, Int) first and then from (Int, Int) to Float using the toRepr and toHigh methods provided by the transformation description objects.

This example is checked automatically in the test suite: test file, flags file and check file.

A different case occurs when a transformed value escapes to a different scope, but it is used as a supertype of the High type:

adrt(IntPairAsLong)  {  
  val n1 = (1, 0)  
}
  val n2: Any = n1

In this case, if we were to use implicit conversions from (Int, Int) to Long and back, it would be insufficient, since n1 is converted to Long, which is a subtype of Any, therefore the compiler would allow the assignment to go through without an implicit conversion.

The adrt scope, on the other hand, marks the n1 value with the @repr annotation, making it incompatible with any non-annotated type. Thus: (Int, Int) @repr(IntPairAsLong) is not a subtype of Any, Scala's top of the type system. Instead, a coercion is introduced by the ildl-coerce phase:

  val n1: (Int, Int) @repr(IntPairAsLong) = ...
  val n2: Any = IntPairAsLong.toHigh(n1)

Finally, the ildl-commit phase transforms the code to:

  val n1: Long = ...
  val n2: Any = IntPairAsLong.toHigh(n1)

Again, the focus on correctness is apparent: even a diligent programmer who would prepare the implicit conversions and import them into the scope would still have trouble with this example, as there would not be any compiler error -- the code would be compiled successfully and a Long value would pop up instead of the expected pair of integers (Int, Int).

This example is checked automatically in the test suite: test file, flags file and check file.

Let us now assume we have defined the BigIntAsLong scope:

  object BigIntAsLong extends TransformationDescription {
    def toRepr(high: BigInt): Long @high = {
      assert(high.isValidLong)
      high.longValue()
    }
    def toHigh(repr: Long @high): BigInt = BigInt(repr)
    ...
  }

So far, so good. But the program you are using also uses a Queue[BigInt] to store values, like the Hamming numbers example. Unfortunately, the ildl transformation is not capable of transforming the BigIng high-level type inside generics, since it's not in control of what the Queue collection does to the values.

To optimize the Queue[BigInt] objects, another transformation description object is necessary:

  object BigIntQueueAsLongQueue extends TransformationDescription {
    def toRepr(high: Queue[BigInt]): Queue[Long] @high =
      high.map(x => { assert(x.isValidLong); x.longValue() })
    def toHigh(repr: Queue[Long] @high): Queue[BigInt] =
      repr.map(x => BigInt(x))
    ...
  }

A question that arises is how are the enqueue/dequeue operations transformed? Since the BigIntQueueAsLongQueue only handles Queue[BigIng], it does not transform the BigInt accepted by enqueue and returned by the dequeue operation to a Long. That's a shame -- whenever we pass values to the queue, the program needs to convert them to BigInt, losing performance. The following code would be transformed to:

  adrt(BigIntAsLong) {
    adrt(BigIntQueueAsLongQueue) {
      val q: Queue[BigInt] = Queue[BigInt](BigInt(1), BigInt(2), BigInt(3))
      val v: BigInt = q.dequeue
    } 
  }

Is transformed to:

  val q: Queue[Long] = ...
  val v: Long = BigIntAsLong.toRepr(q.dequeue) // too bad!

Fortunately, we can fix this by using the optional argument of the @high annotation:

  object BigIntQueueAsLongQueue extends TransformationDescription {
    ... // toHigh, toRepr
    def extension_dequeue(queue: Queue[Long] @high): Long @high(BigIntAsLong) =
      queue(idx)
  }

What the @high(BigIntAsLong) says: the Long is encoded with the BigIntAsLong transformation and corresponds to the BigInt result. Oh goodie! The result is:

  val q: Queue[Long] = ...
  val v: Long = q.dequeue

This example is checked automatically in the test suite: test file, flags file and check file.

The next section will show nested scopes.

Nested scopes allow several transformations to be composed, opening the door to more comprehensive program changes. However, with power comes responsability, and there are several cases where users need to be careful. Still, even in those corner cases, the code generated is correct and the ildl-plugin warns the programmer and explains the situation.

We will look at a correct example and then move on to corner cases.

In the case of nested adrt scopes, the ildl-plugin composes the transformations, something otherwise impossible to define in a single transformation description object. For example, the following method, foo, has two parameters, both of which could be represented differently:

adrt(IntPairAsLong) {
  adrt(IntAsLong) {
    def foo(n1: (Int, Int), n2: Int): Int = ???
  }
}

This transformation could not be specified as a single transformation description object, since each transformation description object can only target a single High type. However, composition, achieved through nested scopes, can combine several transformations into one. Following the ildl-inject phase, the two parameters of method foo are marked for transformation independently, using their respective transformation description objects:

def foo(n1: (Int, Int) @repr(IntPairAsLong), n2: Int @repr(IntAsLong)): Int @repr(IntAsLong) = ...

Jumping directly to the ildl-commit phase, the signature of method foo is going to be transformed to:

def foo(n1: Long, n2: Long): Long = ...

This example is checked automatically in the test suite: test file, flags file and check file.

One of the limitations of nested scopes is that each transformation description object should target a different High type. Should this not be the case, the ildl-plugin will report the issue:

adrt(IntPairAsLong) {
  adrt(IntPairAsFloat) {
    // `n1` can be transformed by two scopes:
    //  * `IntPairAsFloat` - to a floating point number
    //  * `IntPairAsLong` - to a long integer
    // => the innermost description object wins: IntPairAsFloat
    val n1 = (1, 0)
  }
  val n2 = (2, 3)
}

The warning the programmer will see is:

$ ildl-scalac scopes-nested-same-high.scala
scopes-nested-same-high.scala:24: warning: Several `adrt` scopes can be applied here. The innermost will apply: GCDTest.this.IntPairAsFloat
val n1 = (1, 0)
         ^

To see the result of the transformation, we omit the ildl-inject, ildl-bridge and ildl-coerce phases and jump directly to the ildl-commit phase:

  val n1: Float = IntPairAsFloat.toRepr(new (Int, Int)(1, 0));
  val n2: Long = IntPairAsLong.toRepr(new (Int, Int)(2, 3));

Notice that the innermost scope, IntPairAsFloat, won, imposing its representation type for n1. The outermost scope, IntPairAsLong, was able to transform the second statement, since there was no conflict.

This example is checked automatically in the test suite: test file, flags file and check file.

A big pitfall of composing scopes is mis-interpreting a value as an incorrect High type. This can occur when multiple High types share the same Repr type, possibly allowing values to leak between them in the encoded representation type:

adrt(IntPairAsLong) {
  adrt(IntAsLong) {
    var n1 = (1, 0)
    var n2 = 1
    n2 = n1
    println(n1) // (1, 0)
    println(n2) // <garbage>
  }
}

Since both n1 and n2 will be represented as Long, there is a risk that the encoded pair of integers may be interpreted as an integer after the assignment in the 3rd line, creating a breach in the language semantics. Fortunately, this is not the case:

$ ildl-scalac scopes-conflicting-repr.scala
scopes-conflicting-repr.scala:27: error: type mismatch;
 found   : (Int, Int)
 required: Int
      n2 = n1
           ^

Since the program is type-checked at the high level, before the ildl transformation occurs, it is impossible to leak values between different High types through their common representation type. Yeey for correctness!

This example is checked automatically in the test suite: test file, flags file and check file.

Sometimes programmers may need to communicate between different high-level types, such as, for example, between (Int, Int) and (Float, Float). This is possible in two ways:

• Communicating through the high-level types, converting both tuple components to floating-point numbers or
• Communicating through the representation types, in a commonly accepted format

The scopes-pickling.scala test shows the second point:

adrt(IntPairAsLong) {
  adrt(FloatPairAsLong) {
    val n1 = (1, 0)
    val n2 = (3f, 4f)
    val n3 = n2.unpickle(n1.pickle)
    val n4 = n1.unpickle(n2.pickle)
  }
}

Instead of creating a pair of integers and converting its components to floating-point values, the pickle and unpickle methods expect a long integer, which they treat as the representation type. However, since the encodings for (Int, Int) and (Float, Float) are different, the methods do require some work.

Still, what is interesting to notice is that no tuple object is created when pickling and unpickling:

$ ildl-scalac scopes-pickling.scala -Xprint:ildl-commit
[[syntax trees at end of               ildl-commit]] // scopes-pickling.scala
package test {
  object ScopePicklingTest extends Object {
    ...
    def main(args: Array[String]): Unit = {
      val n1: Long = IntPairAsLong.toRepr(new (Int, Int)(1, 0));
      val n2: Long = FloatPairAsLong.toRepr(new (Float, Float)(3.0, 4.0));
      val n3: Long = FloatPairAsLong.implicit_FloatPairPickle_unpickle(n2, IntPairAsLong.implicit_IntPairPickle_pickle(n1));
      val n4: Long = IntPairAsLong.implicit_IntPairPickle_unpickle(n1, FloatPairAsLong.implicit_FloatPairPickle_pickle(n2));
      println("".+(IntPairAsLong.toHigh(n1)).+(" and ").+(FloatPairAsLong.toHigh(n3)));
      println("".+(FloatPairAsLong.toHigh(n2)).+(" and ").+(IntPairAsLong.toHigh(n4)))
    }
  }
}

When running the example, the output is:

$ ildl-scala test.ScopePicklingTest
(1,0) and (1.0,0.0)
(3.0,4.0) and (3,4)

This example is checked automatically in the test suite: test file, flags file and check file.

The last example is probably the most complex. It shows two nested transformations, from pairs of integers to long integers and then from long integers to floating-point numbers:

adrt(IntPairAsLong) {
  adrt(LongAsFloat) {
    val n1 = (1, 0)
  }
}

In this case, a valid question is what will the representation of n1 be? From one perspective, it is a pair of integers, thus it can be represented as a long integer. However, the inner nested scope, LongAsFloat, can transform the long integer into a floating-point number, transitively leading to the integer pair being represented as a floating point number: (Int, Int) -> Long -> Float.

The ildl-plugin performs a single Late Data Layout transformation step, so only the first step of the transformation is performed. Currently, the ildl-plugin will not warn about this problem, since computing the transitive step in general is extremely expensive, especially when [[using FreestyleTransformationDescription objects|Details-~-Transformation-Description]].

This example is checked automatically in the test suite: test file, flags file and check file.

Congratulations! After reading this in-depth tutorial, you are an expert in adrt scopes!

• continue reading the in-depth explanation of the object model
• get back to the home page