Skip to content

feat: let dot notation see through CoeFun instances#5692

Merged
kmill merged 6 commits intoleanprover:masterfrom
kmill:fix_1910
Oct 14, 2024
Merged

feat: let dot notation see through CoeFun instances#5692
kmill merged 6 commits intoleanprover:masterfrom
kmill:fix_1910

Conversation

@kmill
Copy link
Copy Markdown
Collaborator

@kmill kmill commented Oct 13, 2024

Projects like mathlib like to define projection functions with extra structure, for example one could imagine defining Multiset.card : Multiset α →+ Nat, which bundles the fact that Multiset.card (m1 + m2) = Multiset.card m1 + Multiset.card m2 for all m1 m2 : Multiset α. A problem though is that so far this has prevented dot notation from working: you can't write (m1 + m2).card = m1.card + m2.card.

With this PR, now you can. The way it works is that "LValue resolution" will apply CoeFun instances when trying to resolve which argument should receive the object of dot notation.

A contrived-yet-representative example:

structure Equiv (α β : Sort _) where
  toFun : α → β
  invFun : β → α

infixl:25 "" => Equiv

instance: CoeFun (α ≃ β) fun _ => α → β where
  coe := Equiv.toFun

structure Foo where
  n : Nat

def Foo.n' : Foo ≃ Nat := ⟨Foo.n, Foo.mk⟩

variable (f : Foo)
#check f.n'
-- Foo.n'.toFun f : Nat

Design note 1: While LValue resolution attempts to make use of named arguments when positional arguments cannot be used, when we apply CoeFun instances we disallow making use of named arguments. The rationale is that argument names for CoeFun instances tend to be random, which could lead dot notation randomly succeeding or failing. It is better to be uniform, and so it uniformly fails in this case.

Design note 2: There is a limitation in that this will not make use of the values of any of the provided arguments when synthesizing the CoeFun instances (see the tests for an example), since argument elaboration takes place after LValue resolution. However, we make sure that synthesis will fail rather than choose the wrong CoeFun instance.

Performance note: Such instances will be synthesized twice, once during LValue resolution, and again when applying arguments.

This also adds in a small optimization to the parameter list computation in LValue resolution so that it lazily reduces when a relevant parameter hasn't been found yet, rather than using forallTelescopeReducing. It also switches to using forallMetaTelescope to make sure the CoeFun synthesis will fail if multiple instances could apply.

Getting this to pretty print will be deferred to future work.

Closes #1910

kmill added 2 commits October 13, 2024 12:18
Projects like mathlib use projection fields with extra structure, for example one could imagine defining `Multiset.card : Multiset α →+ Nat`, which bundles the fact that `Multiset.card (m1 + m2) = Multiset.card m1 + Multiset.card m2`. A problem though is that so far this has prevented dot notation from working: you can't write `(m1 + m2).card = m1.card + m2.card`.

With this PR, now we can. The way it works is that "LValue resolution" will apply CoeFun instances when trying to resolve which argument should receive the object of dot notation.

This also adds in a small optimization that the parameter list computation in LValue resolution uses `forallTelescope` instead of `forallTelescopeReducing`, lazily reducing when a relevant parameter hasn't been found yet.

Closes leanprover#1910
@github-actions github-actions bot added the toolchain-available A toolchain is available for this PR, at leanprover/lean4-pr-releases:pr-release-NNNN label Oct 13, 2024
ghost pushed a commit to leanprover-community/batteries that referenced this pull request Oct 13, 2024
ghost pushed a commit to leanprover-community/mathlib4 that referenced this pull request Oct 13, 2024
@ghost ghost added the builds-mathlib CI has verified that Mathlib builds against this PR label Oct 13, 2024
@ghost
Copy link
Copy Markdown

ghost commented Oct 13, 2024

Mathlib CI status (docs):

ghost pushed a commit to leanprover-community/batteries that referenced this pull request Oct 13, 2024
@kmill
Copy link
Copy Markdown
Collaborator Author

kmill commented Oct 13, 2024

!bench

ghost pushed a commit to leanprover-community/mathlib4 that referenced this pull request Oct 13, 2024
@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 56c5b87.
There were no significant changes against commit 1d8555f.

ghost pushed a commit to leanprover-community/batteries that referenced this pull request Oct 13, 2024
ghost pushed a commit to leanprover-community/mathlib4 that referenced this pull request Oct 13, 2024
@kmill kmill added this pull request to the merge queue Oct 14, 2024
Merged via the queue into leanprover:master with commit a026bc7 Oct 14, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

builds-mathlib CI has verified that Mathlib builds against this PR toolchain-available A toolchain is available for this PR, at leanprover/lean4-pr-releases:pr-release-NNNN

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Dot notation and CoeFun

2 participants