The explanation of the "Guess the language by the error"

So last time there was the puzzle that

char isOdd(unsigned int n) {
   return n && isEven(n+1);
}

char isEven(unsigned int n) {
   return isOdd(n+1);
}

both functions get optimized away into return 0.

The explanation that I've heard was fairly handwavy along the lines of "there is just one finite return, the other return is infinite, so the compiler makes a decision that only finite return is possible". This is rather thin.

What really is happening, is very more likely this:

We can see that isEven can be inlined into isOdd:

char isOdd(unsigned int n) {
   return n && isOdd(n+2);
}

We can also see that isOdd is a tail call:

char isOdd(unsigned int n) {
   if (n) return isOdd(n+2);
   return 0;
}

Now, tail call optimization:

char isOdd(unsigned int n) {
   while (n) n+=2;
   return 0;
}

Now, there are no happens-before edges between the loop and any other part of the program: the changes happen to a local variable, the changed value does not escape, and the changed value is not accessed in program order, too. So the unused computation is eliminated:

char isOdd(unsigned int n) {
   return 0;
}

---

If it is hard to grasp why unused computations can be eliminated, think of the following valid transformation: spawn a new thread, and execute that computation there; replace all program order edges with synchronization order edges (eg CompletableFuture.complete(n) at the end of the loop, and CompletableFuture.join() at every use of n in the thread that wants to read the final value computed by the loop). Since here there are no program order edges (and no synchronization edges) between expressions in the loop and the rest of the function (and the rest of the program), suspending the newly spawned thread does not stop the rest of the program from making progress: no accesses to n - no one is waiting for CompletableFuture.join() to finish, consequently no one is waiting for the looping thread to enter CompletableFuture.complete(n) - in the end, no one is waiting for the thread to be spawned. If you can suspend the thread forever, you may just as well never spawn it, too.

---

A funny consequence of this optimization is that it works out that an infinite conjunction is always false: 1 && 1 && 1 && ... == 0.