Home » forums » LtU Forum

Tail call experiment

This is probably not a new idea, it was one of those things I just felt like working through myself, but it ended up taking way too much time.

Two stacks for tail calls gives a different approach to tail call optimization than the ones I was able to find, and my hunch is that's because it doesn't improve that much. But I still think it's a neat idea, maybe someone else will too.

By stevechy at 2007-07-06 22:56 | LtU Forum | previous forum topic | next forum topic | other blogs | 6160 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I wonder if there is a way

I wonder if there is a way to get rid of the three rewritings without compromising efficiency. Is the conditional that bad on current-generation processors?

Also would it make sense to keep more than two 'stacks'?

By Denis Bredelet -jido at Sat, 2007-07-07 08:44 | login or register to post comments

Not sure

Mainly I just wanted to know if it would work, then I would run some experiments if it had.

By stevechy at Sun, 2007-07-08 07:30 | login or register to post comments

Interesting, but...

The Forth folks have used this trick for decades. But, as mentioned in my "post-mortem" of RetroForth (7th paragraph), I did a little experiment which suggests that there's nothing to gain from 2 stacks, at least for the lower-level routines I was writing in Forth.

Correct me if I'm wrong, but doesn't functional programming deal mostly with large heap structures? In those cases, recursion overhead is a drop in the bucket.

There should be a better target for functional compilers than C or JVM. I'm not aware of anything suitable, but we could really use such a thing for TUNES (more on that another time.)

By Tom Novelli at Sat, 2007-07-07 17:41 | login or register to post comments

Neat

I guess it's a standard technique, is this something that would be covered in your average forth book?

By stevechy at Sun, 2007-07-08 07:27 | login or register to post comments

Forth uses one stack for

Forth uses one stack for data (arguments) and one stack for return addresses. These simple rules suffice to implement tail call elimination in Forth:

If you see a procedure call, is there a return after it?
- yes: compile a jmp
- no: compile a call

So this:

f g ;

f is f()
g is g()
; is return

in c notation this could be either:

f();
g();
return;

or

return g(f())

or something else.

This will be compiled to:

call f
jmp g

So tail calls are not a problem at all in Forth, not because of the two stacks but rather because you cannot ignore return values: they will remain on the data stack until you use them, or until you remove them explicitly.

By Jules Jacobs at Sun, 2007-07-08 18:50 | login or register to post comments