You are viewing bramcohen

Thu, Apr. 28th, 2005, 10:39 pm
Control flow

Here is a form of control flow not supported in any language I've used:
loopa: while x:
    do stuff
    if something:
        continue loopb
loopb: while y:
    do other stuff
    if something else:
        continue loopa
To be sane, when loopa exits here control flow should naturally jump to after loopb instead of falling through to it, otherwise it's rather like duff's device.

I have to admit I've never really wanted this functionality in any code I've written, but it's a form of cleaning up the call stack and jumping not supported by break/continue/return/raise.

Yesterday I wrote code with the following structure, and corresponding comment, which I find hilarious but is probably a bit on the obscure side:
for p in q:
    do stuff
    for a in b:
        if f(a):
            break
    else:
        # Niklaus Wirth can bite me
        continue
    do more stuff

Fri, Apr. 29th, 2005 06:16 am (UTC)
eqe

The indentation of your else clause is screwy.

What does a continue add when it's the last statement in the loop body? Unless it's supposed to continue the outer loop, which is just freaky.

Fri, Apr. 29th, 2005 07:17 am (UTC)
randallsquared

The else clause is on the for loop, not the if textually just above it.

Fri, Apr. 29th, 2005 07:38 am (UTC)
darius

Heh. PolyFORTH let you put your ELSE outside the loop, but I had no idea Python did too. Not the sort of code you normally think of when you think of Python...

Sat, Apr. 30th, 2005 04:50 am (UTC)
eichin

