Proof automation in a language (15 Nov 2026)
As I wrote previously, we have proof automation now. Given that fact, I think a very timely question is: how can we use it to improve software quality? The same machines that can write these proofs can also write large amounts of code. So an adjacent question is: how can we use them to improve software understandability?
It would be a mistake to start off afresh on those problems because there have been a lot of ideas in programming language design over the decades. The viability of ideas shifts as the underlying cost structures change, so things that didn't take off at the time might suddenly make a lot more sense. Still, language design involves a lot of tradeoffs, and features sometimes interact in surprising ways, so a lot of the work involves mixing some interesting-seeming ingredients together, baking, and asking “what is this? Is this a cake?”.
So I wanted to give a taste of some of the ingredients that I'm thinking about at the moment, and of the result.
Ingredients
Mutable Value Semantics
Value semantics roughly says that you can't observe mutations to one variable through a different name. Value semantics are great for reasoning locally about code as, without them, you're constantly unsure what non-local effects might be happening.
When you work in a language, you instinctively know when it's using value semantics and when it's using reference semantics. Take Python:
x = [1] y = x y[0] = 2 print(x)
You likely know that that prints [2]. (Although if you write the same program in C++ with std::vector it prints [1]! There's no cross-language norm for this.)
Over the span of four lines of code, this is irrelevant. But as the scope of the sharing increases, so does the mental complexity. If you want to be able to jump into a bit of code and understand what it's doing, knowing that there is no such aliasing is a huge boon.
Functional programming resolves this by eliminating mutation: if there's no mutation then you certainly can't observe mutations via a different variable name. But mutation is important for efficiency and a lot of work is then required to get the efficiency back. Lean, for example, will do in-place mutations if there's only a single reference to an object. That's great! But it has the sharp edge that innocent-looking changes can mean that there's now a hidden reference kept somewhere and performance crashes.
Rust claims to fix both issues by restricting references so that you can't ever have both a mutable reference to something, and an active alias to it. (We'll ignore Rc<RefCell<T>> and friends.)
Certainly Rust's restrictions help a great deal, but Mutable Value Semantics says that Rust goes too far by making references first-class, i.e. something that you can return and store in structures. First-class references lead to the borrow checker, which has undergone several deep rewrites (original to NLL, next to Polonius) to try and perfect it, and they lead to lifetimes, DerefMut etc., and much more complexity in the type system in general.
So an MVS system avoids all that by further restricting references and not allowing them in the type system. These ideas started in Swift and are currently championed in Hylo. The best introduction I've found is this talk.
In an MVS system, functions can take three sorts of arguments: immutable, mutable, and owned. Immutable arguments might be a reference or a copy; the semantics are the same. Mutable arguments are conceptually copied in at call time and copied back out when a function returns, but of course that's semantically the same as taking a pointer. Lastly, owned arguments transfer ownership to the function and make it unusable in the caller afterwards.
But there are no references in the type system, so a function can't return or store them. But the inability to return references implies so much copying that MVS systems need to provide an alternative.
Hylo has a very cute system of scoped coroutines, inspired by Swift. These coroutines yield a value and, at the call site, all their arguments are locked for the duration of that value's span. At the end of the span, the coroutine continues running.
One of the common examples is that a coroutine can return a mutable bool for a vector of bits that have been packed into bytes. Then, when the coroutine continues once the return value is no longer used, it can write the new value of that bool back into the array of bytes. This wouldn't be possible without a coroutine because the function would have to return a pointer to a bool that exists nowhere in memory.
Having just lionised this feature, I should note that in my experiments I haven't actually included it because it makes the semantics more complex and I'm spending a lot of complexity budget on verification instead. Which brings us to another idea that combines with MVS…
Reference restrictions sidestep separation logics
If you want to do formal verification on a language like C, then you need to model the heap and you immediately hit the aliasing issues above. Then you end up with a separation logic which lets you model disjoint areas of the heap (i.e. areas with no aliasing between them). Once you can speak about independent heaps, you can reason about a function that operates on one heap and hold the remainder constant.
This can work. The example that I'm (passingly) familiar with is the Verified Software Toolchain which connects to CompCert's semantics and allows you to state properties about C programs (with a separation logic) and thus verify C code all the way to machine code. But it's complex.
However! If you have restricted references then you can drop a huge amount of complexity from such systems! Aeneas/Charon is the current canonical example of this which can translate a subset of Rust code into Lean (and other languages) where things can then be proved about it. Because of Rust's restrictions, the translation doesn't need a separation logic.
But by being more restrictive than Rust, MVS languages are even more amenable to such translation, and thus to formal verification, without going all the way to being functional languages and banning mutation completely.
Design by Contract
Eiffel is the standard reference here. It introduced preconditions, postconditions, and invariants for functions/classes:
class DICTIONARY [ELEMENT] feature put (x: ELEMENT; key: STRING) is -- Insert x so that it will be retrievable -- through key. require count <= capacity not key.empty ensure has (x) item (key) = x count = old count + 1 end ... Interface specifications of other features ... invariant 0 <= count count <= capacity end
While you've probably never used Eiffel, these notions are quite widespread now, although in common programming languages they are at best encoded in assertions if simple, comments if not, but mostly remain only in the author's head.
Eiffel did all its checks at run-time. There has been a lot of work on the balance between run-time and compile-time for these assertions, and on how to discharge assertions statically. Briefly, some work in this space that I'm aware of:
Dafny allows a mixture of run-time and static assertions, and discharges the static ones via SMT solvers. F* does everything statically, again using SMT solvers, but with a functional language. SPARK has a mixture of run-time and static checks, using SMT solvers or (albeit very challenging to use) provers via Why3. I've never touched Verus but it's worth a mention because it's the most recent entry in this lineage and is Rust-based.
The problem with these systems is that the compile-time checking is much more powerful, because it can cover all possible values of the arguments, but the proof burden is significant. SMT solvers help a lot, but they can quickly hit (effective) non-termination for non-trivial cases. I did an F* summer school in Paris once, and the experienced people there had developed a sixth sense about what would displease the SMT solver and would instinctively code around it. It was an impressive skill! But not reassuring.
This is the key cost that has changed: SMT solvers were inadequate for more complex cases, and dropping into a proof assistant overwhelmed you with lots of inscrutable proof states. All this can be largely handled by models now.
Also, I claim that there are some interesting synergies between MVS and design-by-contract. In Rust, and more so in an MVS system, you end up using indices into arenas of objects to replace arbitrary pointers. (Which can be faster due to cache locality.)
Given that one has all these indices flying around, wouldn't it be nice to have explicit invariants about them? Hopefully proven?
Refinement types
When writing code I will fairly often have some structure which has invariants that update as processing progresses. At some early part of the pipeline, the structure may be relatively arbitrary, perhaps freshly parsed from a file, and then as various checks and transforms are applied we know more and more about the value.
But in traditional languages, the structure has one type: its structural type. Even with Eiffel-style Design by Contract, invariants on a type are fixed.
The idea of being able to attach more invariants to a structure without duplicating most of it showed up as Subtypes in proof systems, and refinement types in ML. You'll also see Rust code do this (mostly at run-time) with checked constructors like NonZero and NonNull. But those are run-time checks that the type system carries a certificate of. Similar to the evolution of Eiffel-style conditions, we can hope to make them static checks now, discharged via our new proof automation.
Literate programming
Literate programming was the title of a paper by Knuth in the 80s, and WEB was the original implementation. The idea is that code should be written to be read and thus that it should be ordered for human, not machine, consumption, and that exposition should be at least as important as the code, and not relegated to comments.
Nearly twenty years ago I wanted to understand critbit trees and so wrote an implementation using CWEB to explore both ideas.
Relatedly, in my mind code has a graph structure deriving from which functions call which other functions. Source files are groups of strongly connected functions and I generally have little memory for what order functions have in a given source file. With the widespread use of LSPs and thus code indexing, we are edging slowly towards being less file orientated but I still feel that we could do much more.
There was a burst of such ideas in the 80s: Knuth's work, also Smalltalk & Lisp systems which kept code in databases rather than text files. Given the ecosystem of version control that assumes text-based files, code databases might be too awkward now, but I still feel the itch of dissatisfaction here.
Baking them together
At the top of this post I also set a goal for code to be more understandable and, to that end, the easiest code to understand is the code that you didn't have to read because the contract says all that you need to know about it.
But let's work up to that a little.
Here's a function that looks like Rust (because I don't have better syntax ideas) but which doesn't verify.
fn add(a: u32, b: u32) -> u32 { return a + b; }
When I'm reading code, I'm always trying to track the invariants and think about integer overflows. Sometimes the codebase aims to be overflow-clean and so I'm following bounds precisely. Most of the time I just have to ignore them unless the overflow is especially egregious. Now that we have proof automation, I shouldn't have to do that. So, as in SPARK, Verus, and others, + must statically not overflow and compiling the above gets you:
FAIL (refuted) vc_add_arith_1 arith test:3 - [smt z3 6ms, sat] countermodel (z3, 6 ms; exact: the VC is false for these values): a = 1 b = 4294967295 (2^32-1) goal a + b < 4294967296 becomes 1 + 4294967295 < 4294967296 1 + 4294967295 = 4294967296 (2^32)
That's the SMT solver giving you a counterexample that overflows. (+%, as in Zig, exists if you really want wrapping operations.)
If the values are bounded such that overflow can't happen, then obviously everything will be fine, automatically:
fn add(bytes: Vec<u8>) -> Option<u32> { if bytes.len() < 4 { return None; } let a = u32::from(bytes[0]) << 8 | u32::from(bytes[1]); let b = u32::from(bytes[2]) << 8 | u32::from(bytes[3]); return Some(a + b); }
Casts are similar: u32::from is safe because it must be widening. For narrowing, u32::exact_from statically requires that the cast not truncate and, if you really need the machine operation, u32::wrap_from gives it to you.
And, of course, all vector indices must be statically valid.
Let me try and convince you of the benefits of contracts in terms of code understandability. For this, we're going to discuss a tiny bit of DER, the most common ASN.1 encoding.
DER is a tag-length-value format. We're just going to talk about the encoding of tags. Firstly, tags are in one of four classes which have integer values on the wire:
pub ghost fn class_num(c: Class) -> Int { match c { Class::Universal => 0, Class::Application => 1, Class::ContextSpecific => 2, Class::Private => 3, } }
A DER tag is then a class and a tag number, plus a flag which tells you whether the value contains more DER values nested inside it. In theory, tag numbers are unbounded integers. In practice, everyone limits them; here we'll bound them below 228 because, as you'll see, that limits the tags to five bytes and the next byte would exceed 232. The (class, tag number) combination of (Universal, 0) is banned in DER as it's the BER end-of-contents value:
pub struct Tag { pub(read) class: Class, pub(read) num: u32, pub(read) constructed: bool, } pub invariant @no_universal_zero { self.class == Class::Universal ==> self.num != 0 }
A tag can be encoded as one or more bytes. The first byte has two bits of class, one bit for the constructed flag, and five bits of tag number. If the tag number is ≥ 0x1f (the maximum 5-bit value) then it's encoded as 0x1f and more bytes of tag follow:
pub ghost fn tag_enc(t: Tag) -> Seq<u8> { let id = class_num(t.class) * 0x40 + if t.constructed { 0x20 } else { 0 }; if t.num < 0x1f { seq![u8::exact_from(id + t.num)] } else { seq![u8::exact_from(id + 0x1f)] ++ b128_enc(t.num, false) } }
The tag numbers that need more bytes are big-endian, base-128 encoded, with the high bit set each time if another byte follows:
pub ghost fn b128_enc(v: Int, cont: bool) -> Seq<u8> decreases { v } { let last = seq![u8::exact_from(if cont { 0x80 } else { 0 } + v % 0x80)]; if v < 0x80 { last } else { b128_enc(v / 0x80, true) ++ last } }
Now, here's an encoding function for DER tags:
pub fn format_tag(t: Tag, out: mut Vec<u8>) requires @range { t.num < 0x1000_0000 } ensures @encodes { seq_of(out) == seq_of(old(out)) ++ tag_enc(t) } { … }
The body of the function is missing—but you don't need it! The contract requires that it encodes exactly as tag_enc specifies so you don't need to know more. This isn't saving you too much because the code isn't that complicated. You would have to think about the shifts and masks that it's using for the base-128 encoding (rather than recursion), but that's only a few seconds.
But here's a more substantial saving:
pub fn parse_tag(reader: mut bytes::Reader, in: [u8]) -> Tag ! (Error | bytes::BytesError) ensures @decodes { result.num < 0x1000_0000 && seq_of(in).slice(old(reader).pos, reader.pos) == tag_enc(result) } ensures_err @no_encoding { forall t: Tag :: t.num < 0x1000_0000 && old(reader).pos + tag_enc(t).len() <= old(reader).end ==> seq_of(in).slice(old(reader).pos, old(reader).pos + tag_enc(t).len()) != tag_enc(t) } … { … }
This is saying that:
- If it decodes a value then the given bytes start with the encoding of that value.
- If it returns an error then there is no valid Tag value which encodes to the bytes at the beginning of the input.
This enforces not just the baseline of memory safety, no run-time panics etc., but that the parser is fully strict: it never parses anything other than the canonical encoding of a value, as defined above. This is not a trivial thing to code review, and here you don't have to.
Also you see signs of MVS: a Reader can't hold a reference to in because references can't be stored. Thus in is passed separately (and the indices are proven to be valid). This is part of the tradeoff for local reasoning and strong contracts.
I've not mentioned linear types, views in return values, or Zig-style error unions, and I'll only touch on refinement types in the lightest sense by noting the pleasing definition of the String type in this experiment:
pub form String of Vec<u8> { utf8::valid_from(self, 0) }
Lastly, nodding towards literate programming, I'll note that this blog post itself is a valid source file for this language: the language consumes Markdown files and only compiles lines in annotated code blocks. The Lean proofs are kept in separate files, not for human consumption. There's already a tool for showing a source file with only the public definitions, and with the bodies of functions elided, and there's still more I want to explore here in terms of viewing source files as a graph.
Is the cake a lie?
It's worth discussing the more bitter flavours in this cake too.
The front end of the compiler emits lots of verification conditions for the code to be correct. Every arithmetic operation emits overflow checks, every indexing operation emits range checks, every invariant and postcondition results in checks, every loop must be shown to be terminating, etc.
The little DER tag example above results in 149 of them. Each is first sent to Z3 and then, if Z3 times out (after a couple of seconds), to cvc5. But the solvers are never trusted. If they believe that a condition holds they output the unsat core which is used to trim the hypotheses which are fed into Lean. Lean automation chews on the problem for a while and, if that times out, an LLM comes to write a manual proof in Lean.
There's a cache of proven conditions, of course, and the Lean proofs are saved in a different file. But overall even reasonably simple examples type-check at about 10 lines per second. If you invalidate the cache then medium-sized programs can take multiple hours to recheck on a fast machine. (Not reprove, just to check the proofs that already exist!) So modularity of code is important to keep the scaling line flatter.
LLM compute is needed too: after I laid out the spec for the DER tag example above, a model took about 30 minutes to get it working. But if you ask a modern model to write the same thing in Go, it will do it in under 10 seconds. (Although the result doesn't hit nearly the same quality bar and the lax parsing would cause security problems in sensitive contexts.)
Overall, this language was an experiment in how we can convert compute into high-quality and understandable code. I'll claim that it's making interesting steps towards that goal, but you do need a lot of compute.
Also, there is a considerable trusted base involved here. While you don't have to trust the SMT solvers, you do have to trust that the front end is correctly translating the code into verification conditions for Lean, and you have to trust that it is correctly translating it into LLVM IR. I think that's fine: the comparison here is with regular languages like C++ and Rust. This is not an attempt at a minimal TCB language with extremely strong guarantees like CakeML.
Still, the language does have significant aspects of delight. Being able to write the spec for DER encoding, and then have the correct code for it generated, does make me reflect on the amount of time and suffering that I've put into DER over the years that could now be avoided.
We have proof automation now (26 Jul 2026)
I've long had a soft spot for dependently-typed languages like Coq Rocq and Lean.
They offer the possibility of a type system capable of encoding and enforcing
arbitrarily subtle invariants. The sort of thing that, in regular languages, ends
up (at best) as a comment, and which quickly gets lost as the size of the team grows.
Then you get subtle misunderstandings and components that don't quite
fit together. It's often the case that those components have grown to a
sufficient size that, when the problem is noticed, aligning either of them is a wearying prospect. Perhaps, say
dependent types seductively, you could write those invariants formally and have
a machine check them.
(p.s. Coq changed its name! I remember many years ago at a Coq conference in Princeton, I tried suggesting that, in an English-speaking world, having a programming language called Coq was an impediment. I don't think the audience agreed at the time. I also joked that many of the talks there sounded like a speech by Tyrion Lannister, there being so many Coqs and Hoares. A joke that was hilarious and timely, even though it fell completely flat, coming as it did before the final season of that show and our collective memory-holing of it.)
The problem has always been that with great type-system power comes great proof effort. I can certainly attest to entire days spent proving really quite simple things. Doing proofs is actually quite fun: it's challenging, interactive, and there's a clear goal. But gosh, does it take a lot of time, especially if, like me, you don't know what you're doing. There's also the periodic, galling experience, at the end of many hours of effort, where you realise that the goal that you're trying to prove is, in fact, false. The classic result here is the retrospective from the seL4 effort that found that, even though the project was large enough for the engineers to develop considerable experience, they spent about 10 times as much time proving as they did designing and implementing. They ended up with more than 20 times as many lines of proof code as they did C code.
That overhead has made programming in dependently-typed languages extremely niche. It has also spurred people to try and automate it away. The attempt I'm passingly familiar with is F*, where the system tries to have an SMT solver automatically discharge the obligations. That certainly works for simple cases, but it's very easy to craft something that causes the SMT solver to go off into space and run for hours, leaving you wondering whether it's ever going to finish. I've seen that people who use these languages a lot have to develop a sixth sense for what is going to make the solver happy, and then craft everything around that. It can help, but to an extent it converts the problem into mysticism: you end up serving a complex and fickle god.
A critical fact is that, at least in theory, once the statement is correct, the contents of its proof are irrelevant: only its existence matters. This is not entirely true because of two complicating factors: first, what the seL4 group called “proof engineering”: the need to structure proofs so that the effort of realigning them after code changes is reduced. And, second, sufficiently complicated proofs can cause even type checkers to blow up and consume vast amounts of memory.
We now have LLMs which, combined with proof irrelevance, promise to be an extremely capable form of proof automation. With sufficient amounts of automation perhaps you don't need to worry about proof engineering nearly so much. You still need to avoid blowing up the type checker but, in my limited tests, LLMs can avoid that. Potentially, LLMs suddenly make dependent-type systems dramatically more practical. I wanted to play around with this so built a Zstandard decompressor in Lean, mostly because I was also curious about Zstandard.
Zstandard seems like it's winning the competition to replace gzip as the canonical compression utility. It's another LZ77-style compressor, but it offers better entropy coding and a careful design that allows it to achieve very impressive decompression speeds. It will never be as beautiful as bzip2, but the shining elegance of the Burrows–Wheeler transform doesn't count for too much in the face of significant practical advantages:
(Measurements taken on the standard reference computer, i.e. whatever the author was using at the time. And note the log scale on the y-axis: gzip and Zstandard are in their own speed class. This is an Apple machine and Apple's gzip is especially optimised; expect gzip to be slower elsewhere.)
Zstandard (by Yann Collet, building on the seminal ANS work by Jarek Duda) has an RFC, but it is quite terse. It contains all the information you need to implement a decompressor, but unless you're already quite familiar with compression, I think you'll need to re-read it a few times to understand what's going on. I, at least, had to read section 4.1 half a dozen times before I felt that I had a decent grasp of it. Too late into this process, I discovered that my colleague, Nigel Tao, has written a better write-up of Zstandard than I was going to manage anyway. So, if you want to understand Zstandard, you should read that. I'm just going to give an explanation of the most interesting bit, the entropy encoder, and mix that in with some evangelism about Lean.
The job of an entropy encoder is, given a set of symbols with non-uniform probabilities, to encode a sequence of those symbols using the fewest number of bits. The classic entropy coder is a Huffman encoder. Huffman encoders build a binary tree with symbols at the leaf nodes, and Huffman showed that a very simple algorithm produces an optimal prefix-tree: you take the list of symbols, you find the two with the least probability, and you form a tree node with them as children. That tree node then has a probability that is the sum of its two children, and then you repeat the algorithm with two fewer symbols, but now with a tree node in the mix. Obviously each step of this algorithm reduces the size of the set of elements by one, so it terminates, and it also produces an optimal tree. Huffman trees are very fast because you can build a table indexed by the next n bits (where n is the length of the longest code). The table entry tells you what symbol you've decoded and how many bits to unread. The drawback of Huffman trees is that they can only use a whole number of bits for each symbol: if you have a symbol where -log2(p) = 2.3 then ideally you want to use 2.3 bits to encode it. But Huffman forces you either to round up to 3 bits or to round down, which will force some other symbols to consume more bits.
Zstandard uses Huffman trees, but it also has a higher-compression entropy encoder called FSE. FSE is a state machine. There are more states than symbols, and each symbol gets a fraction of the states that mirrors its probability of occurrence in the stream. So if there's some symbol that is expected to appear 50% of the time, it gets ~50% of the states. Each state has three values: the symbol for that state, a number of bits to read from the bitstream when in that state, and a baseline state number that is added to those bits to get the next state. Now, if you recall, the problem with Huffman trees was that they could only use a whole number of bits, and these states also read a whole number of bits. But the trick is that if you are aiming to read one and a half bits for a given symbol, then half of its states will read one bit and half of them will read two bits. Then you hit your target on average. The table of states is never transmitted. The RFC prescribes an algorithm for building the table from a list of symbol probabilities, and so only the probabilities need to be transmitted.
Let's do an example. Let's say we have four symbols and we're going to use 16 states. So we have to approximate the symbol probabilities in terms of 16ths. (If you want a more accurate approximation of the probabilities, you can use a larger number of states; zstd actually never uses fewer than 32 states.)
| state | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Symbol | A | A | B | D | A | B | C | A | B | C | A | B | C | A | A | B |
| Num_Bits | 2 | 1 | 2 | 4 | 1 | 2 | 3 | 1 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 1 |
| Baseline | 12 | 0 | 4 | 0 | 2 | 8 | 8 | 4 | 12 | 0 | 6 | 0 | 4 | 8 | 10 | 2 |
Any symbol may follow any other symbol, and a symbol might only have a single state. So every symbol must be able to reach every state. Take a look at state three, which is the only state for symbol D. Because it's the only one, it has to read four bits, which is sufficient to encode any other state. But if you look at a symbol like B, its states only demand that you read one or two bits. However, the set of 16 possible next states is exactly partitioned between those states for symbol B. So, for any particular state, there is exactly one state for symbol B that can reach it.
Again, consider symbol B, which we said had a probability of 5/16. The ideal number of bits to encode that symbol is -log2(5/16) = 1.68. There are three symbol B states that read two bits and two that read one bit. The states aren't used equally often and, weighted by how often they're used, the average comes out to almost exactly the right value for the quantised probabilities. If you want to capture the true symbol probabilities with more accuracy, use a bigger table.
The central trick is that, by giving multiple states to more common symbols, the encoder doesn't just pick a symbol: it also picks which of that symbol's states to land in, and that choice carries information forward to the next symbol. That's where the fractional bits of information go. But this entropy encoder is still just table based, and so it runs very quickly.
The wrinkle is that you can't work forwards. Assume that you want to encode C, D. Which C state do you start in? Well, D only has one state so it has to be the C state which can reach that one. If D had multiple states then you would need to worry about what came after D to know which of those you needed. FSE forces you to start at the end of the sequence and work backwards. (That's not too bad because you usually need to know the whole sequence in order to calculate the symbol probabilities anyway.) Furthermore, a Zstandard compressor thus encodes symbols back-to-front, but writes output incrementally, so the decompressor has to seek to the end of a block and read the bits backwards in order to straighten it out! That's getting into broader details of the format that I'm not going to cover; see Nigel's piece.
Basic entropy encoders do not care about inter-symbol probabilities. I.e. they can't use the fact that the letter Q is disproportionately followed by the letter U (in English). There has to be some other encoding that is exploiting those redundancies. In Zstandard, that's a traditional Lempel–Ziv structure where it encodes either literal bytes or back references to previously decoded data. So FSE is primarily used for efficiently encoding these back reference offsets and lengths.
Lean
Let's talk about Lean! Above I said that it's a dependently-typed language, and that is a concept better articulated in examples than in a complicated definition. So here's the type of a function that reads n bytes from a stream and, if it doesn't throw, returns a byte array that the type system knows is n bytes long.
def IO.FS.Stream.readExact (st : Stream) (n : Nat) :
IO {ba : ByteArray // ba.size = n} := …
Here is a function that returns two numbers and a byte array such that the first number is prime, the sum of the two numbers is divisible by six, and the byte array is at least as long as the smaller of those two numbers.
def getResult :
IO (Σ a b : Nat, { bytes : ByteArray //
Nat.Prime a ∧
6 ∣ a + b ∧
Nat.min a b ≤ bytes.size }) := …
That is not a type that anyone will ever need. It's just demonstrating that you can go as wild with this as you want. Dependently-typed languages are sufficient to encode even very complicated mathematical structures, and Lean's dominant use at the moment is as a formal language for stating and proving mathematics. The recent book, The Proof in the Code, is a short, well-written articulation of the story of how Lean came to be. The author does completely butcher constructive mathematics for a few paragraphs but, other than that, I enjoyed it!
Lean is a purely functional language like Haskell, although it has a few properties that make it potentially a lot more convenient as a programming language. Firstly, Lean is strict, while Haskell is lazy. Strictness means that arguments to functions are evaluated before the call happens, whereas in Haskell the evaluation of arguments is deferred until the value is actually required. So in Haskell it's free to write expensive expressions and pass them into functions, because they'll only actually be computed if they end up being used. But it also means that computation can happen in very surprising places in the program. This is a contentious topic but, while I appreciate the elegance of laziness, boy, it can make the performance of programs hard to reason about.
Next, Lean has some nice helpings of sugar. Its monadic do
notation contains for loops and return statements and break statements. If you
want to program in an imperative style, you can do so pretty reasonably!
Lastly, Lean has an optimisation where it will make mutating updates to objects as long as their reference count is equal to one. So you can mutate an array in place as efficiently as in an imperative language, as long as you are careful not to have a reference to it someplace else. Unfortunately, Lean does not have any aspects of a linear type system that I'm aware of, so it does not help you in ensuring that there is only a single reference to a value. It's a bit of a sharp edge that a seemingly minor tweak to the code can completely crater its performance by holding on to a reference to a large array somewhere inconspicuous. But it does mean that if you are trying to optimise the performance of something, you have a lot more tools at your disposal.
Here's an example of some of this, from the zstd decoder I sketched:
while true do let some blockHeaderBytes ← input.readExactOrEof 3 | break let some blockHeader := BlockHeader.fromBytes blockHeaderBytes frameHeader | throw (.userError "invalid block header") let blockBytes ← input.readExact blockHeader.contentSize match hty : blockHeader.type with | .rle => let b := blockBytes.val[0]'(by rw [blockBytes.property, blockHeader.contentSize_rle hty]; omega)
Focus on line 9. There's an array index there, which is exactly the sort of place that implicit invariants live: blockBytes had better not be empty! C-like languages will give you undefined behaviour in that case. Modern languages will throw at run-time, or only give you an optional value to avoid that. Lean has another option: prove that it's not empty. That's what line 10 does. blockBytes.property is the fact that it's as long as the requested read, i.e. exactly blockHeader.contentSize bytes long. blockHeader.contentSize_rle is this:
theorem BlockHeader.contentSize_rle (h : BlockHeader) (hty : h.type = .rle) : h.contentSize = 1 := by simp [contentSize, hty]
That's a proof that, when the type is rle, the contentSize is always one. With those facts, Lean can figure out the rest.
It's a really short proof and probably I could have figured that out myself, but we can aim much higher:
I wrote an implementation of the FSE table construction algorithm from the RFC. The RFC contains “test vectors” for it: three sample outputs from given probabilities. Obviously those go into unit tests. But, in Lean, we can also prove universal properties of the function:
theorem ofDistribution_wellFormed (h : ofDistribution accuracyLog probs = some t) : t.entries.size = 2 ^ accuracyLog ∧ (∀ s : Fin probs.size, t.entries.toList.countP (fun e => e.symbol == s.val) = probCells probs[s]) ∧ (∀ (i : Nat) (hi : i < t.entries.size) (v : Nat), v < 2 ^ (t.entries[i]'hi).nbBits → (t.entries[i]'hi).baseline + v < 2 ^ accuracyLog) ∧ (∀ (s : Fin probs.size), 0 < probCells probs[s] → ∀ x < 2 ^ accuracyLog, ∃! i : Nat, ∃ hi : i < t.entries.size, (t.entries[i]'hi).symbol = s.val ∧ (t.entries[i]'hi).baseline ≤ x ∧ x < (t.entries[i]'hi).baseline + 2 ^ (t.entries[i]'hi).nbBits) := …
Repeating that, in words:
Assuming that the table construction function, when given the “accuracy” constant and a list of symbol probabilities, produces a value, then:
- The table has the correct size for that accuracy.
- The number of states for a given symbol is correct given its probability.
- For all states, reading nbBits bits and adding the baseline value for that state produces a valid state number.
- For all symbols with non-zero probability, and for all target states, there's exactly one state for that symbol which can reach the target state.
These are the subtle assumptions that an optimised decoding inner-loop requires, and things that can only ever be implicit or mere comments in weaker type systems. Proving strong statements like that is part of the 10× effort that the seL4 retrospective described, and a major barrier to the adoption of dependent types in regular software. Several LLMs can do it automatically now in about 20 minutes, and using only a fraction of a $20/month subscription quota. It'll probably be table-stakes next year. I must admit that they needed to change the table-generating code when doing so: I had used too much Id.run (i.e. dropping into imperative mode) and that's harder for the proof machinery to work with. (But Lean are working on it.) I confirmed that the proofs type-check and that there are no sorrys.
Combining dependent types and LLMs is not a new idea, but not much has been done on applying the combination to quotidian software engineering. Lots more experience would be needed. Very strong types can amplify the scope of changes as they have to be propagated out through all the derived types. Perhaps the proof effort scales poorly in larger systems, such that even modern LLMs can't keep up. Lean is a high-level language, and that's not suited to everything. (My toy Zstandard decoder is 10× slower than zstd on the command line.) Still, proof automation is here now and we, practically speaking, have a new type of programming language available to us. That's exciting!
(I'm not publishing the code because, frankly, for a small, well-defined case such as this, the LLMs can probably do a better job than I did. I did this to learn Lean a little and I don't hold my explorations up as an exemplar. This was inspired by lean-zip which does much more, includes a compressor, and proves round-tripping!)
Aside: verified assembly
AWS made LNSym: a semantics and simulator for AArch64. That's cool. Perhaps we could use it to show equivalence between an optimised assembly implementation of some functions, and their Lean counterparts, and then use the assembly code at run-time? Then we could let LLMs rip at optimisation and they couldn't introduce any functional bugs. Verified assembly is well-trodden in crypto implementations, but perhaps now it could be cheap?
I put some (mostly LLM) time into trying this. The small popcount example from the repo uses bv_decide, which is a certifying SAT solver, and that example requires more memory than my system has, which doesn't bode well. Tiny functions do work, and it is possible to get an equivalence proof to tiny Lean functions, and then to use extern to call them at run-time! But I, and a few LLMs, couldn't get it to scale any further.
TRMNL (27 Jul 2025)
The TRMNL is an 800×600, 1-bit e-ink display connected to a battery and a microcontroller, all housed in a nice but unremarkable plastic case. Because the microcontroller spends the vast majority of the time sleeping, and because e-ink displays don't require power unless they're updating, the battery can last six or more months. It charges over USB-C.
When the microcontroller wakes up, it connects to a Wi-Fi network and communicates with a pre-configured server to fetch an 800×600 image to display, and the duration of the next sleep. You can flash your own firmware on the device, or point the standard firmware at a custom server. The company provides an example server, although you can implement the (HTTP-based) protocol in whatever way you wish.
I considered running my own server, but thought I would give the easy path a try first to see if it would suffice. The default service lets you split the display into several tiles, and there are a number of pre-built and community-built things that can display in each. None of them worked well for me, but that's okay because you can create your own private ones. They get data either by polling a given URL, or by having data posted to a webhook. The layout is rendered using the Liquid templating system, which I had not used before, but it's reasonably straightforward.
I wrote a Go program hosted on Cloud Run which fetches the family shared calendar and converts events from the next week into a JSON format designed to make it trivial to render in the templating system.
With a 3D-printed holder, super glue, and some magnets, it's now happily stuck to the fridge where it displays the current date and the family events for the next week.
The most awkward part of the default service is managing the refreshes. The device has a sleep schedule, and so do the tiles, which are only updated periodically. So the combination can easily leave the wrong day showing. It would be helpful if the service told you when the device would next update, and when a given tile would next update. But it's not a huge deal and, after a little bit of head scratching, I managed to configure things such that the device updates in the early hours of the morning and the tiles are ready for it.
The price has gone up a bit since I ordered one, and you have to pay an extra $20 for the Developer Edition to do interesting things with it. So it ends up a little expensive for something that's neat, but hardly life-changing. But maybe you'll figure out something interesting for it! (Or you can repurpose an old Kindle into a TRMNL device.)
Continuous Glucose Monitoring (29 Jun 2025)
Continuous glucose monitoring has been a thing for a while. It's a probe that sits just inside your body and measures blood glucose levels frequently. Obviously this is most useful for type 1 diabetics, who need to regulate their blood glucose manually.
(At this point, I would be amiss not to give a nod to the book Systems Medicine, which I think most readers would find fascinating. I can't judge whether it's correct or not, but it is a delightful exploration of a bunch of maladies from the perspective of differential equations.)
But CGMs have been both expensive and prescription-only. And I am not a diabetic, type 1 or otherwise. But technology and, more importantly, regulation have apparently marched on, and even in America I can now buy a CGM for $50 that lasts for two weeks, over the counter. So CGM technology is now available to the mildly curious, like me.
The device itself looks like a thick guitar pick, and it comes encased inside a much larger lump of plastic that has a pretty serious-looking spring inside. It takes readings every 5 minutes but only transmits every 15 minutes. You need a phone to receive the data and, if the phone is not nearby, it will buffer some number of samples and catch up when it can. The instructions say to keep the phone nearby at all times, so I didn't test how much it will buffer beyond an hour or so.
I've got both an Android and an iPhone, but for this the iPhone was a more convenient device. So everything following probably applies to both ecosystems, but I've only tested it in one.
The app is well made, although you can feel the lawyers & regulators hovering over every part of it. It gives you instructions about how to “install” the sensor, which you do by holding the big lump of plastic with the spring over a suitable spot on your body and then pressing the button.
It's not a large needle, but it's not trivial either. There is a soupçon of cyberpunk about applying it to yourself in the bathroom but, honestly, my first thought after pressing the button and hearing the bang of the spring releasing was, “oh, it didn't work.” Because I didn't feel anything at all. But when I lifted the applicator away, there it was. And after a little while it started providing readings.
It's held in place with some sticky plastic, and you can shower with it on. After a week or two the plastic does start to get a bit messed up. Honestly, I would have preferred to have replaced cover every few days, but I only got one in the box.
I placed it on the upper arm as suggested in the instructions. I put it a little bit further around and I didn't have any problems laying down on that side.
What did I learn? In a couple of cases, meals that I thought would be fairly healthy (or at least not terrible) were pretty terrible. There'll be some things that I'll avoid eating more than I had before. In the bucket of “things that should have been obvious but the effect is still stronger than I thought”: exercise really works. Even a brisk walk resets my blood sugar quite significantly. And the Hawthorne effect works even when you're doing it to yourself.
The app does not seem to let you export the data. However, at least on iOS you can connect it to Apple Health. And Apple Health does let you export all of your data as a big XML file. So a little bit of Go code later, I have a CSV of everything it recorded and per-day averages and variations.
The sensor will stop working after 15 and a half days. It says exactly 15, but I think it will give you another half day to switch over to another sensor. It comes out easily, although the sticky residue takes some effort to get off the skin.
I did not switch to another sensor. I will probably do it again, but I'll give it a while since, as I expected, most of the insights that I think I'm going to get, I got fairly rapidly. Honestly, I think the gamification of not wanting to spike my blood sugar was perhaps the most effective part of it. I still think it's cool that this is a thing now.
A Tour of WebAuthn (23 Dec 2024)
I've done a bunch of posts about WebAuthn/passkeys over time. This year I decided to flesh them out a bit into a longer work on understanding and using WebAuthn. If you were at the FIDO conference in Carlsbad this year, you may have received a physical, printed booklet of the result. It took a while to get around to converting to HTML, but the text is now available online.