Tail recursion

Tail recursion

Post by Aaron Denn » Thu, 10 Jul 2003 03:11:24



That's a property of implementations, not languages, right?
(except for scheme)

AIUI, all the implementations are, but the laziness can still cause
O(N) emory usage in unevaluated thunks, in places you wouldn't expect,
although you can avoid these with the proper strictness annotations.

--
Aaron Denney
-><-
 
 
 

Tail recursion

Post by Jeff Massu » Thu, 10 Jul 2003 07:51:56


@ID-9852.news.dfncis.de:



That's what I assumed, but I ask because there was a program I wrote in
Hugs that crashed (something simple like factorial) which I presumed was
because it "blew the stack" as you put it.

I just rewrote factorial hoping to give an example, but it seems to work
just fine. Perhaps it was another routine (fib?). Can't remember, it was
a week or so ago...

Regardless, thanks for the reply :)

--
Best regards,
Jeff mailto: XXXX@XXXXX.COM
http://www.yqcomputer.com/

 
 
 

Tail recursion

Post by Joachim Du » Thu, 10 Jul 2003 11:15:37


Fib is a classical case of a non-tail recursion.

fib 1 = 1
fib 2 = 1
fib N = fib (N - 1) + fib (N - 2)

is not tail recursive: after the two recursive "fib" calls, there's
still an addition to perform.
It's a bit late, so I'm not sure, but I think stack space is O(N^2),
which is quite bad. However, I know even at 4AM that time complexity is
a horrible O(2^N) ;-)

Professors *love* fib because introducing an accumulator can reduce
space complexity to O(1) and time complexity to O(N).

Regards,
Jo
 
 
 

Tail recursion

Post by mwotto » Thu, 10 Jul 2003 12:40:44

On Wed, 09 Jul 2003 04:15:37 +0200, Joachim Durchholz posted:


On a tangent: is the testing suite called NoFib because it doesn't contain
fibonacci, or because it doesn't use unrealistic examples to tell you lies?

mrak

--
realise your life was only bait for a bigger fish
-- aesop rock
 
 
 

Tail recursion

Post by fjh » Thu, 10 Jul 2003 16:02:49

oachim Durchholz < XXXX@XXXXX.COM > writes:

The canonical definition of "proper tail recursion" is
William Clinger's PLDI'98 paper [1].


Although the original back-end of the Mercury compiler does proper
tail recursion elimination, some of the newer back-ends of the Mercury
compiler do not. They only eliminate direct tail recursion (tail recursion
where a function calls itself directly, not via another function).

Likewise, the Hotdog Scheme compiler does not always do proper tail
recursion elimination.

Kawa (another Scheme implementation) does not do proper tail call recursion
elimination by default; it only does so if the user specifies a
compiler option that tells the compiler to use a different calling
convention.

There are probably quite a few others, I would guess.


That's true of implementations which perform no tail recursion
optimization at all, but it's not true of implementations which
only eliminate direct tail recursion.


When compiling a functional language to a language such as C, C++, or
Java, if function calls in the functional language get mapped to
function calls in the target language, general tail recursion
elimination is not at all easy to implement, since the target language
has no way of expressing it. Only direct tail recursion can be easily
eliminated (since that can be easily expressed using traditional
looping constructs).

Many functional language implementations that compile to C, C++ or Java
get around this by not mapping function calls to function calls, but
instead using a lower-level approach where the functional language is
translated to code for a virtual machine, whose behaviour is then
simulated in the target language. This approach makes it possible to
get proper tail recursion optimization. However, it has some very
significant drawbacks: it can make the compiler and the generated
target code a lot more complicated, and the resulting code may also be
considerably less efficient.

Another reason why implementations might not support full tail
recursion elimination is the desire to be compatible with a particular
platform's ABI; some ABIs can prevent proper tail recursion elimination.


References
----------
[1] William D Clinger. "Proper tail recursion and space efficiency."
In the Proceedings of the 1998 ACM Conference on Programming Language
Design and Implementation, June 1998, pages 174-185.

--
Fergus Henderson < XXXX@XXXXX.COM > | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
 
 
 

Tail recursion

