Exercise 8.1.1

   (fact-iter 4)
=> (loop)         ; The value of N is 4 and the value of A is 1.
=> (loop)         ; The value of N is 3 and the value of A is 4.
=> (loop)         ; The value of N is 2 and the value of A is 12.
=> (loop)         ; The value of N is 1 and the value of A is 24.
=> (loop)         ; The value of N is 0 and the value of A is 24.
=> 24

        The trace is the same as that of FACT-ITER-ACC, except that the
changing values N and A are achieved by updating locations provided by
FACT-ITER rather than by invoking the recursive procedure with different
arguments.



Exercise 8.1.2

   (revappend '(a b c d) '(1 2))
=> (revappend '(b c d) '(a 1 2))
=> (revappend '(c d) '(b a 1 2))
=> (revappend '(d) '(c b a 1 2))
=> (revappend '() '(d c b a 1 2))
=> '(d c b a 1 2)



Exercise 8.1.3

First version:

   (even-length? '(a b c))
=> (odd-length? '(b c))
=> (even-length? '(c))
=> (odd-length? '())
=> #f

Second version:

   (even-length? '(a b c))
=> (even? (length '(a b c)))
=> (even? (+ 1 (length '(a b))))
=> (even? (+ 1 (+ 1 (length '(a)))))
=> (even? (+ 1 (+ 1 (+ 1 (length '())))))
=> (even? (+ 1 (+ 1 (+ 1 0))))
=> (even? (+ 1 (+ 1 1)))
=> (even? (+ 1 2))
=> (even? 3)
=> #f

Flowchart form of first version:

(define even-length?
  (lambda (ls)
    (letrec ((even-loop (lambda ()
                          (if (null? ls)
                              #t
                              (begin
                                (set! ls (cdr ls))
                                (odd-loop)))))
             (odd-loop (lambda ()
                         (if (null? ls)
                             #f
                             (begin
                               (set! ls (cdr ls))
                               (even-loop))))))
      (even-loop))))




Exercise 8.2.1

        The proof is by structural induction on LS.

        Base step: LS is the empty list.  Then (LENGTH LS) is 0, so that (K
(LENGTH LS)) is (K 0); and (LENGTH-CPS LS K) is also (K 0).

        Induction step: Suppose that the proposition holds for all lists of
length m, and that LS is a list of length m + 1.  Then (LENGTH LS) is (+
(LENGTH (CDR LS)) 1), and (K (LENGTH LS)) is (K (+ (LENGTH (CDR LS)) 1)).
(LENGTH-CPS LS K), on the other hand, will be (LENGTH-CPS (CDR LS) (LAMBDA
(V) (K (+ V 1)))).  But, by the hypothesis of induction, this last will be
((LAMBDA (V) (K (+ V 1))) (LENGTH (CDR LS))); by beta-reduction, this too
be (K (+ (LENGTH (CDR LS)) 1)).  So (K (LENGTH LS)) is (LENGTH-CPS LS K),
as required.




Exercise 8.3.3

a.  Not simple, since (F (CDR X)) is an available application; not in tail
    form, since the subexpression (F (CDR X)) is in non-tail position but
    is not simple (since it is itself an available application).

b.  Not simple, since it is itself an available application; in tail form,
    since both F and (CAR (CDR X)) are simple.

c.  Simple, since it contains no available applications (indeed, no
    applications at all); in tail form, since (ZERO? X) is simple.

d.  Simple, since it contains no available applications; in tail form,
    since (LAMBDA (Y) (Y X)) is simple.

e.  Not simple, since (F 3) is an available application; in tail form,
    since (LAMBDA (X) X) is simple.

f.  Not simple, since (G X) is an available application; not in tail
    form, since (G X) is in non-tail position but is not simple.




Exercise 8.4.3

(k (+ (f x) (g y)))

(g y (lambda (v) (k (+ (f x) v))))

(g y (lambda (v) (f x (lambda (w) (k (+ v w))))))




Exercise 8.4.4

(k (p (+ 8 x) (q y)))

(q y (lambda (v) (k (p (+ 8 x) v))))

(q y (lambda (v) (p (+ 8 x) v k)))




Exercise 8.4.7

a.  (k (zero? (if a (p x) (p y))))

    (if a (k (zero? (p x))) (k (zero? (p y))))

    (if a (p x (lambda (v) (k (zero? v)))) (p y (lambda (v) (k (zero? v)))))

b.  (k (zero? (let ((x 3)) (p x))))

    (let ((x 3)) (k (zero? (p x))))

    (let ((x 3)) (p x (lambda (v) (k (zero? v)))))

c.  (k (let ((x (let ((y 8)) (p y)))) x))

    (let ((y 8)) (k (let ((x (p y)))) x))

    (let ((y 8)) (p y (lambda (v) (k (let ((x v)) x)))))

    (let ((y 8)) (p y (lambda (v) (let ((x v)) (k x)))))

d.  (k (let ((x (if a (p x) (p y)))) x))

    (if a (k (let ((x (p x))) x)) (k (let ((x (p y))) x)))

    (if a (p x (lambda (v) (k (let ((x v)) x))))
          (p y (lambda (v) (k (let ((x v)) x)))))

e.  (k (variant-case x (a () (p a)) (b () (q a)) (c (x) (f x))))

    (variant-case x (a () (k (p a))) (b () (k (q a))) (c (x) (k (f x))))

    (variant-case x (a () (p a k)) (b () (q a k)) (c (x) (f x k)))