Instance chain groups #2929

LiamGoodacre · 2017-06-06T20:57:29Z

paf31 · 2017-06-08T02:57:31Z

I like the simplicity of this approach a lot, but there is a potential issue, as we discussed on Slack:

The solver works in stages, since there are two types of constraints:

Type class constraints with functional dependencies
Equality constraints which are generated by functional dependencies

Equality constraints cause types to become more solved by unification, which lets us try to solve more type class constraints, which generates more equalities, and so on.

The problem is that if we have a chain containing more than one instance, we cannot decide to use the second instance in the chain without knowing with certainty that we can never match the first. The problem is that we don't necessarily know this until we have enough information about the types involved to rule out the first instance, and that might require other functional dependencies to be solved first.

For example, suppose we have

class C a

instance x :: C String where
  ...
else instance y :: C a where
  ...

and suppose we need to solve C t0 where t0 is unknown. With the current approach, we would try x and it would fail, but y would succeed, since it matches everything. There is no overlap and we choose y. But some fundep might later be solved which forces t0 ~ String, and then we should have chosen x!

So before we can consider y we need to know that the types in the instance head are apart from the ones in x, not just that we won't choose x this time round.

I think we can do this by modifying the typeHeadsAreEqual function to differentiate the two cases.

LiamGoodacre · 2017-07-31T01:42:34Z

@paf31 There are still some TODOs and refactoring that could be done. But is this the kind of thing you were thinking?

paf31 · 2017-07-31T17:04:18Z

src/Language/PureScript/TypeChecker/Entailment.hs

+        go ([], TUnknown u1)      ([], TUnknown u2)      | u1 == u2   = (Match (), M.empty)
+        go ([], TypeVar v1)       ([], TypeVar v2)       | v1 == v2   = (Match (), M.empty)
+        go ([], Skolem _ sk1 _ _) ([], Skolem _ sk2 _ _) | sk1 == sk2 = (Match (), M.empty)
+        go (sd, r)                ([], TypeVar v)                     = (Match (), M.singleton v [rowFromList (sd, r)])


Do you need an Unknown case here too?

I've been trying for a little while, but I'm not sure how to get this situation to happen. Any ideas?

Actually, I don't think either Unknown case is required. But either both are, or neither is.

paf31 · 2017-07-31T17:04:28Z

src/Language/PureScript/TypeChecker/Entailment.hs

+        go ([], Skolem _ sk1 _ _) ([], Skolem _ sk2 _ _) | sk1 == sk2 = (Match (), M.empty)
+        go (sd, r)                ([], TypeVar v)                     = (Match (), M.singleton v [rowFromList (sd, r)])
+        go _ _                                                        = (Apart, M.empty)
+    typeHeadsAreEqual (TypeVar _) _ = (Unknown, M.empty)


Does this case get hit?

paf31 · 2017-07-31T17:04:51Z

src/Language/PureScript/Parser/Lexer.hs

                  , "infix"
                  , "class"
                  , "instance"
+                  , "instances"


Also else?

Oh I can revert this change. I updated the syntax to use interleaved else - which are already in this list.

paf31 · 2017-07-31T17:06:03Z

Looks great!

Is this breaking? I guess, technically yes, since it reserves new keywords. In that case, maybe we should also disallow overlapping instances, and release this in 0.12.0.

LiamGoodacre · 2017-07-31T17:24:51Z

