G'day all.
On Fri, Apr 19, 2002 at 07:06:04AM +0100, Piers Cawley wrote:
> If I'm going to be doing tail call optimization
> (and I can't call it scheme if I don't) then my first thought was as
> follows.
>
> # This is a tail call
>
> branch FOO_tail
> ...
>
> # This not a tail call
>
> bsr FOO
> ...
>
> FOO: pop_call I0
> FOO_tail: ...
> ...
> FOO_ret: push_call I0
> ret
>
> (In the example I'm using 'I0' as my 'partial continuation
> register'. Essentially the partial continuation is the place where you
> want to return to when the current function is finished.
I don't understand why you need it. Can't you just use the top of
the call stack as the continuation?
Surely all you need to do to perform a tail call is:
- Clean up anything in your current function which needs
cleaning up.
- Simulate the function prologue of whatever you're calling.
- Jump to the point after the prologue (FOO_tail in the
example above).
If you do that and f tailcalls g, then when g calls "ret", it should
automatically return to whatever called f, shouldn't it?
For example (and sorry if this isn't vanilla Scheme; I'm more used
to Common Lisp):
(defun main () (print (fac 5)))
(defun fac (x) (fac_accum x 1))
(defun fac_accum (x acc)
(if (= x 0) acc (fac_accum (- x 1) (* x acc))))
Scheme is a functional language, so by law the first example must
be factorial.
Assuming the calling convention is to push the arguments onto the
stack from left to right with callee-popping (which it probably
isn't; you'll probably be using an SECD-machine-alike or something):
_entry:
bsr main
end
main:
main_TAIL:
save 5
bsr fac
print I0
ret
fac:
restore I0
fac_TAIL:
set I1,1
branch fac_accum_TAIL
fac_accum:
restore I1
restore I0
fac_accum_TAIL:
ne I0,0,ite1
set I0,I1
ret
ite1:
mul I1,I1,I0
sub I0,I0,1
branch fac_accum_TAIL
Try it.
Cheers,
Andrew Bromage
