Skip to content
This repository was archived by the owner on Jul 24, 2024. It is now read-only.

[Merged by Bors] - refactor(*): kill nat multiplication diamonds#7084

Closed
sgouezel wants to merge 45 commits intomasterfrom
nsmul_data
Closed

[Merged by Bors] - refactor(*): kill nat multiplication diamonds#7084
sgouezel wants to merge 45 commits intomasterfrom
nsmul_data

Conversation

@sgouezel
Copy link
Copy Markdown
Collaborator

@sgouezel sgouezel commented Apr 7, 2021

An add_monoid has a natural -action, defined by n • a = a + ... + a, that we want to declare
as an instance as it makes it possible to use the language of linear algebra. However, there are
often other natural -actions. For instance, for any semiring R, the space of polynomials
polynomial R has a natural R-action defined by multiplication on the coefficients. This means
that polynomial ℕ has two natural -actions, which are equal but not defeq. The same
goes for linear maps, tensor products, and so on (and even for itself). This is the case on current
mathlib, with such non-defeq diamonds all over the place.

To solve this issue, we embed an -action in the definition of an add_monoid (which is by
default the naive action a + ... + a, but can be adjusted when needed -- it should always be equal
to this one, but not necessarily definitionally), and declare
a has_scalar ℕ α instance using this action. This is yet another example of the forgetful inheritance
pattern that we use in metric spaces, embedding a topology and a uniform structure in it (except that
here the functor from additive monoids to nat-modules is faithful instead of forgetful, but it doesn't
make a difference).

More precisely, we define

def nsmul_rec [has_add M] [has_zero M] : ℕ → M → M
| 0     a := 0
| (n+1) a := nsmul_rec n a + a

