Re: finite state machines in guile

[hjstein@bfr.co.il (Harvey J. Stein)]

Tel <telford@eng.uts.edu.au> writes:

 > > What is wrong is that scheme is defined as a properly tail recursive
 > > language and that most C compilers will not optimize tail
 > > recursion. (Some will, but that isn't the point.)
 > 
 > Explain exactly what ``properly tail recursive language'' means.
 > It most definitely is not true that every call or recursion in scheme can
 > be optimised to a jump -- only those that are in the correct tail position
 > will optimise. Similarly, some calls and recursions in C can be
 > optimised to jumps and others can't -- of those that can, some compilers
 > optimise some of them.

"Properly tail recursive" is that every tail recursive call becomes a
loop.

 > > Your scheme compiler should turn tail recursion into a loop, not rely
 > > on the target language to be smarter.
 > 
 > This is exactly what I disagree with!

If there are tail recursive calls that don't become loops then it's
not R4RS.

<snip>

 > Whether the C compiler picks up all available optimisations is quite a
 > separate issue but as far as RESPONSIBILITY goes, Hobbit should try to
 > overlap the C compiler as little as possible.

C compilers *cannot* be properly tail recursive without a change in
calling conventions because the caller pushes & pops args off the
stack.  You cannot jump to the routine because the routine won't clean
up the stack itself.  If you were to change the calling conventions to
support this, then a) you'd also have to add a stack size argument to
all calls so that the routine knows how much to pop (to support
varargs), and b) you'd be incompatible with all libraries.

-- 
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il