Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct
mwilson at the-wire.com
Sat Mar 17 15:39:38 CET 2012
Antti J Ylikoski wrote:
> In his legendary book series The Art of Computer Programming,
> Professor Donald E. Knuth presents many of his algorithms in the form
> that they have been divided in several individual phases, with
> instructions to GOTO to another phase interspersed in the text of the
> individual phases.
> I. e. they look like the following, purely invented, example: (Knuth is
> being clearer than me below.....)
> A1. (Do the work of Phase A1.) If <zap> then go to Phase A5,
> otherwise continue.
> A2. (Do some work.) If <zorp> go to Phase A4.
> A3. (Some more work.)
> A4. (Do something.) If <condition ZZZ> go to Phase A1.
> A5. (Something more). If <foobar> then go to Phase A2, otherwise
> I came across the problem, which would be the clearest way to program
> such algorithms with a programming language such as Python, which has
> no GOTO statement. It struck me that the above construction actually
> is a modified Deterministic Finite Automaton with states A1 -- A5 +
> [END], transferring to different states, not on read input, but
> according to conditions in the running program.
> So one very clear way to program Knuth with Python is the following
> kind of a construct.
Yeah. This is an idea that came up during the '70s after Dijkstra published
his "GOTO Considered Harmful". Model the execution pointer as a state, and
then explicit changes to the execution pointer (prohibited in GOTO-less
languages) get replaced by assignments to the state. It preserves the
objectionable part of GOTO: that there's no easy way to predict the
conditions that any statement might execute under. You can't understand any
of the program until you understand all of the program.
I think Knuth kept the assembly-language model for his algorithms because it
promotes his real goal, which is mathematical analysis of the performance of
the algorithms. It helps that his algorithms are very short.
As "the quickest way to get a Knuth algorithm running in Python", this is a
pretty good idea. My own preference is to get the algo "really" coded in
Python, but that usually takes a fair bit of time and effort.
More information about the Python-list