Lean file format

Every AuXSpec problem is one Lean file. It holds a specification, an implementation, two theorems, and test cases, always under the same headings and in the same order.

Sections

A file starts with the problem description and the constraints in a comment. A namespace follows, with these sections in order.

Input and Output
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_spec follows: on valid inputs, the executable postcondition returns true exactly when the declarative postcondition holds.
Implementation helpers and Main algorithm
A function from Input to Output, 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 sorry in 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.

Test layers
LayerWhat runsExpected
L1A valid input through isValidInputAccept
L1bAn invalid input through isValidInputReject
L2A valid input and a correct output through the executable postconditionAccept
L2bA valid input and an incorrect output through the executable postconditionReject
L3The output of the implementation against the expected outputMatch
L4The output of the implementation through the executable postconditionAccept

Example

A complete file for a one-line problem. Plus One is a file from the dataset.

increment.lean
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