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

From	Roy Smith <roy@panix.com>
Newsgroups	comp.lang.python
Subject	Re: Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct
Date	2012-03-17 11:47 -0400
Organization	PANIX Public Access Internet and UNIX, NYC
Message-ID	<roy-84F9E6.11475517032012@news.panix.com> (permalink)
References	<gR09r.22645$I33.16090@uutiset.elisa.fi>

Show all headers | View raw

In article <gR09r.22645$I33.16090@uutiset.elisa.fi>,
 Antti J Ylikoski <antti.ylikoski@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.

Thread

csiph-web