Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Do C compilers disprove Fermat's Last Theorem?

blog.regehr.org

Post reply on HN
Print view View original

21–27 of 27 posts

Re: Do C compilers disprove Fermat's Last Theorem?

#21

Post by Confusion »

neilc wrote: post #17
barrkel wrote: post #10

Earlier quoted context omitted.

Re C99 - the existence of an execution environment is certainly observable (it'll disappear with respect to the program when the program terminates), unless you try to argue that exit(0) has no observable side-effects according to the C standard, and thus we should expect code following exit(0) to also be executed, where I think we would be entering absurdity. Re correctness: That the compiler optimizer cannot see pa…

That an optimizer assumes without proof a solution to the halting problem for some sub-program would mean that it's an unreliable translator The optimizer doesn't need to solve the halting problem for this example. It merely needs to prove that any iteration of the loop has no side effects; hence, an unbounded number of loop iterations also has no side effects, and the loop can be removed. The real issue is whether t…

  if you can point to some language in the spec that would  
  prevent the optimization, I'd love to see it.
The author added an update that says, among other things:

  In contrast, the Java language definition is quite clear
  that infinite loops may not be terminated by the JVM.
(with a link to the JLS)

Re: Do C compilers disprove Fermat's Last Theorem?

#22

Post by antirez »

Make sure to read the first comment of the post, the poster wrote a number of nonsensical things ;)

The compiler does not try at all to analyze the loop to understand if this can exit or not, because it can do this only for very trivial cases. Instead since the variables are not references after the loop, the loop is ignored as it does not matter what will happen, but the outcome of the computation will never be used, so it can be skipped at all.

Re: Do C compilers disprove Fermat's Last Theorem?

#23

Post by gojomo »

barrkel wrote: post #16
gojomo wrote: post #13

Earlier quoted context omitted.

The alternate behavior, while initially non-intuitive, seems more useful to me, in usual scenarios. And the grandparent post's taxonomy including the idea of "partial correctness" also seems useful. So you'll have to justify your " must " a bit more. In particular: a programmer who wants an infinite loop can get one easily enough. Code that is complex, and has no side-effects other than affecting termination, and nev…

If you accept the grandparent's argument on face value, you should accept that a compiler should be able to remove other do-nothing infinite loops, like in the example I mentioned elsewhere: for (;;) /* do nothing */; destroy_the_world(); /* has side-effects */ Why should a compiler remove the loop in the OP's case, but not remove the loop above? Do you accept that removing the loop changes the side-effects of the pr…

It does change the effects -- but in a predictable and possibly-useful way. A loop that doesn't exit or do any work itself is far more likely a bug than an intentional behavior; removing it like other do-nothing code may benefit far more programs seeking "optimization" than the alternative.

Re: Do C compilers disprove Fermat's Last Theorem?

#24

Post by buster »

barrkel wrote: post #19
_delirium wrote: post #18

Earlier quoted context omitted.

Yes, but in what vaguely reasonable circumstances would you write dead code whose deadness depends on the fact that an infinite loop precedes it? The fact that the C standard doesn't consider changing termination properties from nonterminating to terminating to be an impermissible optimization seems reasonably practical. The only thing I can guess at would be something in embedded-land that's using nonterminating loo…

Reasonable has nothing much to do with it, IMO; and I'm not really talking about C (it is only an example), but about compiler optimizers.

In the end, this only means the following:

  - The C spec permits this behaviour, the Java Spec doesn't
  - as a programmer, know the language and the spec that you use
The destroying_world() example only shows that the programmer needs to know the language he is using. The optimization is in my opinion practical and reasonable in most cases.

Every programmer that depends his program workflow and important decisions on the termination of an infinite loop should be bitch slapped to hell. Do you have another more reasonable example? The only example for the infinite loop i can think of is the eventloop of some network code. But i fail to see where any code over a few lines doesn't have any side effects.

Re: Do C compilers disprove Fermat's Last Theorem?

#25

Post by Rexxar »

barrkel wrote: post #20
neilc wrote: post #17

Earlier quoted context omitted.

That an optimizer assumes without proof a solution to the halting problem for some sub-program would mean that it's an unreliable translator The optimizer doesn't need to solve the halting problem for this example. It merely needs to prove that any iteration of the loop has no side effects; hence, an unbounded number of loop iterations also has no side effects, and the loop can be removed. The real issue is whether t…

