Groups > comp.lang.python > #21814 > unrolled thread

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

Started by	Antti J Ylikoski <antti.ylikoski@tkk.fi>
First post	2012-03-17 16:03 +0200
Last post	2012-03-18 11:08 +0000
Articles	18 — 10 participants

Back to article view | Back to comp.lang.python

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

From	Antti J Ylikoski <antti.ylikoski@tkk.fi>
Date	2012-03-17 16:03 +0200
Subject	Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct
Message-ID	<gR09r.22645$I33.16090@uutiset.elisa.fi>

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

[toc] | [next] | [standalone]

#21815

From	Mel Wilson <mwilson@the-wire.com>
Date	2012-03-17 10:39 -0400
Message-ID	<jk27n8$ec0$1@speranza.aioe.org>
In reply to	#21814

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.

[toc] | [prev] | [next] | [standalone]

#21816

From	Kiuhnm <kiuhnm03.4t.yahoo.it>
Date	2012-03-17 15:45 +0100
Message-ID	<4f64a3a0$0$1386$4fafbaef@reader2.news.tin.it>
In reply to	#21814

On 3/17/2012 15: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.
>
>
>
> 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.

A1 and A5 are NOT states: they're labels.
There is no garanteed bijection from labels to states.

> So one very clear way to program Knuth with Python is the following
> kind of a construct.
[...]

Your way is easy, but the result is poor.
Your should try to rewrite it. Decompilers do exactly that.

Kiuhnm

[toc] | [prev] | [next] | [standalone]

#21817

From	Michael Torrie <torriem@gmail.com>
Date	2012-03-17 09:01 -0600
Message-ID	<mailman.758.1331996530.3037.python-list@python.org>
In reply to	#21816

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.

[toc] | [prev] | [next] | [standalone]

#21818

From	Kiuhnm <kiuhnm03.4t.yahoo.it>
Date	2012-03-17 16:12 +0100
Message-ID	<4f64a9e5$0$1385$4fafbaef@reader2.news.tin.it>
In reply to	#21817

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.

>> Your should try to rewrite it.
>> Decompilers do exactly that.
>
> Decompilers rewrite code for people?  That's really neat.

No, they try to rewrite code that contains jmps in order to remove them.
If one jmp is too difficult to remove, one should use a flag or 
something similar.

Kiuhnm

[toc] | [prev] | [next] | [standalone]

#21820

From	Michael Torrie <torriem@gmail.com>
Date	2012-03-17 09:53 -0600
Message-ID	<mailman.759.1331999612.3037.python-list@python.org>
In reply to	#21818

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.

[toc] | [prev] | [next] | [standalone]

#21826

From	Kiuhnm <kiuhnm03.4t.yahoo.it>
Date	2012-03-17 18:55 +0100
Message-ID	<4f64d00a$0$1390$4fafbaef@reader1.news.tin.it>
In reply to	#21820

On 3/17/2012 16:53, Michael Torrie wrote:
> 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.

Why should I write a treatise on decompilation techniques on this ng?

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

That looks like a glaring contradiction to me...
I'm sure the interested reader will think of some ways of getting additional information on the subject.

Here's an example of rewriting:

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. 

==>

A1. (Do the work of Phase A1.)
If not <zap>:
    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. 

==>

A1. (Do the work of Phase A1.)
If not <zap>:
    A2. (Do some work.)
    If not <zorp>:
        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. 

==>

while (True):
    A1. (Do the work of Phase A1.)
    If not <zap>:
        A2. (Do some work.)
        If not <zorp>:
            A3. (Some more work.)
        A4. (Do something.)
        If not <condition ZZZ>:
            break
A5. (Something more).  If <foobar> then go to Phase A2

==>

while (True):
    A1. (Do the work of Phase A1.)
    If not <zap>:
        A2. (Do some work.)
        If not <zorp>:
            A3. (Some more work.)
        A4. (Do something.)
        If not <condition ZZZ>:
            A5. (Something more).
            If <foobar> then go to Phase A2
            break

==>

again = TRUE
while (again):
    A1. (Do the work of Phase A1.)
    If not <zap>:
        while (True):
            A2. (Do some work.)
            If not <zorp>:
                A3. (Some more work.)
            A4. (Do something.)
            If not <condition ZZZ>:
                A5. (Something more).
                If <foobar>:
                    continue
                again = FALSE; break

==>

def f:
    while (True):
        A1. (Do the work of Phase A1.)
        If not <zap>:
            while (True):
                A2. (Do some work.)
                If not <zorp>:
                    A3. (Some more work.)
                A4. (Do something.)
                If not <condition ZZZ>:
                    A5. (Something more).
                    If <foobar>:
                        continue
                    return

==>

