Virtualized Scala Reference

Tiark Rompf edited this page Aug 5, 2014 · 27 revisions

The virtualized version of the Scala compiler allows implementers of domain-specific languages to reuse as much of Scala (the host language) as possible (its syntax, type system, module system,...), without sacrificing efficient execution of the domain program. The latter is enabled by what we call "language virtualization": Scala's built-in constructs are exposed as method definitions that can be overridden by the DSL implementer in order to construct a representation of the programs written in the DSL (the "domain programs").

Concretely, an expression such as if(c) a else b is translated into a method call __ifThenElse(c, a, b). By providing its own implementation of this method, the DSL can have it generate an AST for this part of the domain program, which can thus further be analyzed and optimized by the DSL implementation. When no alternative implementation is provided, the if-then-else has the usual semantics.

For example, we could change if to print its condition and return the then-branch, discarding the else-branch:

scala> def __ifThenElse[T](cond: => Boolean, thenp: => T, elsep: => T): T = {println("if: "+cond); thenp}
__ifThenElse: [T](cond: => Boolean, thenp: => T, elsep: => T)T

scala> if(false) 1 else 2  // virtualized to `__ifThenElse(false, 1, 2)`
if: false
res0: Int = 1

Virtualized built-ins

Besides if, the following control structures and built-ins (left column) are virtualized into method calls (right column):

if (c) a else b __ifThenElse(c, a, b)
while(c) b __whileDo(c, b)
do b while(c) __doWhile(b, c)
var x = i val x = __newVar(i)
x = a __assign(x, a)
return a __return(a)
a == b __equal(a, b)
a == (b_1,..., b_n) __equal(a, b_1, ..., b_n)

These methods are defined as follows (in EmbeddedControls):

def __ifThenElse[T](cond: => Boolean, thenp: => T, elsep: => T): T
def __whileDo(cond: Boolean, body: Unit): Unit
def __doWhile(body: Unit, cond: Boolean): Unit
def __newVar[T](init: T): T
def __assign[T](lhs: T, rhs: T): Unit
def __return(expr: Any): Nothing
def __equal(expr1: Any, expr2: Any): Boolean

Since Predef inherits EmbeddedControls, these methods are visible everywhere. You can either shadow them by defining a synonymous method, or override them by inheriting EmbeddedControls.

Virtualized new (struct types)

So far, these rewrites were pretty straightforward and purely syntactic. Here's a more involved one that is type-directed:

new C{val x_i: T_i = v_i} __new( ("x_i", (self_i: R) => v'_i) )

(Note: the subscripted index _i denotes implicit repetition of the smallest syntax tree that encompasses the subtrees subscripted by the same index.)

There's no definition of __new in EmbeddedControls, as its signature would be too unwieldy. Virtualisation is not performed unless there exists a type constructor Rep, so that C is a subtype of Struct[Rep], where the marker trait Struct is defined in EmbeddedControls:

trait Struct[+Rep[x]]
Furthermore, for all i,
  • there must be some T'_i so that T_i = Rep[T'_i] -- or, if that previous equality is not unifiable, T_i = T'_i
  • v'_i results from retyping v_i with expected type Rep[T'_i], after replacing this by a fresh variable self_i (with type Rep[C{ val x_i: T'_i }], abbreviated as R)

Finally, the call __new(("x_i", (self_i: R) => v'_i)) must type check with expected type R. If this is the case, the new expression is replaced by this method call.

This assumes there is a method in scope whose definition conforms to: def __new[T](args: (String, Rep[T] => Rep[_])*): Rep[T].

e.x_i e.selectDynamic[T_i]("x_i")

When a selection e.x_i does not type check according to the normal typing rules, and e has type Rep[C{ val x_i: T_i }] (for some Rep and where C and the refinement meet the criteria outlined above), e.x_i is turned into e.selectDynamic[T_i]("x_i"). Note the T_i type argument: by defining selectDynamic appropriately, the DSL can provide type safe selection on structs. No type argument will be supplied when the field's type cannot be determined (i.e., it's not in the struct's refinement).

TransparentProxy (being reworked)

Another type-directed rewrite is intended to provide pimp-my-library functionality without the overhead of creating wrapper objects.

It's currently being revised, but here's the rewrite it should perform:, ..., v_n) __forward(x, "foo", v_1, ..., v_n)
type TransparentProxy[+T]
def __forward[A,B,C](self: TransparentProxy[A], method: String, x: TransparentProxy[B]*): TransparentProxy[C]