Velocity Reviews > Programming D. E. Knuth in Python with the Deterministic Finite Automatonconstruct

# Programming D. E. Knuth in Python with the Deterministic Finite Automatonconstruct

Antti J Ylikoski
Guest
Posts: n/a

 03-17-2012

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.

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")

Following is a working Python function which iteratively calculates
the lexicographically ordered permutations of integers [1, 2, 3, 4,
...., n], where n is an arbitary integer. The function was written
after D. E. Knuth with the abovementioned DFA construct.

def iterAllPerm(n):

# iteratively generate all permutations of n integers 1-n
# After Donald Knuth, The Art of Computer Programming, Vol4,
# Fascicle 2,
# ISBN 0-201-85393-0. See pp. 39--40.

listofPerm = [] # list of lists to collect permutations
continueLoop = 1 # indicates whether to continue the iteration
nextStat = "L1" # next phase in Knuth's text
a = list(range(0, n+1)) # [0, 1, 2, 3, 4, ..., n] -- see Knuth

while continueLoop:
if nextStat == "L1":
app = listofPerm.append(a[1:n+1])
nextStat = "L2"
continueLoop = 1
elif nextStat == "L2":
j = n - 1
while a[j] >= a[j+1]:
j -= 1
if j == 0:
continueLoop = 0
nextStat = "Finis Algorithm"
else:
continueLoop = 1
nextStat = "L3"
elif nextStat == "L3":
l = n
while a[j] >= a[l]:
l -= 1
temp = a[j]
a[j] = a[l]
a[l] = temp
nextStat = "L4"
continueLoop = 1
elif nextStat == "L4":
k = j + 1
l = n
while k < l:
temp = a[k]
a[k] = a[l]
a[l] = temp
k += 1
l -= 1
nextStat = "L1"
continueLoop = 1
else:
continueLoop = 0
error("Impossible -- I quit!\n")

return(listofPerm)

kind regards, Antti J Ylikoski
Helsinki, Finland, the EU

Mel Wilson
Guest
Posts: n/a

 03-17-2012
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.

Michael Torrie
Guest
Posts: n/a

 03-17-2012
On 03/17/2012 08:45 AM, Kiuhnm wrote:
> Your way is easy, but the result is poor.

In what way? What is your recommended way?

> Your should try to rewrite it.
> Decompilers do exactly that.

Decompilers rewrite code for people? That's really neat.

Roy Smith
Guest
Posts: n/a

 03-17-2012
In article <gR09r.22645\$(E-Mail Removed)>,
Antti J Ylikoski <(E-Mail Removed)> 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.

Michael Torrie
Guest
Posts: n/a

 03-17-2012
On 03/17/2012 09:12 AM, Kiuhnm wrote:
> On 3/17/2012 16:01, Michael Torrie wrote:
>> On 03/17/2012 08:45 AM, Kiuhnm wrote:
>>> Your way is easy, but the result is poor.

>>
>> In what way?

>
> The resulting code is inefficient, difficult to comprehend and to mantain.
>
>> What is your recommended way?

>
> One should rewrite the code. There is a reason why Python doesn't have
> gotos.

We appear to have a language barrier here. How should one rewrite the
code? Everyone knows python doesn't have gotos and state machines have
to be created using other mechanisms like loops, state variables, and
such. Your suggestion to "rewrite the code" is unhelpful to the OP if
you're not willing to suggest the best method for doing so. Saying, "be
like a decompiler" doesn't say anything.

Antti J Ylikoski
Guest
Posts: n/a

 03-17-2012
On 17.3.2012 17:47, Roy Smith wrote:
> In article<gR09r.22645\$(E-Mail Removed)>,
> Antti J Ylikoski<(E-Mail Removed)> 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"

John Nagle
Guest
Posts: n/a

 03-17-2012
On 3/17/2012 9:31 AM, Antti J Ylikoski wrote:
> On 17.3.2012 17:47, Roy Smith wrote:
>> In article<gR09r.22645\$(E-Mail Removed)>,
>> Antti J Ylikoski<(E-Mail Removed)> 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.

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

