Tollens
Blog

Why formal methods? The full story

This is the long version. It started as an internal note, written to explain the core of what we do to new members of the team, and it takes its time: about 30 minutes if you are focused, and it is fairly technical. If you would rather have the same story in 10, the short version is here.

You are an engineer, and you have been asked to build a lift.

The project is straightforward: eight floors, one car, one set of doors. People press a button on a landing, the car comes, the doors open, they get in, they press a button, the doors close, the car goes.

The client didn't bother to explain in much more detail. You know how a lift works. There is just one very specific sentence in red in the brief.

This building will occasionally host groups of children whose safety is our priority. The doors must never be open when the car moves.

Everything else is comfort. But a lift can be dangerous, after all, door management is rated SIL 3, which roughly means that everything must be checked and re-checked.The relevant standard in Europe is EN 81-20, which assigns safety integrity levels to lift safety functions. SIL 3 is the highest it allows for programmable electronics: a function that needs SIL 4 cannot be solved with software at all, you have to design a different system. The framework for putting software inside those functions is called PESSRAL, and it is contested territory: one sharp critique argues that its two-channel requirement for SIL 3 can be satisfied with two identical channels, which is not obviously redundancy at all.

This (fictional) story tries to draw a picture of what it takes to get it 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 lift

Even a simple lift has rather many components. A car, a motor, a shaft, a set of doors, some buttons, sensors. And you have to take into account the people: users outside, waiting impatiently, and users inside, waiting for their floor.

Your team has dispatched the tasks, and you have been given one of them: building and programming the controller, the central piece of software that decides everything the lift does.

At its core it is pretty simple. You have buttons, you have some sensors, you have motors, and you keep some information over time. Outside of that box is the real world, inside is your domain, and every edge is either information coming in or an order going out.

So you draw this diagram. You sit back in your chair and think about it a bit.

Your system should also behave well when something fails. If your controller crashes for some reason, the user is stuck in a metal box. That is not acceptable.

So as an additional security you wire the inside DOOR OPEN button directly to the door motor, bypassing your controller entirely. This is standard practice, but you're happy you thought about it: your design would not have passed review without it.

However, a button that opens the doors unconditionally would be its own catastrophe. A person with a big bag could lean on it mid-ride and open the doors between floors.

So you interlock it: the direct wire is live only while the lift motor is off. If the car is moving, the button does nothing at all.

Take a minute to look at this diagram. This was supposed to be a simple system, but things are never that simple. You're eager to start writing the controller, but you're not sure your grasp on the whole system is firm enough yet.

The rules of the world

The controller is not the lift. The sentence in red talks about doors and a car, which are not things in your program: your software can ask the door to move, but it is not the only thing that can. So before writing what your controller does, you write down what everything else does. Each rule has the shape "when this is the case, this happens", and you land on four.

The door does as it is told. Ask for it to open, and it opens. Ask for it to close, and it closes, with one exception: it will not close on somebody holding DOOR OPEN. That exception is not a courtesy, it is a door refusing to shut on a person.

The third rule is your thick wire, written down as a rule of the world rather than as a line of your code. If somebody is holding DOOR OPEN and the lift motor is off, the door opens. Your software does not appear in it anywhere.

And the fourth is the car itself. The motor is on, so the car travels.

So the door motor has two clients. Your controller is one of them. The other is the person standing in front of it.

The rules of your controller

Your controller is a simple piece of software, but it still needs to remember a few things from one instant to the next. Which phase it is in, a countdown timer, the list of pending calls, and one tick-box, confirmed.

That box is worth a second. When the controller asks the doors to close, it should not just assume they did. Doors take a second or two, and somebody may be standing in them. So the controller waits for the door sensor to report shut, and only then ticks the box. Confirmed is the memory of that report. Hold on to the word memory.

The first rule is the one that ticks it: the door reads shut, and the controller writes it down. Call it CONFIRM.

Then the easy case. Somebody wants the floor the car is parked on, or the car has just arrived: serve this floor. Drop the call, ask the door to open, untick the box, start the timer.

The rest is housekeeping. While the doors are open the timer counts down, anybody holding DOOR OPEN restarts it, and at zero the controller asks the door to close. On arrival, stop the motor first, then serve the floor. The phase is just which of these the controller is in: idle, holding the doors open, or moving.

