Comment by sp1982
4 hours ago
Suppose I write a distributed algorithm in Rust. To verify it, I might describe the algorithm again in TLA+, model-check that specification, and prove that it satisfies the properties I care about.
Now I have two artifacts:
TLA+ specification --> proved
Rust implementation --> runtime
But the proof establishes something like:
TLA_Spec => Safety
What I actually need is:
Rust_Program => Safety
I believe this is called model-code gap and there are ways to address it but I haven't found an easy-to-follow approach.
I last touched formal verification methods 20 years ago. Back then, Coq had the capacity to automatically transform your proof into OCaml. I would have expected that this would have only gotten better with time.
It’s been renamed recently. Maybe a few times. I think it’s rocq now. [1]
[1] https://rocq-prover.org/docs
Huh, I missed all of that. The linked discussion about the renaming from your link was a bit odd: https://discourse.rocq-prover.org/t/coq-community-survey-202...
It seemed to me from the survey that most people didn't want it changed or didn't care, but due to anglophone users they decided to change it anyway.
> I believe this is called model-code gap and there are ways to address it but I haven't found an easy-to-follow approach.
I would say Ada SPARK solves this problem.
Not just that, I've been seeing a huge effort in the Ada community to leverage LLMs to convert a lot of libraries into formally verified SPARK code. One of the biggest issues I see with vibe coded stuff is that it's difficult to review and difficult to prove that it's doing what you think it's doing, but with a strongly type language like Ada and formal verification with SPARK, LLM output is easy to read and easy to prove.
I think the reality is that it has to be baked into the language. Here's my real attempt at that - if you model the system in the language, the compiler can reason about the distributed fleet: https://hale-lang.org/proof/
I think the gap is real and for it to be resolved, the spec language needs to be elevated to a source of truth and possibly do some degree of codegen, which is currently not well realized with Lean
The analogy I'd make is to the idea of "type driven development" that buf/protoc represent, where one defines their types and schema in proto and then types for specific languages are generated from that
The limitations there however is that proto is not a programming language and inflexible/inexpressive whereas Lean is one of the most expressive languages to date
LLMs are pretty good at this. Not perfect by any means as the model is just a model after all - always wrong, sometimes useful - but the act of writing a TLA+ model helps the frontier LLMs to write correct executable code. It also works the other way around - given code, it can build a model in TLA+ and find latent bugs which it'll likely miss otherwise. (https://github.com/specula-org/Specula)
Apply this to building a house and complaining that the architecture drawings don't include the technical drawings.
The two are different artifacts for different jobs. The same is true for code and architecture. That they have an impedance mismatch is a feature.
It would be even better if there was a machine that could take your architecture and technical drawings and alert you of any mismatches.
I saw a fascinating talk by Clément Pit‑Claudel on closing this gap. I don’t have references handy but his website seems like a starting place:
https://pit-claudel.fr/clement/
As I remember it, he was formalising compilation by connecting the semantics of the higher level to the lower level one inside the proof assistant, so that proofs would carry through.
Something like TLA is to prove the design of an algorithm is what you intended.
Proving a specific implementation in a specific language is really the domain of that language or tools targeting that language.
In digital design for example, SystemVerilog has a whole sub-language for specifying formal properties that can be proved in simulation or with tools that prove the properties mathematically.