Re: Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct

From	Mel Wilson <mwilson@the-wire.com>
Newsgroups	comp.lang.python
Subject	Re: Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct
Followup-To	comp.lang.python
Date	2012-03-17 10:39 -0400
Organization	Aioe.org NNTP Server
Message-ID	<jk27n8$ec0$1@speranza.aioe.org> (permalink)
References	<gR09r.22645$I33.16090@uutiset.elisa.fi>

Followups directed to: comp.lang.python

Show all headers | View raw

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
> end.
> 
> 
> 
> 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.

	Mel.

Thread

csiph-web