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.