http://qs1969.pair.com?node_id=1057242

If you do nothing an infinite number of times, in the end do you end up having done anything?

Yesterday on #perl6 I had a quick talk with TimToady and others about:

loop {}

It was not the first time I saw this construct, but for the first time something bugged me about it.

At first I thought it was because of the idea that Perl 6 is supposed to be parallelism-friendly, but then I realized this is not the issue here.

I couldn't quite grasp what was the problem until I asked myself: "How long is the execution of this instruction supposed to take?"

I suppose a no-op is not instantaneous. Well, for a computer I mean. I guess it takes at least a clock cycle or something. But at least conceptually, in a way an optimizer should be aware of, such an operation is supposed to be instantaneous. Thus its execution time is zero. Thus if you execute it once, twice, ten or a thousand times, it should still be zero.

So, what if you do it an infinite number of times? Is it still zero? Infinite? In other words, what is 0 * Inf?

In maths, zero times infinity is an undefined concept. Perl 6 already knows that:

$ perl6 -e 'say 0 * Inf' NaN

Indeed we get NaN (Not A Number).

So, what happens when you ask a computer to loop a no-op? Well, the computer could actually run some code to perform the loop and just the loop, but a compiler should not request something like that, should it?

I mean if you put a no-op inside a program, like this for instance:

say 'hello';  ; say 'good bye'

The space between the two semi-colons can be considered as a no-op, right? Yet I very much doubt the compiler spends a clock cycle to execute it. More probably it just ignores it and goes directly from say 'hello' to say 'good bye'. Same if you run this:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Obviously such a program would not take twice as much time as:

;;;;;;;;;;;;;;;;;;;;;;;;;;

Because a finite sequence of no-op can reasonably be replaced by a single no-op, right?

To some extend, 'loop {}' is a way of writing an infinite sequence of semi-colons. So, why should it take seriously the no-op inside a loop? I think it shouldn't. It should just ignore it.

However, a compiler can only ignore a finite number of successive no-op. Otherwise it would face an undefined concept, just as in 0 * Inf.

That's why, if you ask me, I'd tell you that I think loop {} should die with a "undefined behavior" message. (or "singular behavior", "degenerated control structure", "infinite empty loop", ... you chose)

Replies are listed 'Best First'.
Re: Should loop {} really loop indefinitely?
by Corion (Patriarch) on Oct 07, 2013 at 10:57 UTC

    I know very little of Perl6 and its current interpretation. At least this random source taken from a Google search claims that loop { ... } is an infinite loop, equivalent to the Perl5 construct while (1) { ... }.

    You seem to be arguing that the empty infinite loop loop { ... } should be invalid.

    Please note that there are external events, like signals or alarms, that can still change the program state in a way that it can leave that infinite loop, or at least, do something else until returning to that infinite loop. The infinite loop is still not energy-friendly, but making Perl6 also force people to behave energy-friendly strikes me as quite out of scope.

    But maybe I'm missing the point - I don't get where execution time comes into play at all here. To me, the program execution never continues after the loop statement, and I don't mind whether the loop itself does something meaningful or not. If I wanted something else to happen, I would write something other than loop {}.

