Am So., 3. Dez. 2023 um 11:49 Uhr schrieb John Cowan <[email protected]>:
> I don't see the analogy. Anyway, the point is that no terminating program > can *rely* on its garbage being collected. > The guarantee is the following one: Given a program with a space complexity of O(1) (according to the Clinger definition) and time complexity of O(N), there is an M independent of N such that in a VM with memory M the program won't run out of memory (for any N) until it halts. > > On Sun, Dec 3, 2023 at 4:58 AM Marc Nieper-Wißkirchen < > [email protected]> wrote: > >> Am So., 3. Dez. 2023 um 06:13 Uhr schrieb John Cowan <[email protected]>: >> >>> Marc Nieper-Wißkirchen scripsit: >>> >>> SRFI 124 is wrong here; by Scheme's proper tail call guarantee, defined >>>> in "Will Clinger's Proper Tail Recursion and Space Efficiency," no longer >>>> used locations must be garbage collected (up to some "O(1)"). >>> >>> >>> Not necessarily. If a program is known to terminate and doesn't >>> require more locations (naively) than the machine makes available, then no >>> garbage collection is required. >>> >> >> This is like saying that bubble sort is an O(1) algorithm for any program >> that terminates. >> >
