Name: Tim Daly Date: 05/19/04-07:02:14 PM Z
In fact I’ve faced the same issue with my work on the Andrews-Curtis
Conjecture. Simply put, this takes a finite representation of a
special
group and applies one of 12 transformation functions iteratively
looking for the identity element.
The initial algorithm is clear but garbage collects like mad (lisp).
The second iteration modifies list storage in place but string-conses.
The third algorithm modifies strings in place but copies on overflow.
The fourth algorithm caches power-of-2 strings (binary buddy).
So the literate program explains the theory and then explains the
first algorithm. Next it explains the problem and its subsequent
refinement. Only the last refinement is extracted but the “thought
processes” leading from the initial implementation up to the efficient
form of the algorithm are presented.
Simply because the code is highly optimized is no reason not to
include the theory or the steps across the impedence gap.
Tim