Re: 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.16...@uutiset.elisa.fi>,
  Antti J Ylikoski<antti.yliko...@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"

--
http://mail.python.org/mailman/listinfo/python-list