2 ms·
"This is the last Lean proof which I will give here. The reason is that for proofs any more complex than this, it gets hard to follow them on paper. The way to
by mcguire 7y ago
"This is the last Lean proof which I will give here. The reason is that for proofs any more complex than this, it gets hard to follow them on paper. The way to understand these proofs best is to look at them in Lean itself. If a proof were running in Lean on a computer then you could click anywhere on the proof and see Lean’s state (what it knows and what it is trying to prove)."
Yeah, there's the problem: Proof-assistant produced proofs are difficult to read as proofs. The alternatives are to execute them, as you would execute a program in a debugger to understand it (um, ick), or to "pretend to be the computer" and execute them manually.
The interesting part is that exactly that problem is faced with software, which developed ways of writing programs that are easier to understand, including using formal methods.
- eli_gottlieb 7y agoI'd be very curious to know, empirically, whether people who aren't trained in computer science, software engineering, or pure mathematics consider reading a proof or reading a program to be easier and more understandable.
- solveit 7y agoI would guess that they bad enough at both that the difference doesn't really matter. I would be interested in what someone at the highest levels of all three fields thought, but I'm not sure these people exist.
- derefr 7y agoHumans like to pretend business-logic workflow digraphs are actually workflow trees. Every programming language† is an attempt to "tell the story" of the runtime paths through a digraph of control-flow, using a lexical tree of syntax structures. I've only written a few proofs in my life, but I get the sense that "at scale", they're quite similar: a narrativization or expiation of a bunch of paths through lemma-space, that branch out and re-converge. When any program becomes sufficiently complex, its nature as a digraph is forced to the surface, and the ability to continue to pretend it's just a tree becomes untenable. We get confused, working with these complex digraphs, unless we use tools that allow us to visualize digraphs as digraphs, walking around them and looking at them from different angles. Honestly, I don't think this is anything to do with "doing programming [or proof-writing] wrong", so much as it is an inherent fact of the nature of systems of lemmas. It's a bit like how humans can't visualize hypercubes directly—we need to instead use a tool (lower-dimensional projection) to "walk around" these mathematical objects and look at them from different angles, in order to understand them. I would posit that systems of lemmas are just such a mathematical object. Sure, you can try to find isomorphic programs, or proofs, that are more lexical-tree-like, and so easier for humans to hold in their heads. But if you require that your programs, or proofs, fit to some standard of tree-like-ness, there'll be some programs/proofs that you just won't be able to write. Maybe that's not so bad for programs (those programs were probably awful anyway), but ignoring a proof (or an area of proof-space) when it's perfectly valid, just because we need tools to look at it, seems a bit silly. --- † Or rather, every programming language that people use in practice, because even in languages with GOTO, people avoid it, and restrict themselves to the structured-programming subset of the language. The programmer who wants to write everything as coroutines or (call/cc)s is pretty rare.