No need to optimize tail recursion, use infinite virtual stack!

[Jonathan A Rees <JAR@AI.AI.MIT.EDU>]

[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
iterations.

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.

Jonathan