News for hackers. Stuff that matters.
Re:A small British firm shows that software bugs aren't inev... by stevoski on Thursday October 22, 2015 @05:29AM (#10431255)
Even algorithms "proved" correct sometimes turn out to have bugs:

"I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug."

That's from Joshua Bloch's discovery in 2006 that Java's binary search implementation was broken: http://googleresearch.blogspot.com.es/2006/06/extra-extra-re...

Re:A small British firm shows that software bugs aren't inev... by efaref on Thursday October 22, 2015 @05:40AM (#10431290)
Interesting. The bug in the proof is in the assumption that ints contain any integer and addition operates the same in normal mathematics, when in fact they're the set of values in [INT_MIN, INT_MAX] and addition has overflow behaviour.

Arguably addition (or any operation) that overflows with signed integers ought to cause some kind of SignedIntegerOverflow exception. If you want to do modulo mathematics in the set of [0, 2^n) then you should explictly use unsigned integers, which are defined to work that way.

Re:A small British firm shows that software bugs aren't inev... by pjc50 on Thursday October 22, 2015 @06:05AM (#10431368)
I've been seriously considering doing a mini programming language where you can type-decorate numbers with exactly what behaviour you want and what their range is.

So you could have "integer, range [a-b), exception on overflow" or "integer, 32-bit, unsigned, wrap" or "integer, 8-bit, signed, saturates" (the latter is useful in codecs and often available in assembly).

Re:A small British firm shows that software bugs aren't inev... by andy_ppp on Thursday October 22, 2015 @06:52AM (#10431481)
While not integer/number specific I like the idea of Guards in Elixir:

    def sum(a, b) when is_integer(a) and is_integer(b) do
      a + b
    end

    def sum(a, b) when is_list(a) and is_list(b) do
      a ++ b
    end

    def sum(a, b) when is_binary(a) and is_binary(b) do
      a <> b
    end

    sum 1, 2
    #=> 3

    sum [1], [2]
    #=> [1,2]

    sum "a", "b"
    #=> "ab"
Re:A small British firm shows that software bugs aren't inev... by arethuza on Thursday October 22, 2015 @07:45AM (#10431629)
That's pretty nice - like CLOS multiple dispatch with arbitrary predicates rather than types.

Are there any restriction on what the code in the guards can do?

Re:A small British firm shows that software bugs aren't inev... by lectrick on Thursday October 22, 2015 @07:59AM (#10431673)
Yes.

But the guard code are just macros, so... ;)

But I do believe that Erlang underneath does have actual limits.

Re:A small British firm shows that software bugs aren't inev... by lifeisstillgood on Thursday October 22, 2015 @07:20AM (#10431540)
That's it - going to set aside some time for getting Elixr on my bare competence skill set. I love that
Re:A small British firm shows that software bugs aren't inev... by revelation on Thursday October 22, 2015 @06:09AM (#10431377)
I think they call that Ada. (not sure on the overflow behavior, but ranges are in)
Re:A small British firm shows that software bugs aren't inev... by david-given on Thursday October 22, 2015 @07:38AM (#10431607)
Ha ha. I'd been reading HN on my phone, saw the parent comment, thought 'I should write a post about Ada', and when I got back to my computer, saw this...

Yes, ranges work. They (and ordinary integers) throw exceptions on overflow:

    type NonoverflowingByte is integer range 0..255;
If you want modulus arithmetic, you specify it:

    type OverflowingByte is mod 256;
Modulus types seem to be always unsigned and are always 0-based. Anyone know different?

For saturating arithmetic, there doesn't seem to be built-in language support. (There isn't even a standard library package. That seems to be a bit of an omission. Isn't saturating arithmetic common in the kind of real-time environment where Ada is used?)

Ada so totally deserves to be better known.

Re:A small British firm shows that software bugs aren't inev... by pjc50 on Thursday October 22, 2015 @07:47AM (#10431635)
> Ada so totally deserves to be better known

I do wonder why it isn't. It's probably handicapped by its history: once people have written off a language they'll never look at it again, despite improvements to fix the very problems they fled.

As an Ada advocate, what does it do badly? String processing? Networking?

