We have proof automation now
imperialviolet.org
imperialviolet.org
I spent some time exploring this topic. Here's my thesis: Formal verification was expensive. 20x expensive compared to just developing the software, as the author notes. The cost of finding and developing exploits also was high. That creates an incentive to put software verification aside, since it solves a relatively small problem, at an extremely high cost.
We've seen how Mythos has found more vulnerabilities than the rest of the security industry combined. (you can argue about the quality and what counts as a vulnerability, but not the point) So the cost of finding and developing exploits has dropped dramatically.
On the other hand, formal verification is now much easier, since LLMs can automate the proof. You don't even need to worry about hallucinations, you merely need to trust Lean core. If the LLM is wrong, the proof will get rejected!
The problem of exploits gets bigger, and the solution of formal verification gets cheaper. As a result, the needle is now moving in the direction of "more formal verification".
I, personally, think that it is ridiculous that ~none of the software we use is known to work correctly. It just happens to work correctly, most of the time.
My (ambitious) goal is to have a self-hosting, formally verified compiler, which allows proof transfer from source code down to assembly. I have not achieved that goal yet.
What I have so far:
- one (non-optimized) compiler step which is formally verified
- three simple functions (hex, hex with labels, strtoull) formally verified, against RISC-V assembly, and against a custom IR
https://github.com/m1el/riscv-fv-bootstrap
The project is in quite a bad shape, and I am trying to improve my skills in that direction.
Here's the list of projects which I'm aware of: https://github.com/m1el/riscv-fv-bootstrap/tree/master/docs/...
Speaking of how difficult can it be to write a proper spec, I think a few years ago someone found a bug in spec in a helloworld-like example in a book about formal methods, and a bug in the code.
You still need to verify that the generated code is what you asked for, though.
What is that supposed to mean?
> It generates Lean code, and conveniently, in Lean, the code is also the proof. It’s not merely a model of the stated system, it is the system.
Yes, and that's great. (Though, of course, the computer doesn't execute lean directly, it gets translated first.)
> You still need to verify that the generated code is what you asked for, though.
Yes, but you only need to read the theorems, not the proofs nor code.
First, the same kind of issue exists with any kind of testing. We all know that having unit tests and integration tests doesn't mean the software is correct and bug-free. Yet we still often believe it's worth investing in writing and maintaining a test suite. Formal methods is an additional level of assurance that I suspect we'd generally find worth it for critical software if it were easy enough to implement, even if it's not perfect.
Second, because formal verification has been so hard, nobody has really bothered making a serious attempt at solving the spec problem before (at least not to my knowledge). We've spent decades building frameworks that make writing tests really easy. We really have not come close to investing the same kind of effort into building frameworks and tools to make writing formal specs easy. I can imagine a world where we have sophisticated tools that help us create specs, plus real-time verification infrastructure that automatically reverifies code against the spec on each PR.
Third, and perhaps most importantly, there are many industries where this is actually low-hanging fruit: aerospace, medical devices, etc., actually already have formal specs that are verified manually by human engineers to satisfy certification requirements. I believe that's a more natural starting point vs. trying to scale formal methods for all software in general.
Proving that some complicated algorithm is actually what you think it is, even after you've proved that it does whatever it is it does, is hard. But to me, and me personally so not necessarily what everyone else thinks, that's not really what I'm interested in from proofs. I'm really more interested in these overarching declarations of what the code definitely doesn't do, or putting bounds on what it does, rather than proving that my billing code bills the customers precisely in the way I expect, when, frankly, the best specification of it I have is already what is in the unproved code base anyhow. I believe those have a very sensible story as to how both humans and AIs can use those assertions.
I don't know. It seems to match the general futility of pedantry that exists in all professions. Yes, you can try to optimize for absolute 0 flaws in your code, but in a world where a CPU itself may have bugs in the way it executes assembly, that seems a bit silly beyond a certain point.
CPUs are tested so so much more thoroughly than any software today. Including using formal proofs.
If the chance of a CPU bug is something like 1/10^6 and each module in your software is 1/10, reducing that to 1/100 makes a bog difference.
I fully agree! I'm all for moving the needle towards moving the needle towards more formal verification, but what GP is suggesting is full verification of programs, which is more akin to trying to achieve a 1/10^6 bug rate.
Lots of security bugs are caused by incorrect specs from misunderstanding the problem and a formal verifier can’t fix these. Humans can’t think through every situation either (or the bugs wouldn’t exist) SMS that’s doubly true because NOBODY understands all the interactions of the system as a whole and how changes in the part they understand affect everything else.
I’m not saying formal verification is bad, but it’s not a panacea and I’d wager would only fix a small percentage of existing bugs.
* Understandable
* Portable across projects, you could imagine something like
from specs import no_stealing_secrets
no_stealing_secrets(secret_table)
* Implicitly proves the absence of RCE, though I suppose
it could allow something truly crazy like an interpreter
that will run any attacker supplied program that can
be proven not to steal the specified secretsMy issue is that the systems today can't even tell for certain "This network-connected program doesn't execute arbitrary code".
We can have a common list of our demands to software. We can eliminate entire classes of issues. We can understand what the software does.
But... if that's not the point, the claim is obviously untrue. The security industry includes public-facing bug bounty platforms. Those find far more vulnerabilities than Mythos ever will, if you're not even worried about what counts as a vulnerability.
https://github.com/orbitalhigh/subrust
How does LowIRSSA compare to P1pp from boot2 ?
LowIRSSA looks way more like SSA-WASM than assembly
Verus (https://github.com/verus-lang/verus) is a good start for the rust ecosystem, but it's essentially a standalone language today (with custom syntax and type system).
Versus appears to just be a formal verification tool. Perhaps I misunderstand?
You want the formal verification built into the language because the tooling can start to get really crazy good. Agda is the dependantly typed language I've used the most (long ago), and the tooling was interactive in a helpful way I've never experienced with other languages.
You don't want a separate language used to verify a base language, because then everyone ends up having to know two languages. Looking at the history of computing though, I wouldn't be surprised if this happens.
The actual programming language and the verification language can be the same language though, if we want.
I'm also playing around with using the lean's compile-to-C tooling to instead compile to rust instead and it's getting more of my focus than the lean-via-verus route right now.
if people are interested, ping me and i can put them up on gh.
So this stuff is always going to be additive and concerned with edge cases, as almost by definition, stuff that isn't edge cases will be found by comprehensive enough testing procedures.
And yet most software doesn't really need to be correct under edge cases, outside of security and data loss issues. People can tolerate a lot of incorrectness in other areas because it's just annoying, not critical.
Security is a case where formal methods could help, but I don't think LLMs will change the industries lack of interest. If anything it'll reduce it even further. Historically security took place in a fog of war. You don't know your enemies capabilities and may not be able to easily match them. But now LLMs are better at finding security bugs than most (all?) humans and ~everyone has access to them, so, from a liability perspective, all you have to do is point a frontier LLM at your codebase and let it fix as many bugs as it can find. Your enemies don't have access to anything better, so once it's done you can tick the box and say security is good enough. Meaning, nobody will fire you if there are still attacks possible.
So in the end I don't see LLMs changing the adoption formal methods.
"Writing formal specs" means simply programming, taking a step upward in programming language abstraction level, and whether it's going to be easy remains to be seen.
All type checkers are theorem provers, btw, that's just Curry Howard. The question is exactly how expressive they are.
Suppose that you have managed to write a non-trivial piece of software with dependent types encoding all sorts of properties everywhere. The actual computation and proof are intermingled. Think of the author's innocent bound-check proof in the zstd decoder, but across the whole program, with more elaborate properties and longer proofs.
Suddenly, you realize that you need to prove a new property of your program. Can you keep your existing work and build on top of it? In general, no, you have to refine every dependent type everywhere by adding a new conjunct expressing a new invariant, and adapt every proof, as the new property is threaded in the existing program.
That is because dependent types (and other staples of naive approaches to proving program properties, like a unique invariant per loop) structure the program along the wrong dimension: they encourage grouping everything that concerns a value ("put this value in a dependent type that encodes everything known about it") or a program point ("write the precondition for this function as a big conjunction mixing all the concerns"), where it works much better, for long-term maintenance, to structure the development along concerns: computational parts of the program, basic functional properties and absence of UB, termination, other functional properties, security, etc., where each layer builds on top of the previous ones without requiring them to change.
That is not to say that dependent types do not have their use. Where they shine is at module boundaries. Consider a library that exposes an opaque type and operations on it. Users of the library can only build and modify values of that type through the library's API. This type should be a dependent type. If it needs to be refined at any point to encode a new invariant, this will have no impact on the library's users, since all they do is pass around values without interpreting them. However, inside the library, I would recommend unpacking/repacking the dependent type at the library's entry points and handling the concerns separately.
Type theory, especially dependant types, are a pretty recent development, and aren't really used in practice in math. Even in Mathlib (what most people mean when they say they've used lean), they encode first order logic. The proofs are dependently typed, but the actual logic of the proof is all in ZFC.
Having to do this is a sign that the new property depends on implementation details in some way. This can definitely feel like annoying busywork when there is only one reasonable implementation. Of course your sorting algorithm doesn't change the multiplicity of elements in the array, you wouldn't write a bug like that. Of course your sorting algorithm doesn't change the order of elements that are already sorted correctly, you wouldn't write a bug like... except unstable sorting algorithms do that and are widely used for performance reasons. So you do have to check your actual implementation step by step to verify that it really does what you think it must of course be doing. Trying to separate the concerns does not change this.
For example, take Hoare's while rule (see https://en.wikipedia.org/wiki/Hoare_logic#While_rule). If you have already proved
{P∧B}S{P}
{Q∧B}S{Q}
{P∧Q∧B}S{Q}
{P∧Q∧B}S{P∧Q}
Yes, and a program is most compact when all modules have been merged, and all functions with a single caller inlined. We have compilers with LTO for that, though; we would never maintain source code in that form.
Snark aside, I get your point about restating the program code, but this can be alleviated by interactive proof assistants that largely reduce the length of proof scripts. This is mostly a matter of tooling.
def function_spec bleh blah := math_blargh
def function_impl bleh blah := code_blargh
theorem function_correct: forall bleh blah, function_impl bleh blah = function_spec bleh blah := by { long proof }
Maintenance is still a headache. If you change a small piece of your code, you would then need to change all the proofs that refer to it, and then if the specs also changed then you need to change all proofs that refer to those specs, etc.
They can also be used to enforce just enough constraints on the inputs of a function to make it total, but this comes down to the tradeoff between either leaving an error path in the program and proving its unreachability later, or not having this error path but immediately requiring the proof. In any case, as you mention, further properties can be proved later without altering the dependent type.
I do not intend to come off as overly negative about dependent types. They have their uses, but they can also bring a maintenance nightmare.
I'm currently developing a unikernel in idris2, and the experience is very pleasant (unfortunately, I'm not quite ready to share it yet).
I'm not convinced that this is much more true than the claim "correct code doesn't scale". If you add to your code in a way depends on a new property for correctness, and the code was not previously written with awareness that the new property was necessary, then you need to check through the rest of your code and make sure that the property is maintained. Formally verifying things is painful because it actually makes you check this.
Instead, we live in a world where we use software that is not completely correct. Browsers have remote code execution vulnerabilities because people who make browsers decided it's more important that javascript can run quickly, and that new standards get implemented, than that we avoid such vulnerabilities at all costs.
I understood you to be saying "bundling is encouraged", in the sense of
https://leanprover-community.github.io/glossary.html#bundled...
I'm not sure it's encouraged. I agree that it felt natural to define a type like NonNegativeInteger, or a wrapper type like `Sorted(T)` to indicate that that wrapped list is sorted. But I think this is an area of style and aesthetic that is still emerging, far from ossified.
The problem of "threading" new things within existing programs is an important one to address, and it has multiple solutions (context management, dynamic scoping (lol), implicit arguments, type classes). I am curious if the claim of "does not scale" is mitigated by one of those solutions...
Eventually I did take a look at all the new code, and found that one of the main features had been implemented completely backwards, in a way that was pointless and completely defeated the purpose.
(An LLM also pointed that out, so I guess it must have been a different one which implemented it? I'm trying to get them to sign their names in the commits...)
These new models are very thorough and responsible however, so of course it had written a copious number of tests, and of course all the tests passed! I found this very amusing. It had diligently proven the correctness of the incorrect functionality!*
I've been thinking about how cool it is the AI can assist with writing proofs now, and how we can use this new ability to boost the correctness of our code. It later occurred to me, however, that formal verification would not have helped in this case. It would have just formally verified that the wrong thing was correct!
--
*Yeah I know tests prove the presence of bugs but not their absence. Couldn't think of a better way to phrase that though.
He was a mathematician and was convinced that formal methods were the future of software engineering. He also loved handwaving that due to Godel's incompleteness theorem, humans were necessary to introduce creative insights (new axioms) that computers would never be able to do.
I eventually obtained top marks both semesters and left convinced that formal methods are a waste of time in >99% of the cases.
Or the same one a minute later. LLMs are the software equivalent of Patagonian weather.
(Unfortunately it also took twice as long and cost twice as much as Fable, but that's besides the point :)
To make a shameless plug, I'm working on a Python package called OpenATP [1] to make it easy to benchmark different models/harnesses for automated theorem proving. It supports running agents in Docker containers or Modal out of the box. If you try it out, I'd love to get your feedback!
I recently wrote about the surprisingly good performance I saw from Grok [2]. On more challenging proofs, Grok doesn't keep up with Opus/Fable and GPT 5.6. I was recently blown away by GPT 5.6 Sol. It's persistence in closing out proofs is unparalleled from what I've seen so far. OpenATP also supports Kimi and Leanstral [3], among others.
[1] https://github.com/henryrobbins/open-atp
When I've used interactive proof systems like Roq, I'd often kinda code myself into a hole by cutting along the wrong axes and not specifying my problem in a way that's easy to prove. After all, this is just like in math: you really want to cut at a problem the right way to get to the easy proof.
I think people are discounting how important that decision making is. It's not just about whether an LLM can churn through specific proof strategies on a problem, but also about how to pose the problem etc.
I'm not saying LLMs can't help, but I think it's less that "proof engineering is not needed" and more that "when these tools are used in the right way, proof engineering is easier". Because at the end of the day these tools work well when they have the right kind of foundations in the first place
> AWS made LNSym: a semantics and simulator for AArch64. That's cool. Perhaps we could use it to show equivalence between an optimised assembly implementation of some functions, and their Lean counterparts, and then use the assembly code at run-time? Then we could let LLMs rip at optimisation and they couldn't introduce any functional bugs. Verified assembly is well-trodden in crypto implementations, but perhaps now it could be cheap?
Trying to one-shot compcert might be hard! Thinking about it and planning it out might make it easier though...
But every time I use Codex unless I specifically give it the abstractions it writes code that is way too specific.
Since we're being pedantic, it means that there are (approximately) 800,000 people better than it. ;)
What's more interesting to me is, how do we prove that the business intent is accurately encoded in the code? This is a different problem. Not "is the logic internally coherent," but "is the logic going to give us what we want?"
And how do we make sure that the logic keeps giving us what we want, iteration after iteration?
I've open source a tool, Drift, for this purpose. So far, biased and anecdotally as its builder, this has been the missing layer. It works because the spec is treated as a duplicate of the code, written and committed in the repo and kept in sync with hashes. The LLM then checks for diffs manually. There are ways to use perplexity here as well. Here is an article about how to get started. https://monarchwadia.medium.com/how-to-make-your-agent-more-...
Doubtless, many more automations will come. We live in very exciting times. It has been a while since a new technology affected every corner of software engineering with such depth of change. This might be unprecedented.
The dimensions to notice are: Research speedup, practitioner expertize, labour dynamics, junior entrants, world impact.
In that sense it's a canary, whatever happens to Math, will in order flow to other sciences in-order of purity: Computer science, physics, chem, bio, social sciences.
External inputs are bound get LLM friendlier with time, in the order I mentioned above.
This isn't new, it is actually part of how Dafny came to be, another formal verification programming language.
"Safe to the Last Instruction: Automated Verification of a Type-Safe Operating System"
https://www.microsoft.com/en-us/research/publication/safe-to...
However so far hardly anyone in mainstram cared about verified assembly, maybe now with LLMs.
"Programming Language Design and Implementation in the Era of Machine Learning"
Or, as Wolfram proposes in another link on the front page today, the irreducibility of computation means we cannot generally get all bugs out of systems.
To my mind, one of the risks of going all in on verification is that you just move the difficulty to a harder, more abstract layer - the specification. In my experience, this typically looks appealing to a 'type' -- very high IQ, very little real world engineering experience -- it's a dream that hits the inevitable grittiness of the real world and .. the real world keeps winning.
The biggest issue was always cost. But there's still an alignment problem. Without human supervision, things might drift away from the original specification and intent.
From my own experience, what works best is some kind of Hoare/separation logic (contracts), as these are quite easy to follow and decompose.
Even something as simple as a minimal Haskell subset, plus a bit of LiquidHaskell, can get you really far if you are pragmatic.
Perhaps that's the same thing as what you're saying, though: we don't specify these things in detail because it's expensive to spend that much time thinking through it all, when users are largely trained to just accept crashes, glitches, inconsistencies, and the occasional sprinkle of data loss.
Indeed. The last bug I fixed in a production app was one where people could not restore from backup due to a de/serialization issue. The correct behavior would have been straightforward to specify (round-tripping). Trying to verify the serializer against the correct behavior would have forced the devs to think through all the edge cases.
This is why it's so important to separate functional from stateful code. Functional code is generally easier to specify. And, by isolating stateful code, one can e.g. fail fast and avoid stepping into undefined behavior.
Agents perform better when programming in Rust than <insert dynamic language here> (at least in my experience), exactly because types matter. Those theorem provers just have a poweful and pedantic type system that insists in being always correct, in detriment of everything else
LiquidHaskell (or flux or creusot in Rust) would be an improvement over Haskell or Rust too.
In either case (full blown theorem provers, or theorem provers laid on top of regular programming languages) the models would need to either focus in posttraining on coming up with good invariants to establish, or you need to prompt agents in a very specific way to get desired results (OP complains that sometimes Claude doesn't want to do this stuff, this happens when it's in out of distribution territory)
If you have bugs in the spec you have bugs in the code.
Whatever happened to Idris? Is that still being developed?
Edit: Looks like they are working on Idris 2 https://github.com/idris-lang/Idris2
LLMs have a VERY different set of things which are easy and which are hard and from software security to math proofs we're seeing very early impressive results but those will run out and new classes of what is difficult will show themselves.
The "this new tech will cause everything to be easy from now on!" feeling has happened many times before and always new limitations were found.
Industrialization was thought to be basically the end of the need for money or significant labor during the industrial revolution (this optimism is where communism came from) and that future never came.
The same will be here: rapid change but also new limitations which are still hard to imagine.
I used HOL Light about 15 years ago. The vast majority of the proof details are done by a machine, generally split between term rewriting and then offloads to a generic automated prover for first-order logic. Your job then is formalising the theorem statements and orchestrating the automation, and the latter still takes an enormous amount of labour.
Around this time, we were getting excited about recommender systems for lemma selection. The idea was that you turn every theorem into a bunch of features and train a recommender system against the lemma needed to prove it. Then when you face a new problem, you use its features to recommend which lemmas are likely to be needed. You then throw those lemmas and your conjecture at a bunch of industrial strength automated provers, get the provers to come back with a minimal set of necessary lemmas, and then use your verified automated prover to do the real proof with a tractable set of inputs. It first got implemented in Isabelle/HOL as Sledgehammer, and was a massive improvement to tooling.
Now LLMs are here and the game looks completely different. I went back over some verification I spent a week on about 5 years ago, in a pretty obscure formal verifier called HOL Light, on a problem of my own making. I'd seen how terrible ChatGPT was at propositional logic a few years back, so this is the sort of thing I'd had in my back-pocket as an "impossible benchmark" for LLMs. So as a half-joke, I gave Claude the main theorem I wanted proving, hoping to watch it embarrass itself.
In a minute or two, it has come up with the same proof strategy I had used, proving four lemmas to get to the main theorem. This was impressive, but that's not the laborious part, and I was pretty confident it would die trying to prove just the first lemma. It has its four lemmas enumerated and goes to thinking, while I go off for a cup of tea.
I come back five minutes later and it has scratched off the first goal. I'm pretty shaken, and go off again trying to process that. Come back, the second goal has gone. And then the third. And then the fourth. And then, after just fifteen minutes, it's pulled off a week of my work, done it more efficiently, and near enough one-shotted each proof. That took me a while to process. I realised that if I had this 15 years ago, it would have done 95% of my PhD, which is to say that 15 years ago, I would have done a 20x more ambitious thesis.
I contacted my old supervisor, who said the theorem proving community are all on top of this, including the creator of HOL Light, now at AWS. HOL Light, incidentally, was used on what I still believe is the most ambitious mathematical theorem proving project to date, the verification of the Kepler Conjecture. The lead on that project recruited a team to get the proof through over about 5 years. Today, I wouldn't be surprised if he could have solo'd it in 6 months. The same goes for another extremely ambitious project, the verification of the seL4 microkernel. And for another open problem, I know there are people seriously wanting to get a verification of Fermat's Last Theorem, which sounded delusional 15 years ago, but sounds pretty plausible now.
Exactly where this goes, I am not sure. I suspect we can now start on verification projects that would have been insane to contemplate. But a few things concern me. One is that Lean seems to have all the mind-share. Maybe it deserves it, but there are very major and mature theorem proving technologies such as Coq (now Rocq), Isabelle, HOL Light, ACL2 and Mizar that I believe still win in terms of having the largest verification libraries and the biggest verified projects. These should not be forgotten about, since they will also probably have the most training data, having been going for many decades now.
The second is that verifying our crappy human specifications probably isn't going to fly. As the creator of HOL Light says, representation (how you formalise your problem domain) is still where it all matters, and the LLMs aren't very good at this. And neither are the writers of our current specs. Verifying that a piece of software meets the HTTP spec will be considered an achievement, but it's the wrong goal.
We'll need specifications that are modular and composable, that mesh together so that each piece is sanity checking the others. This is how we build mathematics, and it's how we'd need to build software. Specs need to be short and comprehensible, so that a human can verify them. If your spec is as long and complex as the implementation, it's worthless.
But I believe it is possible to design software from the ground up where the motivation is specification engineering rather than code engineering, and thereby the specifications become the only human-facing understandable part of software. The implementation is just some artifact that an LLM generates that nobody looks at unless they are curious. And I think LLMS today mean that "build the world over again" isn't as mad a thought as it used to be.
1. Convert the natural language proof steps into formal language
2. Pass it to the solver to verify the steps
Genuinely curious!
That's where most of the tech in a theorem prover exists: its tooling to automatically fill in the gaps so your proof can pass the verifier. The tools and automation here are genuinely great, but you still end up having to write way more steps and inferences than you'd see in any maths textbook, and the details are far more fiddly because the formal verification is not very forgiving.
As an illustration, consider how you get from:
X = (x + y)(z + w)
X = xz + xw + yz + yw
A modern prover will do simple algebra like this for you, but the tooling had to be built to do it. In other domains, the tooling just dies trying to connect what an average working mathematician or even a mathematics undergraduate would consider obvious, and you're stuck either having to elaborate massive tedium, manually guiding the automation, or having to write new bespoke tooling to fill the gaps.
Seriously, please review Curry Howard Isomorphism if you’re getting pulled down this rabbit hole.
Programs are proofs. Proofs are programs.
So if you can formally describe the correct output for every input, you can have an LLM loop automatically fill in the gaps of how to get there. Congrats, that sounds at least as hard as writing the correct program in most cases.
Don’t get me wrong, I do think there are useful tools combining formal methods and llms. Let’s just not get carried away.
That's not remotely true. Or, more formally speaking since we're in a thread about proof assistants, it's not remotely true, up to extensional equality, plus some choices about which axioms you use.
I can write a formal description of what it means to have property in a way that does have computational content that is equivalent to an algorithm[0], but often the clearest way to express the property is equivalent to an algorithm that literally brute forces the problem, like sorting a thing by checking every permutation until you find one that's sorted.
The magic is that you can write a spec that's clear, then have the LLM write the code and prove the spec, so you know that given the right inputs/state, it will return the right outputs/state. Then the gap is performance-like characteristics, which is a pretty great starting point and a lot easier to be just empirical about than correctness.
[0] in Lean you can also use classical logic or add your own axioms, where it's not even comutational.
Really unnecessary levels of snark here.
> often the clearest way to express the property is equivalent to an algorithm that literally brute forces the problem, like sorting a thing by checking every permutation until you find one that's sorted
Have you ever heard of prolog? I’m sure a prolog program can express whatever property you’re attempting to write just as tersely (if that’s your metric for hard). Almost copy/pastable to and from a theorem proofer.
Or are you saying that the program has to be the efficient implementation? Because that’s a different ball game. I’m not even going to get into how you could provably transform brute force propositional logic into efficient algorithms. (At that point we’ll have finally created the fabled “sufficiently smart compiler” and probably solved p=np).
A huge majority of software is simple business rules + CRUD that is trivially verifiable. The entire problem is showing that an efficient/reliable program actually implements those rules.
> The magic is that you can write a spec that's clear
Maybe you can. But I did spend a grad class with rocq (coq at the time) and a decade working with “systems engineers” and am not convinced that this is a realistic expectation.
> The entire problem is showing that an efficient/reliable program actually implements those rules.
Reliability is a standard matter of correctness and captured (partly) by specifications. Efficiency tends to be easy to empirically test, but it is also possible to capture at the specification level [1]. Mind that specifications need not be all-consuming.
> But I did spend a grad class with rocq (coq at the time) and a decade working with “systems engineers” and am not convinced that this is a realistic expectation.
Agree! But this stuff just got massively more accessible, and the tooling around it is growing quickly. I think we'll end up growing specification systems specific to various domains which will be palatable to those "systems engineers", but I err on the side of optimism here. There's definitely a lot left to do for practicality.
[1] See the work of https://cs.nyu.edu/~shw8119 for the case of provably-efficient parallelism and garbage collectors
Why do you look at the speck of sawdust in your brother's eye and pay no attention to the plank in your own?
> I’m sure a prolog program can express whatever property you’re attempting to write just as tersely
No, you won't be able to express the most basic properties in Prolog at all, let alone as tersely as in a proper specification language.
E.g. if you have a language interpreter and a bytecode interpreter, pretty much every specification language will let you express the correctness of a compiler `compile(x)` as
``` for all scripts x and inputs i,
bytecodeInterpreter(compile(x),i) == languageInterpreter(x,i) ```
Good luck expressing this in Prolog, let alone equally tersely.
Like, if you meant "the correct program" in a sense where two pure total functions can be different despite both having the same outputs on the same inputs, then that's not what I'm responding to.
And yeah I know prolog, but proof assistants and logic programming are totally different beasts. Definitely not copy/pastable to/from lean, at least as I've seen and used each.
> Or are you saying that the program has to be the efficient implementation? Because that’s a different ball game. I’m not even going to get into how you could provably transform brute force propositional logic into efficient algorithms. (At that point we’ll have finally created the fabled “sufficiently smart compiler” and probably solved p=np).
I think you're totally misunderstanding. What I'm saying is that in something like Lean (just because I know it best) I can say, "this function takes inputs satisfying Prop1 and returns outputs satisfying Prop2," in ways where I write some brute-force equivalent formalization of Prop1 and Prop2 in the most straightforward way, and then go on to prove that they are true of my program that is not the brute force implementation. Like the wacky famous magical inverse square root implementation from Quake III. You could write a spec that "output = 1/sqrt(input) up to float properties" and the implementation in the famous brainfuckery way. To your comment about how the spec is as hard as the implementation, "output = 1/sqrt(input)" is way easier than the weird efficient implementation, and that class of distinction is super common.
And as you said, the annoying part is showing that the efficient implementation satisfies the spec, but what's magic today is that we have great tools and LLMs can and do fill in the blanks. In practice, I write the spec by hand for the stuff I care about and then prompt the rest and know that my spec is what the LLM implemented.
> > The magic is that you can write a spec that's clear
> Maybe you can. But I did spend a grad class with rocq (coq at the time) and a decade working with “systems engineers” and am not convinced that this is a realistic expectation.
I tried rocq back when it was coq too, and now do most of my work in lean and rust and python with totally normal folks and I'm convinced that the tooling and languages are finally just about Good Enough. If you have any interest in the field, which it sounds like you do, and if you haven't checked out the ecosystem in the last couple years, I'd recommend you check it out again.
I think it's also important not to miss the forest for the trees: even relatively simple specifications like "the compress and decompress functions must be inverses for all inputs" rules out vast classes of bugs in a compression library. This is not a complete specification; for instance, it does not speak about how the decompressor behaves on malicious input. But in my experience, even partial specifications carry the promise of hitting warp speed with LLMs in a way that I haven't seen anywhere else. After a certain level of specification, you have decent guarantees of being able to whole-heartedly forget about the implementation details of the synthesized program. And you get a better-built, more robust program out of it at the end!
The comment at the end of the article about having LLMs directly generate assembly against specifications and letting them rip with finding custom optimizations is the sort of crazy stuff this enables. I really think we're only seeing the tip of the iceberg here. People keep asking what we can do with LLMs that we couldn't before; this is the answer.
Static contracts and proofs are basically solved for industrial use in SPARK, yet somehow we keep reinventing. Is computer science really engineering? We don’t stand on the shoulders of giants, every new generation has the urge to invent a leave a mark. This in itself is great, except that, in contrast to other branches of engineering (say mechanical, or structural) previous know how is ignored and disregarded. Perhaps there is too much of it, and SNR these days is too low, impossible to be held in one’s head. Perhaps it’s easier these days with LLMs to survey what’s done. Yet the slop waves keep crashing on us.
We have seen this with dbs. The relational model layed the foundations. Yet periodically a new craze emerges. Everyone’s chases the latest cool new thing, until the ugly warts that were know to be there decades ago resurface and become real blockers (looking at you mongo).
Yet another post about program proofs, yet no mention of the only industrial strength, actually practical and pleasant to use formal verification language: SPARK.
But still no P=NP.