Right. Few programs should be written as state machines.
As a means of rewriting Knuth's algorithms, it's inappropriate.

Some should. LALR(1) parsers, such as what YACC and Bison
generate, are state machines. They're huge collections of nested
switch statements.

Python doesn't have a "switch" or "case" statement. Which is
surprising, for a language that loves dictionary lookups.
You can create a dict full of function names and lambdas, but
it's clunky looking.

John Nagle

Michael Torrie
Guest
Posts: n/a

 03-17-2012
On 03/17/2012 11:55 AM, Kiuhnm wrote:
> Why should I write a treatise on decompilation techniques on this ng?

You were the one that said simply, you're doing it wrong followed by a
terse statement, do it like a decompiler. I am familiar with how one
might implement a decompiler, as well as a compiler (having written a
simple one in the past), but even now I don't see a connection between a
decompiler and the process of converting a knuth algorithm into a python
python implementation. I was hoping you would shed some light on that.
But alas, I'm not really as much of an "interested reader" as you would
like me to be.

>> Saying, "be like a decompiler" doesn't say anything.

> That looks like a glaring contradiction to me...

True, if you wish to be pedantic. I should have said, "meaningless," or
at least, "not a useful response."

> Here's an example of rewriting:
> <snip>

and how really A1 and A5 were the only real labels in the example.
Though I still do not really see why "states" is not a good equivalence
for labels in this case. As well, Roy's idea for doing the state
machines, which works equally well as the nested if statements, is more
pythonic, which is generally preferred in Python.

Steven D'Aprano
Guest
Posts: n/a

 03-18-2012
On Sat, 17 Mar 2012 17:28:38 -0600, Michael Torrie wrote:

> and how really A1 and A5 were the only real labels in the example.
> Though I still do not really see why "states" is not a good equivalence
> for labels in this case.

Program labels are states.

You can treat every line of code as being invisibly labelled with the
line number. (Or visibly, if you are using BASIC back in 1975.) Clearly
"the interpreter is executing at line 42" is a state distinct from "the
interpreter is executing line 23", but that state *alone* is not
sufficient to know the overall state of the program.

Adding an explicit GOTO label does not change this.

But this refers to the state of the interpreter, not the state of the
program being executed, and either way, is not a state in the sense of a
finite state machine.

--
Steven

Evan Driscoll
Guest
Posts: n/a

 03-18-2012
On 3/17/2012 9: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.
>
>
> 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.

Clearly you just need the goto module (http://entrian.com/goto/):

from goto import goto, label

label .A1
# do work of phase A1
if <zap>: goto .A5

label .A2
# do some work
if <zorp>: goto .A4

# do some more work

label .A4
# do something
if <condition zzz>: goto .A1

label .A5
# something more
if <foobar>: goto .A2

Clearly the best solution of all.

(Note: do not actually do this.)

Evan

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJPZU+ZAAoJEAOzoR8eZTzgx6YH/1r43y6XWZixjFMgw8w4KFrO
gQdYN1sB/sjfjkMnqf8QmN7GKAlXWe9QxuqqqIB1E7dqNrIYwLgbhM2KaQe 72huU
NSAlpSjbBeZNYnpZOYE0ITGQxKfpHV+b82FAGUYHMOoK4uJEpU QhmE5FBMW/+T82
3AF+mNSJddDbP/qEUv8x9BSjPuzl4NuC4Q1epnYJU7WQySvg4OM+UWDENaTEGTtq
VDYUDRRkbjHnZ0iSA9YLge44yehdHchAx+K6DKvnmwSHsD8Ozs y2z3gRbG2nd1Rq
0EBesNyYYlsJOUPJyec2BLw4AXGK9MfIbu38JHeS1lxPxuoMtB K++TlJuYkWGAk=
=Gb8C
-----END PGP SIGNATURE-----

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Juhani Ylikoski Python 2 11-13-2012 07:52 AM Antti J Ylikoski Python 6 04-16-2012 07:53 PM Lawrence D'Oliveiro NZ Computing 2 04-29-2008 11:16 AM Laura Creighton Python 0 02-05-2005 12:39 PM Noah Roberts C++ 4 09-28-2003 06:12 PM