We have proof automation now

Huh, I wasn't actually going for snark. I was trying to preemptively be over-specific about what I meant. As in, you said "... writing the correct program..." and I meant that I'm talking in terms where functions are equal or distinct only based on extensional equality and with some flexibility on computational interpretation and axioms of the logic.

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.

When I did it the biggest problem is writing the spec. It was longer and more complicated than the code itself.

If you have bugs in the spec you have bugs in the code.

I have already written it, and I will write it again: dependent types and total functions do not scale. Maintenance is terrible.

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.

Don't we still need to verify that what the LLM proved is actually the stated system?If agents cutting corners (like deleting tests) is a concern, how can we be sure that the verification corresponds to the software and that every _load bearing_ assumption is true? I don't think that simply trusting the Lean core is enough.

Haskell does not have dependent types.