Tutorial ~ Getting Started

Come back soon for the final page.

We present an automated and composable approach that allows programmers to safely change the data representation in delimited scopes containing anything from expressions to entire class definitions.

Usage

In the example below we present a very simple scenario. The user wants to calculate the sum of squares of all numbers in the input array. This code will overflow in the sum variable addition if the operation adds too large numbers. Let's say for the sake of our example that the programmer does not have write-access to the code of the sumOfSquares method and she would like to change the representation of every variable of this method from Int to Long.

def sumOfSquares(v: Array[Int]) ={
  var i=0
  var sum=0
  while (i < v.length) {
    sum += v(i) * v(i)
    i += 1
  }
}

sumOfSquares(data)

The plugin that we present offers an alternative to manual transformations for the user. Instead of manual encoding various representations by copy/pasting code with the error-prone manual substitution of different representations for types, the plugin offers a modular way to achieve automatic and correct transformation.

We introduce the adrt construct. The user can regard this construct as a method that takes two parameters: a transformation description object that keeps the logic of some data layout transformation, and the actual code that we want this transformation to be applied to. In the example below we see the usage of the aforementioned keyword.

var data = (0 until 10000000).map(i => i).toArray
adrt(IntAsLong) {
  def sumOfSquares(v: Array[Int]) ={
    var i=0
    var sum=0
    while (i < v.length) {
      sum += v(i) * v(i)
      i += 1
    }
  }
}
sumOfSquares(data)

The definition of IntAsLong can be defined as a singleton object. It extends the RigidTransformationDescription (one of the two types of available super types) and essentially specifies the data representation transformation: the high-level type, its representation and the coercions between them.

  object IntAsLong extends RigidTransformationDescription {
    type High = Int
    type Repr = Long
    def toRepr(number: Int): Long @high = ???
    def fromRepr(l: Long @high): Int = ???
  }

We can observe the code in a human-readable, intermediate phase of the compiler with our plugin and without:

With:

