Reducibility hints are used in the convertibility checker. When trying to solve a constraint such a
(f ...) =?= (g ...)
where f and g are definitions, the checker has to decide which one will be unfolded. If f (g) is opaque, then g (f) is unfolded if it is also not marked as opaque, Else if f (g) is abbrev, then f (g) is unfolded if g (f) is also not marked as abbrev, Else if f and g are regular, then we unfold the one with the biggest definitional height. Otherwise both are unfolded.
The arguments of the regular
Constructor are: the definitional height and the flag selfOpt
.
The definitional height is by default computed by the kernel. It only takes into account other regular definitions used in a definition. When creating declarations using meta-programming, we can specify the definitional depth manually.
Remark: the hint only affects performance. None of the hints prevent the kernel from unfolding a declaration during Type checking.
Remark: the ReducibilityHints are not related to the attributes: reducible/irrelevance/semireducible. These attributes are used by the Elaborator. The ReducibilityHints are used by the kernel (and Elaborator). Moreover, the ReducibilityHints cannot be changed after a declaration is added to the kernel.
- opaque : ReducibilityHints
- abbrev : ReducibilityHints
- regular : UInt32 → ReducibilityHints
Equations
- Lean.instInhabitedReducibilityHints = { default := Lean.ReducibilityHints.opaque }
Equations
Equations
- (Lean.ReducibilityHints.regular h_2).getHeightEx = h_2
- h.getHeightEx = 0
Equations
- Lean.ReducibilityHints.abbrev.lt Lean.ReducibilityHints.abbrev = false
- Lean.ReducibilityHints.abbrev.lt x✝ = true
- (Lean.ReducibilityHints.regular d₁).lt (Lean.ReducibilityHints.regular d₂) = decide (d₁ > d₂)
- (Lean.ReducibilityHints.regular a).lt Lean.ReducibilityHints.opaque = true
- x✝¹.lt x✝ = false
Equations
- Lean.ReducibilityHints.abbrev.compare Lean.ReducibilityHints.abbrev = Ordering.eq
- Lean.ReducibilityHints.abbrev.compare x✝ = Ordering.lt
- (Lean.ReducibilityHints.regular a).compare Lean.ReducibilityHints.abbrev = Ordering.gt
- (Lean.ReducibilityHints.regular d₁).compare (Lean.ReducibilityHints.regular d₂) = compare d₂ d₁
- (Lean.ReducibilityHints.regular a).compare Lean.ReducibilityHints.opaque = Ordering.lt
- Lean.ReducibilityHints.opaque.compare Lean.ReducibilityHints.opaque = Ordering.eq
- Lean.ReducibilityHints.opaque.compare x✝ = Ordering.gt
Equations
- Lean.ReducibilityHints.instOrd = { compare := Lean.ReducibilityHints.compare }
Equations
- Lean.ReducibilityHints.abbrev.isAbbrev = true
- x✝.isAbbrev = false
Equations
- (Lean.ReducibilityHints.regular h_1).isRegular = true
- x✝.isRegular = false
Base structure for AxiomVal
, DefinitionVal
, TheoremVal
, InductiveVal
, ConstructorVal
, RecursorVal
and QuotVal
.
Instances For
Equations
- Lean.instInhabitedConstantVal = { default := { name := default, levelParams := default, type := default } }
Equations
- Lean.instBEqConstantVal = { beq := Lean.beqConstantVal✝ }
- isUnsafe : Bool
Instances For
Equations
- Lean.instInhabitedAxiomVal = { default := { toConstantVal := default, isUnsafe := default } }
Equations
- Lean.instBEqAxiomVal = { beq := Lean.beqAxiomVal✝ }
Equations
- Lean.mkAxiomValEx name levelParams type isUnsafe = { name := name, levelParams := levelParams, type := type, isUnsafe := isUnsafe }
Equations
- v.isUnsafeEx = v.isUnsafe
- unsafe : DefinitionSafety
- safe : DefinitionSafety
- partial : DefinitionSafety
Equations
- Lean.instInhabitedDefinitionSafety = { default := Lean.DefinitionSafety.unsafe }
Equations
Equations
- Lean.instReprDefinitionSafety = { reprPrec := Lean.reprDefinitionSafety✝ }
- value : Expr
- hints : ReducibilityHints
- safety : DefinitionSafety
List of all (including this one) declarations in the same mutual block. Note that this information is not used by the kernel, and is only used to save the information provided by the user when using mutual blocks. Recall that the Lean kernel does not support recursive definitions and they are compiled using recursors and
WellFounded.fix
.
Equations
- Lean.instBEqDefinitionVal = { beq := Lean.beqDefinitionVal✝ }
Equations
- Lean.mkDefinitionValEx name levelParams type value hints safety all = { name := name, levelParams := levelParams, type := type, value := value, hints := hints, safety := safety, all := all }
Equations
- v.getSafetyEx = v.safety
- value : Expr
List of all (including this one) declarations in the same mutual block. See comment at
DefinitionVal.all
.
Instances For
Equations
- Lean.instInhabitedTheoremVal = { default := { toConstantVal := default, value := default, all := default } }
Equations
- Lean.instBEqTheoremVal = { beq := Lean.beqTheoremVal✝ }
Equations
- Lean.mkTheoremValEx name levelParams type value all = { name := name, levelParams := levelParams, type := type, value := value, all := all }
Value for an opaque constant declaration opaque x : t := e
- value : Expr
- isUnsafe : Bool
List of all (including this one) declarations in the same mutual block. See comment at
DefinitionVal.all
.
Instances For
Equations
- Lean.instBEqOpaqueVal = { beq := Lean.beqOpaqueVal✝ }
Equations
- Lean.mkOpaqueValEx name levelParams type value isUnsafe all = { name := name, levelParams := levelParams, type := type, value := value, isUnsafe := isUnsafe, all := all }
Equations
- v.isUnsafeEx = v.isUnsafe
Instances For
Equations
- Lean.instInhabitedConstructor = { default := { name := default, type := default } }
Equations
- Lean.instBEqConstructor = { beq := Lean.beqConstructor✝ }
- name : Name
- type : Expr
- ctors : List Constructor
Equations
- Lean.instInhabitedInductiveType = { default := { name := default, type := default, ctors := default } }
Equations
- Lean.instBEqInductiveType = { beq := Lean.beqInductiveType✝ }
Declaration object that can be sent to the kernel.
- axiomDecl (val : AxiomVal) : Declaration
- defnDecl (val : DefinitionVal) : Declaration
- thmDecl (val : TheoremVal) : Declaration
- opaqueDecl (val : OpaqueVal) : Declaration
- quotDecl : Declaration
- mutualDefnDecl (defns : List DefinitionVal) : Declaration
- inductDecl (lparams : List Name) (nparams : Nat) (types : List InductiveType) (isUnsafe : Bool) : Declaration
Instances For
Equations
- Lean.instInhabitedDeclaration = { default := Lean.Declaration.axiomDecl default }
Equations
- Lean.instBEqDeclaration = { beq := Lean.beqDeclaration✝ }
Equations
- Lean.mkInductiveDeclEs lparams nparams types isUnsafe = Lean.Declaration.inductDecl lparams nparams types isUnsafe
Equations
- (Lean.Declaration.inductDecl lparams nparams types isUnsafe).isUnsafeInductiveDeclEx = isUnsafe
- x✝.isUnsafeInductiveDeclEx = false
Equations
- (Lean.Declaration.defnDecl val).definitionVal! = val
- x✝.definitionVal! = panicWithPosWithDecl "Lean.Declaration" "Lean.Declaration.definitionVal!" 194 9 "Expected a `Declaration.defnDecl`."
Equations
- One or more equations did not get rendered due to their size.
- Lean.Declaration.quotDecl.foldExprM f a = pure a
- (Lean.Declaration.axiomDecl { name := name, levelParams := levelParams, type := type, isUnsafe := isUnsafe }).foldExprM f a = f a type
- (Lean.Declaration.thmDecl { name := name, levelParams := levelParams, type := type, value := value, all := all }).foldExprM f a = do let a ← f a type f a value
- (Lean.Declaration.mutualDefnDecl vals).foldExprM f a = List.foldlM (fun (a : α) (v : Lean.DefinitionVal) => do let a ← f a v.type f a v.value) a vals
The kernel compiles (mutual) inductive declarations (see inductiveDecls
) into a set of
Declaration.inductDecl
(for each inductive datatype in the mutual Declaration),Declaration.ctorDecl
(for each Constructor in the mutual Declaration),Declaration.recDecl
(automatically generated recursors).
This data is used to implement iota-reduction efficiently and compile nested inductive declarations.
A series of checks are performed by the kernel to check whether a inductiveDecls
is valid or not.
- numParams : Nat
Number of parameters. A parameter is an argument to the defined type that is fixed over constructors. An example of this is the
α : Type
argument in the vector constructorsnil : Vector α 0
andcons : α → Vector α n → Vector α (n+1)
.The intuition is that the inductive type must exhibit parametric polymorphism over the inductive parameter, as opposed to ad-hoc polymorphism.
- numIndices : Nat
List of all (including this one) inductive datatypes in the mutual declaration containing this one
List of the names of the constructors for this inductive datatype.
- numNested : Nat
- isRec : Bool
true
when recursive (that is, the inductive type appears as an argument in a constructor). - isUnsafe : Bool
Whether the definition is flagged as unsafe.
- isReflexive : Bool
An inductive type is called reflexive if it has at least one constructor that takes as an argument a function returning the same type we are defining. Consider the type:
inductive WideTree where | branch: (Nat -> WideTree) -> WideTree | leaf: WideTree
this is reflexive due to the presence of the
branch : (Nat -> WideTree) -> WideTree
constructor.See also: 'Inductive Definitions in the system Coq Rules and Properties' by Christine Paulin-Mohring Section 2.2, Definition 3
Instances For
Equations
- One or more equations did not get rendered due to their size.
Equations
- v.isRecEx = v.isRec
Equations
- v.isUnsafeEx = v.isUnsafe
Equations
- v.isReflexiveEx = v.isReflexive
Equations
- Lean.instBEqConstructorVal = { beq := Lean.beqConstructorVal✝ }
Equations
- v.isUnsafeEx = v.isUnsafe
Information for reducing a recursor
Equations
- Lean.instInhabitedRecursorRule = { default := { ctor := default, nfields := default, rhs := default } }
Equations
- Lean.instBEqRecursorRule = { beq := Lean.beqRecursorRule✝ }
List of all inductive datatypes in the mutual declaration that generated this recursor
- numParams : Nat
Number of parameters
- numIndices : Nat
Number of indices
- numMotives : Nat
Number of motives
- numMinors : Nat
Number of minor premises
- rules : List RecursorRule
A reduction for each Constructor
- k : Bool
It supports K-like reduction. A recursor is said to support K-like reduction if one can assume it behaves like
Eq
under axiomK
--- that is, it has one constructor, the constructor has 0 arguments, and it is an inductive predicate (ie, it lives in Prop).Examples of inductives with K-like reduction is
Eq
,Acc
, andAnd.intro
. Non-examples areexists
(where the constructor has arguments) andOr.intro
(which has multiple constructors). - isUnsafe : Bool
Instances For
Equations
- One or more equations did not get rendered due to their size.
Equations
- Lean.instBEqRecursorVal = { beq := Lean.beqRecursorVal✝ }
Equations
- v.kEx = v.k
Equations
- v.isUnsafeEx = v.isUnsafe
The inductive type of the major argument of the recursor.
Equations
- v.getMajorInduct = Lean.RecursorVal.getMajorInduct.go v.getMajorIdx v.type
Equations
- Lean.RecursorVal.getMajorInduct.go 0 x✝ = x✝.bindingDomain!.getAppFn.constName!
- Lean.RecursorVal.getMajorInduct.go n.succ x✝ = Lean.RecursorVal.getMajorInduct.go n x✝.bindingBody!
Instances For
Equations
- Lean.instInhabitedQuotKind = { default := Lean.QuotKind.type }
- kind : QuotKind
Instances For
Equations
- Lean.instInhabitedQuotVal = { default := { toConstantVal := default, kind := default } }
Equations
- Lean.mkQuotValEx name levelParams type kind = { name := name, levelParams := levelParams, type := type, kind := kind }
Equations
- v.kindEx = v.kind
Information associated with constant declarations.
- axiomInfo (val : AxiomVal) : ConstantInfo
- defnInfo (val : DefinitionVal) : ConstantInfo
- thmInfo (val : TheoremVal) : ConstantInfo
- opaqueInfo (val : OpaqueVal) : ConstantInfo
- quotInfo (val : QuotVal) : ConstantInfo
- inductInfo (val : InductiveVal) : ConstantInfo
- ctorInfo (val : ConstructorVal) : ConstantInfo
- recInfo (val : RecursorVal) : ConstantInfo
Instances For
Equations
- Lean.instInhabitedConstantInfo = { default := Lean.ConstantInfo.axiomInfo default }
Equations
- One or more equations did not get rendered due to their size.
- (Lean.ConstantInfo.defnInfo { toConstantVal := d, value := value, hints := hints, safety := safety, all := all }).toConstantVal = d
- (Lean.ConstantInfo.axiomInfo { toConstantVal := d, isUnsafe := isUnsafe }).toConstantVal = d
- (Lean.ConstantInfo.thmInfo { toConstantVal := d, value := value, all := all }).toConstantVal = d
- (Lean.ConstantInfo.opaqueInfo { toConstantVal := d, value := value, isUnsafe := isUnsafe, all := all }).toConstantVal = d
- (Lean.ConstantInfo.quotInfo { toConstantVal := d, kind := kind }).toConstantVal = d
- (Lean.ConstantInfo.ctorInfo { toConstantVal := d, induct := induct, cidx := cidx, numParams := numParams, numFields := numFields, isUnsafe := isUnsafe }).toConstantVal = d
Equations
- (Lean.ConstantInfo.defnInfo v).isUnsafe = (v.safety == Lean.DefinitionSafety.unsafe)
- (Lean.ConstantInfo.axiomInfo v).isUnsafe = v.isUnsafe
- (Lean.ConstantInfo.thmInfo val).isUnsafe = false
- (Lean.ConstantInfo.opaqueInfo v).isUnsafe = v.isUnsafe
- (Lean.ConstantInfo.quotInfo val).isUnsafe = false
- (Lean.ConstantInfo.inductInfo v).isUnsafe = v.isUnsafe
- (Lean.ConstantInfo.ctorInfo v).isUnsafe = v.isUnsafe
- (Lean.ConstantInfo.recInfo v).isUnsafe = v.isUnsafe
Equations
- (Lean.ConstantInfo.defnInfo v).isPartial = (v.safety == Lean.DefinitionSafety.partial)
- x✝.isPartial = false
Equations
- d.levelParams = d.toConstantVal.levelParams
Equations
- d.numLevelParams = d.levelParams.length
Equations
- One or more equations did not get rendered due to their size.
- (Lean.ConstantInfo.thmInfo { name := name, levelParams := levelParams, type := type, value := value, all := all }).value? allowOpaque = some value
- info.value? allowOpaque = none
Equations
- (Lean.ConstantInfo.defnInfo val).hasValue allowOpaque = true
- (Lean.ConstantInfo.thmInfo val).hasValue allowOpaque = true
- (Lean.ConstantInfo.opaqueInfo val).hasValue allowOpaque = allowOpaque
- info.hasValue allowOpaque = false
Equations
- One or more equations did not get rendered due to their size.
- (Lean.ConstantInfo.thmInfo { name := name, levelParams := levelParams, type := type, value := value, all := all }).value! allowOpaque = value
- info.value! allowOpaque = panicWithPosWithDecl "Lean.Declaration" "Lean.ConstantInfo.value!" 458 31 "declaration with value expected"
Equations
- (Lean.ConstantInfo.defnInfo { name := name, levelParams := levelParams, type := type, value := value, hints := hints, safety := safety, all := all }).hints = hints
- x✝.hints = Lean.ReducibilityHints.opaque
Equations
- (Lean.ConstantInfo.ctorInfo val).isCtor = true
- x✝.isCtor = false
Equations
- (Lean.ConstantInfo.inductInfo val).isInductive = true
- x✝.isInductive = false
Equations
- (Lean.ConstantInfo.thmInfo val).isTheorem = true
- x✝.isTheorem = false
Equations
- (Lean.ConstantInfo.inductInfo val).inductiveVal! = val
- x✝.inductiveVal! = panicWithPosWithDecl "Lean.Declaration" "Lean.ConstantInfo.inductiveVal!" 478 9 "Expected a `ConstantInfo.inductInfo`."
List of all (including this one) declarations in the same mutual block.
Equations
- (Lean.ConstantInfo.inductInfo val).all = val.all
- (Lean.ConstantInfo.defnInfo val).all = val.all
- (Lean.ConstantInfo.thmInfo val).all = val.all
- (Lean.ConstantInfo.opaqueInfo val).all = val.all
- x✝.all = [x✝.name]
Equations
- Lean.mkRecName declName = declName.mkStr "rec"