def Lean.Expr.toCtorIfLit : Expr → MetaM Expr

Smart unfolding support

@[extern lean_get_structural_rec_arg_pos]

opaque Lean.Meta.getStructuralRecArgPos? (declName : Name) : CoreM (Option Nat)

Forward declaration. It is defined in the module src/Lean/Elab/PreDefinition/Structural/Eqns.lean. It is possible to avoid this hack if we move Structural.EqnInfo and Structural.eqnInfoExt to this module.

def Lean.Meta.smartUnfoldingSuffix : String

@[inline]

def Lean.Meta.mkSmartUnfoldingNameFor (declName : Name) : Name

def Lean.Meta.hasSmartUnfoldingDecl (env : Environment) (declName : Name) : Bool

opaque Lean.Meta.smartUnfolding : Lean.Option Bool

def Lean.Meta.markSmartUnfoldingMatch (e : Expr) : Expr

Add auxiliary annotation to indicate the match-expression e must be reduced when performing smart unfolding.

def Lean.Meta.smartUnfoldingMatch? (e : Expr) : Option Expr

def Lean.Meta.markSmartUnfoldingMatchAlt (e : Expr) : Expr

Add auxiliary annotation to indicate expression e (a match alternative rhs) was successfully reduced by smart unfolding.

def Lean.Meta.smartUnfoldingMatchAlt? (e : Expr) : Option Expr

Helper methods

def Lean.Meta.isAuxDef (constName : Name) : MetaM Bool

Helper functions for reducing recursors

def Lean.Meta.mkProjFn (ctorVal : ConstructorVal) (us : List Level) (params : Array Expr) (i : Nat) (major : Expr) : CoreM Expr

Create the ith projection major. It tries to use the auto-generated projection functions if available. Otherwise falls back to Expr.proj.

Helper functions for reducing Quot.lift and Quot.ind

Helper function for extracting "stuck term"

partial def Lean.Meta.getStuckMVar? (e : Expr) : MetaM (Option MVarId)

Return some (Expr.mvar mvarId) if metavariable mvarId is blocking reduction.

Weak Head Normal Form auxiliary combinators

