Learn Ada with AdaWars¶
AdaWars is a real-time jet-combat battle royale. Humans and bots fly jets around a shrinking arena, firing dumbfire missiles and heat-seekers, dropping flares, boosting away and, if it comes to it, self-destructing. The last jet flying wins.
The rules of the game are written in Ada, in the subset called SPARK, and a tool called GNATprove proves things about them before the game ever runs:
- that no arithmetic overflows and no array is indexed out of bounds;
- that a heat-seeker always locks onto the hottest thing its seeker can see, and never onto the jet that fired it;
- that a boosting jet outruns every missile;
- that no player's view of the match contains a jet their sensors cannot see.
This course teaches Ada, and then proof, from the ground up, using that code. Every example is real: it is quoted from the engine, and every exercise is run against it, so the course cannot drift away from the code.
Who it is for¶
You know how to program in some other language. You have not written Ada, and you have not used a proof tool. You will learn:
- Ada: packages, strong types, records, arrays, expression functions and contracts (chapters 1 to 4).
- SPARK: what proving a program means, the levels of assurance, and how to write loops, specifications and lemmas the prover can follow (chapters 5 to 9).
- Real properties: a no-leak proof for what each player can see, and a parser proved sound and complete at the trust boundary (chapters 10 and 11).
- Where proof stops: the ordinary Ada server around the engine, with tasks and protected objects (chapter 12).
How to use it¶
Read the chapters in order; each builds on the last. Each has Try it exercises. Most of them ask you to break the engine on purpose and watch the prover object, because seeing what a proof catches is the fastest way to understand what it proves. Each exercise shows what the tools say once you make the change, and that is checked (see below).
Undoing an exercise
Every exercise edits a file under engine/src/. When you are done,
git diff shows what you changed and git restore engine/src puts the
engine back.
Setting up¶
You need Alire, the Ada package manager. It fetches the GNAT compiler and GNATprove for you. Then, from the repository root:
cd engine && alr build && cd .. # fetches the toolchain, builds the engine
make proofs # proves every engine unit
make test # runs the engine tests
make proofs runs GNATprove over the whole engine and fails if a single check
is unproved. It takes a few minutes. While doing the exercises you will mostly
prove one unit at a time, which is much quicker:
cd engine
alr exec -- gnatprove -P adawars.gpr -j0 --level=2 --checks-as-errors=on -u adawars-rules.adb
-u names the file to prove (its spec comes with it), -j0 uses every core,
--level=2 sets how hard the provers try, and --checks-as-errors=on makes
an unproved check fail the command, as it does in make proofs.
The course is checked too¶
Nothing in this course is taken on trust:
- Every Ada block is titled with the file it comes from, and
make learn-checkfails if the block is no longer in that file, word for word. - Every exercise is a diff, followed by what the prover, compiler or tests
must say once it is applied.
make learn-exercisesapplies each one to a scratch copy of the engine, runs the command and checks the output. If the engine changes so that an exercise no longer teaches what it says, the check fails.
So an exercise looks like this: the change to make, then what to expect.
postcondition might fail, cannot prove Boost_Speed > Weapons (K).Speed
e.g. when K = Dumbfire
The expect block's title says which command to run: prove FILE is the
GNATprove command above, report FILE the same with --report=all (which
lists the checks that pass too), build is alr build, and test builds
and runs the engine tests. The lines in the block are what the output must
contain; the real output says more, and the wording may vary a little
between versions of the tools. Chapter 2 explains this exercise.
To play the game itself, make play builds everything and serves it on
http://localhost:8484/. The README at the repository root covers the keys.
Where things are¶
| Path | What it holds |
|---|---|
engine/src/ |
The SPARK engine: one package per concern, all proved |
engine/tests/ |
Tests that run the engine with every contract checked |
server/src/ |
The ordinary Ada server: matches, bots, HTTP |
web/ |
The browser UI, which only draws what the engine reports |
PROOFS.md |
The ledger of what is proved about each unit |
DESIGN.md |
The game's rules and the reasons for them |
The engine is the part this course is about. It is a library with no input, output, tasks or global state: just types and functions, which is what makes it possible to prove.