class add_monoid (M : Type u) extends add_semigroup M, add_zero_class M :=
(nsmul : ℕ → M → M := nsmul_rec)
(nsmul_zero' : ∀ x, nsmul 0 x = 0 . try_refl_tac)
(nsmul_succ' : ∀ (n : ℕ) x, nsmul n.succ x = nsmul n x + x . try_refl_tac)

For example, when we define polynomial R, then we declare the -action to be by multiplication
on each coefficient (using the -action on R that comes from the fact that R is
an add_monoid). In this way, the two natural has_scalar ℕ (polynomial ℕ) instances are defeq.

The tactic to_additive transfers definitions and results from multiplicative monoids to additive
monoids. To work, it has to map fields to fields. This means that we should also add corresponding
fields to the multiplicative structure monoid, which could solve defeq problems for powers if
needed. These problems do not come up in practice, so most of the time we will not need to adjust
the npow field when defining multiplicative objects.

With this refactor, all the diamonds are gone. Or rather, all the diamonds I noticed are gone, but if
there are still some diamonds then they can be fixed, contrary to before.

Also, the notation •ℕ is gone, just use .


TODO: do the same for . In another PR, let's keep this one reasonable.

The main pain points in the refactor are the following:

  • we have to adjust the definition of pow to make sure that to_additive works. In particular, a ^ 0 is not any more defeq to 1, and a^ (n+1) is not any more defeq to a * a ^ n. Many proofs were using this, so I had to add a lot of rw pow_zero and rw pow_succ. I don't think it's a problem: relying on anecdotal defeqs in proofs is just prone to breaking. To me, the only place where defeq really matters is where the user has no control on it, i.e., on typeclass diamonds.

  • to construct structures, refine and refine_struct are often perturbed by opt_params and auto_params that need a typeclass which is not already declared. Here, the autoparam field (nsmul : ℕ → M → M := nsmul_rec) requires typeclasses has_zero M and has_add M, that Lean core somehow provides when declaring the full structure, but when using refine or refine_struct this is not so clear, and there are issues with metavariables left. In some situations, it worked fine, and sometimes not. The most efficient way I found is to use refine_struct, and fill the nsmul field like

  nsmul := @nsmul_rec _ ⟨0⟩ ⟨(+)⟩,

replacing the autoparam by hand.

  • Since the structures become more complicated, proofs get slower. In particular, many proofs that were on the edge of timeout became too slow, and had to be fixed by avoiding heavy refls. This has been done in [Merged by Bors] - chore(*): speedup slow proofs #7148 (after which mathlib build time on CI dropped down by roughly 6 minutes).

@eric-wieser
Copy link
Copy Markdown
Member

I think the 20 or so function.injective.monoid-like definitions might need to take a new nsmul argument too, to avoid diamonds.

sgouezel and others added 2 commits April 7, 2021 17:06
Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@bryangingechen bryangingechen added the WIP Work in progress label Apr 7, 2021
@sgouezel
Copy link
Copy Markdown
Collaborator Author

sgouezel commented Apr 7, 2021

I think the 20 or so function.injective.monoid-like definitions might need to take a new nsmul argument too, to avoid diamonds.

We need only change them if it is important for defeqness issues in diamonds for the nat scalar multiplication. This means it is only relevant when one defines a new type which might also get a -action for different reasons (like polynomials, tensor products, and so on). Hopefully, this shouldn't be the case most of the time, so I'd rather say we should only fix it when needed.

@github-actions github-actions bot added the merge-conflict Please `git merge origin/master` then a bot will remove this label. label Apr 7, 2021
@sgouezel
Copy link
Copy Markdown
Collaborator Author

sgouezel commented Apr 8, 2021

No, as I said on Zulip coying just the data fields make things slower!!!

@github-actions github-actions bot added the merge-conflict Please `git merge origin/master` then a bot will remove this label. label Apr 11, 2021
@github-actions github-actions bot removed the merge-conflict Please `git merge origin/master` then a bot will remove this label. label Apr 12, 2021
@github-actions github-actions bot added the merge-conflict Please `git merge origin/master` then a bot will remove this label. label Apr 13, 2021
@github-actions github-actions bot removed the merge-conflict Please `git merge origin/master` then a bot will remove this label. label Apr 13, 2021
@sgouezel sgouezel added awaiting-review The author would like community review of the PR help-wanted The author needs attention to resolve issues and removed WIP Work in progress labels Apr 13, 2021
@sgouezel sgouezel removed the help-wanted The author needs attention to resolve issues label Apr 14, 2021
@jcommelin
Copy link
Copy Markdown
Member

Thanks 🎉

bors merge p=37

bors bot pushed a commit that referenced this pull request Apr 14, 2021
An `add_monoid` has a natural `ℕ`-action, defined by `n • a = a + ... + a`, that we want to declare
as an instance as it makes it possible to use the language of linear algebra. However, there are
often other natural `ℕ`-actions. For instance, for any semiring `R`, the space of polynomials
`polynomial R` has a natural `R`-action defined by multiplication on the coefficients. This means
that `polynomial ℕ` has two natural `ℕ`-actions, which are equal but not defeq. The same
goes for linear maps, tensor products, and so on (and even for `ℕ` itself). This is the case on current
mathlib, with such non-defeq diamonds all over the place.

To solve this issue, we embed an `ℕ`-action in the definition of an `add_monoid` (which is by
default the naive action `a + ... + a`, but can be adjusted when needed -- it should always be equal 
to this one, but not necessarily definitionally), and declare
a `has_scalar ℕ α` instance using this action. This is yet another example of the forgetful inheritance
pattern that we use in metric spaces, embedding a topology and a uniform structure in it (except that
here the functor from additive monoids to nat-modules is faithful instead of forgetful, but it doesn't 
make a difference).

More precisely, we define
```lean
def nsmul_rec [has_add M] [has_zero M] : ℕ → M → M
| 0     a := 0
| (n+1) a := nsmul_rec n a + a

class add_monoid (M : Type u) extends add_semigroup M, add_zero_class M :=
(nsmul : ℕ → M → M := nsmul_rec)
(nsmul_zero' : ∀ x, nsmul 0 x = 0 . try_refl_tac)
(nsmul_succ' : ∀ (n : ℕ) x, nsmul n.succ x = nsmul n x + x . try_refl_tac)
```

For example, when we define `polynomial R`, then we declare the `ℕ`-action to be by multiplication
on each coefficient (using the `ℕ`-action on `R` that comes from the fact that `R` is
an `add_monoid`). In this way, the two natural `has_scalar ℕ (polynomial ℕ)` instances are defeq.

The tactic `to_additive` transfers definitions and results from multiplicative monoids to additive
monoids. To work, it has to map fields to fields. This means that we should also add corresponding
fields to the multiplicative structure `monoid`, which could solve defeq problems for powers if
needed. These problems do not come up in practice, so most of the time we will not need to adjust
the `npow` field when defining multiplicative objects.

With this refactor, all the diamonds are gone. Or rather, all the diamonds I noticed are gone, but if
there are still some diamonds then they can be fixed, contrary to before.

Also, the notation `•ℕ` is gone, just use `•`.



Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@github-actions github-actions bot added ready-to-merge All that is left is for bors to build and merge this PR. (Remember you need to say `bors r+`.) and removed awaiting-review The author would like community review of the PR labels Apr 14, 2021
Comment on lines -310 to -314
/-- All `ℕ`-semimodule structures are equal. -/
instance add_comm_monoid.nat_semimodule.subsingleton : subsingleton (semimodule ℕ M) :=
⟨λ P Q, by {
ext n,
rw [←nsmul_eq_smul, ←nsmul_eq_smul], }⟩
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is there a reason for removing this? It seems like a nice statement to have to justify the design, even if it's not really needed any more.

(obviously let's not stop the build, but I think we should add this back)

@bors
Copy link
Copy Markdown

bors bot commented Apr 14, 2021

Pull request successfully merged into master.

Build succeeded:

@bors bors bot changed the title refactor(*): kill nat multiplication diamonds [Merged by Bors] - refactor(*): kill nat multiplication diamonds Apr 14, 2021
@bors bors bot closed this Apr 14, 2021
@bors bors bot deleted the nsmul_data branch April 14, 2021 12:52
bors bot pushed a commit that referenced this pull request Apr 20, 2021
…id.nat_semimodule.subsingleton (#7263)

As suggested in #7084 (comment).

Even if we now have a design solution that makes this unnecessary, it still feels like a result worth stating.
bors bot pushed a commit that referenced this pull request Apr 25, 2021
Insert a data field `gsmul` in `add_comm_group` containing a Z-action, and use it to make sure that all diamonds related to `Z` -actions disappear.

Followup to #7084



Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
Co-authored-by: Mario Carneiro <di.gama@gmail.com>
bors bot pushed a commit that referenced this pull request Feb 16, 2022
…2072)

`continuous_linear_map.continuous_nsmul` is nothing to do with `continuous_linear_map`s, and is the same as `continuous_nsmul`, but the latter doesn't require commutativity. There is no reason to keep the former.

This lemma was added in #7084, but probably got missed due to how large that PR had to be.

We can't remove `continuous_linear_map.continuous_zsmul` until #12055 is merged, as there is currently no `continuous_zsmul` in the root namespace.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

ready-to-merge All that is left is for bors to build and merge this PR. (Remember you need to say `bors r+`.)

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants