A post on ProgrammingArt got me thinking about the fundamental organization of code. I don't expect to come up with anything new in here, but I wanted to work it out. In the end, I clarified a little my understanding of the relationship between recursive vs. iterative vs. threaded machine code.

For convenience, I'll just lift the problem statement (Ex. 1.3 from SICP)
from the original post:

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

Here is the first version of the code given, the iterative one:

(define (sum-square-largest x y z) (cond ((and (> y x) (> z x)) ;; y and z are largest (+ (* y y) (* z z))) ((and (> x y) (> z y)) ;; x and z are largest (+ (* x x) (* z z))) ((and (> x z) (> y z)) ;; x and y are largest (+ (* x x) (* y y)))))

And here is the recursive version:

(define (sum-square-largest x y z) (cond ((and (> y x) (> z x)) ;; y and z are largest (+ (* y y) (* z z))) (else (sum-square-largest y z x))))

Both versions are not necessarily good solutions (they will fail if all parameters are equal, for example) but they perform the same computation, which is what matters.

Let's first sketch what these look like when plainly translated to machine code. Let's assume a generic MIPS-like machine:

- x, y, and z are initially placed in registers $1, $2, and $3.
- Return value is placed in register $5.
- Opcode format is <op> <src1>,<src2>,<dst>, with meaning of <dst> = <src1> <op> <src2>
- As usual, register $0 always reads zero and discards writes.
- To make subroutine calls simple, assume that register $31 is also a stack.

sub $1,$2,$4 # x - y sub $1,$3,$5 # x - z and $4,$5,$5 # if x is larger than either, yields a positive number bgt $5,next1 # and thus y and z are not the largest mul $2,$2,$4 # y * y mul $3,$3,$5 # z * z add $4,$5,$5 # y^2 + z^2 jr $31 # Return to caller next1: sub $2,$1,$4 # y - x sub $2,$3,$5 # y - z and $4,$5,$5 # if y is larger than either, yields a positive number bgt $5,next2 # and thus x and z are not the largest mul $1,$1,$4 # x * x mul $3,$3,$5 # z * z add $4,$5,$5 # x^2 + z^2 jr $31 # Return to caller next2: sub $3,$1,$4 # z - x sub $3,$2,$5 # z - y and $4,$5,$5 # if z is larger than either, yields a positive number bgt $5,next3 # and thus x and y are not the largest mul $1,$1,$4 # x * x mul $2,$2,$5 # y * y add $4,$5,$5 # x^2 + y^2 jr $31 # Return to caller next3:We should never get here

I've been kind/lazy in the recursive version and eliminated the tail-call recursion. This eliminates the whole register save/restore and parameter passing overhead which isn't relevant to the computation anyway. It alters the locations of x, y, and z but that doesn't matter either.

begin: sub $1,$2,$4 # x - y sub $1,$3,$5 # x - z and $4,$5,$5 # if x is larger than either, yields a positive number bgt $5,next # and thus y and z are not the largest mul $2,$2,$4 # y * y mul $3,$3,$5 # z * z add $4,$5,$5 # y^2 + z^2 jr $31 # Return to caller next: add $1,$0,$4 # x to temp add $2,$0,$1 # y to old x ($1 = y) add $3,$0,$2 # z to old y ($2 = z) add $4,$0,$3 # x to old z ($3 = x) j begin # Do it again with shuffled x, y, and z

We can easily see that the recursive version is necessarily slower since it has to shuffle the parameters after each unsuccessful comparison, whereas this shuffling is implicit in the iterative version. The shuffling was determined at compile time and represented as the appropriate register accesses.

However, to my eye, the recursive version conveys the meaning of the solution better: it makes obvious that the comparison is to be applied to each possible combination of parameters until a match is found (there *has* to be one, given an ordered set of possible values).

We do know that the recursion will never need to repeat more than three times, so lets unroll the recursive code three times and see what we get:

