The OmegaM state monad.

We keep track of the linear atoms (up to defeq) that have been encountered so far, and also generate new facts as new atoms are recorded.

The main functions are:

• atoms : OmegaM (List Expr) which returns the atoms recorded so far
• lookup (e : Expr) : OmegaM (Nat × Option (HashSet Expr)) which checks if an Expr has already been recorded as an atom, and records it. lookup return the index in atoms for this Expr. The Option (HashSet Expr) return value is none is the expression has been previously recorded, and otherwise contains new facts that should be added to the omega problem.
  • for each new atom a of the form ((x : Nat) : Int), the fact that 0 ≤ a
  • for each new atom a of the form x / k, for k a positive numeral, the facts that k * a ≤ x < k * a + k
  • for each new atom of the form ((a - b : Nat) : Int), the fact: b ≤ a ∧ ((a - b : Nat) : Int) = a - b ∨ a < b ∧ ((a - b : Nat) : Int) = 0
  • for each new atom of the form min a b, the facts min a b ≤ a and min a b ≤ b (and similarly for max)
  • for each new atom of the form if P then a else b, the disjunction: (P ∧ (if P then a else b) = a) ∨ (¬ P ∧ (if P then a else b) = b) The OmegaM monad also keeps an internal cache of visited expressions (not necessarily atoms, but arbitrary subexpressions of one side of a linear relation) to reduce duplication. The cache maps Exprs to pairs consisting of a LinearCombo, and proof that the expression is equal to the evaluation of the LinearCombo at the atoms.

structure Lean.Elab.Tactic.Omega.Context : Type

Context for the OmegaM monad, containing the user configurable options.

• cfg : Meta.Omega.OmegaConfig

  User configurable options for omega.

structure Lean.Elab.Tactic.Omega.State : Type

The internal state for the OmegaM monad, recording previously encountered atoms.

• atoms : Std.HashMap Expr Nat

  The atoms up-to-defeq encountered so far.

@[reducible, inline]

abbrev Lean.Elab.Tactic.Omega.OmegaM' (α : Type) : Type

An intermediate layer in the OmegaM monad.

def Lean.Elab.Tactic.Omega.Cache : Type

Cache of expressions that have been visited, and their reflection as a linear combination.

@[reducible, inline]

abbrev Lean.Elab.Tactic.Omega.OmegaM (α : Type) : Type

The OmegaM monad maintains two pieces of state:

• the linear atoms discovered while processing hypotheses
• a cache mapping subexpressions of one side of a linear inequality to LinearCombos (and a proof that the LinearCombo evaluates at the atoms to the original expression).

def Lean.Elab.Tactic.Omega.OmegaM.run {α : Type} (m : OmegaM α) (cfg : Meta.Omega.OmegaConfig) : MetaM α

Run a computation in the OmegaM monad, starting with no recorded atoms.

def Lean.Elab.Tactic.Omega.cfg : OmegaM Meta.Omega.OmegaConfig

Retrieve the user-specified configuration options.

def Lean.Elab.Tactic.Omega.atoms : OmegaM (Array Expr)

Retrieve the list of atoms.

def Lean.Elab.Tactic.Omega.atomsList : OmegaM Expr

Return the Expr representing the list of atoms.

def Lean.Elab.Tactic.Omega.atomsCoeffs : OmegaM Expr

Return the Expr representing the list of atoms as a Coeffs.

def Lean.Elab.Tactic.Omega.commitWhen {α : Type} (t : OmegaM (α × Bool)) : OmegaM α

Run an OmegaM computation, restoring the state afterwards depending on the result.

def Lean.Elab.Tactic.Omega.withoutModifyingState {α : Type} (t : OmegaM α) : OmegaM α

Run an OmegaM computation, restoring the state afterwards.

def Lean.Elab.Tactic.Omega.natCast? (n : Expr) : Option Nat

Wrapper around Expr.nat? that also allows Nat.cast.

def Lean.Elab.Tactic.Omega.intCast? (n : Expr) : Option Int

Wrapper around Expr.int? that also allows Nat.cast.

partial def Lean.Elab.Tactic.Omega.groundNat? (e : Expr) : Option Nat

If groundNat? e = some n, then e is definitionally equal to OfNat.ofNat n.

partial def Lean.Elab.Tactic.Omega.groundInt? (e : Expr) : Option Int

If groundInt? e = some i, then e is definitionally equal to the standard expression for i.

def Lean.Elab.Tactic.Omega.mkEqReflWithExpectedType (a b : Expr) : MetaM Expr

Construct the term with type hint (Eq.refl a : a = b)

def Lean.Elab.Tactic.Omega.analyzeAtom (e : Expr) : OmegaM (List Expr)

Analyzes a newly recorded atom, returning a collection of interesting facts about it that should be added to the context.

def Lean.Elab.Tactic.Omega.lookup (e : Expr) : OmegaM (Nat × Option (List Expr))

Look up an expression in the atoms, recording it if it has not previously appeared.

Return its index, and, if it is new, a collection of interesting facts about the atom.

• for each new atom a of the form ((x : Nat) : Int), the fact that 0 ≤ a
• for each new atom a of the form x / k, for k a positive numeral, the facts that k * a ≤ x < k * a + k
• for each new atom of the form ((a - b : Nat) : Int), the fact: b ≤ a ∧ ((a - b : Nat) : Int) = a - b ∨ a < b ∧ ((a - b : Nat) : Int) = 0