[PRL] almost tail-calling (was: Re: deeep stack)

[John Clements]

On May 22, 2008, at 5:18 PM, Joe Marshall wrote:

> It isn't just about the stack, though.  In a real program, each of
> those frames is hanging
> on to locals and arguments.  Depending on the program, this can make a
> nasty change
> in the order of space usage.  (See Clinger, Proper Tail Recursion and
> Space Efficiency (1998))
> He gives an example program that is O(n^2) in space if the language
> isn't tail recursive,
> but O(n) if it is.
>
> No sane person would use Bubble sort (O (n^2) in time) when O(n log n)
> solutions exist.
> But people seem perfectly happy using a mechanism that can chew up
> that much space.

Goodness, Joe, you don't have to tell *me* that.  After all, it  
doesn't get much worse than the example I already gave; this will run  
forever in constant space in a tail-calling implementation.

My point is not that Java doesn't need to be tail-calling; it does.   
Instead, I'm simply pointing out that teaching students to write  
programs in a recursive fashion in Java is not as irresponsible as  
it's made out to be by loopfans.

John "IANALoopfan" Clements


> On Thu, May 22, 2008 at 4:41 PM, John Clements
> <clements at brinckerhoff.org> wrote:
>> In teaching students last quarter, I had several of them "naively"  
>> implement
>> methods recursively rather than using loops, and was surprised to  
>> discover
>> how deep the stack could get without incident.  Just now, I  
>> decided to see
>> how deep you could go (see *1* below), and I got to
>>
>> 518660
>>
>> That is, Java's not tail-calling, but that's not bad.  Now, these  
>> are itty
>> bitty stack frames.  Adding another argument to the procedure  
>> pulls this
>> down to 346000, and adding a third brings it down to 259000.
>>
>> Regardless, I would argue that it is _entirely_ reasonable to  
>> suggest that
>> for the majority of real-world programming problems, students that  
>> use
>> recursion instead of loops are justified if it saves them  
>> programming and/or
>> debugging time; the latter is especially true since the stack  
>> traces will
>> suddenly contain a whole bunch of useful information (and yes, I  
>> know that
>> this is an argument _against_ tail calling).
>>
>> John Clements
>>
>>
>> *1*
>>
>> class TestStackDepth {
>>  static int testStackDepth(int i) {
>>    if (i % 1000 == 0)
>>      System.out.println (i);
>>    return testStackDepth (i + 1);
>>  }
>>
>>  public static void main(String args[]) {
>>    testStackDepth (0);
>>  }
>> }
>>
>>
>>
>>
>> On May 22, 2008, at 11:00 AM, Joe Marshall wrote:
>>
>>> I wonder how many of those frames are unnecessary (that is, simply
>>> awaiting
>>> a return in order to perform its own return)?
>>>
>>> On Wed, May 21, 2008 at 7:21 PM, Dave Herman  
>>> <dherman at ccs.neu.edu> wrote:
>>>>
>>>> Challenge: how many layers of enterprise abstraction before you  
>>>> blow the
>>>> Java stack? No recursion allowed, of course. :)
>>>>
>>>>
>>>> http://ptrthomas.wordpress.com/2006/06/06/java-call-stack-from- 
>>>> http-upto-jdbc-as-a-picture/
>>>>
>>>> Dave
>>>>
>>>> _______________________________________________
>>>> PRL mailing list
>>>> PRL at lists.ccs.neu.edu
>>>> https://lists.ccs.neu.edu/bin/listinfo/prl
>>>>
>>>
>>>
>>>
>>> --
>>> ~jrm
>>>
>>> _______________________________________________
>>> PRL mailing list
>>> PRL at lists.ccs.neu.edu
>>> https://lists.ccs.neu.edu/bin/listinfo/prl
>>
>>
>
>
>
> -- 
> ~jrm
>
> _______________________________________________
> PRL mailing list
> PRL at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/prl