Re: [Chicken-users] Unbounded stack growth

[Matthew Flatt]

At Thu, 12 Jul 2012 11:25:44 +0900, Alex Shinn wrote:
> I disagree - I think a stack grown too large is likely indicative
> of a programming error, or at the very least an inefficient
> algorithm.  In the general case I want my programs to be
> able to allocate as much heap as possible, but have a
> separate limitation on the stack.

Amen. Just because a computation is naturally expressed as a recursion
does not mean that you should write it that way.

To take a toy example, suppose you're summing numbers in from a binary
tree. For this toy, suppose that a tree is either a number or a `cons'
of two trees. Then, only a novice would write

 ; A tree-of-number is either
 ;  - num
 ;  - (cons tree-of-number tree-of-number)

 ; sum : tree-of-number -> number
 (define (sum t)
   (cond
     [(number? t) t]
     [else
      (+ (sum (car t)) (sum (cdr t)))]))

That `sum' will work fine on relatively balanced trees, but it will
crash (as it should!) if the tree is too large and too list-like. Every
real programmer knows that you should crate your own stack to sum the
numbers.

(I assume that we can all extrapolate from the toy to real programs. A
compiler processes a tree of expressions, right? It may be given a
too-deeply nested pile of function calls, and only an naive compiler
writer would simply recur on sub-expressions to compile an expression.
On second thought, maybe the compiler writer should just recur, and the
right response for too-deeply nested code is a seg fault; that would
serve the compiler user right for producing such a strange input.)

The point here is: you should implement your own continuations! Whether
that continuation is "finish summing numbers", "finish compiling the
program", or "finish drawing the pictures", only a novice would try to
use a language-supplied implementation of continuations. The
continuation data structure is fundamentally too exotic for a language
implementation to get it right.

Don't even get me started on so-called "first-class continuations".
We've known since the 1970s that those are too expensive to
implement...