Zulip Chat Archive
Stream: lean4
Topic: Repackaging `Nat.add`
Siddhartha Gadgil (Mar 28 2022 at 15:10):
The documentation for DiscrTree
says "Moreover, it is the metaprogrammer's responsibility to re-pack applications such as
Nat.add a b
into Add.add Nat inst a b
".
Is there a convenient way to do this, or recognize this is needed? The function Nat.add
is defined earlier, and then an instance of Add.add
lets us repackage. So I am confused about what I should look for to know what the repackaged form is.
Thanks.
Leonardo de Moura (Mar 28 2022 at 16:19):
@Siddhartha Gadgil We can just replace the terms since Nat.add a b
is definitionally equal to a + b
.
Note that simp
does the repackaging for us because we have simp
theorems such as
@[simp] theorem add_eq : Nat.add x y = x + y := rfl
@[simp] theorem mul_eq : Nat.mul x y = x * y := rfl
@[simp] theorem sub_eq : Nat.sub x y = x - y := rfl
The uniform representation is important because of proof automation. To efficiently apply simp
and other forms of proof automation, we use a "term indexing" data structure. For simp
, we use a "discrimination tree", and it helps filter which simp
theorems can be applied to a subterm. It is not feasible to sequentially try all of them. Most arithmetic-related simp
theorems use x + y
(i.e., HAdd.hAdd ... x y
) to represent addition, and will only be tried in subterms of the same form.
Siddhartha Gadgil (Mar 28 2022 at 19:23):
Thanks. What I meant was in general how do we know what are all the valid replacements?
Last updated: Dec 20 2023 at 11:08 UTC