Skip to content

[Merged by Bors] - fix: cc tactic can't unify def-eq instances in OfNat.ofNat#13403

Closed
Komyyy wants to merge 1 commit intomasterfrom
Komyyy/cc_OfNat
Closed

[Merged by Bors] - fix: cc tactic can't unify def-eq instances in OfNat.ofNat#13403
Komyyy wants to merge 1 commit intomasterfrom
Komyyy/cc_OfNat

Conversation

@Komyyy
Copy link
Copy Markdown
Contributor

@Komyyy Komyyy commented May 31, 2024

This issue is consisted of one problem and one bug.

Problem: cc treats an OfNat.ofNat term as an atomic value in the default config
In the default CCConfig, the values field is set to true so cc treats an OfNat.ofNat term as an atomic and it doesn't unify OfNat instances.
This problem can be solved simply by setting values := false by default.

Bug: cc tries to disprove @OfNat α (nat_lit n) i₁ ≠ @OfNat α (nat_lit n) i₂ where α is or and i₁ & i₂ is not alpha-equivalent but def_eq
cc tactic has a mechanism to disprove equality between two different values of , , Char & String, in the function propagateEqUp. This mechanism is trigered when the root representations of two values are not alpha-equivalent, so this example fails.

local instance instOfNatNat' (n : ℕ) : OfNat ℕ n where
  ofNat := n

example : @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat _) =
    @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat' _) := by
  cc
/-
application type mismatch
  (bne_iff_ne 0 0).1 (Eq.refl true)
argument has type
  true = true
but function has type
  (0 != 0) = true → 0 ≠ 0
-/

So we strengthen the condition in propagateEqUp. For the detail, refer to docs in this function.


Resolves #13362

Open in Gitpod

@Komyyy Komyyy added bug Something is not working awaiting-review t-meta Tactics, attributes or user commands labels May 31, 2024
@Komyyy Komyyy requested a review from Vierkantor May 31, 2024 04:30
Copy link
Copy Markdown
Contributor

@Vierkantor Vierkantor left a comment

Choose a reason for hiding this comment

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

Looks good to me, thanks for the detailed explanations!

bors r+

@ghost ghost added ready-to-merge This PR has been sent to bors. and removed awaiting-review labels Jun 14, 2024
mathlib-bors bot pushed a commit that referenced this pull request Jun 14, 2024
This issue is consisted of one problem and one bug.

**Problem: `cc` treats an `OfNat.ofNat` term as an atomic value in the default config**
In the default `CCConfig`, the `values` field is set to `true` so `cc` treats an `OfNat.ofNat` term as an atomic and it doesn't unify `OfNat` instances.
This problem can be solved simply by setting `values := false` by default.

**Bug: `cc` tries to disprove `@OfNat α (nat_lit n) i₁ ≠ @OfNat α (nat_lit n) i₂` where `α` is `ℕ` or `ℤ` and `i₁` & `i₂` is not alpha-equivalent but def_eq**
`cc` tactic has a mechanism to disprove equality between two different values of `ℕ`, `ℤ`, `Char` & `String`, in the function `propagateEqUp`. This mechanism is trigered when the root representations of two values are not alpha-equivalent, so this example fails.
```lean
local instance instOfNatNat' (n : ℕ) : OfNat ℕ n where
  ofNat := n

example : @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat _) =
    @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat' _) := by
  cc
/-
application type mismatch
  (bne_iff_ne 0 0).1 (Eq.refl true)
argument has type
  true = true
but function has type
  (0 != 0) = true → 0 ≠ 0
-/
```
So we strengthen the condition in `propagateEqUp`. For the detail, refer to docs in this function.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jun 14, 2024

Build failed (retrying...):

mathlib-bors bot pushed a commit that referenced this pull request Jun 14, 2024
This issue is consisted of one problem and one bug.

**Problem: `cc` treats an `OfNat.ofNat` term as an atomic value in the default config**
In the default `CCConfig`, the `values` field is set to `true` so `cc` treats an `OfNat.ofNat` term as an atomic and it doesn't unify `OfNat` instances.
This problem can be solved simply by setting `values := false` by default.

**Bug: `cc` tries to disprove `@OfNat α (nat_lit n) i₁ ≠ @OfNat α (nat_lit n) i₂` where `α` is `ℕ` or `ℤ` and `i₁` & `i₂` is not alpha-equivalent but def_eq**
`cc` tactic has a mechanism to disprove equality between two different values of `ℕ`, `ℤ`, `Char` & `String`, in the function `propagateEqUp`. This mechanism is trigered when the root representations of two values are not alpha-equivalent, so this example fails.
```lean
local instance instOfNatNat' (n : ℕ) : OfNat ℕ n where
  ofNat := n

example : @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat _) =
    @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat' _) := by
  cc
/-
application type mismatch
  (bne_iff_ne 0 0).1 (Eq.refl true)
argument has type
  true = true
but function has type
  (0 != 0) = true → 0 ≠ 0
-/
```
So we strengthen the condition in `propagateEqUp`. For the detail, refer to docs in this function.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jun 14, 2024

Pull request successfully merged into master.

Build succeeded:

@mathlib-bors mathlib-bors bot changed the title fix: cc tactic can't unify def-eq instances in OfNat.ofNat [Merged by Bors] - fix: cc tactic can't unify def-eq instances in OfNat.ofNat Jun 14, 2024
@mathlib-bors mathlib-bors bot closed this Jun 14, 2024
@mathlib-bors mathlib-bors bot deleted the Komyyy/cc_OfNat branch June 14, 2024 16:44
AntoineChambert-Loir pushed a commit that referenced this pull request Jun 20, 2024
This issue is consisted of one problem and one bug.

**Problem: `cc` treats an `OfNat.ofNat` term as an atomic value in the default config**
In the default `CCConfig`, the `values` field is set to `true` so `cc` treats an `OfNat.ofNat` term as an atomic and it doesn't unify `OfNat` instances.
This problem can be solved simply by setting `values := false` by default.

**Bug: `cc` tries to disprove `@OfNat α (nat_lit n) i₁ ≠ @OfNat α (nat_lit n) i₂` where `α` is `ℕ` or `ℤ` and `i₁` & `i₂` is not alpha-equivalent but def_eq**
`cc` tactic has a mechanism to disprove equality between two different values of `ℕ`, `ℤ`, `Char` & `String`, in the function `propagateEqUp`. This mechanism is trigered when the root representations of two values are not alpha-equivalent, so this example fails.
```lean
local instance instOfNatNat' (n : ℕ) : OfNat ℕ n where
  ofNat := n

example : @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat _) =
    @OfNat.ofNat ℕ (nat_lit 0) (instOfNatNat' _) := by
  cc
/-
application type mismatch
  (bne_iff_ne 0 0).1 (Eq.refl true)
argument has type
  true = true
but function has type
  (0 != 0) = true → 0 ≠ 0
-/
```
So we strengthen the condition in `propagateEqUp`. For the detail, refer to docs in this function.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

bug Something is not working ready-to-merge This PR has been sent to bors. t-meta Tactics, attributes or user commands

Projects

None yet

Development

Successfully merging this pull request may close these issues.

cc tactic can't unify def-eq instances in OfNat.ofNat

2 participants