Working around a lack of 'goto' in python

B

Brett

Two areas where I've found 'goto' two be useful in other languages are in
(untested examples in C++)

(1) deeply nested loops

for (k=0; k < 10; ++k)
for (j=0; j < 10; ++j)
for (i=0; i <10; ++i)
if (/* some test */) goto END;

END: /* continue */;

and (2) repeating a while or for loop from the beginning:

BEGIN:
for (n=0; n < 20; ++n)
if (/* some test */) goto BEGIN;

What are the techniques in python for simulating these algorithms without a
'goto' command?

Thanks.
 
A

Andrew Koenig

What are the techniques in python for simulating these algorithms without
a
'goto' command?

How about showing us an actual piece of code in which you consider the lack
of a 'goto' to be a significant inconvenience?
 
C

Carmine Noviello

(1) deeply nested loops
for (k=0; k < 10; ++k)
for (j=0; j < 10; ++j)
for (i=0; i <10; ++i)
if (/* some test */) goto END;

done = 0
while k < 10 and not done:
k += 1
while j < 10 and not done:
j+=1
while i < 10 and not done:
i+=1
if /*some test*/: done = 1

and (2) repeating a while or for loop from the beginning:

BEGIN:
for (n=0; n < 20; ++n)
if (/* some test */) goto BEGIN;

while n < 20:
if /*some test*/: n = 0

There is always a way to not use "goto".
 
J

Jeff Schwaber

Two areas where I've found 'goto' two be useful in other languages are in
(untested examples in C++)

(1) deeply nested loops

for (k=0; k < 10; ++k)
for (j=0; j < 10; ++j)
for (i=0; i <10; ++i)
if (/* some test */) goto END;

END: /* continue */;

try:
for k in range(10):
for j in range(10):
for i in range(10):
if "some test": raise Exception("test")
except:
pass


and (2) repeating a while or for loop from the beginning:

BEGIN:
for (n=0; n < 20; ++n)
if (/* some test */) goto BEGIN;

for n in range(20):
if "some test": continue

Jeff
 
P

Peter Otten

Brett said:
Two areas where I've found 'goto' two be useful in other languages are in
(untested examples in C++)

(1) deeply nested loops

class BeamMeUpScotty(Exception):
pass

try:
for i in range(10):
for k in range(10):
for n in range(10):
if i == k == n == 2:
raise BeamMeUpScotty
except BeamMeUpScotty:
pass

print (i, k, n)

Ok, I'm only kidding, here's the real thing:

def beamMeUp():
for i in range(10):
for k in range(10):
for n in range(10):
if i == k == n == 2:
return i, k, n

print beamMeUp()
and (2) repeating a while or for loop from the beginning:

BEGIN:
for (n=0; n < 20; ++n)
if (/* some test */) goto BEGIN;

while 1:
for i in range(10):
print i,
if i == 5 and raw_input("restart?") != "no":
break
else:
break


Can't remember having done that in my code, though. If the need arises I'd
probably go with the function approach again. To me goto seems much like a
speed hack that is fine in, say, the kernel code, but by no means in a
scripting language.

Peter
 
C

Christian Tismer

Rene said:
Brett:



While we're on the subject, is there any way to simulate the 'comefrom'
statement?

Sure. If you grab old Stackless python 1.0 with Python 2.0,
you have first class continuations, and you can make your
code come from wherever you want :)

It *is* possible, but this was no serious proposal. - chris

--
Christian Tismer :^) <mailto:[email protected]>
Mission Impossible 5oftware : Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/
14109 Berlin : PGP key -> http://wwwkeys.pgp.net/
work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776
PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04
whom do you want to sponsor today? http://www.stackless.com/
 
R

Roy Smith

"Brett said:
Two areas where I've found 'goto' two be useful in other languages are in
(untested examples in C++)

Working around the lack of "goto" in a language is kind of like trying
to figure out how to swim without a piano strapped to your back. There
are lots of ways to do it, and even the worst of them is better than the
alternative.
(1) deeply nested loops

for (k=0; k < 10; ++k)
for (j=0; j < 10; ++j)
for (i=0; i <10; ++i)
if (/* some test */) goto END;

END: /* continue */;

I've found two general solutions to the breaking out of a deeply nested
loop. One possibility is to factor the loop out into its own function,
and break out of it with a return:

def findTheHiddenThing ():
for k in range (10):
for j in range (10):
for i in range (10):
if f (i, j, k) == theThingWeWant:
return

Another is to use an exception:

try:
for k in range (10):
for j in range (10):
for i in range (10):
if f (i, j, k) == theThingWeWant:
raise WeFoundIt ("in the last place we looked")
except WeFoundIt:
whatever

Neither of these ideas are particularly Python specific. The first
method works in pretty much any procedural language. The second only
works in languages that support exceptions (in some languages, exception
processing is fairly expensive, so it may not be universally acceptable).

Assuming both methods are equally feasable in your environment, the
choice of which to use may be driven by style, or one may just be a
better fit to your problem domain.

On the other hand, if you're doing linear searches of multi-dimensional
coordinate spaces, that may be a hint that you need to rethink how
you're solving the problem. A different data structure may not only
eliminate the deeply nested loop, but could well be significantly faster
to execute.
and (2) repeating a while or for loop from the beginning:

BEGIN:
for (n=0; n < 20; ++n)
if (/* some test */) goto BEGIN;

I'm going to go out on a limb on this one and say that if you need to
begin a loop from the beginning again, something is probably wrong with
how you're trying to solve the problem. What you've really written is a
nested while/for loop. In C, it should look something like this:

while (1)
for (n = 0; n < 20; ++n)
if (some test)
break

and now you're back to the same sort of "breaking out of a nested loop"
issue like you had above, with the same likely solutions.
 
D

Dan Bishop

Brett said:
Two areas where I've found 'goto' two be useful in other languages are in
(untested examples in C++)

(1) deeply nested loops

for (k=0; k < 10; ++k)
for (j=0; j < 10; ++j)
for (i=0; i <10; ++i)
if (/* some test */) goto END;

END: /* continue */;

# One way is to fake GOTO using try-except

class END(Exception):
pass

try:
for k in xrange(10):
for j in xrange(10):
for i in xrange(10):
if some_test():
raise END()
except END:
pass

# Another is to put the nested loops inside a function

def nested_loops():
for k in xrange(10):
for j in xrange(10):
for i in xrange(10):
if some_test():
return
and (2) repeating a while or for loop from the beginning:

BEGIN:
for (n=0; n < 20; ++n)
if (/* some test */) goto BEGIN;

n = 0
while n < 20:
if some_test():
n = 0
continue
n += 1
 
D

David M. Cooke

Brett said:
Two areas where I've found 'goto' two be useful in other languages are in
(untested examples in C++)

(1) deeply nested loops

for (k=0; k < 10; ++k)
for (j=0; j < 10; ++j)
for (i=0; i <10; ++i)
if (/* some test */) goto END;

END: /* continue */;

If you're not doing anything between the loops, I like to use a
generator:

def iindices(klimit, jlimit, ilimit):
for k in xrange(klimit):
for j in xrange(jlimit):
for i in xrange(ilimit):
yield k, j, i

for k, j, i in iindices(klimit, jlimit, ilimit):
if test_fails(k, j, i):
break
 
S

Stephen Horne

Two areas where I've found 'goto' two be useful in other languages are in
(untested examples in C++)

(1) deeply nested loops

for (k=0; k < 10; ++k)
for (j=0; j < 10; ++j)
for (i=0; i <10; ++i)
if (/* some test */) goto END;

END: /* continue */;

and (2) repeating a while or for loop from the beginning:

BEGIN:
for (n=0; n < 20; ++n)
if (/* some test */) goto BEGIN;

What are the techniques in python for simulating these algorithms without a
'goto' command?

I've been using C++ quite a while and never needed either of those
patterns. I have used a goto in C++ not too long ago, but not for
anything close to your examples, and its my first time in any language
for at least 10 years.

The reason for it was what I call a 'short running state machine' - a
state machine which needs to run to completion when invoked. I could
have used a loop with an embedded switch statement, but that just
didn't fit what was happening and would have made the code less
readable and maintainable - a goto is the natural representation of a
transition between states.

Once in ten years of doing a lot of programming. I don't think many
people need to worry about this use case ;-)

The normal reason for needing to exit deep loops (or any deep set of
structures), and a common reason for using goto in C, is due to an
error condition. In that case, throw an exception. This is a much
better way to handle errors as the code that throws the exception
doesn't need to know how (or if) the exception will be handled.

The only other common case where I've seen C's goto considered a good
thing is in search algorithms. The easy exit from the (probably
nested) loops can be useful. But when doing searches I tend to regard
success as the exceptional case and throw an exception for it, though
I don't think I've used the technique in Python to date.


If you have a use case for the loop restarting, I'd like to see it.
With a use case it is much easier to provide an alternative, and there
isn't any that strikes me as obvious as it stands.
 
R

Roy Smith

Stephen Horne said:
a goto is the natural representation of a transition between states.

Except that a goto allows the code for a state to be fallen into from
the top.

The best way I know to implement a state machine in Python is one
function for each state, and have each function return the next state,
or perhaps an (output, nextState) tuple. Your main loop then becomes
something like:

state = start
while state != end:
nextState, output = state (input)
print output
state = nextState

I would use a similar strategy in a language like C or C++ which allowed
you to pass function pointers around.

I've implemented state machines in Perl with a huge multi-way
if/elif/elif/else statement. It's pretty ugly, but it beats gotos.
 
S

Stephen Horne

Except that a goto allows the code for a state to be fallen into from
the top.

How is this different to the more typical switch-within-loop method?
Or have you never forgotten to include a 'break'? ;-)
The best way I know to implement a state machine in Python is one
function for each state, and have each function return the next state,
or perhaps an (output, nextState) tuple. Your main loop then becomes
something like:

state = start
while state != end:
nextState, output = state (input)
print output
state = nextState

I've done similar in C++. In some extreme cases, I have used a class
heirarchy with a class for each state, using a virtual method to get
essentially the same effect. Having different members depending on the
state can be useful at times, though of course there is a price to
pay.

The same can of course be done in Python, and probably without all the
classes because of the dynamic nature of Python objects.

The point with my 'short running' example, though, is that it didn't
have input as such to worry about. Everything it needed to work on was
available at the time it was invoked. If it had needed to wait for
input sometimes I'd have needed a way to resume from a given state
anyway, implying the switch-for-the-state method or whatever.

Using functions or objects for the states would have meant making a
bunch of local variables accessible by those functions/objects, and
would have meant taking the states code out of context. Often this
would be a good thing, but not in this case - keeping the code in
context makes it much clearer.

The other consideration was that this was an inner loop in a function
that needed to run quickly. Adding function call overheads (especially
with lots of parameters) wasn't an option.
I've implemented state machines in Perl with a huge multi-way
if/elif/elif/else statement. It's pretty ugly, but it beats gotos.

If you say so. But in reality, but returning a function pointer to a
function that is immediately going to call that function pointer,
you're basically just faking the effect of a goto anyway.

Implementing a state machine using gotos (in those extremely rare
cases where it is an option) does not damage readability or
maintainability. Implementing a transition as 'return statefn;' or as
'statevar = stateid;' is really no different than implementing it as
'goto statelabel;'. All are a potential cause of spaghetti code if
abused, because all are just means of branching to a different piece
of code - its just that the goto does exactly what it says, while the
other methods achieve it indirectly. In fact its basically a special
case of the state variable method, using the processors IP as the
state variable.

That said, I did try to avoid using gotos anyway - using a goto is
basically begging to be harassed. I didn't use the loop-and-switch
method, but instead tried to pretent it wasn't really a state machine
by using a birdsnest of loops and conditionals. Never let anyone tell
you that structured code is inherently clean and simple - there's
always a special case where it all goes horribly wrong.

After three fatally buggy attempts using structured code, which I
realised I couldn't understand and thus couldn't debug, I gave up and
used gotos. The result worked first time, and other people have also
been able to understand it easily.
 
R

Roy Smith

Stephen Horne said:
How is this different to the more typical switch-within-loop method?

Not much. The C switch statement isn't much better than a goto, for
just that reason :)
returning a function pointer to a
function that is immediately going to call that function pointer,
you're basically just faking the effect of a goto anyway.

In some respects, you're right. Certainly, both ways get you the same
pseudo-random flow of control, but that's inherent in a state machine.
What the function-per-state approach gets you is modularity. Each
function at least has its own namespace and set of local variables.

To tie this in with the current thread on unit testing, it's also a lot
easier to test a bunch of little functions than a collection of gotos.
You said:
In fact its basically a special case of the state variable method,
using the processors IP as the state variable.

That's a very good observation. Imagine you implemented your state
machine with gotos. To test each transition, you need to get the
machine into the right state before each test by feeding it a sequence
of inputs which navigates your state graph in the right way. That's
complicated and error prone to design (the last thing you want is an
error-prone test procedure). If there were many states and edges, it
would be very slow. If the state machine is non-deterministic (timing
dependencies, perhaps), it would be impossible.

Of course, this is all assuming that the logic implemented in each state
is different enough to require writing individual functions. Some state
machines (like those that execute compiled regular expressions) are
simple enough to be table driven. With a tabular approach, you get the
same testability you do with the functional approach; you can set the
machine to any random state, apply a single input, and see what happens.
You can't do that with gotos because the state is stored in a place
that's not exposed at the language level (unless you're writing in
assembler).
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,834
Latest member
BuyCannaLabsCBD

Latest Threads

Top