A Lean Proof That Adding Two Binary Numbers Is Regular, Explained for Software Engineers

Anatomy of a Lean proof for software engineers

A software engineer walks through a formal Lean proof that the language of bit-column strings where the bottom row equals the sum of the top two is regular. The trick: reverse the language so a DFA can process columns least-significant-bit first, carrying only a single bit of state. The post covers DFAs, regular languages, the adder DFA, and the inductive invariant, showing what it takes to verify a system formally.

The trick is to remember how you add numbers by hand: you work from the least significant digit to the most significant. The only thing you carry from one column to the next is the carry.
  1. thom

    So this is all great, but given that we’re being asked to accept 500k+ line Lean proofs that check but could easily have major semantic errors hidden in them, what’s the plan? These seem like uniquely fragile software artifacts, despite the excellent and robust promises made by the runtime.

  2. WalterGR

    OP: Your article shows “[Contents]” where presumably the table of contents is to be displayed.

  3. fooker

    Please do not try to understand Lean or proof assistants without first getting a rudimentary understanding of the logic involved. This article sort of skips over it, which is reasonable because it is pretty involved.

    Even if you have written a large number of math proofs, you'd usually not have learnt the language or logic of proofs themselves. And even if you are an accomplished computer scientist, logic is not just AND, OR, NOT.

    Here is some necessary reading, feel free to find better sources but wikipedia is good too.

    * Proof trees - https://en.wikipedia.org/wiki/Method_of_analytic_tableaux

    * Constructive/Intuitionistic logic - https://en.wikipedia.org/wiki/Intuitionistic_logic

    * Proofs and Types - https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...

    * (In)completeness - https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

    * Compactness - https://en.wikipedia.org/wiki/Compactness_theorem

  4. whattheheckheck

    the interface between specification and proof is not so clear, as one often has to look at the proof to understand the spec. And if we see something weird in the proof, that’s a good indication that something is off.

    Yeah this is like if I say something is green how do you know that my green is your green? The proof of the mathematically modeled system is in no shape attached to the symbols that implement it unless its the same program or youre doing trace refinement. And then theres no way of proving that the program is correct in serving the business function unless you run it out. Quite computationally irreducible, the state machine of building state machines

  5. woggy

    I’m curious whether people can use Lean primarily as a software specification language, without necessarily intending to prove everything.

    Can we use it to specify module meanings and laws, to make the design precise and checkable, and would allow us to implement property based tests for those laws in our implementation. Lean becomes a tool for more precise thinking about the design.

More from this day

2026-10-02