Sections
A file starts with the problem description and the constraints in a comment. A namespace follows, with these sections in order.
InputandOutput- Type abbreviations for the data the program accepts and returns.
- Specification helpers
- Definitions that the specification refers to.
- Precondition (Validity predicate) ·
isValidInput - A Boolean predicate that encodes the input constraints.
- Declarative postcondition (Ideal specification) ·
<name>_spec - A proposition that characterizes the correct outputs for an input, independently of how they are computed.
- Executable postcondition (Decidable specification) ·
<name>_check - A Boolean function on an input and an output that expresses the same condition. The equivalence theorem
<name>_check_iff_specfollows: on valid inputs, the executable postcondition returns true exactly when the declarative postcondition holds. - Implementation helpers and Main algorithm
- A function from
InputtoOutput, with the helpers it needs. - Correctness theorem ·
<algorithm>_correct - On valid inputs, the implementation satisfies the declarative postcondition. The proof is complete in AuXSpec-Test and left as
sorryin the other files.
Test layers
Test cases are #guard commands, which fail at compilation when the expression is false. They are grouped into layers by the component under test.
| Layer | What runs | Expected |
|---|---|---|
| L1 | A valid input through isValidInput | Accept |
| L1b | An invalid input through isValidInput | Reject |
| L2 | A valid input and a correct output through the executable postcondition | Accept |
| L2b | A valid input and an incorrect output through the executable postcondition | Reject |
| L3 | The output of the implementation against the expected output | Match |
| L4 | The output of the implementation through the executable postcondition | Accept |
Example
A complete file for a one-line problem. Plus One is a file from the dataset.
import Mathlib /-!# Increment Return the input plus one.-/ namespace Increment abbrev Input := Intabbrev Output := Int /-! ### Specification helpers -/ def successor (x : Int) : Int := x + 1 /-! ### Validity predicate (V) -/ def isValidInput (input : Input) : Bool := decide (0 ≤ input) /-! ### Ideal specification (P_spec) -/ def increment_spec (input : Input) (result : Output) : Prop :=result = successor input /-! ### Decidable specification (P_check) -/ def increment_check (input : Input) (result : Output) : Bool :=decide (increment_spec input result) theorem increment_check_iff_spec (input : Input) (result : Output)(h : isValidInput input) :increment_check input result ↔ increment_spec input result := bysimp [increment_check] /-! ### Main algorithm (impl) -/ def increment (input : Input) : Output := input + 1 /-! ### Correctness -/ theorem increment_correct (input : Input) (h : isValidInput input) :increment_spec input (increment input) := byrfl /-! ## Unit tests -/ /-! ### L1 — Validity guard -/#guard isValidInput 2 /-! ### L1b — Negative validity -/#guard !(isValidInput (-1)) /-! ### L2 — Specification guard -/#guard increment_check 2 3 /-! ### L2b — Negative specification -/#guard !(increment_check 2 4) /-! ### L3 — Algorithm output -/#guard increment 2 == 3 /-! ### L4 — Integration -/#guard increment_check 2 (increment 2) end Increment