def sumOfSquares(v: Array[Int]): Unit = {
  var i: Long = GCDTest.this.IntAsLong.toRepr(0);
  var sum: Long = GCDTest.this.IntAsLong.toRepr(0);
  while$1(){
    if (GCDTest.this.IntAsLong.fromRepr(i).<(v.length()))
    {
       {
        sum = GCDTest.this.IntAsLong.toRepr(GCDTest.this.IntAsLong.fromRepr(sum).+(v.apply(GCDTest.this.IntAsLong.fromRepr(i)).*(v.apply(GCDTest.this.IntAsLong.fromRepr(i)))));
        i = GCDTest.this.IntAsLong.toRepr(GCDTest.this.IntAsLong.fromRepr(i).+(1))
      };
      while$1()
    }
 else
   ()
}

Without:

def sumOfSquares(v: Array[Int]): Unit = {
  var i: Int = 0;
  var sum: Int = 0;
  while$1(){
    if (i.<(v.length()))
     {
       {
         sum = sum.+(v.apply(i).*(v.apply(i)));
         i = i.+(1)
       };
       while$1()
     }
   else
     ()
 }

Scala Compiler Phases

The ldl-plugin introduces the phases we described earlier in the compiler, so after the inclusion of the plugin, the sequence of compiler passes is the following:

phase		description
parser	1	parse source into ASTs, perform simple desugaring
ildl-postparser	2
namer	3	resolve names, attach symbols to named trees
packageobjects	4	load package objects
typer	5	the meat and potatoes: type the trees
ildl-inject	6
patmat	7	translate match expressions
superaccessors	8	add super accessors in traits and nested classes
extmethods	9	add extension methods for inline classes
pickler	10	serialize symbol tables
refchecks	11	reference/override checking, translate nested objects
uncurry	12	uncurry, translate function values to anonymous classes
ildl-bridge	13
ildl-coerce	14
ildl-commit	15
tailcalls	16	replace tail calls by jumps
specialize	17	@specialized-driven class and method specialization
explicitouter	18	this refs to outer pointers
erasure	19	erase types, add interfaces for traits
posterasure	20	clean up erased inline classes
lazyvals	21	allocate bitmaps, translate lazy vals into lazified defs
lambdalift	22	move nested functions to top level
constructors	23	move field definitions into constructors
flatten	24	eliminate inner classes
mixin	25	mixin composition
cleanup	26	platform-specific cleanups, generate reflective calls
delambdafy	27	remove lambdas
icode	28	generate portable intermediate code
jvm	29	generate JVM bytecode
terminal	30	the last phase during a compilation run

Let's follow the flow of AST transformations between the basic phases, with a full, simple example. In this example the data representation of a pair of integers is transformed into a long integer:

package test
import ildl._
object SimpleTest {
  object IntPairAsLong extends RigidTransformationDescription {
    type High = (Int, Int)
    type Repr = Long
    def toRepr(pair: (Int, Int)): Long @high = ???
    def fromRepr(l: Long @high): (Int, Int) = ???
  }
  adrt(IntPairAsLong) {
    val n1 = (1, 0)
  }
}

ildl-postparser

This phase runs after parsing and the AST is essentially naked, without any symbols attached. The namer phase doesn't rewrite trees but creates symbols for AST elements and also enters them in scopes. By having the ildl-plugin having a postparser (pre-namer/typer) phase gives us the opportunity to make values outside the adrt scope visible to values in the scope, effectively inlining the transformed code into the outer scope. This is implemented by flattening the AST trees, when the corresponding transformer for this phases meets the adrt term name.

package test {
  import ildl._;
  object GCDTest extends scala.AnyRef {
    def <init>() = {
      super.<init>();
      ()
    };
    object IntPairAsLong extends RigidTransformationDescription {
      def <init>() = {
        super.<init>();
        ()
      };
      type High = scala.Tuple2[Int, Int];
      type Repr = Long;
      def toRepr(pair: scala.Tuple2[Int, Int]): Long @high = $qmark$qmark$qmark;
      def fromRepr(l: Long @high): scala.Tuple2[Int, Int] = $qmark$qmark$qmark
    };
    adrt(IntPairAsLong)(());
    val n1 = scala.Tuple2(1, 0)
  }
}

ildl-inject

This phase identifies the adrt scopes, removes the adrt marker and introduces the transformation object in form of a @repr annotation where a data layout transformation may occur.

object IntPairAsLong extends AnyRef with ildl.RigidTransformationDescription {
  type High = (Int, Int);
  type Repr = Long;
  def toRepr(pair: (Int, Int)): Long @ildl.high = scala.this.Predef.???;
  def fromRepr(l: Long @ildl.high): (Int, Int) = scala.this.Predef.???
};
val n1: (Int, Int) @repr(IntPairAsLong) = scala.Tuple2.apply[Int, Int](1, 0);

ildl-bridge

Bridge is used in more sophisticated scenarios and the reader can refer to the relevant section of this wiki for a more in depth-discussion: Details-Bridges

ildl-coerce

In the coercion phase any value that subjects to layout transformation must be coerced. In the last line of the snippet for the current phase below, we notice that the object creation is encapsulated by the corresponding transformation method from the transformation object IntPairAsLong.toRepr.

object IntPairAsLong extends Object with ildl.RigidTransformationDescription {
  type High = (Int, Int);
  type Repr = Long;
  def toRepr(pair: (Int, Int)): (Int, Int) @repr(IntPairAsLong) = scala.this.Predef.???();
  def fromRepr(l: Long @ildl.high): (Int, Int) = scala.this.Predef.???()
};
val n1: (Int, Int) @repr(IntPairAsLong) = IntPairAsLong.toRepr(new (Int, Int)(1, 0));

ildl-commit

In the last phase, the annotations are removed and any changes are committed by altering the declared type of the corresponding symbols.

object IntPairAsLong extends Object with ildl.RigidTransformationDescription {
  type High = (Int, Int);
  type Repr = Long;
  def toRepr(pair: (Int, Int)): Long = scala.this.Predef.???();
  def fromRepr(l: Long @ildl.high): (Int, Int) = scala.this.Predef.???()
};
val n1: Long = IntPairAsLong.toRepr(new (Int, Int)(1, 0));

From here:

• to continue reading about the automated solution, jump to the data representation transformation
• get back to the home page