fun with nested loops

Discussion in 'Python' started by Daniel, Aug 31, 2011.

  1. Daniel

    Daniel Guest

    Dear All,

    I have some complicated loops of the following form

    for c in configurations: # loop 1
    while nothing_bad_happened: # loop 2
    while step1_did_not_work: # loop 3
    for substeps in step1 # loop 4a
    # at this point, we may have to
    -leave loop 1
    -restart loop 4
    -skip a step in loop 4
    -continue on to loop 4b

    while step2_did_not_work: # loop 4b
    for substeps in step2:
    # at this point, we may have to
    -leave loop 1
    -restart loop 2
    -restart loop 4b
    ...
    ...many more loops...


    I don't see any way to reduce these nested loops logically, they
    describe pretty well what the software has to do.
    This is a data acquisition application, so on ever line there is
    a lot of IO that might fail or make subsequent steps useless or
    require a
    retry.

    Now every step could need to break out of any of the enclosing loops.
    So basically I have to transform every loop to be of the following
    horror:

    # general transformation of
    # "for c in configurations..."
    # to provide restart, break and continue
    # callable from any nesting level inside of the loop

    class loop1_restart(Exception): pass
    class loop1_break(Exception): pass
    class loop1_continue(Exception): pass

    while True:
    try:
    for c in configurations:
    while True:
    try:
    # inner loops go here, of course, they would have
    to get
    # all the boilerplate added, too
    while nothing_bad_happened:
    while step1_did_not_work:
    if cond1:
    raise loop1_restart()
    elif cond3:
    raise loop1_break()
    elif cond3:
    raise loop1_continue()

    break

    except loop1_continue:
    pass
    break
    except loop1_restart:
    pass
    except loop1_break:
    break

    Of course this is extremely tedious and error prone.
    If Python had named loops (PEP 3136, unfortunately rejected), this
    would be trivial:
    In Fortran I can continue (cycle), break (exit) and redo (goto label)
    arbitrary
    loops, which results in neat code:

    10 loop1: do I=1,3
    loop2: do J=1,4
    print *,I,J
    goto 10
    cycle loop1
    exit loop1
    enddo loop2
    enddo loop1


    My question is, how do I obtain something that implements the
    following logic:

    @named_loop(fred) # I wish this would be possible
    for i in range(10):
    for j in range(10):
    break fred # breaks out of outer loop
    continue fred # continues outer loop
    redo fred # resets outer loop and restarts with i=0


    The best solution would be something along the Proposal D - Explicit
    iterators
    in PEP 3136, in this case it would even be possible to peek at the
    next i or
    advance/reverse the iterator a few steps.

    Has anyone an idea on a nice way to write breaks/continues/redos for
    deeply
    nested loops?


    Dan
     
    Daniel, Aug 31, 2011
    #1
    1. Advertising

  2. Daniel

    aspineux Guest

    On Aug 31, 5:51 pm, Daniel <> wrote:
    > Dear All,
    >
    > I have some complicated loops of the following form
    >
    > for c in configurations: # loop 1
    >     while nothing_bad_happened: # loop 2
    >         while step1_did_not_work: # loop 3
    >             for substeps in step1 # loop 4a
    >                 # at this point, we may have to
    >                 -leave loop 1
    >                 -restart loop 4
    >                 -skip a step in loop 4
    >                 -continue on to loop 4b
    >
    >         while step2_did_not_work: # loop 4b
    >             for substeps in step2:
    >                 # at this point, we may have to
    >                 -leave loop 1
    >                 -restart loop 2
    >                 -restart loop 4b
    >                 ...
    >         ...many more loops...
    >
    > I don't see any way to reduce these nested loops logically, they
    > describe pretty well what the software has to do.
    > This is a data acquisition application, so on ever line there is
    > a lot of IO that might fail or make subsequent steps useless or
    > require a
    > retry.
    >
    > Now every step could need to break out of any of the enclosing loops.
    > So basically I have to transform every loop to be of the following
    > horror:
    >
    > # general transformation of
    > # "for c in configurations..."
    > # to provide restart, break and continue
    > # callable from any nesting level inside of the loop
    >
    > class loop1_restart(Exception): pass
    > class loop1_break(Exception): pass
    > class loop1_continue(Exception): pass
    >
    > while True:
    >     try:
    >         for c in configurations:
    >             while True:
    >                 try:
    >                     # inner loops go here, of course,they would have
    > to get
    >                     # all the boilerplate added, too
    >                     while nothing_bad_happened:
    >                         while step1_did_not_work:
    >                            if cond1:
    >                                raise loop1_restart()
    >                            elif cond3:
    >                                raise loop1_break()
    >                            elif cond3:
    >                                raise loop1_continue()
    >
    >                     break
    >
    >                 except loop1_continue:
    >                     pass
    >         break
    >     except loop1_restart:
    >         pass
    >     except loop1_break:
    >         break
    >
    > Of course this is extremely tedious and error prone.
    > If Python had named loops (PEP 3136, unfortunately rejected), this
    > would be trivial:
    > In Fortran I can continue (cycle), break (exit) and redo (goto label)
    > arbitrary
    > loops, which results in neat code:
    >
    > 10 loop1: do I=1,3
    >     loop2: do J=1,4
    >         print *,I,J
    >         goto 10
    >         cycle loop1
    >         exit loop1
    >     enddo loop2
    > enddo loop1
    >
    > My question is, how do I obtain something that implements the
    > following logic:
    >
    > @named_loop(fred) # I wish this would be possible
    > for i in range(10):
    >     for j in range(10):
    >         break fred # breaks out of outer loop
    >         continue fred # continues outer loop
    >         redo fred # resets outer loop and restarts with i=0
    >
    > The best solution would be something along the Proposal D - Explicit
    > iterators
    > in PEP 3136, in this case it would even be possible to peek at the
    > next i or
    > advance/reverse the iterator a few steps.
    >
    > Has anyone an idea on a nice way to write breaks/continues/redos for
    > deeply
    > nested loops?


    Hi Dan, it looks like you have already answered all your questions.

    one more idea, a kind of named loop:

    ic=0
    op='what to do'
    while ic<len(configurations):
    c=configuration[ic]

    if op=='restart':
    ic=0
    elif op=='next'
    ic+=1
    elif op=='terminate'
    ic=len(configurations)

    and at first explicit iterator was also a good idea, when you don't
    need to iter in reverse order

    When it become too complicate, I use state machine:
    http://en.wikipedia.org/wiki/Finite-state_machine


    Regards


    >
    > Dan
     
    aspineux, Aug 31, 2011
    #2
    1. Advertising

  3. On Thu, Sep 1, 2011 at 1:51 AM, Daniel <> wrote:
    >
    > Has anyone an idea on a nice way to write breaks/continues/redos for
    > deeply
    > nested loops?
    >


    Do you only ever have one top-level loop that you would be naming? If
    so, put that loop into a function and use return instead of break.
    Unfortunately that doesn't work for continue.

    ChrisA
     
    Chris Angelico, Aug 31, 2011
    #3
  4. Daniel

    Daniel Guest


    > one more idea, a kind of named loop:

    interesting idea, thanks.


    >
    > When it become too complicate, I use state machine:http://en.wikipedia.org/wiki/Finite-state_machine

    I unsuccessfully played a bit with a FSM, but there is a lot of data
    that is passed around between the states and a lot of counting (like
    trying a certain step n times), so the FSM turned out to be even more
    complex. And I have to keep the code simple for non CS people to run
    the actual experiment. The loops are kind of self-explanatory, this is
    exactly how you would specify the experiment, even though I am really
    hitting a wall at the moment.

    Maybe I am really missing an obvious solution, because breaking out of
    nested loops really doesn't seem like anything fancy. Fortran/c/c++/
    Ruby/Perl all have that facility, even Java has named loops.
     
    Daniel, Aug 31, 2011
    #4
  5. Daniel

    Daniel Guest


    > Do you only ever have one top-level loop that you would be naming? If

    no, unfortunately not. The rough structure is several loops deep, and
    I need to break/continue/restart many of them.
    Continue is used more than break, because most of the time that I find
    some strange value, I'd just _continue_ a few levels up
    to restart the current measurements.


    for some configurations
    while not enough data collected
    while not in the right state
    for steps in steps to bring the system to the right state
    if the system is bad, break out of all loops
    if it just need to be reset, just redo the steps
    if it is ok, go to the next while loop
    while in the right state
    steps to do some measurements
    ...
     
    Daniel, Aug 31, 2011
    #5
  6. On Thu, Sep 1, 2011 at 5:07 AM, Daniel <> wrote:
    >> Do you only ever have one top-level loop that you would be naming? If

    > no, unfortunately not. The rough structure is several loops deep, and
    > I need to break/continue/restart many of them.
    > Continue is used more than break, because most of the time that I find
    > some strange value, I'd just _continue_ a few levels up
    > to restart the current measurements.
    >


    Ah well, was worth a try. Raising exceptions smells wrong for this,
    but peppering your code with sentinel checks isn't much better. I
    don't really know what would be a good solution to this... except
    maybe this, which was proposed a few years ago and which I'd never
    heard of until Google showed it to me just now:
    http://entrian.com/goto/

    ChrisA
     
    Chris Angelico, Aug 31, 2011
    #6
  7. Daniel wrote:

    > And I have to keep the code simple for non CS people to run
    > the actual experiment.


    Do you think the software in the Apple iPod is "simple"? Or Microsoft
    Windows? No. You need to keep the *interface* simple. The internal details
    can be as complicated as they are needed to be.

    Same applies to your data acquisition application. Unless you expect these
    non-CS people to be hacking the source code, they only interact with the
    interface, not the internals.

    Earlier, back in your initial post, you said:

    "I don't see any way to reduce these nested loops logically, they
    describe pretty well what the software has to do.
    This is a data acquisition application, so on ever line there is
    a lot of IO that might fail or make subsequent steps useless or
    require a retry."

    Do you think you're the first person to have written a data acquisition
    application in Python? Almost certainly you can simplify the structure of
    the code by splitting it into functions appropriately, instead of the
    spaghetti code you have (apparently) written with jumps all over the place.
    To take the most obvious, simple example: any time you have a loop that you
    might want to redo, the right solution is to put the loop inside a
    function, and then "redo the loop" becomes "call the function again".

    I suppose that, just possibly, your application really would benefit from
    named labels to jump to. But if so, you've stumbled across something rarer
    than iridium.



    --
    Steven
     
    Steven D'Aprano, Sep 1, 2011
    #7
  8. Chris Angelico wrote:

    > Ah well, was worth a try. Raising exceptions smells wrong for this,
    > but peppering your code with sentinel checks isn't much better. I
    > don't really know what would be a good solution to this... except
    > maybe this, which was proposed a few years ago and which I'd never
    > heard of until Google showed it to me just now:
    > http://entrian.com/goto/


    You're a wicked, wicked man.

    :)


    --
    Steven
     
    Steven D'Aprano, Sep 1, 2011
    #8
  9. Steven D'Aprano wrote:

    [...]
    > Do you think you're the first person to have written a data acquisition
    > application in Python?


    Hmmm, on re-reading that it comes across as much harsher than it sounded in
    my head. Sorry about that Daniel.


    --
    Steven
     
    Steven D'Aprano, Sep 1, 2011
    #9
  10. Daniel

    Daniel Guest

    Hi Steve,

    Thanks for your comments, I appreciate any input.
    > Do you think the software in the Apple iPod is "simple"? Or Microsoft

    No, that's much more complicated that what I am doing.
    But the iPod probably (?) doesn't get new algorithms based on a
    specification discussed with non-programmers once a month.

    I didn't explain enough of what I am doing. This is a fairly complex
    application that has been running for a few years now,
    I am just trying to improve it. The code runs a big
    test machine, that runs >100000 individual tests in one run on
    something like semiconductor chips.

    The specification of these tests is already very complex, it has the
    form of the nested loops,
    for all these configurations try these steps, if they fail try them
    again n times, if it still doesn't work give up
    this configuration, if it works continue on to the next steps etc.
    That's the form the specification is in, and it makes sense and is
    very readable.
    In pseudocode it looks like this, I am using @ to give loops a name:

    @loop1
    for c in configurations:
    @loop2
    while not_done:
    @loop3
    while step1_did_not_work:
    @loop4
    for substeps in step1 # loop 4a
    if hopeless(): continue loop1 # run next configuration
    if substepsFailed(): restart loop4 # try again
    if substepsWorked(): break loop3 # go on to next
    steps, like loop4

    That format is fine, everyone involved can understand it, even the
    people in charge. I'd like to make this executable without
    changing too much of the form. It would be possible to do this as a
    FSM, but then you'd loose the line to line correspondence with the
    specification, and of course some errors always creep in.

    > non-CS people to be hacking the source code, they only interact with the

    This is a research setting, so the person running the machine will
    have to change the source from time to time if
    he gets a new specification. The specifications are far to complex to
    be entered into a user interface because of all the loops.

    > the code by splitting it into functions appropriately, instead of the
    > spaghetti code you have (apparently) written with jumps all over the place.

    I wouldn't call the example above spaghetti code in the sense of old
    Fortran or Basic full of gotos.
    In a language that can break out of nested loops this is highly
    structured code.
    I am not jumping forward to labels, not jumping into functions, not
    using jumps to replace loops etc.

    It is like the Fortran example (just to show the syntax, has an
    infinite loop), everyone can understand that right away, even
    non Fortran people:

    10 loop1: do I=1,3
    loop2: do J=1,4
    print *,I,J
    goto 10 ! redo loop1
    cycle loop1
    exit loop1
    enddo loop2
    enddo loop1

    There is no wild jumping her. The only problem is that Fortran does
    not allow to restart a loop, so instead of restart loop1 you have to
    do a goto 10. Otherwise you could do entirely without gotos (like in
    Ruby with the redo, which is of course much much better)

    > To take the most obvious, simple example: any time you have a loop that you
    > might want to redo, the right solution is to put the loop inside a
    > function, and then "redo the loop" becomes "call the function again".

    Doesn't work, because it can only redo one level, to break out of the
    next loop, I'd need exceptions anyway.
    And having all of these exceptions as gotos doesn't make it more
    readable.
    Replacing loop4 by a function makes it possible to replace the restart
    loop4 by a return, but then I still need an exception to
    continue loop1 and one to break out of loop4 to indicate that we can
    go on to the next step.

    > I suppose that, just possibly, your application really would benefit from
    > named labels to jump to. But if so, you've stumbled across something rarer
    > than iridium.


    Don't think so. I am doing that all of the time in other languages,
    and I am convinced the named loops (not raw labels+gotos, which are
    just a necessary evil) are beautiful and clean things.
    They have a lot of symmetry, break is always break, not sometimes
    break, sometimes return and sometimes raise breakSomeLoopExcept().
    Rewriting the simple Fortran example above in Python would be much,
    much uglier and more difficult to comprehend.
    You always call break and continue with a label, searching for that
    label will tell you right away which loop the break breaks.
    I am always doing that, even if there is only one loop. break and
    continue (without label) are IMO (please no flame war about that)
    worse than goto, at least the goto tells you where it goes, with break/
    continue you always have to scan the surroundings to find the right
    loop.

    I know I am not the only one who is trying to solve that problem, I
    was hoping someone has come up with a hack to solve it, like this goto
    Chis has come up with. I have to play with that a bit.



    Dan
     
    Daniel, Sep 1, 2011
    #10
  11. Am 01.09.2011 16:05 schrieb Daniel:

    > In pseudocode it looks like this, I am using @ to give loops a name:
    >
    > @loop1
    > for c in configurations:
    > @loop2
    > while not_done:
    > @loop3
    > while step1_did_not_work:
    > @loop4
    > for substeps in step1 # loop 4a
    > if hopeless(): continue loop1 # run next configuration
    > if substepsFailed(): restart loop4 # try again
    > if substepsWorked(): break loop3 # go on to next
    > steps, like loop4


    let me have a try:

    def loop(f):
    def wrapper(*a, **k):
    while True:
    try:
    ret = f(*a, **k):
    return ret
    except wrapper.restart:
    continue # next try
    except wrapper.stop:
    return None
    return ret
    wrapper.restart = type('restart', (Exception,), {})
    wrapper.stop = type('stop', (Exception,), {})
    return wrapper




    @loop
    def level1():
    for c in configurations:
    level2(c)

    @loop
    def level2():
    while not_done:
    level3()

    @loop
    def level3():
    while step1_did_not_work:
    level4()

    @loop
    def level4a():
    for substeps in step1
    if hopeless: raise level2.stop
    if substepsFailed: raise level4a.restart
    if substepsWorked: return ok


    I don't know if I have the levels right, but that should be a way which
    works, without too many indentations.

    Another approach could be a decorator which immediately runs the given
    functions, after adding the needed exception classes.


    Thomas
     
    Thomas Rachel, Sep 1, 2011
    #11
  12. Daniel

    Terry Reedy Guest

    On 9/1/2011 10:05 AM, Daniel wrote:

    You seems to be requesting one of the options in
    http://python.org/dev/peps/pep-3136/ Labeled break and continue
    (The 'Other languages' section omits Fortran.)

    The rejection post is at
    http://mail.python.org/pipermail/python-3000/2007-July/008663.html
    I basically agree with it.

    Your use case seems to be valid, extreme, and rare. You would probably
    use the proposed feature responsibly. But you are not everyone. I am not
    sure what Python-solution I would recommend. I might just stick with
    whatever you are doing that works for your group. However, I can also
    understand the desire to improve.

    --
    Terry Jan Reedy
     
    Terry Reedy, Sep 1, 2011
    #12
  13. Daniel

    Carl Banks Guest

    On Wednesday, August 31, 2011 8:51:45 AM UTC-7, Daniel wrote:
    > Dear All,
    >
    > I have some complicated loops of the following form
    >
    > for c in configurations: # loop 1
    > while nothing_bad_happened: # loop 2
    > while step1_did_not_work: # loop 3
    > for substeps in step1 # loop 4a
    > # at this point, we may have to
    > -leave loop 1
    > -restart loop 4
    > -skip a step in loop 4
    > -continue on to loop 4b
    >
    > while step2_did_not_work: # loop 4b
    > for substeps in step2:
    > # at this point, we may have to
    > -leave loop 1
    > -restart loop 2
    > -restart loop 4b
    > ...
    > ...many more loops...
    >
    >
    > I don't see any way to reduce these nested loops logically, they
    > describe pretty well what the software has to do.
    > This is a data acquisition application, so on ever line there is
    > a lot of IO that might fail or make subsequent steps useless or
    > require a
    > retry.
    >
    > Now every step could need to break out of any of the enclosing loops.



    I feel your pain. Every language, even Python, has cases where the trade-offs made in the language design make some legitimate task very difficult. In such cases I typically throw out the guidebook and make use of whatever shameless Perlesque thing it takes to keep things manageable.

    In your example you seem like you're trying to maintain some semblance of structure and good habit; I'd it's probably no longer worth it. Just store the level to break to in a variable, and after every loop check the variable and break if you need to break further. Something like this, for example:

    break_level = 99
    while loop1:
    while loop2:
    while loop3:
    if some_condition:
    break_level = (1, 2, or 3)
    break
    if break_level < 3: break
    break_level = 99
    if break_level < 2: break
    break_level = 99


    Carl Banks
     
    Carl Banks, Sep 1, 2011
    #13
  14. Daniel

    Daniel Guest

    I thought a bit about Carl's and Thomas' proposals, and it gave me an
    idea how this problem could be approached:
    Break is relatively easy to implement with a context manager that
    returns an iterable that throws an exception specific to that context
    manager:

    with named_loop(i for i in range(10)) as loop1:
    for i in loop1:
    with named_loop(i for i in range(10)) as loop2a:
    for j in loop2a:
    loop1._break() # this is easy
    loop1._continue() # this is difficult
    # if we _continue here, we need to do a continue right
    after the with loop2a:
    if loop1.cont: continue # context manager does not create new
    scope

    with named_loop(i for i in range(10)) as loop2b:
    for j in loop2b:
    loop1._break()

    this throws an exception that propagates through all the context
    managers till it hits the one that made loop1
    at that point the exception is caught.

    Now using the idea of break_levels, something like loop1._continue()
    should work.
    It is more difficult, because it should be caught in the last loop
    before the one that is targeted,
    loop1._continue throws an exception that is caught in loop2. Then
    loop1 just continues with the next value.

    I don't know how loop2 can learn that it is enclosed in loop1. Maybe
    loop1 could add itself to a global stack on enter
    and delete itself on exit, or maybe inspect could help?

    The big problem is that loop1._continue breaks out of loop2a, but then
    starts to execute loop2b, which we don't want.
    If loop1 is _continued inside of loop2a, a continue needs to directly
    follow the loop2a with block.

    An alternative would be to wrap each sequence of statements in another
    with statement, I think this is better:

    for i in loop1:
    with sequenced_stuff():
    with named_loop(i for i in range(10)) as loop2a:
    for j in loop2a:
    loop1._continue() # this is caught in
    sequenced_stuff()

    with named_loop(i for i in range(10)) as loop2b:
    for j in loop2b:
    loop1._break()


    Loops can even be restarted with a small modification:
    In a loop like "for i in loop1:" the __iter__ method of loop1 is
    called. If __iter__ returns a smart iterator that keeps a reference to
    loop1, then it can be restarted, advanced etc.
    loop1.restart() would throw an exception that __exits__ all the inner
    loops and gets caught in the loop just before loop1. Then it resets
    the iterable that the iterator returned by __iter__ links to, i.e.
    loop1 restarts.
    Nice side benefit: loops can have a method peek(n) to look ahead.

    Thanks for all your input,

    Dan
     
    Daniel, Sep 2, 2011
    #14
  15. Daniel wrote:

    > That's the form the specification is in, and it makes sense and is
    > very readable.
    > In pseudocode it looks like this, I am using @ to give loops a name:
    >
    > @loop1
    > for c in configurations:
    > @loop2
    > while not_done:
    > @loop3
    > while step1_did_not_work:
    > @loop4
    > for substeps in step1 # loop 4a
    > if hopeless(): continue loop1 # run next configuration
    > if substepsFailed(): restart loop4 # try again
    > if substepsWorked(): break loop3 # go on to next
    > steps, like loop4
    >
    > That format is fine, everyone involved can understand it, even the
    > people in charge.


    Well good for them, because I sure as hell don't understand it. To me,
    that's exactly the sort of thing that Guido was worried about when he
    rejected the idea of named labels. I'd need to sit down and trace a few
    loops by hand to grasp it. I wonder how new people coming into the project
    find it?

    Personally, I consider two nested loops right on the boundary of my "magic
    number seven, plus or minus two" short term memory[1]. I prefer to chunk
    code into functions so that I can ignore details of the inner loops while
    reasoning about the outer loops, and vice versa. If you feel different,
    then I'm not being sarcastic when I say "good for you".

    If you require a 1:1 correspondence between your code and your pseudo-code
    specification, then maybe Python isn't the right language for this task.

    Ruby is very Python-like, and has labelled loops. Perl and PHP less so, but
    can also be quite readable with some discipline. You could also check out
    Cobra -- their website is down just at the moment, so I can't check whether
    it has labelled loops.

    http://cobra-language.com/



    [1] Not really magic, and probably more like 4±2.


    --
    Steven
     
    Steven D'Aprano, Sep 2, 2011
    #15
    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. Andy Fish
    Replies:
    65
    Views:
    1,796
    Mabden
    May 18, 2004
  2. Allan Bruce

    dynamic number of nested loops

    Allan Bruce, Jul 1, 2004, in forum: Java
    Replies:
    5
    Views:
    9,833
    Tor Iver Wilhelmsen
    Jul 3, 2004
  3. dolphin
    Replies:
    4
    Views:
    330
    Jorgen Grahn
    Aug 25, 2007
  4. er
    Replies:
    2
    Views:
    520
  5. Me
    Replies:
    2
    Views:
    253
Loading...

Share This Page