News for hackers. Stuff that matters.
Re:Undefined Behavior in 2017 by pjmlp on Wednesday July 05, 2017 @05:00AM (#14700876)
Not if the language standard doesn't allow for UB to begin with, then there isn't any halting problem to worry about.

This is what the alternatives in the memory safe systems programming language since Algol days do.

Surely they still allow for developers to disable some of those checks explicitly, but then it is the programmers fault to choose "performance trumps correctness" instead of "correctness trumps performance".

Re:Undefined Behavior in 2017 by caf on Wednesday July 05, 2017 @06:48AM (#14701345)
It doesn't matter if the language defines the behaviour of, say, offsetting an array beyond its declared bounds. That doesn't change the general undecidability of statically proving the offset will always be within the bounds at compile-time - in other words, you need runtime checks in some cases (it's just a matter of whether the compiler or the programmer supplies them).
Re:Undefined Behavior in 2017 by eru on Wednesday July 05, 2017 @09:54AM (#14702386)
Nah, with some help from the programmer, you can produce those proofs. It's not too hard.

The halting problem is impossible to solve for arbitrarily evil programs, but that doesn't mean that it's impossible to write programs that are easy to analyse.

Re:Undefined Behavior in 2017 by gpderetta on Wednesday July 05, 2017 @10:12AM (#14702504)
I think that statically guaranteeing something like in-bound indexing or absence of division by zero you need depended types, which is not exactly easy nor mainstream. And even with dependent types, many non-evil, otherwise correct programs will be rejected.
Re:Undefined Behavior in 2017 by eru on Thursday July 06, 2017 @04:15PM (#14713551)
Yes, for the general problem you want dependent types (or similar).

There are middle grounds, of course: you can let the compiler figure out on its own what it can, and let it insert runtime checks for the other cases.

And add some way for the programmer to declare that eg "warn me if this can't be optimized" or "trust me, this is safe" or even "here's a proof for you".

But in any case, dependent types are possible---undecidability is not a hard barrier here.

Re:Undefined Behavior in 2017 by yorwba on Wednesday July 05, 2017 @12:27PM (#14703786)
Aren't dependent types able to express any statement formalizable in predicate logic? This should include most things you might want to say about the correctness of non-evil programs. I think the real problem with them is that type-checking itself becomes undecidable, so you get the additional problem of proving that your program is indeed correctly typed.
Re:Undefined Behavior in 2017 by tom_mellior on Wednesday July 05, 2017 @06:12PM (#14706520)
Here are two nice blog posts on the state of the art of this "not too hard" problem: https://maniagnosis.crsr.net/2017/06/AFL-brute-force-search.... https://maniagnosis.crsr.net/2017/06/AFL-bug-in-quicksearch....

Possible? Yes. Too time-consuming and fiddly for the economic realities of 99.9% of all programmers? Yes, that too.

Re:Undefined Behavior in 2017 by pjmlp on Thursday July 06, 2017 @01:54AM (#14708420)
The economic realities would be quite different if software companies were legally accountable for their defects, just like in many other industries.
Re:Undefined Behavior in 2017 by eru on Monday July 10, 2017 @04:20PM (#14739286)
That would mostly mean that only big companies that can afford a herd of lawyers would be able to produce software.

At least that how bank regulation works out in practice.