Reference¶
Where each idea appears¶
| Idea | Chapter | Where in the engine |
|---|---|---|
| Packages, specs and bodies | 1 | adawars-angles.ads, .adb |
| Modular types | 1 | Angles.Angle |
| Range types and subtypes | 2 | Geometry.Coord, Rules |
| Named numbers | 2 | Geometry.Sub, Rules.Tick_Rate |
| Enumerations, arrays indexed by them | 2 | Rules.Weapon, Rules.Weapons |
| Expression functions | 1, 2 | everywhere |
| Records and aggregates | 2, 3 | Geometry.Point, Worlds.Jet |
Dynamic_Predicate |
3 | Worlds.Jet, Worlds.Missile, Worlds.Flare |
| Unconstrained arrays | 3 | Worlds.Jet_Array |
| Discriminants and variant records | 3 | Worlds.World, Worlds.Outcome |
| Quantified expressions | 2, 3 | Worlds.Two_Flying, Rules.Lemma_Boost_Outruns_Missiles |
Pre and Post |
4 | Guidance.Position, Guidance.Lock_On |
| Run-time contract checks | 4 | -gnata, the tests |
| Silver: no run-time errors | 5 | Sensors.In_Cone |
Flow analysis, Global |
5 | the lemmas |
| Loop invariants and variants | 6 | Worlds.Survivor, Guidance.Lock_On |
| Delta aggregates | 7 | every phase in Simulation |
| Frame conditions | 7 | every phase's Post |
| Opaque bodies | 7 | Simulation.Advance |
| Ghost code and lemmas | 8 | Angles.Lemma_Diff_Rotate, Trig.Table_Facts |
Logical_Equal |
8 | Simulation.Lemmas |
Recursive specifications, Subprogram_Variant |
9 | Simulation.Row_Blast |
| Information-flow properties | 10 | Views.Observe |
| Soundness and completeness | 11 | Wire.Decode, Wire.Lemma_Complete |
Assert_And_Cut |
11 | Wire.Lemma_Complete |
| Protected objects and tasks | 12 | server/src/adawars_server-matches |
Glossary¶
- Aggregate
- An expression that builds a record or array value:
(X => 0, Y => 0),[others => Idle]. - Aspect
- A property attached to a declaration with
with:Pre,Post,Ghost,Dynamic_Predicate,SPARK_Mode. - Attribute
- A property of a type or value, written with an apostrophe:
'First,'Range,'Result,Integer'Max. - Contract
- The preconditions, postconditions and predicates that state what code requires and guarantees.
- Counterexample
- Values GNATprove offers, after
e.g., for which an unproved check might fail. - Discriminant
- A record field that fixes the record's shape: its variant, or the size of its arrays.
- Frame condition
- The part of a postcondition that says what does not change.
- Ghost code
- Code that exists only for verification and can never affect the running program.
- Invariant
- A fact that stays true: across loop iterations (a loop invariant), or
across every step of the game (
Valid). - Lemma
- A ghost procedure kept for its proved postcondition. Calling it makes the fact available.
- Predicate
- A rule attached to a type, checked on every whole value of it.
- Soundness and completeness
- A decoder is sound if whatever it accepts is valid, and complete if it accepts everything that is.
- SPARK
- The subset of Ada that GNATprove can analyse.
- Variant
- A value that strictly decreases (or increases) with each loop iteration or recursive call, proving that the loop or recursion ends.
- Verification condition
- A formula GNATprove generates for a check, true exactly when the check can never fail.
Further reading¶
- learn.adacore.com: interactive courses on Ada and SPARK.
- The SPARK User's Guide: everything GNATprove can do, and how.
- Implementation Guidance for the Adoption of SPARK: the source of the Stone to Platinum levels.
- The Ada Reference Manual: the language definition, for when you need the exact rule.
In this repository, PROOFS.md lists what is proved about every engine unit,
and DESIGN.md gives the game's rules and the reasons for them.