Re: Should loop {} really loop indefinitely?
by moritz (Cardinal) on Oct 07, 2013 at 16:24 UTC

    Since loop { } could either mean "do nothing" or "loop infinitely", and one of these alternatives is clearly useless, it's pretty obvious to me what the construct does.

    The doubts about infinite repetition of no-ops look artificially constructed to me, and make a fine topic for a meditation, as long as you don't actually propose to change the language specification.

    To try to answer on a more technical level: an optimizer is allowed to unroll loops as long as no behavior changes, but if the optimizer unrolls infinitely many iterations for noops into one, it makes an error. And that's because not all operations that work on finite things work the same on infinite things, which is a well-known theme in mathematics. (For example proof by induction only works over finite numbers).

      Consider this program:

      for ^1_000 {}

      Would you accept that an optimizer just replaces it with a single no-op? Or that it just ignores it entirely, like a comment? To me it would make sense, but I understand it's far from obvious and could be argued (not all for (...) {} constructs should be ignored, as there could be side-effects in the ...).

      Though if you do accept to ignore such a construct, then consider the state of 'loop {}' (with the current semantic, when loop {} is looping doing nothing) during the 1_000th loop. At this point, the program has been doing something (one thousand consecutive no-ops) that it would not have done in an other context (i.e. with for ^1000 {}). It's as if, as soon as you decide your loop will not end, you made your program forget the fact that consecutive no-ops could be ignored. Does not seem right.

      In other words, at any point during the execution of loop {}, assuming it didn't die as I suggest, your program is supposed to have been 'looping' for a duration $T, during which it is supposed to have executed $n no-ops, with $n being any positive natural integer. Whatever the value of $n is, it will mean that your program will have had executed $n no-ops in $T seconds, although normally $n no-ops can be executed in exactly zero seconds (since they are normally ignored). So the behavior is not consistent.

      That being said, as you mentioned this is just a meditation. It probably does not matter much anyway, and you Perl 6 guys do such a great job that I don't want to upset you with this or anything. I'm totally fine with 'loop {}' keeping doing what it is currently doing. It's more a philosophical issue than anything, I guess.

      To try to answer on a more technical level: an optimizer is allowed to unroll loops as long as no behavior changes, but if the optimizer unrolls infinitely many iterations for noops into one, it makes an error.

      Indeed, because that would mean that Inf * 0 == 0, which is not true. But it is also not true that Inf * 0 == Inf, which would mean that the program must run indefinitely.

      Edit:

      Since loop { } could either mean "do nothing" or "loop infinitely", and one of these alternatives is clearly useless, it's pretty obvious to me what the construct does.

      My point is that loop {} actually means neither "do nothing", nor "loop infinitely".

Re: Should loop {} really loop indefinitely?
by hdb (Monsignor) on Oct 07, 2013 at 11:39 UTC

    And how will you calculate the BogoMips?

      Point taken. I guess it could be done with a special optimizer parameter, or with an explicit no-op instruction that would never be ignored from compilation.

      loop { no-op() }
Re: Should loop {} really loop indefinitely?
by boftx (Deacon) on Oct 07, 2013 at 21:40 UTC

    The infinite loop is in fact very useful, and I had to explicitly tell my optimizing C compiler (back in the day) not to replace it with a nop instruction when in fact the loop was waiting for an interrupt to occur from an I/O port.

    With that perspective, I think the code should in fact just loop there forever. You presumably wrote it that way for a reason. :)

    On time, cheap, compliant with final specs. Pick two.

      In Perl 6, when you want to idle indefinitely, you should probably write:

      sleep(Inf);

      Also, as mentioned above, replacing loop {} by a nop would be just as false as letting it loop forever. 0 * Inf is neither 0 nor Inf.

Re: Should loop {} really loop indefinitely?
by Anonymous Monk on Oct 07, 2013 at 14:09 UTC
    That's why, if you ask me, I'd tell you that I think loop {} should die with a "undefined behavior" message.
    See, the problem is that doing that would define loop {} as die with a "undefined behavior" message and thus it wouldn't be undefined behavior anymore.

      It's not at the same level in the tarskian hierarchy.

Re: Should loop {} really loop indefinitely?
by Crackers2 (Parson) on Oct 09, 2013 at 20:20 UTC

    Shouldn't loop {} be considered the equivalent of

    LABEL: goto LABEL;

    i.e. yes the thing you're executing inside the loop is a nop, but that doesn't invalidate the concept of the loop itself.

    So looping infinitely seems like the only logical behaviour to me.

Re: Should loop {} really loop indefinitely?
by sundialsvc4 (Abbot) on Oct 09, 2013 at 23:15 UTC

    Obviously, a string of empty-statements (should...) generate no code at all, no matter how many repetitions there are.   This is purely a syntactic construct; not a semantic one.

    The only way to know what the Perl Implementors (ommmm ....) actually did, is to look for yourself at perlguts (or its v6 equivalent).   But it is fair to predict that they only concerned themselves with real-world probable cases, not hypothetical ones.   (There are no Whetstones to be dealt with here ...)   Therefore, the mere existence of an empty <body> probably isn’t enough by itself to cause no code at all to be generated.   After all, many Perl programs live-and-die by their “side effects,” that is, what happens in the conditional-block that controls a loop vs. the loop itself.   Would the optimizer be smart-enough to omit a block that was altogether empty?   Guess it depends on whether the author of the thing cared to test for it.   Most likely, it wasn’t worth the bother.