Skip to content

typeclass inference can go haywire #2055

@kbuzzard

Description

@kbuzzard

Prerequisites

  • Put an X between the brackets on this line if you have done all of the following:
    • Checked that your issue isn't already filed.
    • Reduced the issue to a self-contained, reproducible test case.

Description

Lean's type class inference system sometimes tries and fails to solve the same problem 384 or more times consecutively in the middle of a proof.

Steps to Reproduce

NOTE: Far simpler examples are further down the thread.

class Zero (α : Type u) where
  zero : α

instance Zero.toOfNat0 {α} [Zero α] : OfNat α (nat_lit 0) where
  ofNat := ‹Zero α›.1

instance Zero.ofOfNat0 {α} [OfNat α (nat_lit 0)] : Zero α where
  zero := 0

class One (α : Type u) where
  one : α

instance One.toOfNat1 {α} [One α] : OfNat α (nat_lit 1) where
  ofNat := ‹One α›.1

instance One.ofOfNat1 {α} [OfNat α (nat_lit 1)] : One α where
  one := 1

class MulZeroClass (M₀ : Type _) extends Mul M₀, Zero M₀ where
  zero_mul : ∀ a : M₀, 0 * a = 0
  mul_zero : ∀ a : M₀, a * 0 = 0

class AddSemigroup (G : Type u) extends Add G where
  add_assoc : ∀ a b c : G, a + b + c = a + (b + c)

class Semigroup (G : Type u) extends Mul G where
  mul_assoc : ∀ a b c : G, a * b * c = a * (b * c)

class CommSemigroup (G : Type u) extends Semigroup G where
  mul_comm : ∀ a b : G, a * b = b * a

class AddCommSemigroup (G : Type u) extends AddSemigroup G where
  add_comm : ∀ a b : G, a + b = b + a

class SemigroupWithZero (S₀ : Type _) extends Semigroup S₀, MulZeroClass S₀

class MulOneClass (M : Type u) extends One M, Mul M where
  one_mul : ∀ a : M, 1 * a = a
  mul_one : ∀ a : M, a * 1 = a

class AddZeroClass (M : Type u) extends Zero M, Add M where
  zero_add : ∀ a : M, 0 + a = a
  add_zero : ∀ a : M, a + 0 = a

class MulZeroOneClass (M₀ : Type u) extends MulOneClass M₀, MulZeroClass M₀

class AddMonoid (M : Type u) extends AddSemigroup M, AddZeroClass M where

class Monoid (M : Type u) extends Semigroup M, MulOneClass M where

structure Units (α : Type u) [Monoid α] where
  val : α
  inv : α
  val_inv : val * inv = 1
  inv_val : inv * val = 1

postfix:1024 "ˣ" => Units

class Inv (α : Type u) where
  inv : α → α

postfix:max "⁻¹" => Inv.inv

instance [Monoid α] : Inv αˣ :=
  ⟨fun u => ⟨u.2, u.1, u.4, u.3⟩⟩

instance [Monoid α] : CoeHead αˣ α :=
  ⟨Units.val⟩

def divp [Monoid α] (a : α) (u : Units α) : α :=
  a * (u⁻¹ : αˣ)

infixl:70 " /ₚ " => divp

class MonoidWithZero (M₀ : Type u) extends Monoid M₀, MulZeroOneClass M₀, SemigroupWithZero M₀

class LeftCancelSemigroup (G : Type u) extends Semigroup G where
  mul_left_cancel : ∀ a b c : G, a * b = a * c → b = c

class LeftCancelMonoid (M : Type u) extends LeftCancelSemigroup M, Monoid M

class RightCancelSemigroup (G : Type u) extends Semigroup G where
  mul_right_cancel : ∀ a b c : G, a * b = c * b → a = c

class RightCancelMonoid (M : Type u) extends RightCancelSemigroup M, Monoid M

class AddCommMonoid (M : Type u) extends AddMonoid M, AddCommSemigroup M

class SubNegMonoid (G : Type u) extends AddMonoid G, Neg G, Sub G where
  sub a b := a + -b
  sub_eq_add_neg : ∀ a b : G, a - b = a + -b := by intros; rfl

