buenomini

Porting existing code to Bend to prove it

Bend can prove code correct, but only Bend code, so I've been thinking about an agent porting the real code as the bridge.

6 min readai, learning

I've been playing with Bend lately. It's a pure language that looks a lot like Python (sadly), and it checks proofs. You write the rules your code must follow as laws, an AI writes the proofs, and bend PROOF.bend prints ALL PROOFS CHECK or SOME PROOFS FAIL. To be honest, I tried to understand how it actually does it, but it bends my brain (tudum-ts)

The split is what got me interested tho. The laws live in LAWS.bend and a human owns that file. The proofs live in PROOF.bend and the AI writes them. I can't write a proof, but I can read a law and tell if it's the rule I want. Say you have a function that decides if someone can see a document:

# The owner of a document can always see it.
law owner_sees_own_doc:
  for shared: Bool
  for reader: Bool
  {Doc.can_view(True{}, shared, reader) == True{} : Bool}

No tests run when Bend checks this. It claims it works more like algebra. It simplifies the code with the inputs left as unknowns. If the code says "owner, so yes" and owner is True, that branch collapses to True and the law holds. When it gets stuck on an unknown boolean, the proof splits into both cases and checks each one. For lists it uses induction, which is basically dominoes: prove it for the empty list, prove that one more element keeps it true, and it holds for a list of any length.

A test samples inputs and a proof covers all of them. For small inputs that matters less than it sounds, and you can probably get away with some good matrix testing. Bend earns its place when the inputs have no limit, like lists. I also see it probably being useful on large codebases with a lot of people working on them, laws can make the unknown unknowns break your builds.

# Bend can only prove Bend

The proofs stop at the edge of Bend. It compiles to JavaScript, so TypeScript can import it, but it can't read TypeScript. There's no translator, and anything you import from JS sits outside the proofs. Most of the code I work with is TypeScript and async.

What I wanted to know is if you can build a bridge to code that already exists.

# Porting the pure core

A lot of code that looks impure has a pure core. Reducing all the code and porting is a job an agent can do. You point it at the real function, it writes the Bend version, states the laws you agreed on and writes the proofs. That work is what made formal proofs too expensive for normal code.

The obvious problem is that the port can be wrong. An agent translating code is one more place for a bug, and a proof about a wrong translation tells you nothing about your code. So the port needs its own check. So far I have a not so great solution for my playing around:

# The loop

flowchart LR
    A[Real code] -->|agent ports| B[model.bend]
    B -->|bend PROOF.bend| C[Laws hold]
    B -->|compile| D[model.mjs]
    D --> E[Compare]
    A --> E
    E -->|they disagree| B
  1. The agent ports a slice of the real code to Bend.
  2. bend PROOF.bend checks the laws against the model.
  3. Bend compiles the model to a JavaScript module.
  4. A test feeds the same random inputs to the compiled model and to the real code, and checks they give the same answer. With fast-check this is a few lines.
  5. When the real code changes, the comparison fails and the agent ports again.

Step 4 is the bridge. The proofs say the model follows the laws, and the comparison says the model behaves like the code. If the code reads a database, the comparison can run against a real test database too, as long as you can generate random setups to put in it.

# Two alarms

The two checks fail for different reasons. When a proof fails, the model breaks a law. If the port is faithful the real code breaks it too, so that's a bug report (or a law that's wrong).

When the comparison fails, the model and the code disagree. Either the port was wrong from the start, or someone changed the code and the port is stale. The fix there is a new port, and the code is probably fine.

# What porting digs up

Porting makes you write down things the code only assumes. Take a law that the list view and the single item view always agree on who sees what. In the model it might only hold if a database index guarantees one row per user and document. The real code depends on that index too, it just never says so. The proof won't go through without it, so the assumption ends up in the law where people can see it.

I think that might be worth something even if you never fully trust the proofs.

# Obvious limitations

The agent can change a law to make the proof easier. So a human should own every change to LAWS.bend.

It's also easy to write a comparison that checks nothing. If it compares the wrong outputs, or the random inputs never reach the interesting cases, it passes for any port. The way to check it is to give it a port you know is wrong (drop one condition) and see it fail. This is not a new problem in invariant testing.

Then there's the JS boundary. Bend's compiled module takes booleans as plain true and false. If you pass the shape the guide suggests for constructors, {$: "False"}, it runs without an error and gives wrong answers, because any JS object is truthy. The module ships no types either, so you write a typed wrapper, and the proofs don't cover that wrapper.

# What I'm not sure about

The whole chain is a proven model plus a sampled comparison. That's a lot stronger than example tests, and it still leaves the real code unproven. The weak link is the sampling, which is the thing proofs were supposed to get rid of. I don't know yet if it gives enough confidence to test the real code any less.

I'm also not sure which code is worth it. Small pure functions are the easy targets, but they barely change and usually have good tests already. Where I think it pays off is the big shared code I mentioned at the start: critical, changed by a lot of people, with rules that hold for any number of inputs (a permission engine, say). That's also the hardest code to port, and every change to it can mean a new port and new proofs.

The other way around is to ship the Bend, compile it, import it, and the code that runs is the code that's proven. That is probably the intended way, but it requires teams adopting a 2 month old language into prod as the primary place for business logic (huge no-no).