[clean-list] Re: Memory usage in recursion

[Eddy Van Esch]

Hi Richard,
Thanks for clearing up a few things.
I thought that recursion always used the stack. Of course, if a tail call
is only a jump there couldn't be any problem. I didn't know that.
My concern was that the stack size is determined by the programmer and
wasn't changed by the run time system. So if the stack size would be fixed,
a program could run out of stack space. While if it would use the heap, the
system could use all of its virtual memory....
But it seems that I have been worrying over nothing..:-)
Kind regards  
Eddy

At 11:46 21-11-00 +1300, you wrote:
>	As I understand from the Clean tutorial "Functional programming in Clean",
>	Clean uses quite a lot of recursion to implement certain functions.
>
>Any good book about functional programming will make clear the difference
>between "body" calls and "tail" calls; tail calls are effectively jumps.
>
>	What I know from other languages is that recursion usually makes
>	extensive use of the stack.  When the code is assembled you
>	usually see a number of 'pushes' and 'pops' to store and
>	retrieve data on the stack.
>
>There need not be any stack at all; Simula 67 put "stack frames" on the
>garbage collected heap, and at least some functional languages do that to
>this day (which makes it easier to implement concurrency).  Even those
>language implementations that do use a stack do NOT commonly use pushes
>or pops for that purpose.  C compilers don't.  The Quintus Prolog compiler
>certainly didn't.
>
>	As you all know the danger is that the depth of recursion
>	depends on the data to be processed by the function in question.
>	Usually you don't know in advance what the 'size' of the data
>	will be and you don't know exactly how deep the recursion will
>	be.  As a result of this, a 'stack overflow' can occur.
>
>Danger?  In the case of tail recursion, the depth of recursion could be
>a hundred million million billion and the stack depth could still be zero.
>But if data _do_ have to be saved on the stack, they have to be saved
>_somewhere_.  Why is running out of stack space thought to be worse
>than running out of space anywhere else?  It's only language implementations
>such as old MS-DOS C compilers that artificially limited the stack size to
>64 kB that had any special problem with this.  If you have 64MB of data to
>store and 64MB of memory to put it in, why should you *care* whether the
>place it's put is called "stack", "heap", or something else?  For what it's
>worth, the stack is probably the cheapest place to put anything, because
>it's likely to be reclaimed quickly and cheaply.
>	
>	Is this also the case in Clean or is the data storage during recursion
>	handled in a different way?
>
>You don't need to know.  There isn't any special problem.
>