class AddGroup (A : Type u) extends SubNegMonoid A where
  add_left_neg : ∀ a : A, -a + a = 0

class AddMonoidWithOne (R : Type u) extends AddMonoid R, One R where

class CommMonoid (M : Type u) extends Monoid M, CommSemigroup M

class AddGroupWithOne (R : Type u) extends AddMonoidWithOne R, AddGroup R where

class AddCommGroup (G : Type u) extends AddGroup G, AddCommMonoid G

class Distrib (R : Type _) extends Mul R, Add R where
  protected left_distrib : ∀ a b c : R, a * (b + c) = a * b + a * c
  protected right_distrib : ∀ a b c : R, (a + b) * c = a * c + b * c

class NonUnitalNonAssocSemiring (α : Type u) extends AddCommMonoid α, Distrib α, MulZeroClass α

class AddCommMonoidWithOne (R : Type _) extends AddMonoidWithOne R, AddCommMonoid R

class NonAssocSemiring (α : Type u) extends NonUnitalNonAssocSemiring α, MulZeroOneClass α,
    AddCommMonoidWithOne α

class NonUnitalSemiring (α : Type u) extends NonUnitalNonAssocSemiring α, SemigroupWithZero α

class Semiring (α : Type u) extends NonUnitalSemiring α, NonAssocSemiring α, MonoidWithZero α

class Ring (R : Type u) extends Semiring R, AddCommGroup R, AddGroupWithOne R

class CommRing (α : Type u) extends Ring α, CommMonoid α

theorem divp_eq_iff_mul_eq [Monoid α] {x : α} {u : αˣ} {y : α} : x /ₚ u = y ↔ y * u = x := sorry

theorem divp_mul_eq_mul_divp {α : Type u} [CommMonoid α] (x y : α) (u : αˣ) :
    x /ₚ u * y = x * y /ₚ u := sorry

@[simp] theorem mul_right_eq_self {M : Type u} [inst : LeftCancelMonoid M] {a b : M} :
    a * b = a ↔ b = 1 := sorry

variable {R : Type _} [CommRing R] (a b : R) (u₁ u₂ : Rˣ) in
set_option trace.Meta.synthInstance true in
set_option trace.Meta.Tactic.simp true in
example : a /ₚ u₁ = b /ₚ u₂ ↔ a * u₂ = b * u₁ := by
  simp [divp_eq_iff_mul_eq, divp_mul_eq_mul_divp]
/-
...

[Meta.synthInstance] ❌ LeftCancelMonoid R ▶

[Meta.synthInstance] ❌ LeftCancelMonoid R ▶

[Meta.synthInstance] ❌ LeftCancelMonoid R ▶

[Meta.synthInstance] ❌ LeftCancelMonoid R ▶

[Meta.synthInstance] ❌ LeftCancelMonoid R ▶

[Meta.synthInstance] ❌ LeftCancelMonoid R ▶
...
-/

The instance trace in this minimal example shows Lean trying and failing to solve LeftCancelMonoid R 384 times.

Expected behavior:

I would hope that Lean does not need to go up this blind alley.

Actual behavior: [What actually happens]

In this minimal example, Lean spends a lot of time trying and failing very quickly to solve LeftCancelMonoid R. In the mathlib example which this was minimised from, Lean tries to solve LeftCancelMonoid R over 500 times and each time it takes a lot longer to fail because in mathlib there are of course ways to prove that something is a left-cancel-monoid. Lean 4 takes about 0.001 seconds to fail each time in the mathlib example, contributing to a 0.5 second delay. Unfortunately it then tries to solve RightCancelMonoid R hundreds of times, and then CancelMonoidWithZero R hundreds of times (I could probably update the MWE to indicate this behaviour if you want to see the wild goose chase happening multiple times), meaning that the simp call takes so long to complete that Lean runs out of heartbeats.

Reproduces how often: [What percentage of the time does it reproduce?]

100%

Versions

Lean (version 4.0.0-nightly-2023-01-16, commit 5349a08, Release)

Additional Information

Zulip discussion here.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions