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

[Antti J Ylikoski]

On 17.3.2012 17:47, Roy Smith wrote:
> In article<gR09r.22645$I33.16090 at uutiset.elisa.fi>,
>   Antti J Ylikoski<antti.ylikoski at tkk.fi>  wrote:
>
>> 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.
>>
>>
>>
>> continueLoop = 1
>> nextState = "A1"
>>
>> while continueLoop:
>>       if nextState == "A1":
>>           # (Do the work of Phase A1.)
>>           if<zap>:
>>         	   nextState = "A5"
>>       elif nextState == "A2":
>>            # (Do some work.)
>> 	 if zorp:
>> 	    nextState = "A4"
>> 	 else:
>> 	    nextState = "A3"
>>       elif nextState == "A3":
>>           # (Some more work.)
>> 	nextState = "A4"
>>       elif nextState == "A4":
>>           # (Do something.)
>> 	if ZZZ:
>> 	    nextState = "A1"
>> 	else:
>> 	    nextState = "A5"
>>       elif nextState == "A5":
>>           # (Something more).
>> 	if foobar:
>> 	    nextState = "A2"
>> 	else:
>> 	    continueLoop = 0
>>       else:
>>           error("Impossible -- I quit!\n")
>
> Oh, my, I can't even begin to get my head around all the nested
> conditionals.  And that for a nearly trivial machine with only 5 states.
> Down this path lies madness.  Keep in mind that Knuth wrote The Art of
> Computer Programming in the 1960s.  The algorithms may still be valid,
> but we've learned a lot about how to write readable programs since then.
> Most people today are walking around with phones that have far more
> compute power than the biggest supercomputers of Knuth's day.  We're no
> longer worried about bumming every cycle by writing in assembler.
>
> When I've done FSMs in Python, I've found the cleanest way is to make
> each state a function.  Do something like:
>
> def a1(input):
>     # (Do the work of Phase A1.)
>      if<zap>:
>          return a5  # goto state a5
>      else:
>          return a1  # stay in the same state
>
> # and so on for the other states.
>
> next_state = a1
> for input in whatever():
>     next_state = next_state(input)
>     if next_state is None:
>        break
>
> You can adjust that for your needs.  Sometimes I have the states return
> a (next_state, output) tuple.  You could use a distinguished done()
> state, or just use None for that.  I wrote the example above as global
> functions, but more commonly these would be methods of some StateMachine
> class.

Thank you, that is a very good idea to my opinion.

Antti "Andy"