sub $1,$2,$4 # x - y sub $1,$3,$5 # x - z and $4,$5,$5 # if x is larger than either, yields a positive number bgt $5,next1 # and thus y and z are not the largest mul $2,$2,$4 mul $3,$3,$5 add $4,$5,$5 # return value jr $31 # Return to caller next1: add $1,$0,$4 # x to temp add $2,$0,$1 # y to old x ($1 = y) add $3,$0,$2 # z to old y ($2 = z) add $4,$0,$3 # x to old z ($3 = x) sub $1,$2,$4 # y - z sub $1,$3,$5 # y - x and $4,$5,$5 # if y is larger than either, yields a positive number bgt $5,next2 # and thus z and x are not the largest mul $2,$2,$4 mul $3,$3,$5 add $4,$5,$5 # return value jr $31 # Return to caller next2: add $1,$0,$4 # y to temp add $2,$0,$1 # z to old y ($1 = z) add $3,$0,$2 # x to old z ($2 = x) add $4,$0,$3 # y to old x ($3 = y) sub $1,$2,$4 # z - x sub $1,$3,$5 # z - y and $4,$5,$5 # if z is larger than either, yields a positive number bgt $5,next3 # and thus x and y are not the largest mul $2,$2,$4 mul $3,$3,$5 add $4,$5,$5 # return value jr $31 # Return to caller next3:we should never get here

Notice something? There's a lot of repeated calculations operating on the same registers. We can factor out these fragments into subroutines and tie them back together with subroutine calls, resulting in threaded code with a definitely reduced size and improved clarity:

permute: add $1,$0,$4 # a to temp add $2,$0,$1 # b to old a ($1 = b) add $3,$0,$2 # c to old b ($2 = c) add $4,$0,$3 # a to old c ($3 = a) jr $31 test: sub $1,$2,$4 # a - b sub $1,$3,$5 # a - c and $4,$5,$5 # if a is larger than either, yields a positive number jr $31 calc: mul $2,$2,$4 mul $3,$3,$5 add $4,$5,$5 # return value add $31,$0,$0 # pop stack jr $31 # Return to caller (of 'do-all') do-one: jal test bgt $5,next jmp calc # tail-call next: jr $31 do-all: jal do-one jal permute jal do-one jal permute jmp do-one # tail-call jr $31

*OK, yes, popping the stack in 'calc' is a hack, but it is much clearer
than inserting another 'bgt $5' test after each call to 'do-one', and keeps the
correspondence to the original unrolled recursive code. A better approach would
be to eliminate 'do-one', change the test to a 'blt $5' after each call to
'test' and branch to a single instance of 'calc' at the end. Alternatly, not
reusing register $5 opens up other possibilities.*

Imagine writing *all* your code like this out of simple little subroutines tied together by implicit data locations, and you've got yourself the basis for a very nice programming system. If your implicit data is a stack, you've got Forth or Joy. If it's a list, you've got Lisp or Scheme. If it's a dictionary, then you're probably heading towards something like Lua or Python. etc, etc...

But these are all dynamic, interpreted languages to a large extent. How could we write the simpler recursive or threaded code but get the faster iterative code under the hood?

Well, one big feature these languages give us is the ability to define code at runtime. So I'll assume a function called "compile" which takes its arguments, places them in the source code given to it, and creates whatever internal representation used by the language (bytecodes, for example).

*This is Lisp-ish to match the original code, but I don't know Lisp.
Don't expect this to be actually correct, but only to convey the meaning.*

First, we create a function which compiles particular instances of the test and sum-of-squares calculation:

(define (compile-sum-square-largest-test x y z) (compile ((and (> y x) (> z x)) ;; y and z are largest (+ (* y y) (* z z)))))

We can then map that function onto each permutation of the arguments and give the output as the guts of a conditional expression:

(define (compile-sum-square-largest x y z) (cond (map compile-sum-square-largest-test (permutations (x y z)))))

And finally, we wrap it up under the function name and arguments we want and "execute" on-the-fly the result of the compilation just done:

(define (sum-square-largest x y z) (execute (compile-sum-square-largest (x y z))))

Of course, we could also do all this ahead of time to avoid compiling everytime we called the sum-square-largest function.

Still, it would be a good thing if the recursive expression somehow automatically reduced to the iterative machine code. It might be possible for a compiler to do it by transforming the register permutations into register renaming, via Static Single Assignment (SSA), before register allocation.

Like I said earlier, it wouldn't surprise me that this approach has been solved already, but I thought it was at least a nice little exercise.

fpgacpu.ca