@[specialize #[]]

partial def Lean.Meta.whnfEasyCases (e : Expr) (k : Expr → MetaM Expr) : MetaM Expr

Auxiliary combinator for handling easy WHNF cases. It takes a function for handling the "hard" cases as an argument

inductive Lean.Meta.ReduceMatcherResult : Type

• reduced (val : Expr) : ReduceMatcherResult
• stuck (val : Expr) : ReduceMatcherResult
• notMatcher : ReduceMatcherResult
• partialApp : ReduceMatcherResult

The "match" compiler uses dependent if-then-else dite and other auxiliary declarations to compile match-expressions such as

match v with
| 'a' => 1
| 'b' => 2
| _   => 3

because it is more efficient than using casesOn recursors. The method reduceMatcher? fails if these auxiliary definitions cannot be unfolded in the current transparency setting. This is problematic because tactics such as simp use TransparencyMode.reducible, and most users assume that expressions such as

match 0 with
| 0 => 1
| 100 => 2
| _ => 3

should reduce in any transparency mode.

Thus, if the transparency mode is .reducible or .instances, we first eagerly unfold dite constants used in the auxiliary match-declaration, and then use a custom canUnfoldAtMatcher predicate for whnfMatcher.

Remark: we used to include dite (and ite) as auxiliary declarations to unfold at canUnfoldAtMatcher, but this is problematic because the dite/ite may occur in the discriminant. See issue #5388.

This solution is not very modular because modifications at the match compiler require changes here. We claim this is defensible because it is reducing the auxiliary declaration defined by the match compiler.

Remark: if the eager unfolding is problematic, we may cache the result. We may also consider not using dite in the match-compiler and use Decidable.casesOn, but it will require changes in how we generate equation lemmas.

Alternative solution: tactics that use TransparencyMode.reducible should rely on the equations we generated for match-expressions. This solution is also not perfect because the match-expression above will not reduce during type checking when we are not using TransparencyMode.default or TransparencyMode.all.

def Lean.Meta.canUnfoldAtMatcher (cfg : Config) (info : ConstantInfo) : CoreM Bool

Auxiliary predicate for whnfMatcher. See comment above.

def Lean.Meta.reduceMatcher? (e : Expr) : MetaM ReduceMatcherResult

def Lean.Meta.projectCore? (e : Expr) (i : Nat) : MetaM (Option Expr)

def Lean.Meta.project? (e : Expr) (i : Nat) : MetaM (Option Expr)

def Lean.Meta.reduceProj? (e : Expr) : MetaM (Option Expr)

Reduce kernel projection Expr.proj .. expression.

partial def Lean.Meta.expandLet (e : Expr) (vs : Array Expr) (zetaHave : Bool := true) : Expr

Zeta reduces lets/haves. If zetaHave is false, then haves are not zeta reduced.

Auxiliary function for whnfCore and Simp.reduceStep, to implement the zeta option. This function does not implement zetaUnused logic, which is instead the responsibility of consumeUnusedLet. The expandLet function works with expressions with loose bound variables, and thus determining whether a let variable is used isn't an O(1) operation.

Note: since expandLet and consumeUnusedLet are separated like this, a consequence is that in the +zeta -zetaHave +zetaUnused configuration, then whnfCore has quadratic complexity when reducing a sequence of alternating lets and haves where the lets are used but the haves are unused.

partial def Lean.Meta.consumeUnusedLet (e : Expr) (consumeNondep : Bool := false) : Expr

Consumes unused lets/haves. If consumeNondep is false, then haves are not consumed.

Auxiliary function for whnfCore, isDefEqQuick, and Simp.reduceStep, to implement the zetaUnused option. In the case of isDefEqQuick, it is also used when zeta is set.

def Lean.Meta.whnfCore (e : Expr) : MetaM Expr

Apply beta-reduction, zeta-reduction (i.e., unfold let local-decls), iota-reduction, expand let-expressions, expand assigned meta-variables, unfold aux declarations.

def Lean.Meta.smartUnfoldingReduce? (e : Expr) : MetaM (Option Expr)

Recall that _sunfold auxiliary definitions contains the markers: markSmartUnfoldingMatch (*) and markSmartUnfoldingMatchAlt (**). For example, consider the following definition

def r (i j : Nat) : Nat :=
  i +
    match j with
    | Nat.zero => 1
    | Nat.succ j =>
      i + match j with
          | Nat.zero => 2
          | Nat.succ j => r i j

produces the following _sunfold auxiliary definition with the markers

def r._sunfold (i j : Nat) : Nat :=
  i +
    (*) match j with
    | Nat.zero => (**) 1
    | Nat.succ j =>
      i + (*) match j with
          | Nat.zero => (**) 2
          | Nat.succ j => (**) r i j

match expressions marked with markSmartUnfoldingMatch (*) must be reduced, otherwise the resulting term is not definitionally equal to the given expression. The recursion may be interrupted as soon as the annotation markSmartUnfoldingAlt (**) is reached.

For example, the term r i j.succ.succ reduces to the definitionally equal term i + i * r i j

def Lean.Meta.unfoldProjInst? (e : Expr) : MetaM (Option Expr)

Auxiliary method for unfolding a class projection. Recall that class fields are not marked with [reducible], but we want to reduce them when the transparency setting is .instances. For example, given a b : Nat, the term a ≤ b is LE.le Nat instLENat a b. Unfolding the class field LE.le gives instLENat.1 a b. This method goes further and reduces the instance projection to return Nat.le a b.

def Lean.Meta.unfoldProjInstWhenInstances? (e : Expr) : MetaM (Option Expr)

Auxiliary method for unfolding a class projection when transparency is set to TransparencyMode.instances. Recall that class instance projections are not marked with [reducible] because we want them to be in "reducible canonical form". See unfoldProjInst?

opaque Lean.Meta.backward.whnf.reducibleClassField : Lean.Option Bool

When true, unfolding a [reducible] class field at TransparencyMode.reducible also unfolds the associated instance projection at TransparencyMode.instances.

Motivation: Consider a ≤ b where a b : Nat and LE.le is [reducible]. Unfolding LE.le gives instLENat.1 a b, which is stuck because instLENat is [implicit_reducible] (not [reducible]). Similarly, stM m (ExceptT ε m) α unfolds to an instance projection that is stuck at .reducible. Without this option, marking a class field as [reducible] is pointless when the instance providing it is only [implicit_reducible]. This option makes the [reducible] annotation on class fields work as the user expects by temporarily bumping to .instances for the projection.

See unfoldDefault for the implementation.

def Lean.Meta.unfoldDefinition? (e : Expr) (ignoreTransparency : Bool := false) : MetaM (Option Expr)

Unfold definition using "smart unfolding" if possible. If ignoreTransparency = true, then the definition is unfolded even if the transparency setting does not allow it.

def Lean.Meta.unfoldDefinition (e : Expr) : MetaM Expr

@[specialize #[]]

partial def Lean.Meta.whnfHeadPred (e : Expr) (pred : Expr → MetaM Bool) : MetaM Expr

def Lean.Meta.whnfUntil (e : Expr) (declName : Name) : MetaM (Option Expr)

def Lean.Meta.whnfCoreUnfoldingAnnotations (e : Expr) : MetaM Expr

Applies whnfCore while unfolding type annotations (outParam/optParam/etc.).

def Lean.Meta.reduceRecMatcher? (e : Expr) : MetaM (Option Expr)

Try to reduce matcher/recursor/quot applications. We say they are all "morally" recursor applications.

unsafe def Lean.Meta.reduceBoolNativeUnsafe (constName : Name) : MetaM Bool

unsafe def Lean.Meta.reduceNatNativeUnsafe (constName : Name) : MetaM Nat

@[implemented_by Lean.Meta.reduceBoolNativeUnsafe]

opaque Lean.Meta.reduceBoolNative (constName : Name) : MetaM Bool

@[implemented_by Lean.Meta.reduceNatNativeUnsafe]

opaque Lean.Meta.reduceNatNative (constName : Name) : MetaM Nat

def Lean.Meta.reduceNative? (e : Expr) : MetaM (Option Expr)

@[inline]

def Lean.Meta.withNatValue {α : Type} (a : Expr) (k : Nat → MetaM (Option α)) : MetaM (Option α)

def Lean.Meta.reduceUnaryNatOp (f : Nat → Nat) (a : Expr) : MetaM (Option Expr)

def Lean.Meta.reduceBinNatOp (f : Nat → Nat → Nat) (a b : Expr) : MetaM (Option Expr)

def Lean.Meta.reducePow (a b : Expr) : MetaM (Option Expr)

def Lean.Meta.reduceBinNatPred (f : Nat → Nat → Bool) (a b : Expr) : MetaM (Option Expr)

def Lean.Meta.reduceNat? (e : Expr) : MetaM (Option Expr)

@[export lean_whnf]

partial def Lean.Meta.whnfImp (e : Expr) : MetaM Expr

def Lean.Meta.reduceProjOf? (e : Expr) (p : Name → Bool) : MetaM (Option Expr)

If e is a projection function that satisfies p, then reduce it