[Python-Dev] Re: Proper tail recursion

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

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