Re:A small British firm shows that software bugs aren't inev... by david-given on Thursday October 22, 2015 @09:00AM (#10431907)
It's got a lot of historic warts. e.g. the OO system is a retrofit with invisible syntax: functions defined immediately after the type representing the object are methods, but you can't interleave them with other statements. It desperately needs an explicit `class...end` structure. The OO model is kinda weird, too, although once you've beaten your head against it it makes sense. Another wart is that you can only define an expression function in a module specification and not in a module body. Huh? Likewise, you can only define pre- or post-conditions on public data, so you can't have a module assert on its private state; you must export the state first.

String processing is both really nice and a pain. Built-in strings are fixed size, but the `array<>` magic means you do string processing using functional style without needing to explicitly size anything. The string libraries are a bit of a mess, with `Wide_String` and `Wide_Wide_String`, because they made the same mistake as Java and Windows about UCS-2 vs Unicode.

The standard library is mostly really cool, but it makes the same mistake C++ does in that entries in collections are always initialised by copying, so you can't have collections of non-copyable objects. I forget the details but I think the last time I tried to do collections of pointers I couldn't make it work properly.

Ada's generics are awesome. Nested functions that work properly are awesome. The compilation time is awesome. Access semantics that prevent you leaking pointers to inner stack frames are awesome. in-out parameters are awesome (they mostly replace pointers). Being unable to pass a nested function to a procedure as a callback parameter is less awesome; the access semantics forbid it.

To my mind, though, the biggest showstopper in Ada is a technically fairly trivial thing: it's case insensitive. This means that any programmer used to case sensitive languages, which is basically any programmer, will have to drastically revamp their coding style to work with Ada, because none of the usual conventions about separating locals from globals by capitalisation work any more. It also makes Ada code look ugly to the untrained eye. It's hard to convert people when the first thing they say when looking at code is 'ugh'.

Re:A small British firm shows that software bugs aren't inev... by CyberDildonics on Thursday October 22, 2015 @04:00PM (#10434660)
> same mistake C++ does in that entries in collections are always initialised by copying, so you can't have collections of non-copyable objects

Cool breakdown. This isn't true anymore in C++11 with move semantics.

Also the expression functions only being in module specifications is probably due to their source code being needed to inline them.

Re:A small British firm shows that software bugs aren't inev... by i_feel_great on Thursday October 22, 2015 @09:01AM (#10431917)
Ada is up against C, C++, C# and Java. They all have larger everything - libraries, pool of programmers, support companies etc. Ada is doomed to spend its lifetime in the shadows. Pity, it is superior to all these languages, at least in my experience.
Re:A small British firm shows that software bugs aren't inev... by CyberDildonics on Thursday October 22, 2015 @04:02PM (#10434672)
With LLVM and the JVM making languages is easy, but making tools and the whole experience is difficult.
Re:A small British firm shows that software bugs aren't inev... by reacweb on Thursday October 22, 2015 @06:58AM (#10431496)
Yes, Ada is a marvellous language. The exception is not named overflow, but constraint error. When used correctly, its typing system is very effective to avoid mistakes. The problem is that Ada types can become very annoying in bad code like the one produced by people with a very weak knowledge of the language. It is really too sad this language is almost not teached anymore in school.
Re:A small British firm shows that software bugs aren't inev... by AndyMcConachie on Thursday October 22, 2015 @06:16AM (#10431395)
You might also argue that SQL shares some of these characteristics.
Re:A small British firm shows that software bugs aren't inev... by creshal on Thursday October 22, 2015 @06:40AM (#10431458)
It does. It also makes for a rather… clumsy general-purpose language.
Re:A small British firm shows that software bugs aren't inev... by vidarh on Thursday October 22, 2015 @06:53AM (#10431486)
Pascal also has ranges. "VAR foo : 42...56;"

Don't remember how it handled overflow.

