Hint Mode +
should not shelve dependent subgoals that only appear in +
positions
#14707
Labels
part: typeclasses
The typeclass mechanism.
We were trying to use
Hint Mode +
to tell typeclass search that thekey
andvalue
arguments of amap
typeclass are to be considered as inputs, ie typeclass search should only act on goals of the formmap K V
where bothK
andV
are known, but not on goals of the formmap ?key ?value
, because this might later lead to surprising error messages if typeclass search picks any map implementation with potentially the wrongkey
andvalue
types.Here's a minimized example (in Coq 8.13.2):
If I use
Hint Mode +
, Coq fails to infer a(_ : goal)
, and I have to useHint Mode -
in order to get it to work again.It is also interesting that
Check mk_goal
can infer the missing arguments, whereasCheck (_: goal)
cannot, so why is this?Using
Set Typeclasses Debug Verbosity 2
and comparing the output of the two, I think I found out why:Check mk_goal
first looks for aword
, findsdefault_word
, and then looks for amap default_word B
, which succeeds as well.On the other hand,
Check (_: goal)
starts by findingmk_goal
, which opens two subgoals, and since the first subgoal appears as a dependency in the second subgoal, the first subgoal is shelved, and typeclass search works on the second subgoal, which appears as(map ?key B)
. Now, since we have aHint Mode map + + : typeclass_instances
, the two arguments ofmap
are treated as inputs to typeclass search, and since one of them is unknown, this subgoal is "suspended", and resolution continues "on the remaining goals", but there are none (because the shelved ones are not considered), so it tries one more time, and then sees that it has reached "a fixed point when the set of remaining suspended goals does not change", so no solution is found.This explanation is derived from combining the output of
Set Typeclasses Debug Verbosity 2
with the explanation in this paragraph in the the manual:A simple solution to this problem is to simply do
Hint Mode map - - : typeclass_instances
, because then typeclass search succeeds on the(map.map ?word byte)
subgoal, but then we can't benefit from theHint Mode +
feature any more.I also tried
Set Typeclasses Dependency Order
, but that didn't help.It seems to me that if
Hint Mode +
is set, after applyingmk_goal
, typeclass search should detect that even though the first subgoal appears as a depencency of the second subgoal, it must not be shelved, because it only appears in an input (+
) position, so solving the second subgoal will not determine the first subgoal.So at my current state of understanding, I'd tend to call this a bug, but maybe I misunderstood how
Hint Mode
is supposed to be used, or there is already a flag that makes this example work? Some guidance by typeclass experts would be appreciated :)The text was updated successfully, but these errors were encountered: