Exercise 5.34.  Compile the iterative factorial procedure

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Annotate the resulting code, showing the essential difference between 
the code for iterative and recursive versions of factorial that makes 
one process build up stack space and the other run in constant stack 
space.

————————————————————————————————————————————————————————————————————————

Compiling and pretty-printing the compiled code at the REPL:

1 ]=> (define x (compile '(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1)) 'val 'next))
1 ]=> (pp x)

The output, annotated:

  (assign val (op make-compiled-procedure) (label entry2) (reg env))
  (goto (label after-lambda1))
entry2                                                  ;; calls to factorial enter here
;; make the (define (iter product counter) ...) lambda
  (assign env (op compiled-procedure-env) (reg proc))
  (assign env (op extend-environment) (const (n)) (reg argl) (reg env))
  (assign val (op make-compiled-procedure) (label entry7) (reg env))
  (goto (label after-lambda6))
  entry7
;; start of the 'iter' procedure
  (assign env (op compiled-procedure-env) (reg proc))
  (assign env (op extend-environment) (const (product counter)) (reg argl) (reg env))
  (save continue)
  (save env)
;; test the if predicate (> counter n)
  (assign proc (op lookup-variable-value) (const >) (reg env))
  (assign val (op lookup-variable-value) (const n) (reg env))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value) (const counter) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch22))
  compiled-branch21
  (assign continue (label after-call20))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
  primitive-branch22
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
  after-call20
  (restore env)
  (restore continue)
;; here we have the result of the predicate in val
  (test (op false?) (reg val))
  (branch (label false-branch9))
  true-branch10
;; the (> counter n) case, just return the product, we are done.
  (assign val (op lookup-variable-value) (const product) (reg env))
  (goto (reg continue))
  false-branch9
;; the (not (> counter n)) case
;; we are going to call (iter (* counter product) (+ counter 1))
;; and return the result, which means we don't need to come back 
;; to this stack frame.
;; first we need to evaluate the arguments...
  (assign proc (op lookup-variable-value) (const iter) (reg env))
  (save continue)
  (save proc)
  (save env)
;; do (+ counter 1)
  (assign proc (op lookup-variable-value) (const +) (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value) (const counter) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch16))
  compiled-branch15
  (assign continue (label after-call14))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
  primitive-branch16
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
  after-call14
  (assign argl (op list) (reg val))
  (restore env)
  (save argl)
;; do (* counter product)
  (assign proc (op lookup-variable-value) (const *) (reg env))
  (assign val (op lookup-variable-value) (const product) (reg env))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value) (const counter) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch13))
  compiled-branch12
  (assign continue (label after-call11))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
  primitive-branch13
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
  after-call11
;; and here we have the value of (* counter product) in val
  (restore argl)
  (assign argl (op cons) (reg val) (reg argl))
;; now we have the argl set up with (* counter product) and (+ counter 1), so it's time to call iter.
  (restore proc)
;; and what happens next is why this runs in constant space:
;; instead of setting the continue register to come back here after the call, we just restore continue to what it was:
  (restore continue)
;; and then do the procedure call, which will return to the original caller of iter
;; so, even though there are recursive calls to iter, each one will just be a jump back to the start of the procedure.
;; the continue register will never change during all the recursive calls to iter, it will always point back to the original caller of iter, never to iter itself.
;; this runs in constant space because the stack depth at the recursive call to iter is the same as it was when iter was entered.
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch19))
  compiled-branch18
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
  primitive-branch19
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
  (goto (reg continue))
  after-call17
  after-if8
  after-lambda6
  (perform (op define-variable!) (const iter) (reg val) (reg env))
  (assign val (const ok))
  (assign proc (op lookup-variable-value) (const iter) (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  (assign val (const 1))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch5))
  compiled-branch4
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
  primitive-branch5
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
  (goto (reg continue))
  after-call3
  after-lambda1
  (perform (op define-variable!) (const factorial) (reg val) (reg env))
  (assign val (const ok))