Post by fjh » Thu, 10 Jul 2003 16:03:47


XXXX@XXXXX.COM (Mark Alexander Wotton) writes:


Yes ;-)

--
Fergus Henderson < XXXX@XXXXX.COM > | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: < http://www.yqcomputer.com/ ~fjh> | -- the last words of T. S. Garp.
 
 
 

Tail recursion

Post by Graham Mat » Thu, 10 Jul 2003 22:22:39


Can anyone point me at a good description of how to implement
tail recursion elimination. I have a sketch idea of how to do it, but
it seems too simple ....

thanks
graham
 
 
 

Tail recursion

Post by Joachim Du » Fri, 11 Jul 2003 00:13:32


It is too simple if you can manipulate the stack directly.
Pop off all local variables and parameters (but not the return address),
push the parameters for the last call, then jump to the last routine.

Note that there are several complications:
1) If you first pop all locals and parameters, you have no place where
to store all the values you're going to push. The simple solution would
be a scratch area large enough to accommodate the largest conceivable
parameter list as temporary storage for data about to be pushed. A more
general solution would be to overwrite parameters (and to be careful to
do that in an order that doesn't overwrite data that's needed for the
next parameter to be written - this is particularly fun if your stack
conventions allow for two, four, six, and eight bytes depending on
parameter type).
2) Rewriting the stack clobbers any type discipline that the VM may
have. (This is a serious problem if you have a VM that tries to ensure
security and safety by tracing data types - the JVM is a very real
example for this case. The .net runtime can handle tail calls AFAIK, but
I don't know how much type tracing/checking it does.)
3) You really, really, really need to be able to manipulate parameters
on the stack. The JVM doesn't even allow this, so it's impossible to
implement general tail call optimization on it (as Fergus correctly
pointed out).
4) If you're running on primitive hardware where application stack and
interrupt stack are the same, you have to be quite careful not to store
data in places that are beyond top-of-stack. I.e. if the new stack frame
is smaller than the old one, you need to set up stack contents first,
then adjust stack size; if the new stack frame is larger, you have to
adjust size first, then copy the data.
5) There are issues with exceptions and such. This is one of the areas
that make tail call optimization *very* awkward in C++. (Also, C++
requires that destructors be run after the call, so the real tail call
often is a destructor call that's not even written down explicitly. And
if the local variable that triggers the destructor call isn't a
reference, there is no way to reorder destruction and explicit tail call
so that the recursion really gets tail call optimized. C++ sucks...)
6) De *** s will miss the stack frames of tail call optimized calls.
You may or may not choose to do something about it. In a paging
operating system, the most efficient option is probably to forego tail
call elimination and to make sure that the stack space can be swapped to
disk if/when the stack becomes too large. To me, this sounds very
nonportable.

I'm sure that others will have more thoughts on the issue :-)

Regards,
Jo
 
 
 

Tail recursion

Post by Marcin 'Qr » Fri, 11 Jul 2003 01:33:39


Is this project alive?

