I love TLA+ to describe systems precisely yet succinctly and reason about them. But as someone who's been using formal methods to help software development for many years, this whole industry around tools to connect such a wonderful mathematical language and others like it, like Lean, with AI, to the point of hiding the reasoning from people, confuses me.
Proving programs correct end-to-end (i.e. code to high-level properties) - as this company and others purport to do - is so difficult that humans have only been able to do it for very small programs (~10KLOC) and even then, in very specialised cases, where the programs have been written in an extra-simple way (often at the cost of performance, because performance often requires more complicated algorithms). If AI becomes at least an order of magnitude more capable than humans at software development, which is what will be required for this task, would it need our help to write various tools and harnesses that help with the task? After all, writing these tools is so much easier than using them for that goal that I don't understand the hypothesis behind AI capability here.
This company says: they're "developing the agentic frameworks to make these correctness guarantees accessible to all software engineers". But developing all that is the easy part! If AI can do the hard part, why does it need our help to make this accessible, it can surely find a way to do that easy part itself! It's like saying, "Soon we'll have a machine that can harness so much energy to boil an ocean; we've built a service that lets you order a taxi to take the machine to the beach!"
Why would an AI that is so much better than us at writing software need our help writing any kind of software for it?
I have long being fascinated by the the field and curious about it on an amature level, i took some basic proof verification and distributed computing classes back in the grad school days, but I'm clearly not an expert in the field by any means. From the article, it seemed like there are plenty of "traps" that i did not even consider - starting from lean hatches like assume(false), expressive power of TLA+ (CTL, ATL), and ofc challenges of tying an real implementation to a proof. To me all three of the above seem challenging enough to deserve their own tools, and i would appreciate smart people putting effort into addressing these rough edges.
Question to you: i can understand how proof verification like z3 or lean requires a special language and an inference engine; given that model checkers like tla+ are mostly about exploring possible program states and checking properties of such states and chains of states, i do not quite understand why it can't be done with a conventional imperative language to express state transitions and invariants - especially an interpreted one like python (esp with continuation support) or a language targeting a vm like wasm where one should be able to snapshot program state?
TLA+ is not a model checker. It's a general language for writing mathematics, akin to Lean, only Lean focuses on high mathematics while TLA+ focuses on dynamic systems. There are a proof checker and at least one model checker that work on subsets of TLA+.
As to why TLA+ is better at describing systems than programming languages, the reason is that it's much more general. It can say things like "a routine that sorts in a quadratic number of steps or less" rather than a specific sorting algorithm, and it allows stating (and proving) that a specific sorting algorithm matches that description or not. Most TLA+ formulas are too abstract to be run by a computer (i.e. they describe too many potential algorithms), but that's exactly what makes them useful to describe things when either you don't care about the details or you want to show that a particular algorithm implements a general property.
BTW, even algorithms like Quicksort are, themselves, too general to be accurately described by a programming language (i.e. a language that can be executed). Quicksort doesn't specify how a pivot is chosen (it doesn't matter for the correctness), it doesn't specify how that partitioning is done (ditto), and it doesn't specify in what order the recursion is done or perhaps even in parallel (ditto). Yet a computer needs to be told all these details to run an implementation of Quicksort, even though the algorithm works, and can be proven to work, no matter what these details are. In a language like TLA+ you can say how to choose a pivot or you can say "a pivot is somehow chosen" (which covers all possible mechanisms for choosing one).
Also, TLA+ is much simpler than a programming language and obeys simple and intuitive substitution rules - e.g. `x = 3` is equivalent to `3 = x` and `x = y + 1` is (almost) equivalent to `x - y = 1`, which is what you want when you're after clarity. It's just different from programming languages (because it's maths), so it's a different, though simpler, kind of language to learn.
Many languages can do that (Ada SPARK, Dafny, even Java with JML, and quite a few more), but there are really two languages here, the spec language and the program language. The spec language isn't executable, and the program language doesn't spec. What TLA+ does is offer a a single continuum, with a language that's much simpler than both Eiffel's spec language and its program language, and can describe anything at arbitrary precision. It can describe the QS algorithm in general, and it can describe the activations of the logic gates in the CPU as a specific QS runs on a specific machine, and it can take any description of QS, at any level, and show the abstraction/implementation between them. Again, this is all in a language that's much simpler than Python, and that allows reasoning directly in the language because it supports substitution and all the normal manipulation capabilities we expect from mathematical formulas.
pron · · focus · HN ↗
Proving programs correct end-to-end (i.e. code to high-level properties) - as this company and others purport to do - is so difficult that humans have only been able to do it for very small programs (~10KLOC) and even then, in very specialised cases, where the programs have been written in an extra-simple way (often at the cost of performance, because performance often requires more complicated algorithms). If AI becomes at least an order of magnitude more capable than humans at software development, which is what will be required for this task, would it need our help to write various tools and harnesses that help with the task? After all, writing these tools is so much easier than using them for that goal that I don't understand the hypothesis behind AI capability here.
This company says: they're "developing the agentic frameworks to make these correctness guarantees accessible to all software engineers". But developing all that is the easy part! If AI can do the hard part, why does it need our help to make this accessible, it can surely find a way to do that easy part itself! It's like saying, "Soon we'll have a machine that can harness so much energy to boil an ocean; we've built a service that lets you order a taxi to take the machine to the beach!" Why would an AI that is so much better than us at writing software need our help writing any kind of software for it?
bbminner · · focus · HN ↗
Question to you: i can understand how proof verification like z3 or lean requires a special language and an inference engine; given that model checkers like tla+ are mostly about exploring possible program states and checking properties of such states and chains of states, i do not quite understand why it can't be done with a conventional imperative language to express state transitions and invariants - especially an interpreted one like python (esp with continuation support) or a language targeting a vm like wasm where one should be able to snapshot program state?
pron · · focus · HN ↗
As to why TLA+ is better at describing systems than programming languages, the reason is that it's much more general. It can say things like "a routine that sorts in a quadratic number of steps or less" rather than a specific sorting algorithm, and it allows stating (and proving) that a specific sorting algorithm matches that description or not. Most TLA+ formulas are too abstract to be run by a computer (i.e. they describe too many potential algorithms), but that's exactly what makes them useful to describe things when either you don't care about the details or you want to show that a particular algorithm implements a general property.
BTW, even algorithms like Quicksort are, themselves, too general to be accurately described by a programming language (i.e. a language that can be executed). Quicksort doesn't specify how a pivot is chosen (it doesn't matter for the correctness), it doesn't specify how that partitioning is done (ditto), and it doesn't specify in what order the recursion is done or perhaps even in parallel (ditto). Yet a computer needs to be told all these details to run an implementation of Quicksort, even though the algorithm works, and can be proven to work, no matter what these details are. In a language like TLA+ you can say how to choose a pivot or you can say "a pivot is somehow chosen" (which covers all possible mechanisms for choosing one).
Also, TLA+ is much simpler than a programming language and obeys simple and intuitive substitution rules - e.g. `x = 3` is equivalent to `3 = x` and `x = y + 1` is (almost) equivalent to `x - y = 1`, which is what you want when you're after clarity. It's just different from programming languages (because it's maths), so it's a different, though simpler, kind of language to learn.
senderista · · focus · HN ↗
<a href="https://bertrandmeyer.com/2014/12/07/lampsort/" rel="nofollow">https://bertrandmeyer.com/2014/12/07/lampsort/
pron · · focus · HN ↗