METAML is a meta-programming system. It has an object language and a meta-language. Meta-programs are programs that manipulate object programs. In METAML\ both the object language and the meta-language are ML. In METAML an object-program is both a data structure that can be manipulated, and a program that can be run.
This duality plays an important role in target code generation. The result of applying the staged interpreter from the previous step (a meta-program) to a DSL program to be compiled is a highly constrained residual program (an object program). This program is both a data-structure and a program, so it can be both directly executed (rapid prototype) and analyzed.
We use the object-code analysis capabilities of MetaML to transform the object program into the final target language. This analysis can include both source to source transformations, or translation into another form (i.e. intermediate code, assembly language, or target language).
Control over the form of the residual program is crucial here. The residual program is always an ML program (ML is the object language). But the user can control the form of this ML program. A goal of the translation is to make the object program use only those ML features directly supported by the target language. For example, we may structure the staged interpreter such that the residual program is first order, or just a sequence of primitive actions encoded as non-standard morphisms in the monad. This is where we connect the abstract monadic actions to their efficient implementations.
The object program produced above is an ML code fragment. It can be executed or analyzed. The code produced by interpret2 is a restricted subset of ML. Disregarding the higher-order functions implicit in the monad, it is first order, and contains only Do expressions, Return expressions, if expressions, calls to the non-standard morphisms read, write, push , pop, and output, primitive arithmetic operators - and '>', and local looping functions (like loop above). The code is so regular that it can be captured by a simple grammar. The next step is to analyze this code to make the final translation to the target language, or to apply some ML-source to ML-source level optimizations. The reader might notice that the object-program above could be considerably, further simplified by applying the monad laws. There are many opportunities for doing so. After these laws are applied we obtain the much more satisfying:
<Do %mswo
{ %push 10
; a <- %read 1
; b <- Return %mswo a %- 1
; c <- %write 1 b
; d <- %read 1
; e <- %output d
; Return %mswo ()
; %pop
}>
In addition to the monad laws which hold for all monads, we can also use laws which hold for particular non-standard morphisms. For instance, in the example above, we could avoid the second read of location 1 using the following rule:
Do { e1
; c <- %write 1 b
; d <- %read 1; e2
}
=
Do { e
; c <- %write 1 b
; e2[b/d]
}
Every target language will have many such laws, and because our target language is both executable-code, and data-structure we can perform these optimizations. The final step is to translate the ML code fragment into the target language. This step uses the same intensional analysis of code capabilities of the optimization steps, and is the subject of the next section.