### Tail calls, continued

Tuesday, August 26th, 2008If we look closely at the tail call optimizations, we can see the beginnings of a continuation-based implementation. One characteristic of a continuation is the abandonment of an environment, and replacing it with another.

(evlist-cmd) (set! cmddef (car result)) (set! arglist (cdr result)) (set! envstk (cdr envstk)) ; -- remove environment (evapply-cmd) ; -- may stack another environment

It seems that a continuation is a procedure that will be called as a tail call, complete with tail call optimization. Now that I think of it, the textbook example I saw of primitive continuations start out showing them as tail calls.

We can gather up the code and reshuffle which procedures the stacking and unstacking of various stacks occur. Adding redundant expressions to allow the use of the tail call versions of the evaluator procedures, we might come up with the following pair for our conditional tail calls.

(proc-call-tail (lambda () (set! seq (procbody cmddef)) (cond ( (null? seq) (undefined-tail) ) ( #t (set! envstk (cdr envstk)) (set! envstk (cons (add-args (procformals cmddef) arglist (procenv cmddef)) envstk)) (evseqhead-tail) (cond ( (constant? exp) (evconst-tail) ) ( (symbol? exp) (evvar-tail) ) ( (symbol? (car exp)) (set! cmddef (bound-value (lookup (car exp) (car envstk)))) (cond ( (eq? (first cmddef) prim-syntax-mark) (cond ( (eq? (second cmddef) 'quote) (evquote-tail) ) ( (eq? (second cmddef) 'cond) (evcondhead-tail) (evseq-tail) ) ( (eq? (second cmddef) 'set!) (evset-tail) ) ( (eq? (second cmddef) 'letrec) (evletrec-tail) ) ( (eq? (second cmddef) 'lambda) (evlambda-tail) ) ( #t (undefined-tail) ) ) ) ( #t (evcall-tail) ) ) ) ( #t (evcall-tail) ) ) ) ) ) ) (evcond-tail (lambda () (evcondhead-tail) (set! envstk (cons (car envstk) envstk)) ; -- duplicate env TOS (evseq-tail) (set! envstk (cdr envstk)) ) )

Because of the duplication of the environment, the stacking and unstacking in *evcond-tail* is redundant. After removal, the tail call optimization of tail *cond* expressions is complete, and *proc-call-tail* can call *evcond-tail* directly. This leads to further reductions…

(proc-call-tail (lambda () (set! seq (procbody cmddef)) (set! envstk (cdr envstk)) (set! envstk (cons (add-args (procformals cmddef) arglist (procenv cmddef)) envstk)) (evseq-tail) ) )

The unstacking followed immediately by the stacking of the environment can be redone as the non-consing *set-car!* for direct replacement of the top of the environment stack.

(proc-call-tail (lambda () (set! seq (procbody cmddef)) (set-car! envstk (add-args (procformals cmddef) arglist (procenv cmddef))) (evseq-tail) ) )

My first reduction of *letrec* processing was the following.

(evletrec-tail (lambda () (set! letstk (cons exp letstk)) (evletvar-tail) (set! envstk (cons (append result (car envstk)) envstk)) (set! lvalstk (cons '() lvalstk)) (evletexp-tail) (set! exp (car lvalstk)) (set! lvarstk (cons (car envstk) lvarstk)) (evletbind-tail) (set! lvarstk (cdr lvarstk)) (set! lvalstk (cdr lvalstk)) (set! seq (cdr(cdr (car letstk)))) (set! envstk (cons (car envstk) envstk)) ; -- duplicate env TOS (evseq-tail) (set! envstk (cdr envstk)) (set! letstk (cdr letstk)) (set! envstk (cdr envstk)) ) )

The stack and unstacking of *envstk* surrounding *evseq-tail* are redundant. The stacking of the environment after *evletvar-tail* is unstacked by *evseq-tail*. We can create a redundant unstack-stack pair at the beginning because *evletvar-tail* does not use the environment.

(evletrec-tail (lambda () (set! envstk (cdr envstk)) (set! envstk (cons (car envstk) envstk)) ; -- duplicate env TOS (set! letstk (cons exp letstk)) (evletvar-tail) (set! envstk (cons (append result (car envstk)) envstk)) (set! lvalstk (cons '() lvalstk)) (evletexp-tail) (set! exp (car lvalstk)) (set! lvarstk (cons (car envstk) lvarstk)) (evletbind-tail) (set! lvarstk (cdr lvarstk)) (set! lvalstk (cdr lvalstk)) (set! seq (cdr(cdr (car letstk)))) (evseq-tail) (set! letstk (cdr letstk)) (set! envstk (cdr envstk)) ) )

Because *evseq-tail* performs the matching unstack to the stack of the environment after *evletvar-tail*, we can move the trailing environment unstacking to just after *evletvar-tail*. And because *evletvar-tail* does not use the environment, we can move the final unstack to just after the duplication of the top of environment stack. The two cancel out, and the remaining unstack at the beginning can be moved down for similar reasons.

(evletrec-tail (lambda () (set! letstk (cons exp letstk)) (evletvar-tail) (set! envstk (cdr envstk)) (set! envstk (cons (append result (car envstk)) envstk)) (set! lvalstk (cons '() lvalstk)) (evletexp-tail) (set! exp (car lvalstk)) (set! lvarstk (cons (car envstk) lvarstk)) (evletbind-tail) (set! lvarstk (cdr lvarstk)) (set! lvalstk (cdr lvalstk)) (set! seq (cdr(cdr (car letstk)))) (evseq-tail) (set! letstk (cdr letstk)) ) )

The unstack followed by stack can be redone with a *set-car!*. And because the *letrec* stack is not needed after the expression sequence has been pulled out, it can be unstacked before calling *evseq-tail*.

(evletrec-tail (lambda () (set! letstk (cons exp letstk)) ;; bind variables to ***undefined*** ;; return list of bindings in "result" (evletvar-tail) (set-car! envstk (append result (car envstk))) (set! lvalstk (cons '() lvalstk)) ;; create list of "let" initialization values ;; return in lvalstk (evletexp-tail) (set! exp (car lvalstk)) ;; rebind "let" variables (set! lvarstk (cons (car envstk) lvarstk)) (evletbind-tail) (set! lvarstk (cdr lvarstk)) (set! lvalstk (cdr lvalstk)) (set! seq (cdr(cdr (car letstk)))) (set! letstk (cdr letstk)) (evseq-tail) ) )

The *lvarstk* variable is renamed to *letbindstk* because it doesn’t stack lists of variables, but lists of variable bindings. The stacking and unstacking of *lvarstk* are also “hoisted” from *evletvar-tail*.

(evletrec-tail (lambda () (set! letstk (cons exp letstk)) (set! letbindstk (cons '() letbindstk)) ;; bind variables to ***undefined*** ;; return list of bindings in letbindstk (evletvar-tail) (set! result (car letbindstk)) (set-car! envstk (append result (car envstk))) (set! lvalstk (cons '() lvalstk)) ;; create list of "let" initialization values ;; return in lvalstk (evletexp-tail) (set! exp (car lvalstk)) ;; mutate "let" variable bindings (evletbind-tail) (set! letbindstk (cdr letbindstk)) (set! lvalstk (cdr lvalstk)) (set! seq (cdr(cdr (car letstk)))) (set! letstk (cdr letstk)) (evseq-tail) ) )