[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
No need to optimize tail recursion, use infinite virtual stack!
[I wanted to send this only to REM, but I don't know his network address
-- MIT-AI's mailer doesn't know about host IMSSS.]
Date: 18 Jul 1986 1410-PDT
From: Rem at IMSSS
To: COMMON-LISP at SU-AI
Re: No need to optimize tail recursion, use infinite virtual stack!
If a finite segment of stack is in real memory, but upon overflowing the
stack the old part of it is swapped out to disk and the upper part in
memory bubbled down to make new room, an effectively infinite stack can
be emulated. With tail recursion emulating iteration, there is one big
sweep of gobbling up more and more virtual stack, followed by one
quick unwind of all that stack, thus very little thrashing, thus not
too inefficient. When bubbling the stack, stack frames have to be updated,
or else must reference virtual stack locations at the outset, but there
seem to be no major problems. Has any implementation of any LISP whatsoever
tried virtual infinite stacks?
You'd be limited by the amount of available backing store, which is
certainly not "effectively infinite," and could very easily be
inadequate. E.g. assuming, say, 16 bytes per iteration of a loop, and a
200-megabyte backing store for the stack, a loop could only iterate less
than 13 million times. More typically, a loop might take 64 bytes, and
the backing store would be 30 meg, and you'd be limited to 500,000
NIL took this approach, but with the heap instead of with the stack
(i.e. it had no GC), and it worked much better than I would have
expected. But in general, far fewer things are allocated on the heap
than on the stack, so I don't think that virtual memory, without either
GC or early deletion, would work as well for a stack.