Brazillians are sometimes blind to perfect hints

[JasonGross]

Why does this hint, which exactly matches the goal (up to symmetry), not get used?

Definition Type := Universe f0.

Parameter sigma : forall (A : Type), (A -> Type) -> Type.

Parameter pair :
  forall (A : Type)
         (P : A -> Type)
         (a : A)
         (b : P a),
         sigma A P.

Parameter sigma_elim :
  forall (A : Type)
         (P : A -> Type)
         (u : sigma A P)
         (C : sigma A P -> Type),
         (forall (a : A) (b : P a), C (pair A P a b)) -> C u.

Parameter sigma_half_eta' :
  forall (A : Type)
         (P : A -> Type)
         (u : sigma A P),
    sigma_elim A P u (fun (_ : sigma A P) => sigma A P)
               (fun (a : A) (b : P a) => pair A P a b)
    ==
    u.

Definition sigma_eta_helper_helper' :=
  fun (A : Type)
      (P : A -> Type)
      (u : sigma A P)
  =>
    rewrite sigma_half_eta' A P u in
    refl u
    :: sigma_elim A P u (fun (_ : sigma A P) => sigma A P) (fun (a : A) (b : P a) => pair A P a b)
     == u (* match u with (a; b) => (a; b) end == u *).
(* Warning: Why are terms
           u
         and
           sigma_elim A P u (fun (_ : sigma A P) => sigma A P)
           (fun (a : A) (b : P a) => pair A P a b)
         equal?
Typing error: examples/sigma.br:34:5: expression refl u has type u == u
but should have type sigma_elim A P u (fun (_ : sigma A P) => sigma A P)
                     (fun (a : A) (b : P a) => pair A P a b)
                       ==
                       u *)

[christopherastone]

Probably a difference in a hidden type annotation, something like El(unitname) vs. Unit. I've patches this by having exact matches use the built-in equivalence algorithm (without hints or rewrites) instead of alpha-equivalence. #14 also runs.

Unfortunately, this change makes the system noticeably slower. (because running beta-eta equivalence on every subterm to see if it's the term-to-rewrite is at least a constant factor slower than running alpha-equivalence on every subterm to see if it's the term-to-rewrite).

[JasonGross]

Do you short-circuit the alpha-equivalence case? Is there a verbosity level that prints out the hidden annotations? (If not, can there be?)

[christopherastone]

Sure, but the the short circuit can only make equivalence faster. Inequivalence, which is the likely issue here, doesn't speed up at all. (When alpha-equivalence fails, you still have to do the full beta-eta check to make sure they're not somehow equivalent).

--annotate tells the pretty-printer not to elide the hidden stuff, but do so only if you have a strong stomach.

[JasonGross]

Why is inequivalence the issue here?

[christopherastone]

It's now working harder to identify subterms that can be rewritten, by
using a more general notion of equivalence.

99% of subterms are not rewritable, but there's no way to identify
them ahead of time...they still have to be checked for equivalence to
verify they're not equivalent to any rewriting hint. This checking has
gotten more expensive.

(Actually we compares types of terms and patterns before comparing the
types and patterns themselves, but the principle still applies)

[JasonGross]

You've probably already thought of all of this, but can you store the hints in beta-normal (and eta-long?) form, and beta-(eta-)normalize the things you're checking against? (The beta-normal form, at least, can be computed once-and-forall for the whole term, I think.)

[andrejbauer]

Actually, I think the user should be giving hints in normal form. At least for now.

[andrejbauer]

Obsolete, the hints are gone from the kernel.