Tollens
Blog

Why formal methods? The short story

Want the full story? This post started as an internal note, written to explain the core of what we do to new members of the team. Eventually we turned it into a full post, which walks through the story with everything you need to understand it and figure things out for yourself. It takes about 30 minutes to read if you are focused. This one tells the same story in 10 :)

A few days ago, a friend asked me: “You always take lifts as an example, but why would anyone need to prove anything about a lift? Doesn't the person who programs it just have to be careful?”

I thought that deserved a polished answer. So here is a (fictional) story about what it may take to get a lift design right.We have no hardware or lift engineering skills: the core of this story is the logical puzzle more than the context. If anything in the process of designing a lift is glossed over or misrepresented, please tell us!

The sentence in red

An engineer is asked to build the controller of a lift: eight floors, one car, one set of doors. The controller is the small piece of software that decides everything the lift does. Information comes in from buttons and sensors, orders go out to the motors.

The spec is short, with one sentence in bold and red:

The doors must never be open when the car moves.

This sentence bears a load that the others do not: it must not just hold most of the time, it must hold all the time.

Our engineer is careful, and careful people think about failure first. There are many cases to think about. For instance, if their controller crashes, whoever is inside is stuck in a metal box. So they wire the door-opening button inside the car directly to the door motor, bypassing the software entirely. Call it the thick wire. It is standard practice, and a good idea.

Two ways to open the door. Only one goes through the software.

Then they keep thinking. What if a passenger with a big bag leans on the button by mistake and opens the doors between floors? So they interlock it: the button acts on the doors only while the lift motor is off. Between floors, it does nothing at all. Careful again.

The thick wire, cut whenever the car moves.

Then again, doors take a second or two to close, and somebody may be standing in between. The controller should not just assume they closed because it asked, right? So it waits for the door sensor to report shut, and only then ticks a box in its memory: confirmed. Whenever it opens the doors, it unticks the box. And it only starts the motor if the box is ticked. That condition is the sentence in red, translated into code.

Three for three

The controller is designed and coded. But before shipping, our engineer does what people who take their work seriously do, and spends a bit more time imagining the worst.

  • A claustrophobic child holds DOOR OPEN for the entire journey? The thick wire is dead while the car moves, so the doors stay shut until the car reaches a floor.
  • Somebody blocks the doors open at a landing? The doors never report shut, the box stays unticked, and the car refuses to move.
  • The controller crashes while the doors are open, then reboots? It starts with the box unticked, so it will not move the car before it has seen the doors close again. Annoying, but safe!

Three for three. Then comes a scale model, and a week of tests: every floor, calls from two floors at once, DOOR OPEN held, released, hammered, the power cut mid-journey. The car never once moves with its doors open.

The real lift goes in. The engineer is happy.

The phone call

Three weeks later, the phone rings.

“Uhm, hey. It's about the lift. There's been… a thing.

“A woman on the third floor was getting an electric piano into the car. Big thing, half in, half out. She held the open button to keep pushing it in. And then somebody upstairs called the lift. And it went. With the doors open.

“She's fine. No, no, don't worry, she's fine. The piano is crushed flat, though.”One honest omission. A real lift has a line of defence I have left out: the door contacts sit in series in a safety chain, a loop of switches wired so that if any of them opens, the motor is physically cut off, no software involved. It is the reason this precise accident is rare in real lifts. I left it out because most of the systems you and I build do not come with one, and because the reasoning error is entirely real. Where you can get a hardware backstop, take it.

What happened

The engineer pulls up the logs. You will have to trust me that nothing is hidden here: no component broke, none behaved unexpectedly. It is only logic. (If you would rather figure it out for yourself, every rule is laid out in the full post, and you are very welcome to try.)

  • The woman calls the lift from the third floor. It is already there, so the doors open, and the controller unticks the box.
  • She walks in to put her bag down, before going back for the piano.
  • The doors time out and close. The sensor reports shut, and the controller ticks the box. So far, so good.
  • She has not pressed a floor button yet, since the piano is still outside. So she presses DOOR OPEN.

Reading that line of the log, the engineer starts to understand. The DOOR OPEN button is not wired to the controller at all. The thick wire opens the doors, and the controller, which never asked for it, still has its box ticked.

  • While she wrestles with the piano, the doors start closing every time she lets go of the button: as far as the controller knows, they are supposed to be shut. So she keeps pressing DOOR OPEN, and the thick wire keeps them open, exactly as designed.
  • Then somebody on the seventh floor calls the lift. The controller looks at its situation: idle, a call elsewhere, and the box says the doors are shut. It starts the motor.
Every decision was right, given the box. The box was wrong.

Notice what broke: nothing. The thick wire did its job. The interlock did its job. The box did its job, faithfully remembering that the doors had been shut, which they had, a few minutes earlier.

The problem was an honestly tricky path, along which the controller's picture of the world quietly drifted away from the physical reality.

Why careful was not enough

So, back to my friend's question. Doesn't the person who programs it just have to be careful?

