[Python-Dev] Re: Proper tail recursion (original) (raw)

Andrew Koenig ark-mlist at att.net
Fri Jul 16 16:47:55 CEST 2004

http://mail.python.org/pipermail/python-list/2003-November/193953.html http://mail.python.org/pipermail/python-list/2003-November/193956.html

As an interesting example of writing such algorithms without explicit recursion: The garbage collector for Spitbol/360 uses a mark-and-sweep algorithm, which it implements in such a way as to use O(1) auxiliary space, including the stack! It does do by using the following trick:

Every block of memory begins with a word that usually contains the block's type. The memory-management system requires that every pointer must point to the beginning of a block (i.e. to the type word) -- there are no pointers to memory within blocks.

The mark phase of the garbage collector replaces each type word with the head of a singly linked through the pointers that originally pointed to that block. The tail of the list is the original type word with the low-order bit turned on to indicate that it is the end.

When garbage collection is complete, then, every pointer that originally pointed to a block is now either a copy of that block's original type word (with the low-order bit turned on) or is a pointer to another pointer that originally pointed to that block. Every live block's type word is a pointer to a pointer that originally pointed to it. Every dead block's type word retains its original value.

The sweep phase is done in two passes. The first one goes through every block. If the block is dead, it does nothing. If it is live, it goes through the chain of pointers that are now linked to that block, setting every pointer to the address that the block will occupy after the second pass is complete. Once it has done this, it can restore the block's type word.

The second pass of the sweep phase relocates every live block to its final position. There is no need to change any pointers in this pass, because the first pass changed them all.

The result is that all live blocks are now contiguous, and all pointers point to the blocks' new location. There is also the nice side effect that all live blocks' addresses remain in the same relative order, a property that is used by other parts of the compiler.

I mention this rather long example to show that it is possible to eliminate recursion even in fairly complicated algorithms, but that you may not actually want to do it unless you're Robert Dewar :-)

More information about the Python-Dev mailing list