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

(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 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:

• to propagate static information past conditionals without techniques described in [writing-mix-in-cps]

• may handle other control structures, or at least provide a framework for handling them

• superset of many high-level languages.

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