Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct
Sat Mar 17 15:45:45 CET 2012
On 3/17/2012 15:03, 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.
A1 and A5 are NOT states: they're labels.
There is no garanteed bijection from labels to states.
> So one very clear way to program Knuth with Python is the following
> kind of a construct.
Your way is easy, but the result is poor.
Your should try to rewrite it. Decompilers do exactly that.
More information about the Python-list