Re:A small British firm shows that software bugs aren't inev... by CyberDildonics on Thursday October 22, 2015 @03:50PM (#10434571)
Look at Ada first and see if there is anything missing.
Re:A small British firm shows that software bugs aren't inev... by tekacs on Thursday October 22, 2015 @05:51AM (#10431319)
'Beware of bugs in the above code; I have only proved it correct, not tried it.' - Donald Knuth, 1977
Re:A small British firm shows that software bugs aren't inev... by brodo on Thursday October 22, 2015 @05:48AM (#10431306)
There is a Google tech talk called "The Remote Agent Experiment: Debugging Code from 60 Million Miles Away" where the speaker describes how they did a proof that their code was deadlock free but it still ran into a deadlock. (I don't remember the details)
Re:A small British firm shows that software bugs aren't inev... by sqldba on Thursday October 22, 2015 @07:29AM (#10431574)
Link for the apathetic and disaffected https://www.youtube.com/watch?v=_gZK0tW8EhQ
Re:A small British firm shows that software bugs aren't inev... by bhrgunatha on Thursday October 22, 2015 @06:23AM (#10431415)
Maybe he probably proved the mathematical algorithm was correct. The problem is we have to implement algorithms using machines, which aren't perfect. They do a great job most of the time, but they exist in a physical environment which has restrictions and outside influences.

We can only work with the tools and techniques we've discovered so far. Later, we find situations or results that show our tools or techniques aren't correct or aren't good enough and we improve them to cover the new situations.

Re:A small British firm shows that software bugs aren't inev... by knappador on Thursday October 22, 2015 @06:32AM (#10431437)
Safe points, jit, and VM all introduce extra layers of complexity. I bet it's definitely harder in the context of the JVM muddying up the picture.
Re:A small British firm shows that software bugs aren't inev... by gohrt on Friday October 23, 2015 @12:23AM (#10436789)
Sure. You can trivially prove any algorithm is correct, if you abstract away enough details, where the devil lives.
Re:A small British firm shows that software bugs aren't inev... by PhantomGremlin on Thursday October 22, 2015 @05:50AM (#10431312)
I've seen that example before, but I don't like it. It's an example of fixed-point overflow, but it wouldn't occur in practice.

It would manifest itself with 32-bit integer indexes and with arrays of greater than 2^30 elements. So phooey. You can't even fit that many array elements into a 32-bit address space. And if you're in a 64-bit address space, you should be using 64-bit indexes.

Whine: way back in the 1960s, the IBM S/360 threw a fixed-point overflow exception (okay, to be pedantic, they called it a "program interruption", but it's the same idea) when you did that. Sadly, the Fortran compiler of the day masked it. And this same philosophy has carried over to today. About 99 times out of 100, fixed point overflow is bad, why is it being masked off?

Re:A small British firm shows that software bugs aren't inev... by andrewmu on Thursday October 22, 2015 @06:13AM (#10431390)
Java only allows signed 32-bit integers as array indices. It 's a compile time error to access an array with a long index (http://docs.oracle.com/javase/specs/jls/se8/html/jls-10.html...).
Re:A small British firm shows that software bugs aren't inev... by Alphasite_ on Thursday October 22, 2015 @03:47PM (#10434548)
Not every language masks it, Swift certainly doesn't.
Re:A small British firm shows that software bugs aren't inev... by georgerobinson on Thursday October 22, 2015 @05:41AM (#10431292)
Can you elaborate on this further?

Would this mean that Bentley's proof was in fact incorrect (i.e. not a valid proof at all) or that it simply didn't consider integer overflow for fixed size ints?

I wonder to what extent the implementation (i.e. the size of the integer type used) should affect the proof that an algorithm is correct?

Re:A small British firm shows that software bugs aren't inev... by chriswarbo on Thursday October 22, 2015 @08:08AM (#10431710)
I suppose different people may answer your questions in different ways, depending on how they define words like "proof" and "correct". I would answer like this: the proof was correct, but it was solving the wrong problem (unbounded ints rather than bounded).

Inside a formal system it's relatively easy to understand what's going on; the real difficulties are at the boundaries: how do we build a formal model of a real system, and how do we translate formal results back to the original system? It's a lot like programming: manipulating data is easy, the problems are getting the right data and interpreting what the output means.

In this case, the model didn't capture overflow; so the proof is valid for that model, but it's not a useful model for Java's ints.

Re:A small British firm shows that software bugs aren't inev... by pdpi on Thursday October 22, 2015 @06:10AM (#10431383)
The exact size doesn't matter nearly as much as the fact that it has a bounded size. That changes the algebraic structure your proof operates on — and proofs on finite fields are often either general or at least give you results that explicitly depend on the size of the underlying set.