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:
code ::= (code name args instructions) instruction ::= (prim v prim . args) | (const v c) | (exit v) | (if v true-branch) | (jump v . args) v ::= variable true-branch ::= instructions instructions ::= instruction list args ::= variable list c ::= constant name ::= constant prim ::= lambda-value[note match]
(define (eval-root code args) (match code (('code name formal-args source-code) (let loop ((instrs source-code) (env (zip formal-args args))) (let ((lu (lookup env))) (match instrs ; not just the car ((('exit arg)) (lu arg)) ((('jump fn . args)) (eval-root (lu fn) (map lu args))) ((('if pred t-branch) . f-branch) (if (lu pred) (loop t-branch env) (loop f-branch env))) ((('const var c) . rest) (loop rest (cons (cons var c) env))) ((('prim var prim . args) . rest) (let ((v (apply prim (map lu args)))) (loop rest (cons (cons var v) env))))))))))
Note that in fact only
jump may appear in final
position in instruction lists.
code structure is like a procedure because it has a formal
parameter list, but instead of returning a value, it simply jumps to
code structure. Allocation for activation records is
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.