Re: why tail recursion matters and why Java isn't it, was Re: lisp performance was Re: problems with lisp

[John Clements <address@hidden>]

On Thursday, September 4, 2003, at 01:24  PM, Pascal Costanza wrote:

> David Herman wrote:
>>> This doesn't prove anything. In Scheme you're relying on a very 
>>> specialized feature of tail calls to be sure that your code is 
>>> efficient.
>> This was my first impression of proper tail recursion, too. It even 
>> felt like a violation of an abstraction boundary. But in fact, the 
>> opposite is true: the expectation that the runtime will blow its 
>> stack beyond a fixed depth of recursion is the violation. You should 
>> be able to use recursion without having to think about the runtime 
>> implementation
> [...]
>
> Agreed. Still, proper tail recursion is a very specific feature of 
> Scheme, and one of its strong advantages. You don't find it in a lot 
> of other languages. That's all I wanted say.
>
>>> In both cases, you have to know the languages well to get your work 
>>> done to your satisfaction. In the Common Lisp case, I have at least 
>>> three options to express my intent - one of them is straightforward, 
>>> the other two are not.
>> A particular loop construct may be natural (for some definition 
>> thereof) for some problems, but not for others. With recursion and 
>> higher-order functions you can build your own loop constructs that 
>> fit the problem space better.
>
> If a particular loop construct is natural for a particular problem, 
> why shouldn't I use it? If it's not natural I use something else.
>
> I don't care for the general case, I care for the particular case. If 
> a particular case is not covered I have to find a better solution and 
> need to apply a more general construct.
>
>>> Luke Gorrie mailed me this other solution.
>>>
>>> (mapcar 'car list)
>> Try doing that with iteration, mutation, and integer indexes and 
>> still convince yourself that a for-loop is more natural. :)
>
> I didn't say that a for-loop is _generally_ more natural. I also 
> wouldn't say that recursion is generally more natural. Again, for a 
> particular class of cases, recursion is the best solution.

In the absence of TCO, recursion is not a more general form of looping; 
replacing a loop with recursion in a language like Java may change the 
program from one that runs in finite space to one that grows without 
bound.

As a result, you cannot teach programming in such a language by 
presenting one simple general form (recursion) and a number of more 
specialized constructs (loops); you must show the two as separate, and 
explain to the students which one to use in which cases.

john clements