formal

package
v0.0.6 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 11, 2026 License: Apache-2.0 Imports: 18 Imported by: 0

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

View Source
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

View Source
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.

View Source
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.

View Source
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 Build

func Build(ctx context.Context, o Options) (string, error)

Build runs lake build and AlgoExtract, and returns the path of decls.jsonl.

func ClaimClass

func ClaimClass(bound string) string

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

func ClassOf(typ string) string

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

func IsClassLemma(typ string) bool

IsClassLemma tells if a type states an asymptotic class, such as `f =O[Filter.atTop] g`.

func MirrorOf

func MirrorOf(rel string) string

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

func Mirrors(mod, rel string) bool

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

func (d Decl) Disallowed() []string

Disallowed returns the axioms of d that the policy does not permit.

type Decls

type Decls map[string]Decl

Decls maps each full name to its declaration.

func Load

func Load(path string) (Decls, error)

Load reads a decls.jsonl file.

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

func Check(c *node.Corpus, ds Decls) []Finding

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

func CheckClaims(n *node.Node, ds Decls) []Finding

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

func CheckNode(n *node.Node, ds Decls) []Finding

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.

func (Finding) Sev

func (f Finding) Sev() string

Sev returns the severity of the finding: block, level or warn.

func (Finding) String

func (f Finding) String() string

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.

type Pos

type Pos struct {
	Line    int `json:"line"`
	EndLine int `json:"end_line"`
}

Pos is the line range of a declaration in its module.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL