Working around a lack of 'goto' in python

Discussion in 'Python' started by Brett, Mar 6, 2004.

  1. Brett

    Brett Guest

    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.
    Brett, Mar 6, 2004
    #1
    1. Advertising

  2. > 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?
    Andrew Koenig, Mar 6, 2004
    #2
    1. Advertising

  3. > (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".

    --
    Don't you know why your Python application has crashed?
    Take a look to http://www.pycrash.org
    My Home Page http://cnoviello.altervista.org
    Carmine Noviello, Mar 6, 2004
    #3
  4. On Sat, 2004-03-06 at 10:18, Brett wrote:
    > 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
    Jeff Schwaber, Mar 6, 2004
    #4
  5. Brett

    Peter Otten Guest

    Brett wrote:

    > 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
    Peter Otten, Mar 6, 2004
    #5
  6. Brett

    Rene Pijlman Guest

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


    While we're on the subject, is there any way to simulate the 'comefrom'
    statement?
    http://www.gre.ac.uk/~hj05/stuff/comefrom.htm

    --
    René Pijlman
    Rene Pijlman, Mar 6, 2004
    #6
  7. Rene Pijlman wrote:

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

    >
    >
    > 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:>
    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/
    Christian Tismer, Mar 6, 2004
    #7
  8. Brett

    Roy Smith Guest

    In article <UBo2c.26879$>,
    "Brett" <> wrote:

    > 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.
    Roy Smith, Mar 6, 2004
    #8
  9. Brett

    Dan Bishop Guest

    "Brett" <> wrote in message news:<UBo2c.26879$>...
    > 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

    > What are the techniques in python for simulating these algorithms without a
    > 'goto' command?
    Dan Bishop, Mar 6, 2004
    #9
  10. At some point, "Brett" <> wrote:

    > 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

    --
    |>|\/|<
    /--------------------------------------------------------------------------\
    |David M. Cooke
    |cookedm(at)physics(dot)mcmaster(dot)ca
    David M. Cooke, Mar 7, 2004
    #10
  11. On Sat, 06 Mar 2004 18:18:28 GMT, "Brett" <> wrote:

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


    --
    Steve Horne

    steve at ninereeds dot fsnet dot co dot uk
    Stephen Horne, Mar 7, 2004
    #11
  12. Brett

    Roy Smith Guest

    Stephen Horne <> wrote:

    > 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.
    Roy Smith, Mar 7, 2004
    #12
  13. On Sun, 07 Mar 2004 13:54:33 -0500, Roy Smith <> wrote:

    >Stephen Horne <> wrote:
    >
    >> 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.


    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.


    --
    Steve Horne

    steve at ninereeds dot fsnet dot co dot uk
    Stephen Horne, Mar 7, 2004
    #13
  14. Brett

    Roy Smith Guest

    Stephen Horne <> wrote:
    >> 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?


    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).
    Roy Smith, Mar 7, 2004
    #14
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mark 'Kamikaze' Hughes

    Re: does lack of type declarations make Python unsafe?

    Mark 'Kamikaze' Hughes, Jun 29, 2003, in forum: Python
    Replies:
    4
    Views:
    786
    Anton Vredegoor
    Jul 1, 2003
  2. Anton Vredegoor
    Replies:
    4
    Views:
    803
  3. Piet
    Replies:
    0
    Views:
    495
  4. ssylee

    getting around lack of bool type support

    ssylee, Dec 29, 2007, in forum: C Programming
    Replies:
    25
    Views:
    2,508
  5. Network/Software Buyer
    Replies:
    0
    Views:
    396
    Network/Software Buyer
    May 23, 2010
Loading...

Share This Page