mathlib documentation

tactic.linarith.parsing

Parsing input expressions into linear form #

linarith computes the linear form of its input expressions, assuming (without justification) that the type of these expressions is a commutative semiring. It identifies atoms up to ring-equivalence: that is, (y*3)*x will be identified 3*(x*y), where the monomial x*y is the linear atom.

Variables are represented by natural numbers.
Monomials are represented by monom := rb_map ℕ ℕ. The monomial 1 is represented by the empty map.
Linear combinations of monomials are represented by sum := rb_map monom ℤ.

All input expressions are converted to sums, preserving the map from expressions to variables. We then discard the monomial information, mapping each distinct monomial to a natural number. The resulting rb_map ℕ ℤ represents the ring-normalized linear form of the expression. This is ultimately converted into a linexp in the obvious way.

linear_forms_and_vars is the main entry point into this file. Everything else is contained.

Parsing datatypes #

meta def linarith.monom :

Type

Variables (represented by natural numbers) map to their power.

meta def linarith.monom.one :

1 is represented by the empty monomial, the product of no variables.

meta def linarith.monom.lt :

linarith.monom → linarith.monom → Prop

Compare monomials by first comparing their keys and then their powers.

@[protected, instance]

meta def linarith.monom.has_lt :

has_lt linarith.monom

meta def linarith.sum :

Type

Linear combinations of monomials are represented by mapping monomials to coefficients.

meta def linarith.sum.one :

1 is represented as the singleton sum of the monomial monom.one with coefficient 1.

meta def linarith.sum.scale_by_monom (s : linarith.sum) (m : linarith.monom) :

sum.scale_by_monom s m multiplies every monomial in s by m.

meta def linarith.sum.mul (s1 s2 : linarith.sum) :

sum.mul s1 s2 distributes the multiplication of two sums.`

meta def linarith.sum.pow (s : linarith.sum) :

ℕ → linarith.sum

The nth power of s : sum is the n-fold product of s, with s.pow 0 = sum.one.

meta def linarith.sum_of_monom (m : linarith.monom) :

sum_of_monom m lifts m to a sum with coefficient 1.

meta def linarith.one :

The unit monomial one is represented by the empty rb map.

meta def linarith.scalar (z : ℤ) :

A scalar z is represented by a sum with coefficient z and monomial one

meta def linarith.var (n : ℕ) :

A single variable n is represented by a sum with coefficient 1 and monomial n.

Parsing algorithms #

meta def linarith.linear_form_of_atom (red : tactic.transparency) (m : list (expr × ℕ)) (e : expr) :

tactic (list (expr × ℕ) × linarith.sum)

linear_form_of_atom red map e is the atomic case for linear_form_of_expr. If e appears with index k in map, it returns the singleton sum var k. Otherwise it updates map, adding e with index n, and returns the singleton sum var n.

meta def linarith.linear_form_of_expr (red : tactic.transparency) :

list (expr × ℕ) → expr → tactic (list (expr × ℕ) × linarith.sum)

linear_form_of_expr red map e computes the linear form of e.

map is a lookup map from atomic expressions to variable numbers. If a new atomic expression is encountered, it is added to the map with a new number. It matches atomic expressions up to reducibility given by red.

Because it matches up to definitional equality, this function must be in the tactic monad, and forces some functions that call it into tactic as well.

meta def linarith.sum_to_lf (s : linarith.sum) (m : native.rb_map linarith.monom ℕ) :

native.rb_map linarith.monom ℕ × native.rb_map ℕ ℤ

sum_to_lf s map eliminates the monomial level of the sum s.

map is a lookup map from monomials to variable numbers. The output rb_map ℕ ℤ has the same structure as sum, but each monomial key is replaced with its index according to map. If any new monomials are encountered, they are assigned variable numbers and map is updated.

meta def linarith.to_comp (red : tactic.transparency) (e : expr) (e_map : list (expr × ℕ)) (monom_map : native.rb_map linarith.monom ℕ) :

tactic (linarith.comp × list (expr × ℕ) × native.rb_map linarith.monom ℕ)

to_comp red e e_map monom_map converts an expression of the form t < 0, t ≤ 0, or t = 0 into a comp object.

e_map maps atomic expressions to indices; monom_map maps monomials to indices. Both of these are updated during processing and returned.

meta def linarith.to_comp_fold (red : tactic.transparency) :

list (expr × ℕ) → list expr → native.rb_map linarith.monom ℕ → tactic (list linarith.comp × list (expr × ℕ) × native.rb_map linarith.monom ℕ)

to_comp_fold red e_map exprs monom_map folds to_comp over exprs, updating e_map and monom_map as it goes.

meta def linarith.linear_forms_and_max_var (red : tactic.transparency) (pfs : list expr) :

tactic (list linarith.comp × ℕ)

linear_forms_and_vars red pfs is the main interface for computing the linear forms of a list of expressions. Given a list pfs of proofs of comparisons, it produces a list c of comps of the same length, such that c[i] represents the linear form of the type of pfs[i].

It also returns the largest variable index that appears in comparisons in c.