Re: why tail recursion matters (but not much)

[Matthias Felleisen <address@hidden>]

On Monday, September 8, 2003, at 08:59 AM, Vadim Nasardinov wrote:

> Matthias Felleisen wrote:
> > What truly bothers me is that pl researchers and ll workers just 
> don't
> > get this insight. There are two kinds of traversals for data 
> (including
> > natural number):
> >
> >  - those that follow the structure (that's the essence of OOP 
> dispatch, to
> >     call methods only; loops are *not* OOP per se, though you can 
> fit them
> >     in via iterators; for the contrary, see Java)
> >
> >  - those that generate new data before they recur.
> >
> > There is nothing else.
>
>
> Undereducated persons of practicality may counter like so:
>
>   There are only two kinds of recursive data structure:
>
>   * shallow lists (finite or otherwise);
>
>   * deeply nested lists, also known as trees.
>
>
>  For the former, various kinds of specialized looping constructs, like
>  "for", "while", "do-while", "map", "reduce", and "filter", are
>  sufficient in practice.
>

Yes, because they are TCO'ed.

>  For the latter, recursive functions with no TCO are sufficient in
>  practice.  This rests on the following observation.  Let's say your
>  deeply nested recursive structure is a balanced, densely populated
>  binary tree.  To compensate for this oversimplification, let's assume
>  the data structure has a few gazillion elements.  Let's take googol 
> as a
>  nice, round, unreachable number.  In this case, the depth of the tree 
> is
>  only 700.  Here's a sample of the default stack sizes for some -- 
> shall
>  we say, popular? -- languages:
>
>    Python 1.5.2:  10,000
>    Python 2.2:     1,000
>    Tcl 8.3:        1,000
>    Java 1.3.1:     1,024
>    Perl 5.6:       ???[1]
>

This doesn't matter because you overlook the following problem:

    You don't want to use loops until you know that you can
    use this abstraction.

Why? A class hierarchy's mutual references are like gotos in a
program listing. (Thank's to Java computed goto, aka pointers,
are on their way out.) So if you want to naturally match your program
structure (aka method organization) to your class hierarchy structure
then you want a "goto" at the code level. That's method call -- if it is
implemented via TCO. If it so happens that your pointer structure
is linear and you have an iterator macro/pattern around, sure use it.
If you don't, your code still runs in great space and probably good 
time.

-- Matthias