def f:
    while (True):
        A1. (Do the work of Phase A1.)
        If <zap>:
            continue
        while (True):
            A2. (Do some work.)
            If not <zorp>:
                A3. (Some more work.)
            A4. (Do something.)
            If not <condition ZZZ>:
                A5. (Something more).
                If <foobar>:
                    continue
                return

==>

def f:
    while (True):
        A1. (Do the work of Phase A1.)
        If <zap>:
            continue
        while (True):
            A2. (Do some work.)
            If not <zorp>:
                A3. (Some more work.)
            A4. (Do something.)
            If <condition ZZZ>:
                continue
            A5. (Something more).
            If <foobar>:
                continue
            return

==>

def f:
    while (True):
        A1. (Do the work of Phase A1.)
        If <zap>:
            continue
        while (True):
            A2. (Do some work.)
            If not <zorp>:
                A3. (Some more work.)
            A4. (Do something.)
            If <condition ZZZ>:
                continue
            A5. (Something more).
            If not <foobar>:
                return

Etc... until you're satisfied with the result.

If the code is more complex, divide et impera.

Kiuhnm

[toc] | [prev] | [next] | [standalone]

#21838

From	Michael Torrie <torriem@gmail.com>
Date	2012-03-17 17:28 -0600
Message-ID	<mailman.768.1332026927.3037.python-list@python.org>
In reply to	#21826

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>

Thank you.  Your example makes more clear your assertion about "labels"
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.

[toc] | [prev] | [next] | [standalone]

#21846

From	Steven D'Aprano <steve+comp.lang.python@pearwood.info>
Date	2012-03-18 01:54 +0000
Message-ID	<4f654042$0$29981$c3e8da3$5496439d@news.astraweb.com>
In reply to	#21838

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

> Thank you.  Your example makes more clear your assertion about "labels"
> 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

[toc] | [prev] | [next] | [standalone]

#21854

From	Albert van der Horst <albert@spenarnc.xs4all.nl>
Date	2012-03-18 11:03 +0000
Message-ID	<m12uq7.oav@spenarnc.xs4all.nl>
In reply to	#21846

In article <4f654042$0$29981$c3e8da3$5496439d@news.astraweb.com>,
Steven D'Aprano  <steve+comp.lang.python@pearwood.info> wrote:
>On Sat, 17 Mar 2012 17:28:38 -0600, Michael Torrie wrote:
>
>> Thank you.  Your example makes more clear your assertion about "labels"
>> 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.

This is the idea of the original (not universal, hard coded) Turing
machine with cards. Of course you then still need the infinite tape
to store calculation input and output.

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

I hope the reference to the Turing machine makes this clearer.
Turing Machines and Finite State Machines are different constructions
in automaton theory.

Remember those definitions are like

A Turing machine is a set <S, T, F, G, Q >

        S the set of symbols <blank, 0, 1>
        T a mapping of S onto IZ (natural numbers)
        ...
        F is a mapping from SxT into G
        ..

Some such.

(A FSM is just different <A,B,C..Z> with different mappings )

The memory of the Turing machine is T , the tape, time dependant.
The program of the Turing is e.g. F, to be thought of as hard wiring.

A Turing machine is *not* a stored program computer!
The universal Turing machine is, it contains a hardwired program
to execute a stored program on the tape.

>
>--
>Steven

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#21870

From	Kiuhnm <kiuhnm03.4t.yahoo.it>
Date	2012-03-19 02:02 +0100
Message-ID	<4f6685a2$0$1389$4fafbaef@reader2.news.tin.it>
In reply to	#21838

On 3/18/2012 0:28, Michael Torrie wrote:
> 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.

Many ASM languages don't have structured control flow statements but 
only jmps, which are roughly equivalent to gotos. A good decompiler will 
need to analize the net of jmps and try to rewrite the code using 
structured control flow statements.
The idea is to maximize readability, of course.

>> Here's an example of rewriting:
>> <snip>
>
> Thank you.  Your example makes more clear your assertion about "labels"
> 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.

What I don't like about the entire issue is that (pseudo-)code shouldn't 
be cut and pasted or blindly ported to another language.
Python is a very expressive language. I don't think you like it when 
someone writes C code in Python. Now we're writing ASM code in Python!
If you want to emulate a DFA, do it, but if you want to implement an 
algorithm whose pseudo-code happens to use labels and gotos, please use 
higher-level control flow statements (unless you're pressed on time and 
you need it done yesterday, of course).

Regarding labels and state, I simply meant that they're completely 
different things, in fact this program has two labels but infinitely 
many states:
A1:  cur = cur + 1
A2:  goto A1
I was being pedantic, to say it your way ;)

Kiuhnm

[toc] | [prev] | [next] | [standalone]

