Interesting article, they list applied use of the theory on mainstream tools, things I never see on my readings. https://plv.mpi-sws.org/rustbelt/popl18/ for instance. Very cool
My goal with this tutorial was to introduce the core aspects of the language (dependent types, tactics, etc.) from first principles. If you're fascinated by proof assistants like Coq or Lean and want to understand how to use them, this tutorial is written for you.
I've done Logical Foundations and part of Programming Language Foundations, and some of the stuff in your tutorial is new to me (especially dependent types).
Your tutorial is very interesting, but in comparison to the Software Foundations series you have relatively few exercises and they're all at the end of the chapter. I found it helpful to do exercises as I went along, in many cases testing or exercising my knowledge of a new concept or Coq feature right away. So I would suggest writing more exercises and sprinkling them closer to where some of the material is introduced.
Also, some of your exercises in some chapters have a pretty steep ramp-up in difficulty, so again it might be nice to have exercises that gradually build in difficulty.
These are probably important considerations when readers are going to be working through this material entirely on their own and it might be their first exposure to Coq. (I think your tutorial says it was previously presented in-person, which has got to be a lot easier, since people can ask questions!)
For a more practical approach (though limited to C) you can try the Frama-C suite. It works by annotating C code, instead of having to manually rewrite the code in Coq.
One thing that the post does not mention is that things get nasty real quick if you use actual machine integers (or number generally) instead of ideal ones in Coq- though that can also be due to my own ignorance as an amateur.
I used Coq in one class in school, and I never encountered wat or wreck. It’s possible they’re user- or library-defined tactics.
One thing I think is important about Coq is that it really is meant to be interactive. Even after a fair amount of usage I still find it somewhat tricky to just read a proof, especially a nontrivial one. A good IDE will show you a panel that includes all your hypothesis and requirements so far, updating as you run each line
As other people note, a lot of those seem to be local aliases defined by the author.
But the most important thing to understand about Coq is that it's meant to be read in an IDE. The IDE will show you, at each step, what has been proved and what remains to be proved. The "tactics" you see above basically mean, "At this point in the proof, we can make progress by substituting Hv. And in context, this will make sense.
But without being able to see the proof state at each step, Coq can be incredibly cryptic.
I find the introduction interesting, it somehow clicked. Devs are like toddlers playing with wooden bricks, who are demanded to scale up this act of building to the level of a grown up's house.
In fact it often feels that way. You're either asked to extend or improve existing constructions that feel like sticks and stones bound together with rubber bands. Or one feels excited for being allowed to make up such a construction as a demo, not knowing it will be used as a basis for a production-quality construction.
I'm not sure if mathematical proof is the way to go. There's just too much code to cover for this approach to be realistic.
Most problems are born on the drawing table. The designs seem right on paper and only in practice, during or after building, they become visable.
> I'm not sure if mathematical proof is the way to go. There's just too much code to cover for this approach to be realistic.
It may be unrealistic, but people are doing it anyway. It may be the case that there are just a few Leslie Lamports capable of doing this stuff, and it's unrealistic to expect the rest of us to.
But even if that's the case, I still want them to publish their code as libraries, so I can reach for tools that will work - even if I couldn't have proved it myself.
And if this whole mathematical/proofy way of doing things is a dead end (which I strongly disagree with - we're just at the beginning!) then it's no big deal, because we are already really good at turning JSON into stack traces.
Turning a foam architectural model into a house without the required cost investment because the foam model was “so quick to make” feels like a frustratingly accurate description.
We build a train and then someone asks to turn it into a skyscraper because skyscrapers are the in thing now. It already looks like one on its side, how hard can it be to turn it right side up?
While I do think proof constructed code could be superior, I am not convinced for two reasons:
1. The problem expressed here has to do with a particular, well understood problem. It is not subject to the whims or constraint needs of the "customer". Proof construction is great when the problem is properly understood, I don't know how well it handles constantly changing requirements. (This encompasses business and interaction constraints too - perhaps you can construct a provable correct UI, but will it be engaging or usable?)
2. Test driven development can guide high quality code construction, arguably at lower construction cost. That is the reason I'd argue this has not taken off in comparison to traditional "test" based design.
You can argue it produces lower quality code, and you'd probably be right. But in comparison to construction of complex, rich design, I suspect that it produces faster results at lower cost. The provable solution will win out...eventually. Depends on whether it can make significant marker penetration once it is complete.
Nevertheless, yes of course we should be building foundations witb concrete not plywood and Styrofoam, so this is a good development. I do think a proper engineering approach with test based verification can build a "somewhat concrete" foundation, at least.
The article shows how interesting properties can be proved (with a nontrivial amount of effort). That's cool, but I wouldn't call it correct by construction.
It's a standard phrase in the formal methods field, [0] emphasising that it's an alternative to the usual approach where we hope that our testing (which can never be complete) is enough to catch all the worrisome bugs.
Personally, this article didn't strike me as being very easy to follow, or as being the most compelling demonstration of the value of formal methods. At the risk of going off-topic: if you're not seeing the point, I recommend this example using SPARK, a non-functional language. [1]
Right, not all of the techniques shown yield code that’s correct by construction. For example, an argument was indirectly given, and that error was only found after writing a theorem involving it and finding it was impossible to prove.
In the section “Correct BST by Construction”, they explain the technique of requiring every constructor of a BST to supply a proof that it maintains the properties of a BST. Any modification to a BST constructs a new BST (since Coq is pure), so any operations on a BST must also supply a proof of their correctness. That is correct by construction.
There's some software where it's important not to have bugs and know exactly what it does, and some where any attempt to specify what it's supposed to be doing, let alone fixing all the bugs, is a waste of time. (And things in between...)
Currently, a lot of instances of the first situation get the treatment befitting the second. This is because it's still too hard to use these tools at scale. However, the trend is certainly towards improving tooling and the cost of doing this will go down a lot.
Maybe in a hundred years programming will be replaced by either "formally specify what you want", if you know what you want, (AI fills in implementation of how it does what you want, as well as a proof that it does) or, if you only very roughly know what you want, explain it to the chatbot and answer it's questions.
In the general case, the "write the spec and the AI does the rest" boils down to automated theorem proving, and I'm optimistic AIs will get pretty good at this in a lot of useful situations.
Even today, in limited well-defined problem spaces, there are sometimes good algorithms for this sort of thing. See Dana Angluin's algorithm for learning the DFA that recognizes a regular language given through an interactive process of having the user provide examples/counterexamples, which serve to provide an increasingly constrained spec.
AI probably disrupts programming in the next couple of decades, where they produce not only software but static and dynamic validation artifacts of correctness. It’s sad though, I would have really liked to see how human programming could improve with better tooling, it seems like a lot of formal specification work (and program synthesis using such) could be improvised with just better user interfaces.
If an LML can write an essay that humans can read, surely it’s conceivable that it could spit out proofs/tests/docs etc…in a human readable form. So really, you can just decide for yourself then.
Building software is a conversation right? Your specification starts out vague, the AI makes a bunch of assumptions, and then you just say “oh, I really didn’t want that”, wash rinse and repeat.
I'm not convinced this is adequate, your specifications will be come rather unweildy.
If you employed this approach, I would want to pair it at a minimum with a test suite.
Even then, how do you know that your system (covered by hill climbing suites of tests that pass), has correct behavior for all things you didn't specify?
You don't. Better to build from the ground up formally than fight with "AI" that probably got it worse than wrong first try.
You don’t anyways now. You just have some assurance, not total assurance, with current practices. Many people will find something conversational (in that you have some documentation about what it did and can correct assumptions) good enough because it brings close enough to the human status quo.
I hope your pessimism is founded though, I would really like to see programming by human advance rather than the whole thing be taken over by AI. Hybrid approaches are also possible (AI in the loop but not in the core position).
The article title was obviously a troll (I've changed it to the subtitle now). The HN guidelines ask commenters to abstain not only from feeding trolls but also from gobbling their bait:
"Please don't pick the most provocative thing in an article or post to complain about in the thread. Find something interesting to respond to instead."
I know it's a lot to ask, but we have to, given the site mandate, and anyway why not? It's an interesting experiment to work on as a community.
You have to admit it’s a good one though. Haha. I don’t want this place to become a cesspool like Reddit but once in a blue moon I do need a good laugh
