Chapter 5, Computing with Register Machines
Exercise 5.22
append (immutable)
Code and example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
1 ]=>
(define append-machine
(make-machine
'(x y rs continue)
(list (list 'null? null?)
(list 'cons cons)
(list 'car car)
(list 'cdr cdr)
(list 'not not))
'((assign continue (label done))
loop
(test (op null?) (reg x))
(branch (label base-case))
(save continue)
(save x)
(assign continue (label after-append))
(assign x (op cdr) (reg x))
(goto (label loop))
after-append
(restore x)
(restore continue)
(assign x (op car) (reg x))
(assign rs (op cons) (reg x) (reg rs))
(goto (reg continue))
base-case
(assign rs (reg y))
(goto (reg continue))
done))
)
;Value: append-machine
1 ]=> (set-register-contents! append-machine 'x '(1 2 3))
;Value: done
1 ]=>
(set-register-contents! append-machine 'y '(a b))
;Value: done
1 ]=> (start append-machine)
;Value: done
1 ]=> (get-register-contents append-machine 'rs)
;Value 57: (1 2 3 a b)
1 ]=>
append! mutable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
1 ]=>
(define append!-machine
(make-machine
'(x y iterx temp)
(list (list 'null? null?)
(list 'set-cdr! set-cdr!)
(list 'cdr cdr))
'((assign iterx (reg x))
loop
(assign temp (op cdr) (reg iterx))
(test (op null?) (reg temp))
(branch (label base-case))
(assign iterx (op cdr) (reg iterx))
(goto (label loop))
base-case
(perform (op set-cdr!) (reg iterx) (reg y)))))
;Value: append!-machine
1 ]=> (set-register-contents! append!-machine 'x '(p q))
;Value: done
1 ]=> (set-register-contents! append!-machine 'y '(r s))
;Value: done
1 ]=> (start append!-machine)
;Value: done
1 ]=> (get-register-contents append!-machine 'x)
;Value 58: (p q r s)
1 ]=>