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: Lean.ReducibilityHints
- abbrev: Lean.ReducibilityHints
- regular: UInt32 → Lean.ReducibilityHints
Instances For
Equations
- Lean.instInhabitedReducibilityHints = { default := Lean.ReducibilityHints.opaque }
Equations
Instances For
Equations
- (Lean.ReducibilityHints.regular h_2).getHeightEx = h_2
- h.getHeightEx = 0
Instances For
Equations
Instances For
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
Instances For
Equations
- Lean.ReducibilityHints.instOrd = { compare := Lean.ReducibilityHints.compare }
Equations
- Lean.ReducibilityHints.abbrev.isAbbrev = true
- x.isAbbrev = false
Instances For
Equations
- (Lean.ReducibilityHints.regular h_1).isRegular = true
- x.isRegular = false
Instances For
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✝ }
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 }
Instances For
- unsafe: Lean.DefinitionSafety
- safe: Lean.DefinitionSafety
- partial: Lean.DefinitionSafety
Instances For
Equations
- Lean.instInhabitedDefinitionSafety = { default := Lean.DefinitionSafety.unsafe }
Equations
Equations
- Lean.instReprDefinitionSafety = { reprPrec := Lean.reprDefinitionSafety✝ }
- name : Lake.Name
- type : Lean.Expr
- value : Lean.Expr
- hints : Lean.ReducibilityHints
- safety : Lean.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
.
Instances For
Equations
- Lean.instInhabitedDefinitionVal = { default := { toConstantVal := default, value := default, hints := default, safety := default, all := default } }
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 }
Instances For
- name : Lake.Name
- type : Lean.Expr
- value : Lean.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 }
Instances For
Equations
- Lean.instInhabitedOpaqueVal = { default := { toConstantVal := default, value := default, isUnsafe := default, all := default } }
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 }
Instances For
Equations
- Lean.instInhabitedConstructor = { default := { name := default, type := default } }
Equations
- Lean.instBEqConstructor = { beq := Lean.beqConstructor✝ }
- name : Lake.Name
- type : Lean.Expr
- ctors : List Lean.Constructor
Instances For
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: Lean.AxiomVal → Lean.Declaration
- defnDecl: Lean.DefinitionVal → Lean.Declaration
- thmDecl: Lean.TheoremVal → Lean.Declaration
- opaqueDecl: Lean.OpaqueVal → Lean.Declaration
- quotDecl: Lean.Declaration
- mutualDefnDecl: List Lean.DefinitionVal → Lean.Declaration
- inductDecl: List Lake.Name → Nat → List Lean.InductiveType → Bool → Lean.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
Instances For
Equations
- (Lean.Declaration.inductDecl lparams nparams types isUnsafe).isUnsafeInductiveDeclEx = isUnsafe
- x.isUnsafeInductiveDeclEx = false
Instances For
Equations
- (Lean.Declaration.defnDecl val).definitionVal! = val
- x.definitionVal! = panicWithPosWithDecl "Lean.Declaration" "Lean.Declaration.definitionVal!" 194 9 "Expected a `Declaration.defnDecl`."
Instances For
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
Instances For
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.
- name : Lake.Name
- type : Lean.Expr
- 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
Number of indices. An index is an argument that varies over constructors.
An example of this is the
n : Nat
argument in the vector constructorcons : α → Vector α n → Vector α (n+1)
. 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
- One or more equations did not get rendered due to their size.
Instances For
Equations
- v.numCtors = v.ctors.length
Instances For
Instances For
Instances For
- name : Lake.Name
- type : Lean.Expr
- induct : Lake.Name
Inductive type this constructor is a member of
- cidx : Nat
Constructor index (i.e., Position in the inductive declaration)
- numParams : Nat
Number of parameters in inductive datatype.
- numFields : Nat
Number of fields (i.e., arity - nparams)
- isUnsafe : Bool
Instances For
Equations
- Lean.instInhabitedConstructorVal = { default := { toConstantVal := default, induct := default, cidx := default, numParams := default, numFields := default, isUnsafe := default } }
Equations
- Lean.instBEqConstructorVal = { beq := Lean.beqConstructorVal✝ }
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- Lean.instInhabitedRecursorRule = { default := { ctor := default, nfields := default, rhs := default } }
Equations
- Lean.instBEqRecursorRule = { beq := Lean.beqRecursorRule✝ }
- name : Lake.Name
- type : Lean.Expr
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 Lean.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
- One or more equations did not get rendered due to their size.
Instances For
Instances For
Instances For
Instances For
Equations
- v.getInduct = v.name.getPrefix
Instances For
- type: Lean.QuotKind
- ctor: Lean.QuotKind
- lift: Lean.QuotKind
- ind: Lean.QuotKind
Instances For
Equations
- Lean.instInhabitedQuotKind = { default := Lean.QuotKind.type }
- name : Lake.Name
- type : Lean.Expr
- kind : Lean.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 }
Instances For
Information associated with constant declarations.
- axiomInfo: Lean.AxiomVal → Lean.ConstantInfo
- defnInfo: Lean.DefinitionVal → Lean.ConstantInfo
- thmInfo: Lean.TheoremVal → Lean.ConstantInfo
- opaqueInfo: Lean.OpaqueVal → Lean.ConstantInfo
- quotInfo: Lean.QuotVal → Lean.ConstantInfo
- inductInfo: Lean.InductiveVal → Lean.ConstantInfo
- ctorInfo: Lean.ConstructorVal → Lean.ConstantInfo
- recInfo: Lean.RecursorVal → Lean.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
Instances For
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
Instances For
Equations
- (Lean.ConstantInfo.defnInfo v).isPartial = (v.safety == Lean.DefinitionSafety.partial)
- x.isPartial = false
Instances For
Equations
- d.name = d.toConstantVal.name
Instances For
Equations
- d.levelParams = d.toConstantVal.levelParams
Instances For
Equations
- d.numLevelParams = d.levelParams.length
Instances For
Equations
- d.type = d.toConstantVal.type
Instances For
Equations
- (Lean.ConstantInfo.defnInfo { name := name, levelParams := levelParams, type := type, value := r, hints := hints, safety := safety, all := all }).value? = some r
- (Lean.ConstantInfo.thmInfo { name := name, levelParams := levelParams, type := type, value := r, all := all }).value? = some r
- x.value? = none
Instances For
Equations
- (Lean.ConstantInfo.defnInfo val).hasValue = true
- (Lean.ConstantInfo.thmInfo val).hasValue = true
- x.hasValue = false
Instances For
Equations
- (Lean.ConstantInfo.defnInfo { name := name, levelParams := levelParams, type := type, value := r, hints := hints, safety := safety, all := all }).value! = r
- (Lean.ConstantInfo.thmInfo { name := name, levelParams := levelParams, type := type, value := r, all := all }).value! = r
- x.value! = panicWithPosWithDecl "Lean.Declaration" "Lean.ConstantInfo.value!" 456 33 "declaration with value expected"
Instances For
Equations
- (Lean.ConstantInfo.defnInfo { name := name, levelParams := levelParams, type := type, value := value, hints := r, safety := safety, all := all }).hints = r
- x.hints = Lean.ReducibilityHints.opaque
Instances For
Equations
- (Lean.ConstantInfo.ctorInfo val).isCtor = true
- x.isCtor = false
Instances For
Equations
- (Lean.ConstantInfo.inductInfo val).isInductive = true
- x.isInductive = false
Instances For
Equations
- (Lean.ConstantInfo.inductInfo val).inductiveVal! = val
- x.inductiveVal! = panicWithPosWithDecl "Lean.Declaration" "Lean.ConstantInfo.inductiveVal!" 472 9 "Expected a `ConstantInfo.inductInfo`."
Instances For
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]
Instances For
Equations
- Lean.mkRecName declName = declName.mkStr "rec"