darius: I suspect (having not looked that Forth in ages) you may still be missing the meaning of the code (and it is an almost-but-not-quite unique feature in python - I'm pretty sure Ada95 has it too - but it is rare, if expressive) in that else clause *isn't* on the inner "if"... it's actually on the for, that is, it is a for-break-else construct. It is perhaps best thought as a "find loop" -- look in these things until you find something, or ELSE do something else.

The fact that the break is actually "right there" probably helps mislead you (or other readers), in that regard, if you haven't seen it before.

Sun, May. 1st, 2005 06:37 am (UTC)
darius

I think that's pretty much the same as the Forth construct (though that was a WHILE and not a FOR) -- the funny thing there, though, was that it was an accident. Someone noticed that some of the 'loop' and 'if' words could be mixed in a nonnested way with this useful behavior -- so it started as a hack and got promoted to a documented language feature.

It couldn't have happened that way with Python since Python actually checks for syntax errors...

Fri, Apr. 29th, 2005 04:08 pm (UTC)
bramcohen

the continue isn't in the inner for's scope, since it's in the else section, which comes later, but it is in the outer for's scope, which is what gets continued to.

Fri, Apr. 29th, 2005 06:49 am (UTC)
node

Don't continuations (in ML, or Scheme) give you that kind of control flow? An example in Python.

Fri, Apr. 29th, 2005 07:36 am (UTC)
darius

Yeah, though you don't need continuations here, just tail-call elimination, unless you really really want to use a while loop.

Fri, Apr. 29th, 2005 07:39 am (UTC)
darius

er, s/elimination/optimization/

Fri, Apr. 29th, 2005 04:25 pm (UTC)
bramcohen

Yes, I guess in lisp the two loops can simply call each other, since you don't get that super-deep stack. Does 'return f()' automatically do tail elimination in Python? It looks like it could. That would *almost* allow for the following:
def loopa():
    while x:
        do stuff
        if something:
            return loopb()
def loopb():
    while y:
        do other stuff
        if something else:
            return loopa()
loopa()

Unfortunately I think Python's scoping rules break that one, since loopa can't see loopb. Maybe you could create a stub for loopb which loopa can see, then set the value it wraps after loopb is defined. I don't know if there's clean syntax for that though.

Fri, Apr. 29th, 2005 04:29 pm (UTC)
bramcohen

To test whether Python does tail-elimination I just did the following:
def f(n):
    if n == 0:
        return 0
    return f(n-1)
f(1000000)

It bombs out. I don't know if it would bomb out when running stackless. Fixing this would probably be a good thing.

Fri, Apr. 29th, 2005 07:24 pm (UTC)
darius

The scoping rules don't appear to be a problem, though I've never bothered to learn Python's exact rules. This worked:

def test():

    def even(n):
	if n == 0: return True
	return odd(n-1)

    def odd(n):
	if n == 0: return False
	return even(n-1)

    print even(123)


I can think of two reasons Python wouldn't optimize tail calls: its stack is the C stack, and C doesn't (I guess Stackless would fix that, as you mentioned); and refcounting means the language defines a lifetime for references, which would expose the different times a stack frame is reclaimed. Oh, and things like tracebacks would change visibly too, of course.

Sat, Apr. 30th, 2005 05:35 pm (UTC)
(Anonymous)

Yeah, I'm pretty sure Guido recently rejected a patch to add tail-call elimination, for some or all of those reasons.

-- Nathaniel

Sat, May. 7th, 2005 06:21 am (UTC)
bramcohen

Interesting. If a call to even() is put between the even and odd functions then the parser complains. Apparently there's a fair amount of smarts in there.

The one problem with that approach is that variables local to test() can't be referred to directly from inside even() and odd(), but it still basically works.

Losing info for stack traces would be a quite unpleasant side effect of tail call elimination.

Sat, May. 7th, 2005 10:14 am (UTC)
(Anonymous): python namespace stuff

Interesting. If a call to even() is put between the even and odd functions then the parser complains. Apparently there's a fair amount of smarts in there.

After calling it, the body of the outer function `test' is executed line by line: first an inner function `even' is defined (i.e. `even' is put as key in the namespace local to the function `test', and it has the (inner) function object as value), then `odd', then when `even()' is called, it has access to both `even' and `odd' as they are as keys present in the local namespace.

After putting the call to `even' in-between, it would have access to `even', as that is lexically above it, but at that point `odd' is not defined yet, so function `even' can't call `odd'.

(Indeed, a proper backtrace is a major reason not to do tail call merging -- yet Common Lisp has _solved_ this issue of conflicting goals by letting the programmer control the optimization using `declare'; although tcm is not required by the language spec, several implementations support it.)

Fri, Apr. 29th, 2005 04:10 pm (UTC)
bramcohen

Continuations are lisp's 'goto'. My examples are ones which are both fairly safe programming practice and fairly easy to understand.

Fri, Apr. 29th, 2005 08:48 am (UTC)
(Anonymous): Double negation is unpythonic.

This shoud do:
for p in q:
    do stuff
    if any(f(a) for a in b):
        do more stuff

where any can pre-python2.5 be defined as (see Guido's Weblog entry (http://www.artima.com/weblogs/viewpost.jsp?thread=98196)):
def any(l):
    for i in l:
        if i: 
            return True
    return False

No more double negation (by break/continue). Not so funny, but pythonic.
Note that you can use filter(f, b) instead of any, but this will evaluate all f(a) for a in b instead of stopping at the first positive.

Yes, I am bereft of humor. ;)

Cheers,
Andre

Fri, Apr. 29th, 2005 04:18 pm (UTC)
bramcohen: Re: Double negation is unpythonic.

There are a few of these things in a row, each of which can be logically removed separately, so forcing the later section to get indented throws off the logic quite a bit.

I do agree that the following would look cleaner in this case:
for p in q:
    do stuff
    if any(f(a) for a in b):
        continue
    do more stuff

But my real code example was actually more complicated that this - it's actually looking for two things to hit, not just one, and has a counter in there. So your simplification wouldn't work on my real code, but it does on the simplified example.

Fri, Apr. 29th, 2005 02:00 pm (UTC)
misterajc

Bram sez:

Here is a form of control flow not supported in any language I've used:
[...]
I have to admit I've never really wanted this functionality in any code I've written [...]


Coincidence?

Andrew

Fri, Apr. 29th, 2005 04:19 pm (UTC)
bramcohen

Probably not, but noone's ever explained to me what co-routines do (not in a way I understand, anyway), and I was thinking maybe I reinvented those.

Tue, Jun. 21st, 2005 03:03 pm (UTC)
(Anonymous): coroutines

i'm thinking you might have. i don't really grok coroutines either, but your example reminded me of some examples of coroutines i've seen while trying to grok continuations in Scheme. the "sorta-threading" examples that tend to be shown off in that context, i believe, often work something like your loopa/loopb logic would have to, only using continuations to do the switching between contexts.

of course, i've never really seen any point in using coroutines either, so i'm not entirely positive.

Tue, Jun. 21st, 2005 03:10 pm (UTC)
(Anonymous): Co-routines

Your example does look a lot like coroutines, which are quite similar to Duff's device. This page http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html shows the similiarity between the two and how to use it to implement coroutines in C.

Sun, Jun. 26th, 2005 07:44 pm (UTC)
bramcohen: Re: Co-routines

Thank you, that's the first readable explanation of coroutines I've ever seen.

I tend to be in favor of rewriting both sides, mostly because it forces you to unroll a whole bunch of cases which otherwise are completely obfuscated and tend to cause nasty bugs. Those bugs are much more inspectable in the rewritten versions, however inelegant they may be at first blush.

Fri, Apr. 29th, 2005 02:15 pm (UTC)
etrepum

I've definitely written funky loops like this before, using try:except: might be "better" depending on how twisted your loops are. I'd probably have written this case like Andre's suggestion, though.

This is probably my worst offense:
dct = {....}
while True:
    for key, condition in dct.iteritems():
        if condition() is None:
            continue
        # modifying a dict being iterated.. but breaking
        del dct[key]
        break
    else:
        # break out of the while loop
        break


It's done this way because the "condition" functions have side-effects (if returning something other than None) that can effect whether other condition functions will trigger, so this chunk of code waits until the system reaches equilibrium... either by exhausting the dict, or going through a pass where it doesn't change.

It's obviously not the optimal algorithm for doing this, but it's the best way I've found to express it in this case given the density of doing it another way, the size of the data set, and Python's behavior.

...

On a related note, have you been following any of the PEP-340 discussions on python-dev? There's some interesting possibilities in there.

Fri, Apr. 29th, 2005 04:32 pm (UTC)
bramcohen

That does look fairly sketchy, not because it's hard to read but because it's fragile - it would be easy to forget the rule later and break it.

The wonkiest thing to read in your example is the 'if condition() is None:', because it seems to imply that condition() has no side effects, which is very misleading.

I haven't been following those discussions, although I've only even seen finally used for cleanup, so I'm all in favor of cleaner, less dangerous syntax which gets rid of it.

Fri, Apr. 29th, 2005 04:38 pm (UTC)
etrepum

It doesn't actually read as "if condition() is None", but that is the effect. It uses the result of the callable, but the way in which it uses the result is not important to the example.

Forgetting the rule isn't really an issue, it's clearly marked.

Fri, Apr. 29th, 2005 04:37 pm (UTC)
nvioli

seems like you could do this pretty easily using recursion in scheme or similar (no loops needed):

(define (function1 arg1)
(begin
(dostuff)
(if (something)
(function2 (increment arg1))
(output1))))

(define (function2 arg2)
(begin
(domorestuff)
(if (somethingelse)
(function1 (increment arg2))
(output2))))

forgive me if that's not what you meant. i'm pretty new at this stuff.

Fri, Apr. 29th, 2005 04:38 pm (UTC)
nvioli

sorry about the indentation. i don't know how to do fixed width fonts.

Fri, Apr. 29th, 2005 04:41 pm (UTC)
bramcohen

Use the <pre> tag

Fri, Apr. 29th, 2005 04:42 pm (UTC)
bramcohen

Yeah, it can be done in scheme (which I haven't really used). See earlier discussion - Python doesn't have tail recursion and have some scoping limitations which make this trick not work there.

Mon, May. 2nd, 2005 03:04 pm (UTC)
(Anonymous): int

Dear Mr Cohen,

My name is Chun-fai Yung of TVB News, Hong Kong. I want to ask something about your program. Please reply to cf.yung@tvb.com.hk
Thank you very much.

Best regards,

Chun-fai Yung.


Tue, May. 3rd, 2005 10:08 am (UTC)
ciphergoth: Re: int

Try repeatedly spamming his journal with this crap - that'll work.

Tue, May. 3rd, 2005 04:08 pm (UTC)
(Anonymous): Control flow

I've come across one case where this control structure would have been useful. It's in the "almost inverse algorithm" for calculating polynomial inverses (used in elliptic curve cryptography, see http://citeseer.ist.psu.edu/schroeppel95fast.html).

One case in 20 years isn't really enough to justifying adding this to a programming language, I think :-)

It's easy enough to simulate by adding another outer loop, anyway.

-- David Hopwood

Tue, May. 10th, 2005 02:54 pm (UTC)
(Anonymous): coroutines

These are coroutines... you can do them in any language.

Sun, Jun. 26th, 2005 07:45 pm (UTC)
bramcohen: Re: coroutines

Not quite coroutines - coroutines yield instead of returning, keeping their stack information between calls.

Tue, Jun. 21st, 2005 02:50 pm (UTC)
(Anonymous): C is your friend

Yeah, they're evil blah blah:

loopa: while(1) {
         do_something();
         if(something) goto loopb;
}
loopa: while(1) {
         do_something_else();
         if(something_else) goto loopa;
}


The point is, its possible.

Sun, Jun. 26th, 2005 07:46 pm (UTC)
bramcohen: Re: C is your friend

you have a typo - you meant loopb in that second label.

Yeah, forgot about good ol' goto. C gets away with that by forcing all local variables to be scoped for the entire function.

Tue, Jun. 21st, 2005 02:55 pm (UTC)
(Anonymous): Perhaps I misunderstand

What's the difference between your loops and this code?

def loopb():
    while y:
    do other stuff
    if something else:
        yield

#loop a
while x:
    do stuff
    if something:
        loopb()


--p3d0

Sun, Jun. 26th, 2005 07:47 pm (UTC)
bramcohen: Re: Perhaps I misunderstand

In that example loopb isn't calling loopa.

Tue, Jun. 21st, 2005 06:39 pm (UTC)
(Anonymous)

not supported in any language I've used


Hmm you must be using broken languages. You have my sympathy. Any language at all with tail-recursion can express this example e.g. lua, scheme, ml, haskell, etc. Here is an example in ocaml (http://caml.inria.fr)


let x = ref true in
let y = ref true in
let something = ref true in
let somethingelse = ref true in

let do_stuff () =
  (* do whatever to x and y *)
  print_string "doing stuff\n" in

let do_otherstuff () =
  print_string "doing otherstuff\n" in

let rec loopa () = 
  if !x then
    begin
      do_stuff ();
      if !something then loopb () else loopa ()
    end

and loopb () =
  if !y then
    begin
      do_otherstuff ();
      if !somethingelse then loopa () else loopb ()
    end

in loopa ()

Sun, Jun. 26th, 2005 07:48 pm (UTC)
bramcohen

That also depends on different variable scoping rules than are in languages I've used. I tend to think of the way your preferred languages carry around variable scope as fairly broken though, since it's a lot less clear where variables are coming from.

Point taken, however.

Mon, Jun. 27th, 2005 07:41 pm (UTC)
(Anonymous): scoping

Why do you think the scoping is confusing? It's just straightforward lexical scoping...



Can you give me an example of what feels off?

Tue, Jun. 21st, 2005 07:13 pm (UTC)
(Anonymous)

for p in q:
    do stuff
    flag = False
    for a in b:
        if f(a):
            flag = True
            break
    if flag == False:
        continue
    do more stuff

Sun, Jun. 26th, 2005 07:50 pm (UTC)
bramcohen

That only supports one entry point from the first section to the second. But it can be extended using two checks to be more general, and the two code sections can both use yield to support full-blown coroutines.

Wed, Jun. 22nd, 2005 01:04 am (UTC)
(Anonymous): Java (named continues)

Just to point it out, Java can do this:

public class test {
	public static void main(String args[]) {
		int x = 20, y = 20;
		
		loopa: while (x > 0) {
			System.out.println("X = " + x);

			x -= 2;

			if (y == (x + 4)) {
				while (y > 0) {
					--y;
					System.out.println("Y = " + y);
					if (x >= y) {
						continue loopa;
					}
				}
			}
		}
	}
}


Derek

Sun, Jun. 26th, 2005 07:51 pm (UTC)
bramcohen: Re: Java (named continues)

That only supports one entry point into the second section of code, based on where it's included.

The two sections can both be pulled out and put in an if/else to fix that problem, although that gets fairly ugly.

Wed, Jun. 22nd, 2005 08:59 am (UTC)
nothings

If I'm not confused, your original request can be satisfied with any C-like language that has named break/continue, without using gotos, using exactly two exceptional flow control statements (e.g. break, continue), and may well translate to your language of choice, if it has end-checked loops.

As coded, you have two ways of exitting each loop (loopa and loopb); you've made 'x' and 'y' the primary loop controls, and 'something' and 'something else' the exceptional events that trigger switching to the other loop. If you instead view it as a single sustained process, then the '!x' and '!y' events terminate the complete process, and you can view those as exceptional (they only ever happen once, whereas 'something [else]' can happen multiple times).

So all you have to do is make explicit that these two loops are sustained (nested inside another loop), and reverse the primary loop controls:

outer:
   for(;;) {
      do {
         if (!x)
            break outer;
         stuff1;
      } while (!something);
      do {
         if (!y)
            break outer;
         stuff2;
      } while (!something else);
   }


This generalizes to three or more loops, but only if they change control in a strictly cyclic fashion. It also wouldn't be as nice if you had had 'stuff' on both sides of your original 'if something' conditions, since that requires a middle-checked loop, which C-like languages don't have either (so they turn into infinite loops with breaks in the middle, and at that point I wouldn't want to claim 'native' support).

The comment above this one with the java example shows another way of structuring this, but without the extra outer loop, putting one inside the other. However it has a bug--it left out a 'break' after the inner while stops, and it obfuscates the flow control (hence the bug, I guess), unless it happens to actually be a natural mapping of the problem, and it doesn't scale to more loops (each of which get nested inside the next one). If the inner loop of that example were rewritten as above, it would reduce it from needing both a continue and a break to needing only a break.

Coroutines would do something like this, but 'continue' expresses 'restart the loop from the front', whereas coroutine would be more like 'keepgoing' meaning 'continue from whereever it was when you called keepgoing'--which means the same thing here since your continues are last, but wouldn't be the same thing in general, so if what you want is 'restart the loop at the front' coroutines are definitely different.

Of course C-like languages can't even express your second example, but it comes up all the time, and neither solution that I use is ideal. (#1: instead of the 'else:' there's a repeated test of the loop condition to see if it reached the end, otherwise identical; #2: the 'do more stuff' is moved up to between 'if f(a):' and 'break;'.)

Sun, Jun. 26th, 2005 07:55 pm (UTC)
bramcohen

Yeah, that approach works, although it's a bit ugly. In Python you can support full-blown coroutines with that approach using yield, which is even uglier, but at least is understandable, unlike coroutines in C.