[GHC] #11650: Default definitions for Alternative(some, many) can easily blow up
#11650: Default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Consider this case (taken from #11649) {{{#!hs import Control.Applicative data U1 p = U1 instance Functor U1 where fmap f U1 = U1 instance Applicative U1 where pure _ = U1 U1 <*> U1 = U1 instance Alternative U1 where empty = U1 U1 <|> U1 = U1 instance Show (U1 p) where show U1 = "U1" main = print (some U1) }}} This looks fine, right? Wrong, {{{ $ ./Main Main: <<loop>> }}} It seems that the default definitions of `some` and `many` will produce looping code in these cases (although it's not entirely clear to me which cases "these" cases are). I suppose this is due to the fact that `U1` will always "succeed". We should ensure that this is noted in the documentation to ensure that users don't end up with accidentally bottoming instances. Well, consider what happens -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * cc: core-libraries-committe (removed) * cc: core-libraries-committee (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * cc: core-libraries-committee (removed) * cc: core-libraries-committee@… (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by bgamari: @@ -30,0 +30,10 @@ + Of course, this can be avoided by simply defining `some` and `many` in + `U1`'s `Alternative` instance, + {{{#!hs + instance Alternative U1 where + empty = U1 + U1 <|> U1 = U1 + some U1 = U1 + many U1 = U1 + }}} + New description: Consider this case (taken from #11649) {{{#!hs import Control.Applicative data U1 p = U1 instance Functor U1 where fmap f U1 = U1 instance Applicative U1 where pure _ = U1 U1 <*> U1 = U1 instance Alternative U1 where empty = U1 U1 <|> U1 = U1 instance Show (U1 p) where show U1 = "U1" main = print (some U1) }}} This looks fine, right? Wrong, {{{ $ ./Main Main: <<loop>> }}} Of course, this can be avoided by simply defining `some` and `many` in `U1`'s `Alternative` instance, {{{#!hs instance Alternative U1 where empty = U1 U1 <|> U1 = U1 some U1 = U1 many U1 = U1 }}} It seems that the default definitions of `some` and `many` will produce looping code in these cases (although it's not entirely clear to me which cases "these" cases are). I suppose this is due to the fact that `U1` will always "succeed". We should ensure that this is noted in the documentation to ensure that users don't end up with accidentally bottoming instances. Well, consider what happens -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by bgamari: @@ -45,3 +45,2 @@ - should ensure that this is noted in the documentation to ensure that users - don't end up with accidentally bottoming instances. - Well, consider what happens + should note this in the documentation to ensure that users don't end up + with accidentally bottoming instances. New description: Consider this case (taken from #11649) {{{#!hs import Control.Applicative data U1 p = U1 instance Functor U1 where fmap f U1 = U1 instance Applicative U1 where pure _ = U1 U1 <*> U1 = U1 instance Alternative U1 where empty = U1 U1 <|> U1 = U1 instance Show (U1 p) where show U1 = "U1" main = print (some U1) }}} This looks fine, right? Wrong, {{{ $ ./Main Main: <<loop>> }}} Of course, this can be avoided by simply defining `some` and `many` in `U1`'s `Alternative` instance, {{{#!hs instance Alternative U1 where empty = U1 U1 <|> U1 = U1 some U1 = U1 many U1 = U1 }}} It seems that the default definitions of `some` and `many` will produce looping code in these cases (although it's not entirely clear to me which cases "these" cases are). I suppose this is due to the fact that `U1` will always "succeed". We should note this in the documentation to ensure that users don't end up with accidentally bottoming instances. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): We could also fix this issue by making the `Applicative` instance less strict: {{{#!hs instance Applicative U1 where U1 <*> _ = U1 }}} I'm not sure which is the best approach. `Proxy` (which is isomorphic to `U1`) doesn't pattern-match on its arguments in ''any'' of its instances, which allows it to short-circuit in a lot of possibly diverging computations. Then again, `Proxy` doesn't have an `Alternative`/`MonadPlus` instance for some reason... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ekmett): The only reason it doesn't have `Alternative` and `MonadPlus` instances is that I didn't think of them! (Similarly, `MonadZip`) I have absolutely no objection to adding them. If someone concocts a patch to add them to `base`, I'll readily retroactively add them to the `tagged` package, and Ryan can incorporate backports of them into `base-orphans`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): OK. I noticed that `U1` is also missing a `MonadPlus` instance as well, so we can scoop up all the missing `U1`/`Proxy` instances in another patch. So now that question remains: do we fix `U1`'s `Alternative` instance by overriding `some`/`many`, or do we fix it by making `<*>` lazier? I'm inclined to pick the former, since `U1` is almost always used in the context of GHC generics, and strictly pattern-matching on it is almost always what you intend to do. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ekmett): I mostly lack a preference here, but if we make it match the semantics of `Proxy` it'd avoid complications later on if we were to ever decide to make the leap and unify `(:*:)` with `Product`, `(:+:)` with `Sum`, `U1` with `Proxy`, etc. rather than retain two of each. I'm not proposing that we unify these things today, when and if we decide to do so it should be carefully deliberated, with possible wins weighed against ecosystem disruption, but anything that takes them further apart for trivial reasons forecloses interesting possible futures for no real gain. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for
Alternative(some, many) can easily blow up
-------------------------------------+-------------------------------------
Reporter: bgamari | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Documentation | Version: 7.10.3
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
| Unknown/Multiple
Type of failure: None/Unknown | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Ben Gamari
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): RyanGlScott, I've committed the patch in comment:9 as a stop-gap measure; I hope you'll have a chance to add the instance mentioned in comment:7 and when you do so fix `U1` to your liking. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): Replying to [comment:8 ekmett]:
I mostly lack a preference here, but if we make it match the semantics of `Proxy` it'd avoid complications later on if we were to ever decide to make the leap and unify `(:*:)` with `Product`, `(:+:)` with `Sum`, `U1` with `Proxy`, etc. rather than retain two of each.
That's a pretty convincing argument. It does seem like it would save us work in the long run to make `U1` as `Proxy`-like as possible (and similarly with other `GHC.Generics` datatypes), so I'll do this before 8.0 lands. Some questions we should answer: 1. Do change `U1`'s derived `Eq`, `Ord`, `Read`, and `Show` instances (which have been around for a while) and manually implement them with lazy pattern-matching? That seems like the sensible thing to do, although it would be a subtle semantic change. 2. Do we add all of the extra instances which `Proxy` has but `U1` doesn't? (`Enum`, `Bounded`, `Ix`, etc.) My gut reaction is to punt on this and only add them if someone requests it. Plus, if we decide to merge `U1` and `Proxy`, it will be a moot point after that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for
Alternative(some, many) can easily blow up
-------------------------------------+-------------------------------------
Reporter: bgamari | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Documentation | Version: 7.10.3
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
| Unknown/Multiple
Type of failure: None/Unknown | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Ben Gamari
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): We could still use some documentation for `Alternative` to point out this gotcha? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11650: Documentation does not mention that default definitions for Alternative(some, many) can easily blow up -------------------------------------+------------------------------------- Reporter: bgamari | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Documentation | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): We could, although I'm not quite sure what is the best way to describe the problem (and solution). There is a [https://mail.haskell.org/pipermail /haskell-cafe/2011-December/097589.html haskell-cafe] thread from 2011 which tried to address the issue of documenting `some`/`many` more precisely, but that never seemed to reach a consensus. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11650#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC