[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] Unbounded stack growth
From: |
Matthew Flatt |
Subject: |
Re: [Chicken-users] Unbounded stack growth |
Date: |
Wed, 11 Jul 2012 20:55:24 -0600 |
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...
- [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, John Cowan, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Felix, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth,
Matthew Flatt <=
- Re: [Chicken-users] Unbounded stack growth, John Cowan, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, cjtenny, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Queiroz, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Queiroz, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/12
Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
Re: [Chicken-users] Unbounded stack growth, Shiro Kawai, 2012/07/11
Re: [Chicken-users] Unbounded stack growth, Jim Ursetto, 2012/07/11