Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

fun with nested loops

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

Contents

  fun with nested loops Daniel <dalist0@gmail.com> - 2011-08-31 08:51 -0700
    Re: fun with nested loops aspineux <aspineux@gmail.com> - 2011-08-31 09:35 -0700
      Re: fun with nested loops Daniel <dalist0@gmail.com> - 2011-08-31 11:40 -0700
        Re: fun with nested loops Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-09-01 10:11 +1000
          Re: fun with nested loops Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-09-01 10:50 +1000
            Re: fun with nested loops Daniel <dalist0@gmail.com> - 2011-09-01 07:05 -0700
              Re: fun with nested loops Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2011-09-01 16:57 +0200
              Re: fun with nested loops Terry Reedy <tjreedy@udel.edu> - 2011-09-01 14:40 -0400
              Re: fun with nested loops Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-09-02 11:04 +1000
    Re: fun with nested loops Chris Angelico <rosuav@gmail.com> - 2011-09-01 04:13 +1000
      Re: fun with nested loops Daniel <dalist0@gmail.com> - 2011-08-31 12:07 -0700
        Re: fun with nested loops Chris Angelico <rosuav@gmail.com> - 2011-09-01 05:15 +1000
          Re: fun with nested loops Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-09-01 10:18 +1000
    Re: fun with nested loops Carl Banks <pavlovevidence@gmail.com> - 2011-09-01 12:02 -0700
      Re: fun with nested loops Daniel <dalist0@gmail.com> - 2011-09-01 17:21 -0700

#12492 — fun with nested loops

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

[toc] | [next] | [standalone]

#12497

On Aug 31, 5:51 pm, Daniel <dali...@gmail.com> 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

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

#12517

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

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

#12534

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

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

#12537

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

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

#12565

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

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

#12567

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

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

#12576

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

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

#12597

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

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

#12512

On Thu, Sep 1, 2011 at 1:51 AM, Daniel <dalist0@gmail.com> 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

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

#12518

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

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

#12519

On Thu, Sep 1, 2011 at 5:07 AM, Daniel <dalist0@gmail.com> 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

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

#12535

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

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

#12577

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

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

#12595

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web