Root Language

The root language (input to and output from cogen) is a untyped CPS-CPS (continuation passing style, closure passing style) language [Appel]. You could also describe it as an unlimited-register abstract machine code. It should be easy to assemble it into executable code, allowing fast generated compilers.

Here is a quick definition of the root language's syntax and semantics:

[note match]

Note that in fact only exit and jump may appear in final position in instruction lists.

A code structure is like a procedure because it has a formal parameter list, but instead of returning a value, it simply jumps to another code structure. Allocation for activation records is explicit.

I chose an untyped language because types complicate partial evaluation [BiWe93].

I chose a continuation passing language over a procedure-call language for several reasons:

Here is some example programs in the root language: zip and compose.