--
__("< Marcin Kowalczyk
\__/ XXXX@XXXXX.COM
^^ http://www.yqcomputer.com/ ~qrczak/
 
 
 

Tail recursion

Post by Joachim Du » Fri, 11 Jul 2003 03:20:28


More importantly: is it finally in a usable state?
Last time I looked, the site strongly advised to use it only for testing.
...
Well, nothing beats looking at the site for answers.

To Marcin's question: Yes, it's alive, the main page of the project says
"last updated 06 Jun 2003", which is pretty recent.

To my question: No, it's not generally usable yet, the relevant quote is
"the compiler is still not ready for prime time".
(Though the contents of the page has changed substantially since last
time I looked - there's definitely progress, though I can't tell how far
from a working system they are.)

(I sincerely hope something will come of it...)

Regards,
Jo
 
 
 

Tail recursion

Post by Aaron Denn » Fri, 11 Jul 2003 04:24:52


Aren't these then not conformant to the scheme report?

--
Aaron Denney
-><-
 
 
 

Tail recursion

Post by oleg » Fri, 11 Jul 2003 10:28:25

erhaps the following quite an extensive thread will prove
illuminating:

Re: Implementing call/cc or Dynamic Continuations in ANSI CL
http://groups.google.com/groups?threadm=3E9F3E99.5EE41AAB%40sonic.net

The thread discusses at length the difference between tail-recursion
(syntactic property), tail call elimination and proper tail recursion.
The latter is a technical term, perhaps ill-worded, and
not a moral judgment and definitely is not a sum of its constituent
words. Of special interest is the following excerpt from the post by
William D. Clinger (Apr 21, 2003):

***> begin quote

Yes. The problem is that the phrase is not compositional: the word
"proper" does not modify "tail recursion". Instead, the entire
phrase "proper tail recursion" refers to a property that is achieved
by implementing (syntactic) tail calls in any of several systematic
ways, and is not achieved by several other systematic ways or by any
unsystematic approach.

I don't like that either, but it is the way Steele and Sussman used
the phrase. OTOH, their usage was better than prior usage, which
overloaded "tail recursion" to mean three distinct things: syntactic
tail calls, a certain approach to implementing them, and the space
efficiency property. That they themselves often overloaded "proper
tail recursion" to mean both a certain approach to implementing them
and the space efficiency property helped cause the confusion between
tail call optimization and the space efficiency property. Now that
we have an established literature on "tail call optimizations" that
are seldom systematic enough to achieve the space efficiency property,
we have arrived at the kind of three-fold terminology that, in an
ideal world, we would have had from the start:

a syntactic concept (tail calls, aka tail recursion)
implementation techniques (tail call optimization, tail merging)
space efficiency property (proper tail recursion)

It is indeed unfortunate that one of the common terms for the first
is a subphrase of the established term for the third. The situation
is much like that surrounding the abominable parsing technique known
as "recursive descent with backup", which is not a form of the
excellent parsing technique known as "recursive descent". With the
parsing techniques, the confusion has led to alternative terms such
as "definite clause grammar (DCG) parser" for the abominable technique,
and "hand-coded LL(1) parser" for the excellent technique.

Thus I prefer "tail call" to "tail recursion" for the syntactic
concept. I would be willing to consider an alternative name for the
space efficiency property if one can be found. I do not, however,
believe that it is helpful to deny that "proper tail recursion" is
the established name for that property, or to claim that Steele and
Sussman hijacked it. So far as I know, they were the first to use
it, and their terminology was definitely an improvement over what
had come before.
***> end quote


The thread also mentions three main approaches to achieving the proper tail
recursion when compiling into C:
- whole program compilation into one C function; map source
language calls into gotos. Stalin and Gambit, to a certain
extend, do something like that.
That's the best way to test your C compiler.
- trampolines (pioneered by Guy L. Steele in the first
Scheme->C compiler)
- Cheney on MTA, implemented in Chicken
 
 
 

Tail recursion

Post by fjh » Fri, 11 Jul 2003 10:52:40

Aaron Denney < XXXX@XXXXX.COM > writes:


Yes, at least for some compiler option settings.
Which is presumably why they document it.

That's the advantage of putting such a requirement in the language
standard: it won't guarantee conformance, but at least implementations
that don't support proper tail recursion elimination are more likely to
document this fact! ;-)

--
Fergus Henderson < XXXX@XXXXX.COM > | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: < http://www.yqcomputer.com/ ~fjh> | -- the last words of T. S. Garp.
 
 
 

Tail recursion

Post by fjh » Fri, 11 Jul 2003 10:57:53

Joachim Durchholz < XXXX@XXXXX.COM > writes:


There are some limitations, in particular an inability to do tail calls to
routines with by-ref parameters in verifiable code, and an inability to
do tail calls between routines that occur in different assemblies with
different security privileges.

--
Fergus Henderson < XXXX@XXXXX.COM > | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: < http://www.yqcomputer.com/ ~fjh> | -- the last words of T. S. Garp.
 
 
 

Tail recursion

Post by Richard Bo » Fri, 11 Jul 2003 15:58:38

In article <behekf$3es$ XXXX@XXXXX.COM >,




# Research on C-- and Quick C-- is supported by a generous gift from
# Microsoft Research.

Are you sure you'd actually recommend this to anyone who wishes to
remain a free man?

Richard