Chapter 5, Computing with Register Machines
Exercise 5.33
This exercise is kind of interesting after attempting ex-5.31.
The difference between two versions of factorial
is just the order of operands:
(* n (factorial-alt (- n 1)))
vs (* (factorial (- n 1)) n)))
.
So, to check the performance difference, we can think similar to ex-5.31, that what saves and restores can be avoided in first case vs the second case.
But, There is one important thing we should consider which is different here from ex-5.31. Now we are comparing the outputs from compiler! And the compiler unlike evaluator, causes the evaluation of arguments from right to left instead of left to right.
First consider the factorial-alt
version:
- It evaluates arguments to
*
from right, thus evaluating(factorial-alt (- n 1))
. Since this is a procedure, this can changeenv
which will be needed to evaluate the next argument, so we saveenv
. This is apparent from the code generated:
1
2
3
4
5
6
7
8
9
;;....
(save continue)
(save proc)
(save env)
(assign proc (op lookup-variable-value) (const factorial-alt) (reg env))
(save proc)
(assign proc (op lookup-variable-value) (const -) (reg env))
(assign val (const 1))
;;....
- Now, we evaluate the next argument which is
n
. Since this is just a variable, it does not change any registers apart fromval
. Thus we can avoid saving and restoring registerargl
while evaluating this. This is again apparent from the code generated:
1
2
3
4
5
6
;;....
(assign argl (op list) (reg val))
(restore env)
(assign val (op lookup-variable-value) (const n) (reg env))
(assign argl (op cons) (reg val) (reg argl))
;;....
Now consider the orginal factorial
version:
- Here, we first evaluate
n
. Since this can not changeenv
, we do not save or restoreenv
as is apparent from the code generated:
1
2
3
4
5
6
7
8
9
;;....
(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))
(save argl)
(assign proc (op lookup-variable-value) (const factorial) (reg env))
;;....
- Now, we evaluate
(factorial-val (- n 1))
. Even though this can changeenv
we don’t need to save n restoreenv
because this is last argument and we do not need env after this argument. But here we need to save and restoreargl
since this can changeargl
. This can also be seen in the generated code shown above.
Thus in the first case we save and restore env
while in the second case we save and restore argl
. Thus the number of operations in both cases turn out to be equal!
So, they are equally efficient.