Staging is an important technique for developing efficient programs, but it requires some forethought. To get the best results one should design algorithms with their staged solutions in mind.
The meaning of a while-program depends only on the meaning of its component expressions and commands. In the case of expressions, this meaning is a function from environments to integers. The environment is a mapping between names (which are introduced by Declare) and their values.
There are several ways that this mapping might be implemented. Since we intend to stage the interpreter, we break this mapping into two components. The first component, a list of names, will be completely known at compile-time. The second component, a list of integer values that behaves like a stack, will only be known at the run-time of the compiled program.
The functions that access this environment distribute their computation into two stages. First, determining at what location a name appears in the name list, and second, by accessing the correct integer from the stack at this location. In a more complicated compiler the mapping from names to locations would depend on more than just the declaration nesting depth, but the principle remains the same. Since every variable's location can be completely computed at compile-time, it is important that we do so, and that these locations appear as constants in the next stage.
Splitting the environment into two components is a standard technique (often called a binding time improvement) used by the partial evaluation community[8]. We capture this precisely by the following purely functional implementation.
type location = int;
type index = string list;
type stack = int list;
(* position : string -> index -> location *)
fun position name index =
let fun pos n (nm::nms) =
if name = nm
then n
else pos (n+1) nms
in pos 1 index end;
(* fetch : location -> stack -> int *)
fun fetch n (v::vs) =
if n = 1
then v
else fetch (n-1) vs;
(* put: location -> int -> stack -> stack *)
fun put n x (v::vs) =
if n = 1
then x::vs
else v::(put (n-1) x vs);
The meaning of Com is a stack transformer and an output accumulator. It transforms one stack (with values of variables in scope) into another stack (with presumably different values for the same variables) while accumulating the output printed by the program.
To produce a monadic interpreter we could define a monad which encapsulates the index, the stack, and the output accumulation. Because we intend to stage the interpreter we do not encapsulate the index in the monad. We want the monad to encapsulate only the dynamic part of the environment (the stack of values where each value is accessed by its position in the stack, and the output accumulation).
The monad we use is a combination of monad of state and the monad of output.
datatype 'a M =
StOut of (stack -> ('a * stack * string));
fun unStOut (StOut f) = f;
fun unit x = StOut(fn n => (x,n,""));
fun bind e f =
StOut(fn n =>
let val (a,n1,s1) = (unStOut e) n
val (b,n2,s2) = unStOut(f a) n1
in (b,n2,s1 ^ s2) end);
(* mswo is the Monad of state with output *)
val mswo : M Monad = Mon(unit,bind);
The non-standard morphisms must describe how the stack is extended (or shrunk) when new variables come into (or out of) scope; how the value of a particular variable is read or updated; and how the printed text is accumulated. Each can be thought of as an action on the stack of mutable variables, or an action on the print stream.
(* read : location -> int M *)
fun read i = StOut(fn ns => (fetch i ns,ns,""));
(* write : location -> int -> unit M *)
fun write i v =
StOut(fn ns =>( (), put i v ns, "" ));
(* push: int -> unit M *)
fun push x = StOut(fn ns => ( (), x :: ns, ""));
(* pop : unit M *)
val pop = StOut(fn (n::ns) => ((), ns, ""));
(* output: int -> unit M *)
fun output n =
StOut(fn ns => ( (), ns, (toString n)^" "));