The only breaking part here would be that the order of overlapping instances might be different (if we don't disallow them). But we don't advise people use overlapping instances anyway? There are no new keywords.

paf31 · 2017-07-31T17:28:59Z

Ok, great, then we can merge this into 0.11.x and disallow overlaps in 0.12.0 as a breaking change!

Very excited to merge this 😄

LiamGoodacre · 2017-07-31T21:19:09Z

src/Language/PureScript/TypeChecker/Entailment.hs

                  return $ uncurry Solved (head tcds)
-              | otherwise = return $ uncurry Solved (minimumBy (compare `on` length . tcdPath . snd) tcds)
+              | otherwise =
+                return $ uncurry Solved (minimumBy (compare `on` (\d -> (tcdChain d, tcdIndex d, length (tcdPath d))) . snd) tcds)


Now that we are considering instances in order, I shouldn't need to do this any more.

LiamGoodacre · 2017-07-31T21:19:42Z

src/Language/PureScript/TypeChecker/Entailment.hs

            overlapping TypeClassDictionaryInScope{ tcdDependencies = Nothing } _ = False
            overlapping _ TypeClassDictionaryInScope{ tcdDependencies = Nothing } = False
-            overlapping tcd1 tcd2 = tcdValue tcd1 /= tcdValue tcd2
+            overlapping tcd1 tcd2 = tcdValue tcd1 /= tcdValue tcd2 && (null (tcdChain tcd1) || tcdChain tcd1 /= tcdChain tcd2)


Shouldn't need this either.

paf31 · 2017-08-05T22:19:57Z

@LiamGoodacre Is this ready for a final review then?

LiamGoodacre

@paf31 should be good for a review. I've left some comments on things to consider. If you (or anyone) can think of any more examples to test with, that would be great. I should perhaps add some failing tests too.

LiamGoodacre · 2017-08-05T23:50:17Z

src/Language/PureScript/TypeChecker/Entailment.hs

+                  -- TODO: efficiency
+                  chain <- groupBy ((==) `on` tcdChain) $ forClassName (combineContexts context inferred) className' tys''
+                  -- process instances in a chain in index order
+                  let found = for (sortBy (compare `on` tcdIndex) chain) $ \tcd ->


Hmm, I might need to special-case when tcdChain = []. The processing of any non-chain instances shouldn't interfere with each other. In this case we wouldn't get the overlapping instances warning.

LiamGoodacre · 2017-08-05T23:51:27Z

src/Language/PureScript/TypeChecker/Entailment.hs

-                  ]
+            let instances = do
+                  -- TODO: efficiency
+                  chain <- groupBy ((==) `on` tcdChain) $ forClassName (combineContexts context inferred) className' tys''


The efficiency note here was to consider grouping using a Map instead.

garyb · 2017-08-06T12:21:45Z

This only supports a single chain of instances per class then? It seems if you try to define multiple there's no error aside from the fact overlaps start occurring again. Maybe it should have an explicit error instead? (Or ideally support multiple chains 😜)

LiamGoodacre · 2017-08-06T13:54:34Z

@garyb This is supposed to support multiple chains. But, in the same way that you shouldn't define overlapping instances, you shouldn't define overlapping chains.

Although, I did just try to use overlapping chains and it failed to solve.

class Learn a b | a -> b
instance learnInst :: Learn a String

class IsString t o | t -> o

instance isStringString :: IsString String True
else instance isStringElse :: IsString a False

instance isStringString' :: IsString String True
else instance isStringElse' :: IsString a False

learnIsString :: forall a t o.
  IsString t o =>
  Learn a t =>
  Proxy o
learnIsString = Proxy

isStringEg0 :: Proxy True
isStringEg0 = learnIsString

With the output:

[1/1 OverlappingInstances]

  Overlapping type class instances found for

    Foo.IsString t0 True

  The following instances were found:

    Foo.isStringElse (chosen)
    Foo.isStringElse'

  Overlapping type class instances can lead to different behavior based on the order of module imports, and for that reason are not recommended.
  They may be disallowed completely in a future version of the compiler.

  where t0 is an unknown type

[1/1 TypesDoNotUnify] src/Foo.purs:71:15

  71  isStringEg0 = learnIsString

  Could not match type

    False

  with type

    True

  while solving type class constraint

    Foo.IsString t0 True

If I don't have the duplicate chain, then it passes.

--instance isStringString' :: IsString String True
--else instance isStringElse' :: IsString a False

So something is wrong 😄

garyb · 2017-08-06T14:29:53Z

