Daily reminder that every Turing complete language has undefined behavior.
replies(1):
The language specification, or standard, guarantees certain things about the behavior of programs written to the specification. "Undefined behavior" means "you did something such that the guarantees of this specification no longer apply to your program." It's pretty much a worst case scenario in terms of writing programs. The program might do... anything. Fortunately, in reality it happens all the time and programs often keep behaving close enough to what we expect.
Turing completeness is unrelated to that sense of "undefined behavior".
> halting
They are not entirely unrelated. C++ UB is often things that would be very difficult to detect.
For example infinite template recursion is undefined. Specifying any other behavior is impossible due to halting problem.
Another example: a system might be able to detect out of bounds pointer deref, or maybe not. Same with signed integer overflow.
Well, your point is wrong because UB is not an inherent computing problem. That's what the post above tried to explain.
Many forms of UB are inherent to C-like languages, but languages don't have to be C-like.
> For example infinite template recursion is undefined. Specifying any other behavior is impossible due to halting problem.
A language can avoid this by not having infinite template recursion.
C++ currently allows infinite recursion at the language level, while acknowledging that compilers might abort early and recommending that 'early' is a depth of 1024 or higher. But a future version could bake that limit into the language itself, removing the problem.
> Another example: a system might be able to detect out of bounds pointer deref, or maybe not. Same with signed integer overflow.
A language can avoid out of bounds deref in many ways, one of which is not allowing pointer arithmetic.
Signed integer overflow is trivial to handle. I'm not sure what problem you're even suggesting here that the person in charge of the language spec can't overcome. C++'s lack of desire to remove that form of UB is not because it would be difficult.
How does it know whether a definition is infinitely recursive? This IS the halting problem.
> But a future version could bake that limit into the language itself,
In other words, take away the Turing completeness of templates. Which goes back to my original comment.
Also note that limiting recursion hurts real world use case (types getting arbitrarily complex in a program over time) in favor of theoretical benefit (now you can say it’s not UB).
> pointer Deref
Let me explain again. In a language with pointers checking whether a deref is valid requires comparing every address to every allocation bounds. That’s ridiculously expensive.
The only solution is to take away pointers (Java, C#, etc) OR do what C does, crash on obviously bad derefs. Since “obviously bad” depends on the implementation (maybe you are a safety sadist and you want 2000 instructions per deref) the standard cannot guarantee any behavior. Maybe it crashes, maybe you get “lucky” and it doesn’t notice.
The only way to avoid UB is to limit expressiveness (pretend addresses don’t exist), and all Turing complete languages have UB.
I have more responses, but you’re not grasping the ones I already made.
Template halting is only a correctness issue because it's done at compile time. Turing completeness is not a problem in general, and limiting the amount of computation at compile time is fine.
> The only solution is to take away pointers (Java, C#, etc) OR do what C does
Something along those lines.
> The only way to avoid UB is to limit expressiveness (pretend addresses don’t exist), and all Turing complete languages have UB.
The only way to avoid UB is to limit expressiveness, and NOT all Turing complete languages have UB.
Pointers are a big thing to restrict for a safe language. But you really don't have to do that much else. Whether a program halts or doesn't halt at runtime isn't a safety issue, there's no UB involved. It just runs indefinitely.