Chapter 5, Computing with Register Machines

Exercise 5.34


That’s interesting.

How to spot the code which is causing the process to be iterative?

As we saw in the tail recursion in section 5.5.3 under heading Applying compiled procedure, pg-586:

Because of Tail call optimisation, we can have two cases while applying a procedure:

  • If the linkage is label:
1
2
3
(assign continue (label <linkage>))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
  • If the linkage is return:
1
2
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

Now, consider what happen if the procedure is iterative:

The last expression executed in the procedure must cause return to the previous continue point without introducing any new points of returns.

Lets see the given iter, an iterative case, to understand:

1
2
3
4
5
6
7
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

There is only one expression, if inside which for the false case we have a recursive invocation. Now this recursive invocation because of the book’s tail call optimization will cause to return to the same place continue from where we invoked iter.

But what will happen for the recursive process case:

1
2
3
4
(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))

The last expression here also is if and the recursive call happens in the false branch of if. Now notice that here continue after invocation of factorial will need to return to the place where we are creating argl for *.

Thus for every recursive call in this case will cause to save a continue on the stack!

This was not the case in iterative version because continue is always same in each recursive call!

To summarise:

The iterative procedure will generate recursive call as:

1
2
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

while the recursive version will generate the recursive call as:

1
2
3
(assign continue (label <linkage>))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

Now we can see this in the assembly code generated:

Which place we need to see? Yes, the false branch case where recursive call is made in both iterative and recursive cases!

Let’s first see the iterative case code(check under false branch):

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
51
52
53
54
55
56
57
58
59
false-branch9
;;start of instructions to invoke recursive call to iter
(assign proc (op lookup-variable-value) (const iter) (reg env))
;;this continue is saved because we are evaluating arguments which might change continue
(save continue)
(save proc)
(save env)
;;start of instructions to invoke '+'
(assign proc (op lookup-variable-value) (const +) (reg env))
(assign val (const 1))
(assign argl (op list) (reg val))
(assign val (op lookup-variable-value) (const counter) (reg env))
(assign argl (op cons) (reg val) (reg argl))
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch16))
compiled-branch15
(assign continue (label after-call14))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
primitive-branch16
;;results of (+ counter 1) are stored here in val
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call14
;;now we proceed to make argl for recursive call iter. the first argument
;;is the result of (+ counter 1) is saved in argl 
(assign argl (op list) (reg val))
(restore env)
(save argl)
;;start of instructions to invoke '*' 
(assign proc (op lookup-variable-value) (const *) (reg env))
(assign val (op lookup-variable-value) (const product) (reg env))
(assign argl (op list) (reg val))
(assign val (op lookup-variable-value) (const counter) (reg env))
(assign argl (op cons) (reg val) (reg argl))
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch13))
compiled-branch12
(assign continue (label after-call11))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
primitive-branch13
;;at this point results of (* product counter) are saved in argl
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call11
(restore argl)
;;now with this below instruction the argl is complete for the recursive call iter.
(assign argl (op cons) (reg val) (reg argl))
(restore proc)
;;restored continue which we saved earlier because it might have been changed while invoking '*' and '+'
;;thus this continue contains the same return point when iter was invoked first time.
(restore continue)
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch19))
compiled-branch18
;;here we make the recursive call. THIS IS THE MAIN DIFFERENCE POINT
;;NOTICE that we are not saving any internal continue points but just using the same value of continue
;;which was present originally when this procedure is invoked!
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

Note that in the above code the stack has same number of elements before and after each invocation of iter.

Now, let’s see the recursive case(again just see the code under false branch):

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
51
52
53
54
55
56
57
58
false-branch4
(assign proc (op lookup-variable-value) (const *) (reg env))
(save continue)
(save proc)
(assign val (op lookup-variable-value) (const n) (reg env))
(assign argl (op list) (reg val))
;;note that here we save argl on the stack before the recursive call to factorial so that when
;;we return at after-call9 label we can restore this and compute '*'.
(save argl)
;;start of instructions for recursive invocation of factorial
(assign proc (op lookup-variable-value) (const factorial) (reg env))
(save proc)
;;here we evaluate arguments to be passed to factorial
(assign proc (op lookup-variable-value) (const -) (reg env))
(assign val (const 1))
(assign argl (op list) (reg val))
(assign val (op lookup-variable-value) (const n) (reg env))
(assign argl (op cons) (reg val) (reg argl))
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch8))
compiled-branch7
(assign continue (label after-call6))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
primitive-branch8
;;at this point val contains the result of (- n 1)
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call6
;;now this completes the argl which is needed for factorial invocation.
(assign argl (op list) (reg val))
(restore proc)
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch11))
compiled-branch10
;;THIS IS THE MAIN POINT WHERE WE CAN SEE THE DIFFERENCE
;;notice that we are changing continue here to return to the place where
;;we can proceed to evaluate '*' procedure invocation.
(assign continue (label after-call9))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
primitive-branch11
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call9
(restore argl)
(assign argl (op cons) (reg val) (reg argl))
(restore proc)
(restore continue)
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch14))
compiled-branch13
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
primitive-branch14
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
(goto (reg continue))
after-call12
after-if3
after-lambda1

Note that in this case after each invocation of factorial the number of elements in stack keeps growing till last recursive invocation and then the stack is unwind while performing the computations for *.


Comments

Isn’t it awesome! The initial sections of this chapter were not as interesting as ch-4 so I was considering to leave it. These interesting details I would have missed!