Our engineer was careful. They thought about many, many scenarios. They put in mechanisms to prevent them, and went the extra mile of checking that those additions did not create new risks. But tests and imagination can only get you so far.

And testing harder would not help much. This lift is a toy example; real systems are far more complex, with orders of magnitude more moving parts interacting. What the engineer wants to be sure of is not a list of situations, it is every possible history of the lift: every sequence of presses, arrivals and door movements, in every order, of any length. That set is infinite, and it branches. A week of tests is a sample of it. This accident needs a handful of ordinary events in one particular order, and a sample can miss that for a very long time.Mathematicians may know this feeling. In 1919 Pólya conjectured that among the numbers up to any n, at least half have an odd number of prime factors. It was checked, and checked, and it held for every n anybody could reach. It is false. The smallest counterexample is n = 906,150,257. Nobody was being careless. They simply could not count high enough.

Tests follow a few branches. The accident was on another one.

You do not check a theorem by trying examples. You prove it. And that, it turns out, is a lot less work than it sounds.

What a proof would have asked

To prove the lift safe, our engineer needs nothing they do not already have. The rules were already on a whiteboard, each of the shape “when this is the case, this happens”: nine of them, counting the door, the thick wire and the car. And there is the sentence in red.

A proof tool takes the two and does the tedious part. For each rule, it asks: if everything was safe just before, is it still safe just after? Where it can see why on its own, it moves on. Where it cannot, it stops and asks a question.

Eight rules go through without a word. On the ninth, the one that starts the motor, the tool asks: the box is ticked. Why is the door shut?

Eight rules go through. The ninth gets a question.

The engineer knows the answer. They have been relying on it all along: when the box is ticked, the door really is shut. It sounds so obvious that nobody ever writes that kind of thing down. But it is an assumption, and in our case, it could be false. So the tool asks you to state it, just to be sure. The engineer writes it down, and the tool checks this new sentence against the nine rules, the same way.

It stops once more, on the thick wire. The door was shut and the box ticked. Somebody pressed DOOR OPEN. Now the door is open and the box is still ticked. Why is that fine?

The engineer looks, and frowns. There is no good answer, because it is not fine. That is the piano, found on a whiteboard, three weeks before the phone rang. Asking every question, exhaustively, is how you catch any particular run of events that could break your system. The fix is simple, a single line changed. Run the tool again, and it has no questions left. The sentence in red is proved.

With such a tool, the engineer would not have had to imagine the piano, or think of the right test, or hold the whole lift in their head at once. They only had to answer questions, one rule at a time, about things they already knew. A proof does not go looking for the accident. It asks you to defend every sentence you are leaning on, including the ones you never noticed writing, and hands back the one you cannot.

Not only would it have saved a lot of cost and damage control, it may even have saved time: all those hours spent imagining worst cases, when the tool would have found the one that mattered in a matter of seconds!

What you have, once it is proved

When you have a formal proof, you have a strong guarantee. Here: there is no sequence of events whatsoever that ends with the motor running and the door open. Not “none was found”. None exists.

If there is ever a problem, it will not be the controller.

And the second prize, which may be the bigger one: the tool made our engineer write down a sentence that appears in no specification, that nobody would have thought to check, and that had been quietly true until somebody added a thick wire for excellent reasons. It was a sentence everyone on the team would have agreed with, if only somebody had asked.

So, my friend, the answer is yes: the person who programs it has to be careful. Being careful is what lets you answer the questions. Formal methods are what give you a real chance of being careful enough.

And your job?

This post takes lifts and engineering as an example, but the scope is much broader. The ingredients were a system whose rules can be written down, one thing that must never happen, and the gap between checking some cases and checking all of them. We think those three show up in a great many jobs. Here are our guesses.

  • An economist? A benefits schedule is a set of rules, and “no household loses money by earning one euro more” is your sentence in red. Are the cliff-edges in the tax code places where two good rules meet badly?
  • A chemist? The interlock on a reactor, never heat while the vent is shut, is the sentence in red word for word. Is the relief valve your thick wire?
  • A doctor? A dosing protocol is a set of rules over time. Is “these two drugs are never active at the same time” written down anywhere, or just known?
  • A lawyer, a regulator? Eligibility rules are already a formal system, interpreted by people instead of machines. Where are the gaps harder to see?

The recipe does not change. Write down the rules, all of them, including the ones too obvious to state. Write down the one thing that must never happen. Then let something check it, and take its questions seriously, because that is where the discoveries are.

But those are only guesses, and you know your job far better than we do. So take a minute and think about it: what are the rules of your work, and what is your sentence in red?

This is what we are building at Tollens: a tool that lets you make the argument above in your own notation, in your own field, without first having to learn logic and computer science. And to build it well, we need to hear from you. Whether your field is on the list or not, whether you think it would fit or you are sure it would not, write to us. We would genuinely love to hear from you 🙂

Write to us

Even just a few words, we’ll be happy to hear from you.

Privacy settings

You can change your mind at any time, from the link at the bottom of every page.