Order-sensitivity in SpecConstr
Consider this code
foo :: Int -> (a,a) -> Maybe (a,a)
foo 0 p = Just p
foo n (x,y) = foo (n-1) (y,x)
wombat1 = foo 20 ("yes", "no")
wombat2 xs ys = foo 3 (xs, ys)
Here foo
is lazy in its second argument, but it does decompose it, so SpecConstr
should catch it. We have two calls, one of which (in wombat2
)is polymorphic.
Ideally we would like to see
RULE forall a. forall n::Int, x::a, y:;a. foo n (x,y) = $sfoo n x y
which fires on all three calls to foo
. And that is what happens if the declaration of
wombat2
appears before wombat1
. But as written, we get this specialisation (only):
RULES: "SC:$wfoo0" [2]
forall (sc_sVo :: [Char])
(sc_sVp :: [Char])
(sc_sVn :: GHC.Prim.Int#).
$wfoo_sV6 @String sc_sVn (sc_sVo, sc_sVp)
= $s$wfoo_sVt sc_sVo sc_sVp sc_sVn]
and indeed the call in wombat2
is never specialise. Boo!
Diagnosis
We discover two calls but in callsToNewPats
we see
-- Remove duplicates
non_dups = nubBy samePat new_pats
Moreover samePat
treats both calls (one polymorphic and one at type String) as the "same".
So the nubBy
drops one of them, and which is dropped is order-dependent.
Why does it treat them the same? Because of Note [Ignore type differences]
which points out that we don't want lots of identical
specialisations, differing only in their type. Good point, but the consequences are bad.
Cure
We need some form of patten-generality comparison, to make the polymorphic pattern "beat" the monomorphic one.
This pattern-subsumption approach would then be vulnerable to generating multiple specialisations for calls
foo 10 ("foo", "baz") -- Called at String
foo 10 (True, False) -- Called at Bool
Ideally we'd like to to generalise to a specialisation that works for all types, not just String
and Bool
.
And that must be possible, because if the function scrutinises its argument, can't be
poymorphic in it. Using foo
's polymorphic type, We ought to be able to generalise from a single call
foo @Int 10 (3,4)
to the more general form
foo @a n (x::a, y:;a)
That looks do-able, but not trivial.
Meanwhile, a simple subumption check would avoid discarding the wrong pattern. It risks generating lots of identical specialisations, while we currently arbitrarily pick one. But we have other (crude) ways of throttling lots of specialisations.