And the case that matters. A call from another floor: start the motor towards it, but only if the box is ticked. That condition is your translation of the sentence in red.

On the real chip this is a loop and about forty lines. But these five rules are what it means.

Is my design sound?

Before going further, you take a few minutes to convince yourself that the design is sound. A large part of building things for other people is wondering, in great detail, about the worst situations they will put your beautiful product in.

A claustrophobic child holds DOOR OPEN for the entire journey. Your thick wire is interlocked on the motor being off, so between floors that button is electrically dead. The doors stay shut. This is exactly the failure you imagined in your chair, and you are pleased with yourself.

Somebody blocks the doors open at a landing. The controller asks the door to close, but a door will not close on a person. So it stays open, CONFIRM never fires, the box stays unticked, and the car refuses to move. Good.

Your controller crashes entirely. The passenger presses DOOR OPEN, and the thick wire opens the doors without any help from your software.

Three for three. You have thought about the users and about yourself failing, and the design holds every time. Every one of those verdicts, incidentally, is correct.

Tuesday afternoon

You build a scale model and you test it, the way people who take their work seriously test things.

Up and down, every floor. Called from two floors at once. DOOR OPEN held, released, hammered. Doors blocked. The power cut mid-journey. Every scenario above and thirty more, dozens of times each, and the car never once moves with its doors open.

Then the real one goes in. You stand in the lobby of a finished building and watch your lift arrive, doors sliding open on a floor whose logic you wrote. It is one of the best days of your career.

Three weeks later

Your phone rings.

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

“So, a woman on the third floor was getting an electric piano into the car. Big thing, half in, half out. The doors started to close on it, so she held the open button from inside, and kept pushing the piano in.

“And then somebody upstairs called the lift. And it went. With the doors open. It went up with the piano sticking out, and the piano got caught between the car and the top of the doorway.

“She's fine. Really, she's fine. The piano is crushed flat, though.”

Before you read on

The car moved with its doors open. You had tested that for a week, so the answer is not in the tests. It is in the rules, and all nine of them are next to this text: four for the world, five for the controller.

There is a sequence of them, starting from an ordinary parked lift, that ends with the motor running and the door open. Only one rule can start the motor, so that is where the sequence has to end. The trap is not a typo, and it is not inside any single rule: every rule is correct on its own.

If you would like to try, it is worth five minutes.

What happened

She calls the lift. It is already parked on the third floor, so the controller serves it: the doors open, and the box is unticked. Exactly as designed.

The doors close behind her. She steps in to put her bag down before going back for the piano. The timer runs out, the doors close, the sensor reports shut, and CONFIRM ticks the box. A parked car, doors shut, nothing pending: this is where a lift spends most of its life.

She presses DOOR OPEN. She has not chosen a floor, since the piano is still outside. The motor is off, so the thick wire opens the door, with no involvement from your software at all. The controller is idle with nothing to do. It never opened the doors, so it never unticked the box. The box stays ticked.

She keeps holding it. While she wrestles with the piano, the doors start closing every time she lets go: as far as the controller knows, they are supposed to be shut. So she holds the button, and the thick wire keeps them open. Nothing about this looks like an accident. Then somebody on the seventh floor presses a call button.

The controller looks up. Idle, a call elsewhere, and the box says the door is shut. It starts the motor. The interlock worked perfectly. It checked the box, and the box said yes.

Motor running, door open. The one state you wrote down in red, at the very beginning, as the thing that must never happen.

Now put this beside the reassuring scenario from before: block the doors open at a landing, and the car will not move. That was true, and it is still true. The only difference is that here, the doors closed once, while she put her bag down, before she reopened them.

Two situations that are identical from inside the car. In one of them the lift is immovable. In the other it leaves.

Notice also what did not go wrong. The doors did not open mid-flight: your interlock prevented that, exactly as designed. The failure runs the other way, the car started moving while the doors were already open. The flaw was never inside the controller and never inside the door circuit. It lived in the join between them, because a join has no owner.

And this is why every test passed. You did test DOOR OPEN, but where a person naturally uses it: doors open, people getting in. There the controller has just opened the doors itself, so the box is already unticked, and the button is harmless every single time.

