Check out the new USENIX Web site. next up previous
Next: Monads in Langauge Design Up: DSL Implementation Using Staging Previous: Introduction

Staging in MetaML

METAML is almost a conservative extension of Standard ML. Its extensions include four staging annotations. To delay an expression until the next stage one places it between meta-brackets. Thus the expression <23> (pronounced ``bracket 23'') has type <int> (pronounced ``code of int''). The annotation, splices the deferred expression obtained by evaluating e into the body of a surrounding Bracketed expression; and evaluates e to obtain a deferred expression, and then evaluates this deferred expression. It is important to note that is only legal within lexically enclosing Brackets. We illustrate the important features of the staging annotations in the short METAML \ sessions below.

-| val z = 3+4;
val z = 7 : int

Users access METAML through a read-type-eval-print top-level. The declaration for z is read, type-checked to see that it has a consistent type (int here), evaluated (to 7), and then both its value and type are printed.

-| val quad = 
   ( 3+4,  <3+4>,    lift (3+4), <z>  );
val quad =    
   ( 7,    <3 %+ 4>, <7>,        <%z> ) :
   ( int * <int> *   <int> *     <int>)
The declaration for quad contrasts normal evaluation with the three ways objects of type code can be constructed. Placing brackets around an expression (<3+4>) defers the computation of 3+4 to the next stage, returning a piece of code. Lifting an expression (lift (3+4)) evaluates that expression (to 7 here) and then lifts the value to a piece of code that when evaluated returns the same value. Brackets around a free variable (<z>) creates a new constant piece of code with the value of the variable. Such constants print with a % sign to indicate they are constants. We call this lexical-capture of free variables. Because in METAML operators (such as + and *) are also identifiers, free occurrences of operators in constructed code often appear with % in front of them.

-| fun inc x = <1 + ~x>;
val inc = Fn  : ['a].<int> -> <int>
The declaration of the function inc illustrates that larger pieces of code can be constructed from smaller ones by using the escape annotation. Bracketed expressions can be viewed as frozen, i.e. evaluation does not apply under brackets. However, is it often convenient to allow some reduction steps inside a large frozen expression while it is being constructed, by ``splicing'' in a previously constructed piece of code. METAML allows one to escape from a frozen expression by prefixing a sub-expression within it with the tilde () character. Escape must only appear inside brackets.
-| val six = inc <5>;
val six =  <1 %+ 5> : <int>
In the declaration for six, the function increment is applied to the piece of code <5> constructing the new piece of code <1 %+ 5>.
-| run six;
val it = 6 : int
Running a piece of code, strips away the enclosing brackets, and evaluates the expression inside. To give a brief feel for how MetaML is used to construct larger pieces of code at run-time consider:
-| fun mult x n = 
       if n=0 then <1> 
              else < ~x * ~(mult x (n-1)) >;
val mult = fn  : <int> -> int  -> <int>

-| val cube = <fn y => ~(mult <y> 3)>;
val cube = <fn a => a * (a * (a * 1))> 
         : <int  -> int>

-| fun exponent n = <fn y => ~(mult <y> n)>;
val exponent = fn  : int  -> <int  -> int>

The function mult, given an integer piece of code x and an integer n, produces a piece of code that is an n-way product of x. This can be used to construct the code of a function that performs the cube operation, or generalized to a generator for producing an exponentiation function from a given exponent n. Note how the looping overhead has been removed from the generated code. This is the purpose of program staging and it can be highly effective as discussed elsewhere [4, 6, 11, 23, 27]. In this paper we use staging to construct compilers from interpreters.


next up previous
Next: Monads in Langauge Design Up: DSL Implementation Using Staging Previous: Introduction

Zine-El-abidine Benaissa
Wed Jul 21 11:46:59 PDT 1999