• Animats an hour ago

    The trouble with formal specification, from someone who used to do it, is that only for some problems is the specification simpler than the code.

    Some problems are straightforward to specify. A file system is a good example. The details of blocks and allocation and optimization of I/O are hidden from the API. The formal spec for a file system can be written in terms of huge arrays of bytes. The file system is an implementation to store arrays on external devices. We can say concisely what "correct operation" means for a file system.

    This gets harder as the external interface exposes more functionality. Now you have to somehow write down what all that does. If the interface is too big, a formal spec will not help.

    Now, sometimes you just want a negative specification - X must never happen. That's somewhat easier. You start with subscript checking and arithmetic overflow, and go up from there.

    That said, most of the approaches people are doing seem too hard for the wrong reasons. The proofs are separate from the code. The notations are often different. There's not enough automation. And, worst of all, the people who do this stuff are way into formalism.

    If you do this right, you can get over 90% of proofs with a SAT solver, and the theorems you have to write for the hard cases are often reusable.

    • readthenotes1 an hour ago

      Some realized that building the tests was the more important part of writing the software long ago...

      Test tables and scenarios may not cover all the things that can go wrong (a la Goëdel), but not doing them almost guarantees broken software.

      • jackblemming an hour ago

        Whenever you look closely at what these proof nerds have actually built you typically find… nothing. No offense to them, it’s simply reality.

        • AlotOfReading an hour ago

          SeL4, a number of mathematical theorems, a bunch of cryptography. You've likely trusted your life to compcert. It's not nothing, but it's admittedly a bit limited.

          Formal methods are the hardest thing in programming, second only to naming things and off by one errors.

          • atomicnature 31 minutes ago

            Leslie Lamport built latex, most of distributed systems such as AWS services depend on formal verification. The job of Science here is to help Engineering with managing complexity and scale. The researchers are doing their jobs

            • ofrzeta 7 minutes ago

              What does LaTeX have to do with TLA+? Also I think "most of distributed systems such as AWS" might be an exaggeration. At least the public known examples of formal verification in AWS are scarce.

              • MangoToupe a minute ago

                I think the implication is that Lamport is a proof nerd, not that LaTeX has a direct relationship to proof software.