Re: Why do lisps have stack limits?

From: Kent M Pitman (pitman_at_nhplace.com)
Date: 11/24/03 

Date: 24 Nov 2003 15:20:18 -0500

Duane Rettig <duane@franz.com> writes:

> But who's to say what is bad programming style and what is simply
> a large (deeply recursive, in this case) problem to solve?

Well, indeed. My real point here was that the original post seemed to
have as its implication that stack limits were bad, and I wanted to
point out that whether they are is subjective. There are indeed some
reasons for wanting deep recursion, and for this one can just write a
handler that extends the stack (in implementations that allow it), or
pre-allocate lots of stack (for other implementations). But infinitely
deep stacks are no substitute for tail call elimination if the calls are
supposed to be getting cleaned up and are not. And calling functions
recursively when the language or implementation doesn't assure you that
tail call elimination will occur is no substitute for writing a loop.
So I wasn't meaning to take a political stance here other than to say
that whether there was even a problem in the first place is already
subjective.

> The moral? The appropriateness of a program's resource usage is not
> necessarily proportional to the program's well-written-ness.

Yes. But to this I'll add: well-written-ness is not an absolute. It
is relative to a context. The implementation and/or language spec
generally precedes the program, and the program is written in the
context of resource limitations. In a small address space, these
things were of concern and well-written programs _for that context_
did not do that, _even if_ the context did not promote the kinds of
programs we hoped to be writing in the long run...

Relevant Pages

  • Re: sanity check (coding style)
    ... I kind of shy away from recursion when I ... Lisp makes look very slow and inefficient. ... Stack overflow. ... Most implementations have very inefficient FORMAT ...
    (comp.lang.lisp)
  • Re: The machine stack and the C language
    ... functions in C implies a logical stack. ... I've used such implementations. ... No need for recursion there. ... You had to impose caller-saved and callee-saved registers by convention, jumping to the return register address, and since it had 32 registers you could actually go quite deep in trivial functions before needing to resort to putting out data to memory. ...
    (comp.lang.c)
  • Re: Any use for recursion?
    ... In modern languages there is no overhead. ... popped back off the stack, the program counter being changed again. ... Recursion is ubiquitous in modern software. ...
    (comp.programming)
  • Re: Memory management strategy
    ... >>trading memory for speed ... The use of registers instead of the stack doesn't need inlining. ... >longer instructions to access smaller data than they were optimized for. ... square) but it didn't need recursion or some kind of stack. ...
    (comp.lang.c)
  • Re: grassfire algorithm in java
    ... > How many recursions did it take to overflow the stack? ... > say, recursion counting does. ... For debugging it MAY be a useful technique - but you are talking about using ...
    (comp.lang.java.programmer)