But a loop that never exits will never continue on to the rest of the program, which will never have its side-effects. This loop has no side-effects: for (;;) /* do nothing */; So the compiler, according to the spec, can remove it, right? for (;;) /* do nothing */; destroy_the_world(); /* has side-effects */ So will the world be destroyed? Or is the following code dead? In which case, it's not OK for the compiler to…

Every optimization can potentially have a side-effect :

    {
        time ta0 = getTime();
        for (;;) { /* do something 1*/ }
        time ta1 = getTime();
        
        time tb0 = getTime();
        for (;;) { /* do something 2*/ }
        time tb1 = getTime();
        
        if(ta1-ta0
The result depends of the speed of execution of each loops. Should optimizations really be allowed only if they don't have any side effect ?

Re: Do C compilers disprove Fermat's Last Theorem?

#26

Post by dkersten »

barrkel wrote: post #20
neilc wrote: post #17

Earlier quoted context omitted.

That an optimizer assumes without proof a solution to the halting problem for some sub-program would mean that it's an unreliable translator The optimizer doesn't need to solve the halting problem for this example. It merely needs to prove that any iteration of the loop has no side effects; hence, an unbounded number of loop iterations also has no side effects, and the loop can be removed. The real issue is whether t…

But a loop that never exits will never continue on to the rest of the program, which will never have its side-effects. This loop has no side-effects: for (;;) /* do nothing */; So the compiler, according to the spec, can remove it, right? for (;;) /* do nothing */; destroy_the_world(); /* has side-effects */ So will the world be destroyed? Or is the following code dead? In which case, it's not OK for the compiler to…

The C spec states[1] that code without side-effects may be removed. The C spec does not list non-termination as a side-effect. The C spec also states that anything not explicitly stated is undefined behaviour. That means that in the abstract machine that the C spec defines, it is valid to remove the loop.

If you don't want the loop to be removed, then you are working outside of the defined abstract machine, which means that its up to you to make sure it operates as desired. The embedded systems guys mentioned in the article (on the llvm bug tracker, they also said it "wasn't much of an issue" for them, because they did, in fact, tell the compiler to do what they wanted, wheras the author stated that it was) did this by compiling the necessary code without optimisations. Other valid approaches would be to tell the compiler that the loop may, in fact, have side-effects which cannot be known in the context of the code by declaring the variables volatile (the C spec defines reading volatile varibales as side-effects). If you see non-termination as side-effects, then you should tell your compiler somehow.

The C programming language runs in a well defined abstract machine. Anything a compiler does which is not defined by the abstract machine (so long as it doesn't contradict the abstract machine, ie the abstract machine functions as stated) is not a bug, but is considered undefined behaviour and cannot be relied upon - therefore relying on an infinite loop which does not contain side-effects is undefined behaviour.

--

As for if a programming language in general (rather than specifically C) should remove infinite loops.. I think its up to each language to define this. If a language states that non-termination is a side-effect, then compilers cannot optimise away code which may not terminate, unless the user invokes undefined compiler-specific behaviour by telling it to (eg compiler options) or by changing the code to make your intent obvious to the compiler. Or by solving the halting problem.

So, in summary: The C compilers are NOT wrong to elliminate the side-effect free infinite loops. Other languages MAY be wrong to do so - it depends on what the language specs state. You CAN get around this by telling the compiler what your intent is, by either changing the code (eg by introducing side-effects) or by invoking non-standard behavour (eg, through compiler switches).

[1] 5.1.2.3 (Execution Environment), paragraphs 2 and 3.

Re: Do C compilers disprove Fermat's Last Theorem?

#27

Post by jfoutz »

barrkel wrote: post #15
jfoutz wrote: post #12

Earlier quoted context omitted.

No, i think he's suggesting knowledge understanding and science as a whole depend on observable side effects. For example, i have a program that does in fact provide a counter example to fermat's last theorem. Unfortunately it does not print the result. If you deny observable side effects as a requirement, you must accept that i do have a program that does that. Most cs curriculums cover propositional logic. if you r…

I find it somewhat difficult to believe we're having this conversation in any seriousness. Consider this program fragment: for (;;) /* do nothing */; destroy_the_world(); /* has side-effects */ Would you say that a compiler that removed the loop changed the side-effects of the program?

You're absolutely right. Strict evaluation requires proof of termination. I should never comment right before bed.
Post reply on HN