On Jun 3, 2009, at 8:02 PM, Abdulaziz Ghuloum wrote:
On Jun 3, 2009, at 7:47 PM, John Clements wrote:
Why do you need a ring at the outside? To preserve tail-calling,
it would be sufficient to have a stack of rings, right?
Right. But then, you'd have to allocate a new ring every time you
make a nontail call which would make it far slower than it already
is.
Another point is that having an unbounded stack also changes the space
complexity of some programs. For a contrived example:
(define (f n ls)
(if (zero? n)
0
(+ (f (- n 1) (append ls '(1))) 1)))
(f N '()) will run in O(N^2) space instead of O(N) space if the
debugger preserves all N lists.
Aziz,,,
