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 ]=>