Exercise 5.21.  Implement register machines for the following 
procedures. Assume that the list-structure memory operations are 
available as machine primitives.

a. Recursive count-leaves:

(define (count-leaves tree)
  (cond ((null? tree) 0)
        ((not (pair? tree)) 1)
        (else (+ (count-leaves (car tree))
                 (count-leaves (cdr tree))))))

b. Recursive count-leaves with explicit counter:

(define (count-leaves tree)
  (define (count-iter tree n)
    (cond ((null? tree) n)
          ((not (pair? tree)) (+ n 1))
          (else (count-iter (cdr tree)
                            (count-iter (car tree) n)))))
  (count-iter tree 0))

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

a.

Input is in the register "tree", output in "val".

  (assign continue (label count-done))
loop
  (test (op null?) (reg tree))
  (branch (label null))
  (test (op pair?) (reg tree))
  (branch (label pair))
  ; if it is not null and not a pair, it is a leaf
  (assign val (const 1))
  (goto (reg continue))
null
  (assign val (const 0))
  (goto (reg continue))
pair
  ; recursively count the car
  (save continue)
  (save tree)
  (assign continue (label cdr))
  (assign tree (op car) (reg tree))
  (goto (label loop))
cdr
  ; count the cdr and add the two sums
  (assign car-sum (reg val))
  (assign continue (label cdr-done))
  (restore tree)
  (assign tree (op cdr) (reg tree))
  (goto (label loop))
cdr-done
  (assign val (op +) (reg car-sum) (reg val))
  (restore continue)
  (goto (reg continue))
count-done

b.

  (assign continue (label count-done))
  (assign n (const 0))
loop
  (test (op null?) (reg tree))
  (branch (label null))
  (test (op pair?) (reg tree))
  (branch (label pair))
  ; leaf
  (assign val (op +) (const 1) (reg n))
null
  (assign val (reg n))
  (goto (reg continue))
pair
  (save continue)
  (assign continue (label car-result))
  (save tree)
  (assign tree (op car) (reg tree))
  (goto (label loop))
car-result
  (restore tree)
  (assign n (reg val))
  (assign continue (label cdr-result))
  (goto (label loop))
cdr-result
  (restore continue)
  (goto (reg continue))
count-done