#21876

From	Dennis Lee Bieber <wlfraed@ix.netcom.com>
Date	2012-03-19 01:02 -0400
Message-ID	<mailman.796.1332133377.3037.python-list@python.org>
In reply to	#21870

On Mon, 19 Mar 2012 02:02:23 +0100, Kiuhnm
<kiuhnm03.4t.yahoo.it@mail.python.org> declaimed the following in
gmane.comp.python.general:

> 
> Many ASM languages don't have structured control flow statements but 
> only jmps, which are roughly equivalent to gotos. A good decompiler will 
> need to analize the net of jmps and try to rewrite the code using 
> structured control flow statements.
> The idea is to maximize readability, of course.
>
	Never met Sigma's Meta-Symbol <G>

	Okay, the machine level code was limited to basic condition/jump...
But a master of Meta-Symbol (I wasn't such -- not in a trimester college
course) could create macros that would make it structured. 

	In a way, Meta-Symbol wasn't an assembly language so much as a
language for defining assembly languages (I once wasted a few hours at
work writing out the Meta-Symbol definition file needed to produce
absolute-address 8080 output. Even the native Sigma instruction set had
to be loaded into Meta-Symbol before it could process a file).

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#21885

From	Kiuhnm <kiuhnm03.4t.yahoo.it>
Date	2012-03-19 11:24 +0100
Message-ID	<4f670968$0$1379$4fafbaef@reader2.news.tin.it>
In reply to	#21876

On 3/19/2012 6:02, Dennis Lee Bieber wrote:
> On Mon, 19 Mar 2012 02:02:23 +0100, Kiuhnm
> <kiuhnm03.4t.yahoo.it@mail.python.org>  declaimed the following in
> gmane.comp.python.general:
>
>>
>> Many ASM languages don't have structured control flow statements but
>> only jmps, which are roughly equivalent to gotos. A good decompiler will
>> need to analize the net of jmps and try to rewrite the code using
>> structured control flow statements.
>> The idea is to maximize readability, of course.
>>
> 	Never met Sigma's Meta-Symbol<G>
>
> 	Okay, the machine level code was limited to basic condition/jump...
> But a master of Meta-Symbol (I wasn't such -- not in a trimester college
> course) could create macros that would make it structured.

You can do that in MASM (and others) as well.

Kiuhnm

[toc] | [prev] | [next] | [standalone]

#21819

From	Roy Smith <roy@panix.com>
Date	2012-03-17 11:47 -0400
Message-ID	<roy-84F9E6.11475517032012@news.panix.com>
In reply to	#21814

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.

[toc] | [prev] | [next] | [standalone]

#21821

From	Antti J Ylikoski <antti.ylikoski@tkk.fi>
Date	2012-03-17 18:31 +0200
Message-ID	<e%29r.22687$I33.5204@uutiset.elisa.fi>
In reply to	#21819

On 17.3.2012 17:47, Roy Smith wrote:
> 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.

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

Antti "Andy"

[toc] | [prev] | [next] | [standalone]

#21829

From	John Nagle <nagle@animats.com>
Date	2012-03-17 11:44 -0700
Message-ID	<4f64db92$0$12041$742ec2ed@news.sonic.net>
In reply to	#21821

On 3/17/2012 9:31 AM, Antti J Ylikoski wrote:
> On 17.3.2012 17:47, Roy Smith wrote:
>> 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.
>> 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

[toc] | [prev] | [next] | [standalone]

#21849

From	Evan Driscoll <driscoll@cs.wisc.edu>
Date	2012-03-17 21:59 -0500
Message-ID	<mailman.773.1332040943.3037.python-list@python.org>
In reply to	#21814

[Multipart message — attachments visible in raw view] — view raw

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

[toc] | [prev] | [next] | [standalone]

#21855

From	Albert van der Horst <albert@spenarnc.xs4all.nl>
Date	2012-03-18 11:08 +0000
Message-ID	<m12uyz.od0@spenarnc.xs4all.nl>
In reply to	#21814

In article <gR09r.22645$I33.16090@uutiset.elisa.fi>,
Antti J Ylikoski  <antti.ylikoski@tkk.fi> 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 can rewrite this into Python in my sleep, without resorting
to formal techniques.
Instead try one of the harder algorithms like T (Toom Cook)
that must be translated to recursive functions that pass
data down. That took me quite a wile.

The correct answer is, it is just labour. Deal with it.
Note that if you want to translate it to assembler, it is
relatively easy.

<SNIP>

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

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [standalone]

csiph-web

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

Contents

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

#21815

#21816

#21817

#21818

#21820

#21826

#21838

#21846

#21854

#21870

#21876

#21885

#21819

#21821

#21829

#21849

#21855