The dangerous state is the one where nothing is happening: a parked car, doors shut, nobody waiting, and somebody pressing DOOR OPEN anyway. Nobody writes that test, because "the lift is idle and a passenger touches a button" is not a scenario. It is an ordinary afternoon.

Why you may have missed it with a year of testing

You go back to the model and cannot reproduce it. The temptation is to test harder: more scenarios, more hours, a rig that presses buttons at random all night.

But what you are checking is not a list of situations, it is the set of possible histories: every sequence of presses, arrivals and door movements, in every order, of any length. That set is infinite, and it branches. A test is a sample of it, and a random rig is a faster sample. This accident needs a handful of ordinary events in one particular order, and a sample can miss that for a very long time.Mathematicians have a favourite story about this. 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.

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 you

Here is what it takes. You say what the machine is, which you have already done on a whiteboard: a state is a snapshot, floor, motor, door, phase, timer, calls, box. A run is what happens from switch-on, one rule at a time.

The sentence in red is now a sentence about every state of every run: if the motor is on, the door is shut. You hand the nine rules and that sentence to a proof tool, and it does the tedious part. It checks the sentence at switch-on, then tries each of the nine rules in turn to see whether it stays true.

Eight of them go through without a word. On the ninth, the rule that starts the motor, the tool stops and asks you a question. The box is ticked. Why is the door shut?

You know the answer. You have been relying on it all along, you just never wrote it down: when the box is ticked, the door really is shut. You would never put that in a specification. It is not a requirement, it is an assumption, and this is the first time anyone has said it out loud.

The tool takes your sentence and does the same tedious thing with it. Nine rules, two sentences, eighteen checks. Seventeen close. One does not: your thick wire, against the sentence you just wrote.

So it asks again. The door is shut, the box is ticked, the motor is off, somebody holds the button. The door opens. Now the door is open and the box is still ticked. Why is that fine?

You have no answer, because it is not fine. What you had in mind all along was one sentence, one every person in the design review would have nodded at: the door cannot open unless we ask it to. You built the thick wire specifically so that this would be false. It was the best idea you had that week.

That is the whole job. Nine rules you had already written, one sentence in red, two questions. An afternoon, three weeks before the phone rang. 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 it hands back the one you cannot.

What you have, once it is proved

The fix is one line: look at the door instead of the box. You make it, run the tool again, and it has no questions left. Here is what you have then, and it is worth being precise, because "we proved it" is easy to hear as "we tested it really hard". Before: the car did not move with its doors open in any of the thousand situations you tried. After: there is no sequence of events whatsoever that puts this machine in a state where the motor is running and the door is open. Not "none was found". None exists.Real lifts also get this kind of certainty from geometry. A piece of metal, called a skate or a clutch depending on who you learn it from, makes a landing door physically incapable of opening unless the car is there. Safety by construction rather than by belief. EN 81 requires the lock to engage by at least 7 mm before the car is permitted to move. Somewhere there is a document explaining why it is not 5 and not 10.

And the second prize, which may be the bigger one: the tool made you write down a sentence that appears in no specification, that nobody would think to check, and that had been quietly true until the day somebody added a hardwired button for excellent reasons, probably in a different meeting. It was a sentence you would have agreed with, if only somebody had asked you.One honest omission. A real lift has a line of defence I have left out: the door contacts sit in series in the safety chain, a loop of switches wired so that if any of them opens, the motor is physically de-energised, 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 and I have watched people make it. Where you can get a hardware backstop, take it. This article is about everything else.

And your field?

This post is not really about lifts. The ingredients were a system whose rules can be written down, one thing that must never happen, and the fact that checking cases is not proving. We think those three show up in a lot of places. Here are our guesses. Is one of them you?

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. Do the cliff-edges in the tax code look like a join nobody owns?

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 state machine. 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 the moment where it asks you a question seriously, because that is where the discoveries are.

Sometimes it has no questions, and you have something better than confidence. Sometimes it does, and there is a woman with an electric piano on the third floor who now never has to find out.


This is what we are building at Tollens: the thing that lets you do the argument above in your own notation, in your own field, without first having to learn logic and computer science. We are guessing about your field, and we would much rather hear it from you. If your work has rules and a sentence in red, tell us what it is 🙂


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.