5.22 Exercise 5.22

We are asked to reimplement append and append! in our assembly language.

(define (append x y)

(if (null? x)

y

(cons (car x) (append (cdr x) y))))

start-machine

(assign continue (label append-done))

recurse-test

(test (op null?) (reg x))

(branch (label base-case))

(save continue)

(assign continue (label after-recurse))

(save x)

(assign x (op cdr) (reg x))

(goto (label recurse-test))

after-recurse

(restore x)

(assign rest (reg val))

(assign first (op car) (reg x))

(assign val (op cons) (reg first) (reg rest))

(restore continue)

(goto (reg continue))

base-case

(assign val (reg y))

(goto (reg continue))

append-done

(define (append! x y)

(set-cdr! (last-pair x) y)

x)

(define (last-pair x)

(if (null? (cdr x))

x

(last-pair (cdr x))))

If we ignore the function separation between append! and last-pair, we can write a very compact procedure:

last-pair-init

(assign x-iter (reg x))

last-pair-recurse

(assign temp (op cdr) (reg x-iter))

(test (op null?) (reg temp))

(branch (label perform-append))

(assign x-iter (reg temp))

(goto (label last-pair-recurse))

perform-append

(perform (op set-cdr!) (reg x-iter) (reg y))

However, we ought to go the extra mile and make last-pair a real function. By my implicit calling conventions, this means that it should return a value in the val register and should not require a special communication register like x-iter. This version is quite similar: The only substantive differences are that we save the value of x before starting to recurse, and that we assign the last x value we encounter to the val register before exiting.

last-pair-init

(save x)

last-pair-recurse

(assign temp (op cdr) (reg x))

(test (op null?) (reg temp))

(branch (label after-last-pair-recurse))

(assign x (reg temp))

(goto (label last-pair-recurse))

after-last-pair-recurse

(assign val (reg x))

(restore x)

perform-append

(perform (op set-cdr!) (reg val) (reg y))

Both of these machines work, but it should be noted that append! doesn’t support appending to an empty list, due to its use of set-cdr!.