Hmm I think I see what's happening with the case I tried then, I'd need to be cleverer with the definitions (or maybe it's impossible)... I tried writing an Inject instance for second type isomorphic to Coproduct, and including any of the instances for Coproduct2 results in an overlap in a test case where I was trying to inject just into Coproduct.

LiamGoodacre · 2017-08-12T20:43:24Z

Turns out that groupBy doesn't do what I thought it did 😄

LiamGoodacre · 2017-08-12T22:46:58Z

Ummmmm, travis is complaining about code that doesn't exist? @paf31

/home/travis/build/purescript/purescript/src/Language/PureScript/AST/Declarations.hs:534:11: error:
    • The constructor ‘TypeInstanceDeclaration’ should have 8 arguments, but has been given 6
    • In the pattern: TypeInstanceDeclaration _ n _ _ _ _
      In an equation for ‘declName’:
          declName (TypeInstanceDeclaration _ n _ _ _ _) = Just (IdentName n)

LiamGoodacre · 2017-08-12T22:47:24Z

Or am I completely crazy?

LiamGoodacre · 2017-08-12T23:48:06Z

Oh, did it rebase my commits onto master and then try to build? 😕

LiamGoodacre · 2017-08-13T00:11:32Z

Okay, I've rebased and fixed the issue that Travis was complaining about.

hdgarrood · 2017-08-13T00:52:01Z

Oh, did it rebase my commits onto master and then try to build?

I think CI will usually merge your branch into master (locally, ie without modifying actual master in the repo), and attempt to build that. I think that is probably what it should be doing, too.

paf31 · 2017-09-10T00:11:27Z

@LiamGoodacre Could you please rebase this?

LiamGoodacre · 2017-09-10T21:54:35Z

Ah rebased at the wrong time, need to do it again 😄

LiamGoodacre · 2017-09-13T18:54:57Z

This should be good to go now.

paf31

💯 Thank you!

paf31 added the needs more work label Jun 8, 2017

paf31 reviewed Jul 31, 2017

View reviewed changes

LiamGoodacre commented Jul 31, 2017

View reviewed changes

LiamGoodacre commented Aug 5, 2017

View reviewed changes

tfausak mentioned this pull request Aug 15, 2017

Using purescript in a pragmatic manner tfausak/purescript-neon#113

Closed

LiamGoodacre changed the title ~~WIP prototype instance chain groups~~ Instance chain groups Aug 17, 2017

LiamGoodacre added 2 commits September 10, 2017 23:43

Add instance chain groups

9215177

Make OverlappingInstances an error

de51bbf

paf31 approved these changes Sep 13, 2017

View reviewed changes

paf31 merged commit aacdb9a into purescript:master Sep 13, 2017

LiamGoodacre deleted the feature/instance-chains branch September 13, 2017 21:28

JordanMartinez mentioned this pull request Aug 11, 2018

Document instance chains JordanMartinez/purescript-jordans-reference#22

Closed

Instance chain groups #2929

Instance chain groups #2929

Uh oh!

Conversation

LiamGoodacre commented Jun 6, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

paf31 commented Jun 8, 2017

Uh oh!

LiamGoodacre commented Jul 31, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

paf31 Jul 31, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

paf31 commented Jul 31, 2017

Uh oh!

LiamGoodacre commented Jul 31, 2017

Uh oh!

paf31 commented Jul 31, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

paf31 commented Aug 5, 2017

Uh oh!

LiamGoodacre left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

garyb commented Aug 6, 2017

Uh oh!

LiamGoodacre commented Aug 6, 2017

Uh oh!

garyb commented Aug 6, 2017

Uh oh!

LiamGoodacre commented Aug 12, 2017

Uh oh!

LiamGoodacre commented Aug 12, 2017

Uh oh!

LiamGoodacre commented Aug 12, 2017

Uh oh!

LiamGoodacre commented Aug 12, 2017

Uh oh!

LiamGoodacre commented Aug 13, 2017

Uh oh!

hdgarrood commented Aug 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

paf31 commented Sep 10, 2017

Uh oh!

LiamGoodacre commented Sep 10, 2017

Uh oh!

LiamGoodacre commented Sep 13, 2017

Uh oh!

paf31 left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

LiamGoodacre commented Jun 6, 2017 •

edited

Loading

paf31 Jul 31, 2017 •

edited

Loading

hdgarrood commented Aug 13, 2017 •

edited

Loading