Live data from Hacker News

How Did Software Get So Reliable Without Proof? (1996) [pdf]

gwern.net

31–40 of 126 posts

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#31

Are there any research projects trying to make "proof" programs / languages?

Dependently typed languages may fit what you're asking for. See Idris and the book Type-Driven Development with Idris for an example of encoding critical information into the type system.

Beyond that, see SPARK where you're limited to a provable subset of the Ada language (the subset has been extended with each version) so you can make assertions and it will attempt to prove (as part of compilation) that the assertions hold. As in, you could have a function that should always return a non-negative integer, but if it does something like (not fluent, so may be wrong but the principle is correct):

  function Foo(A : Integer; B :integer) return Integer with
    Post => Foo'Result > 0;

  function Foo(A : Integer; B : Integer) return Integer is
  begin
    return A - B;
  end Foo;
This should fail when the proof checker is run on this program.

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#32

One thing I would think helps software is Linus's law: "Given enough eyeballs, all bugs are shallow". https://en.wikipedia.org/wiki/Linus%27s_law As far as I know, this is not something available to other forms of engineering.

"Given enough projects, all eyeballs are elsewhere."

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#33
post #16

Earlier quoted context omitted.

Because traditionally, articles were published in journals, and journals had the date written on the cover, so it was superfluous to add it on every page.

That seems rather sloppy to start with: you could easily end up a year or two out (the date that matters isn't the date of publication, it's the date that was in the author's head when they wrote something like "Twenty years ago"). In any case nowadays I think there's no excuse for this practice continuing. It's far too common for a paper to get sent around, or put on the author's personal website, with no associated…

Some journals have the date of submission and the date of acceptance in the paper header for this reason. Unfortunately, it is not a common practice.

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#35

It didn't - but most errors are simply tolerated because imperfect automation still has absurd economy of scale, very few applications are on a regulated field or have a well-defined quality standard to meet, and unreliable software tends to at least fail consistently, so it's still a win to diagnose and fix processes compared to humans making creative mistakes.

It is also replacing humans most of the time as well, who are prone to making all sorts of errors. Worse, humans can make the same error twice even after being corrected.

Software can also make the same mistake, thousands of times per second or more :)

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#36
I am usually programming in Haskell (the little programming I do besides research) and I try to do property based testing a lot. And of course, you have to come up with the properties to test for when generating test cases.

With a proof doubly so, as you need a specification that you can prove your implementation against. In my time in industry (YMMV) I think I've never seen a formal enough specification that would be useful in that sense.

I think we're in a specification crisis where behavior is unspecified and documentation diverges from that as well. APIs break regularily and services are down daily. It's a miracle the whole house of cards has not come down yet.

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#38
post #8

Earlier quoted context omitted.

I don't think that's true, or at the very least it's misleading. Qualified eyeballs are often expensive, and moreover there are consistent intellectual biases of human beings that interfere with catching all bugs.

Though the 'law' is associated with reading source code, I think it can also apply to people using the code, and reporting errors (sometimes automatically). They may not be able to fix it, but just noticing there is a problem is a big first step.

Sure, I'm just saying in reality it's not as ideal as it would seem. You're not going to get thousands of new qualified people reading every codebase every year, things will inevitably slip through the cracks, and at a guess open-source lines of code probably have fewer people reading them net than all currently maintained proprietary software, just because there is so much vastly more open source software these days.

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#39
In my view, type systems have replaced formal methods as the main way of enforcing guarantees around program behavior. Type systems are conceptually simpler, and although they aren't nearly as powerful as formal verification, they're good enough for many common purposes.

Re: How Did Software Get So Reliable Without Proof? (1996) [pdf]

#40

One thing I would think helps software is Linus's law: "Given enough eyeballs, all bugs are shallow". https://en.wikipedia.org/wiki/Linus%27s_law As far as I know, this is not something available to other forms of engineering.

"No one reads anything. Those who do read, they do not understand. Those who do understand, they immediately forget."

"Linus's law" is refered to as "Linus's fallacy" now.

Post reply on HN