Documentation
¶
Overview ¶
Package formal builds the Lean package of the content repository and reads what it proves (spec 07).
Build runs lake build in the lean directory, then runs AlgoExtract (Extract.lean) with lake env lean. AlgoExtract writes one JSON line for each declaration in the namespace Algo to decls.jsonl. Check reads that file and reports each declaration that uses an axiom outside the policy of 07.5, and each name of a lean field that does not exist.
Index ¶
- Constants
- Variables
- func Build(ctx context.Context, o Options) (string, error)
- func ClaimClass(bound string) string
- func ClassOf(typ string) string
- func IsClassLemma(typ string) bool
- func MirrorOf(rel string) string
- func Mirrors(mod, rel string) bool
- type Decl
- type Decls
- type Finding
- type ModuleTime
- type Options
- type Pos
Constants ¶
const ( SlowModule = 60 * time.Second TooSlowModule = 300 * time.Second )
The limits of rule L10 (spec 07.18). A module that takes more than SlowModule to build gets a warning, and a module that takes more than TooSlowModule blocks the merge.
Variables ¶
var Allowed = []string{"propext", "Classical.choice", "Quot.sound"}
Allowed are the axioms that a proof can use (spec 07.5). Each other axiom, such as sorryAx or Lean.ofReduceBool, fails the build.
var Kinds = map[string][]string{
"model": {"def"},
"spec": {"def", "inductive", "structure"},
"correct": {"theorem"},
"cost": {"theorem"},
"space": {"theorem"},
}
Kinds are the kinds that each key of a lean field must name.
var Severities = map[string]string{"L01": "block", "L02": "level", "L03": "block", "L05": "level", "L07": "level", "L09": "block", "L10": "warn"}
Severities are the severities of the L rules in 13.3: a block rule stops a merge, and a level rule keeps the node below the level that needs it.
Functions ¶
func ClaimClass ¶
ClaimClass returns the class of a front matter bound in the same normal form, such as "nlogn" for "Θ(n log n)". It returns "" when the bound is not of the form Θ(...), O(...) or Ω(...).
func ClassOf ¶
ClassOf returns the class of a class lemma in a normal form, such as "nlogn" for `f =O[Filter.atTop] fun n => ↑n * Real.log ↑n`. It returns "" when typ is not a class lemma.
func IsClassLemma ¶
IsClassLemma tells if a type states an asymptotic class, such as `f =O[Filter.atTop] g`.
func MirrorOf ¶
MirrorOf returns the module that mirrors the node path in full (spec 07.2): nodes/graphs/shortest-paths/dijkstra gives Algo.Graphs.ShortestPaths.Dijkstra.
func Mirrors ¶
Mirrors tells if a module mirrors the node path (rule L09). The last part is the slug in CamelCase, the first part after Algo is the top area, and the parts between are some of the sub-areas, in order. So both Algo.Sorting.ComparisonSorts.MergeSort and Algo.Sorting.MergeSort mirror nodes/sorting/comparison-sorts/merge-sort.
Types ¶
type Decl ¶
type Decl struct {
Decl string `json:"decl"`
Kind string `json:"kind"`
Module string `json:"module"`
Type string `json:"type"`
TypeHash string `json:"type_hash"`
Axioms []string `json:"axioms"`
Deps []string `json:"deps"`
Sorry bool `json:"sorry"`
Computable bool `json:"computable"`
Doc string `json:"doc,omitempty"`
Pos *Pos `json:"pos,omitempty"`
}
Decl is one line of decls.jsonl.
func (Decl) Disallowed ¶
Disallowed returns the axioms of d that the policy does not permit.
type Finding ¶
type Finding struct {
// Rule is the audit rule of 07.15, such as L01 or L03.
Rule string
// Where is the declaration, or the node and its field.
Where string
Msg string
// Node is the slug of the node of the finding, and Decl the declaration, when there is one.
Node string
Decl string
// Severity, when it is not empty, overrides the severity of the rule in Severities. L10 uses it, because a slow module is a warning and a very slow module blocks.
Severity string
}
Finding is one problem that Check finds.
func Check ¶
Check reports each declaration that uses an axiom outside the policy (rule L03), and each name of a lean field that is not in ds or has the wrong kind (rule L01). The findings are in a stable order.
func CheckClaims ¶
CheckClaims compares the time claims of a node that has lean.cost with the class lemmas of its module (rule L05). A claim with no class lemma of the same class is a finding. Space claims count only when lean.space is set.
func CheckNode ¶
CheckNode checks the lean field of one node: each name exists with the right kind (L01), the module mirrors the node path (L09), the correctness theorem names the spec and the model (L02), and the model is total and computable (L07).
func CheckTimes ¶
func CheckTimes(ts []ModuleTime) []Finding
CheckTimes reports each module that is slower than SlowModule (rule L10). The finding is a warning up to TooSlowModule, and blocks above it.
type ModuleTime ¶
type ModuleTime struct {
// Module is the module name, such as Algo.Search.BinarySearch, and File its path in the package.
Module string
File string
// Took is the time of the module alone, without the load of its imports. Wall is the time of the whole lean process.
Took time.Duration
Wall time.Duration
}
ModuleTime is the time that one module of the package takes to build.
func Time ¶
func Time(ctx context.Context, o Options) ([]ModuleTime, error)
Time elaborates each module of the namespace Algo again with the Lean profiler, and measures the time. Run it after the build, so that the modules that a module imports are built. The time of a module is the sum of the profiler times without import and initialization, because the load of Mathlib takes the same time for each module and is not the cost of its proofs. When the profiler gives no times, the time is the wall time. The result is sorted by module name.
type Options ¶
type Options struct {
// Dir is the Lean package, the lean directory of the content repository.
Dir string
// Out is the directory for decls.jsonl and the copy of Extract.lean, such as build/lean.
Out string
// NoBuild skips lake build, when the package is built already.
NoBuild bool
// Wrap changes a command before it runs, for example to run it in a container. Nil runs it on the host.
Wrap func(argv []string) []string
// Log gets the output of lake.
Log io.Writer
}
Options tell Build where the package is and how to run lake.