This section demonstrates how higher-order root code works, how root is created with Scheme, and more about how it is displayed graphically.

The following Scheme procedure:

(define (compose f g) (lambda (x) (f (g x))))

(define compose
  (car (code-rec
	`((code compose
		(f g k)
		(,@(make-closure 'apply-g '(f g) 'ag)
		 ,@(call 'k '(ag))))
	  (code apply-g
		(ag x k)
		(,@(unmake-closure '(f g) 'ag)
		 ,@(make-closure 'apply-f '(f k) 'af)
		 ,@(call 'g '(x af))))
	  (code apply-f
		(af r)
		(,@(unmake-closure '(f k) 'af)
		 ,@(call 'f '(r k))))))))

make-closure, unmake-closure, and call are Scheme procedures used to simplify writing higher-order code:

(make-closure code-name save-locals result-name)

(unmake-closure restore-locals closure)

(call closure args)

code-rec makes the small changes required to convert sexpr syntax into code structures. It's most important task is to ease building recursive procedures by replacing names of codes with the actual values.

The above Scheme code expands into the following code structure. Compose creates and returns a closure (ag) made of apply-g and f and g. [more?]

((code compose
       (f g k)
       ((const cnstr#-16 ())
        (prim cnstr#-15 cons g cnstr#-16)
        (prim cnstr#-13 cons f cnstr#-15)
        (const p#-14 (code apply-g ...))
        (prim ag closure-cons p#-14 cnstr#-13)
        (prim code-pointer#-17 car k)
        (jump code-pointer#-17 k ag))
       ...)

 (code apply-g
       (ag x k)
       ((prim dstr#-18 cdr ag)
        (prim f car dstr#-18)
        (prim dstr#-19 cdr dstr#-18)
        (prim g car dstr#-19)
        (prim dstr#-20 cdr dstr#-19)
        (const cnstr#-24 ())
        (prim cnstr#-23 cons k cnstr#-24)
        (prim cnstr#-21 cons f cnstr#-23)
        (const p#-22 (code apply-f ...))
        (prim af closure-cons p#-22 cnstr#-21)
        (prim code-pointer#-25 car g)
        (jump code-pointer#-25 g x af))
       ...)

 (code apply-f
       (af r)
       ((prim dstr#-26 cdr af)
        (prim f car dstr#-26)
        (prim dstr#-27 cdr dstr#-26)
        (prim k car dstr#-27)
        (prim dstr#-28 cdr dstr#-27)
        (prim code-pointer#-29 car f)
        (jump code-pointer#-29 f r k))
       ...))

Graphically it appears:

ps

Dotted lines link jump instructions to any code structures passed as arguments, generally they are continuations or closures.