[GHC] #9495: Do What I Mean RULES for foldr2 look shady
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 7.8.3 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Unknown | Type of failure: Runtime Blocked By: | crash Related Tickets: | Test Case: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- There's a comment in the source: {{{ The foldr2/right rule isn't exactly right, because it changes the strictness of foldr2 (and thereby zip) E.g. main = print (null (zip nonobviousNil (build undefined))) where nonobviousNil = f 3 f n = if n == 0 then [] else f (n-1) I'm going to leave it though. }}} This rule is intended to allow `foldr2` to fuse with ''either'' argument list. There are thus two problems, one already documented and the other not: 1. The rule can turn working code into non-working code, although this seems to be ''relatively'' unlikely. (The problem the above example is showing is that if the left list ends at the same time the right list bottoms out, the world goes boom. So `foldr2 f [1,2,3,4] (1:2:3:4:undefined)` appears to be a problem. You could argue this is not a big deal, I suppose. 2. The `foldr2/left` and `foldr2/right` rules are not confluent. They are both active in all phases, but if both list arguments are good producers, they will each want to rewrite the expression differently. So if you actually care about which one fuses, you need to explicitly block fusion with one argument using `NOINLINE`, which of course could easily muck up some other optimization. My uninformed opinion: nix the `foldr2/right` rule, and change the documentation to indicate that `foldr2` fuses with its ''left'' argument. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): An alternative would be to change the definition of `foldr2` (to check for the end of the right list first) and then eliminate the `foldr2/left` rule instead. I think that gives a slightly more consistent interface. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: highest | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * priority: normal => highest * milestone: => 7.8.4 Comment: I'm elevating the priority because it causes an ''undocumented'' reduction in laziness depending on optimization flags. Changing the documentation would lower the priority. Note: if eliminating the DWIM non-confluent rules is considered too much of a breaking change, we can fix the semantics, at least in part, by changing the baseline definition of `foldr2`, and making sure the documentation matches. Specifically, make the first base case look like {{{#!hs foldr2 c n [] ys = ys `seq` n }}} I'm not sure if the rewritten version will end up with the ''same'' semantics, but I'm pretty sure it won't be ''less'' defined, which is the current situation. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: highest | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nomeata): The root of all this is the asymmetry of {{{ Prelude> zip [] undefined [] Prelude> zip undefined [] *** Exception: Prelude.undefined }}} So what does the report say? It defined `zip` via `zipWith`: {{{ zipWith :: (a->b->c) -> [a]->[b]->[c] zipWith z (a:as) (b:bs) = z a b : zipWith z as bs zipWith _ _ _ = [] }}} At first I thought that this definition will imply `zipWith (+) [] ⊥ = ⊥`, but that doesn’t seem to be the case – pattern are tried from left to right. So while I dislike the slight asymmetry here, I don’t think it is justified to not follow the standard here. OTOH, I also don’t think that the semantic change, although a wart, is bad enough to justify not being able to fuse on one or the other side. I also think it is reasonable to try to fuse on boths sides (even if the result is not confluent if we could fuse on both sides). So I currently don’t see how to improve the code. Which leaves us improving the documentation. Would you provide a patch against that? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: highest | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:3 nomeata]:
So while I dislike the slight asymmetry here, I don’t think it is justified to not follow the standard here.
We ''already'' aren't following the standard here! These are the three options I see (tl;dr: I think options 1 and 3 deserve serious consideration, and option 4 less; option 2 is more a Haskell Prime kind of question): 1. Eliminate `foldr1/right`, which will bring us into compliance with the standard, and change the documentation to indicate that we only fuse on the left list. The confluence problem is eliminated. The only downside is that if someone is relying on this rule, then their code will slow down. They will be able to fix this easily, but only if they pay attention to GHC release notes, are still maintaining their code, etc. 2. Change the baseline (not rewritten) definition of `foldr2` to check for nil on the second list first, and then eliminate `foldr1/left`. Document a violation of the standard. This also eliminates the confluence problem. I think it's arguably friendlier to fuse on the ''last'' argument than the first. That said, I don't think this is really a sensible option at this point because it has the downsides of most of the other options combined. 3. Change the baseline (not rewritten) definition of `foldr2` to force the second list to WHNF if the first is nil, rendering `foldr2` symmetrical. Document a violation of the standard. This approach ensures (I ''believe'') that the (still non-confluent) rules cannot produce bottoms that weren't there before. Personally, I would consider this the most conservative acceptable approach. 4. Leave things as they are in the code, but explain the situation in the documentation. I don't like this option, for the simple reason that code that runs correctly with `-O0` and doesn't do anything weird with funky `GHC.*.*` or `unsafe*` functions really should also run correctly with `-O`, but currently that is not the case. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: highest | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nomeata):
We already aren't following the standard here!
hmm, true. In that case I’m in favor of 3. I don’t think we guarantee confluence anywhere, and I’m not sure if it is worth more than possibilities for fusion. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: highest | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): To broaden this a bit, it is worth remembering that ''the main `foldr/build` rule itself is unsound in the presence of `seq`''. See, for example, the [http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion#In_the_pr... Haskell wiki page]. This is not nice. The "right" solution is for `seq` to be an operation of a type class, something that was the case in Haskell originally, and then changed after ''extensive'' debate on the Haskell committee. So currently we are stuck in the unsatisfactory situation that certain optimisations, which have a generally very beneficial effect on performance, can change termination behaviour. Eta reduction/expansion is another. In that general context I don't have a strong opinion about the `foldr2` question. I'd consult the Core Libraries Committee. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
To broaden this a bit, it is worth remembering that ''the main `foldr/build` rule itself is unsound in the presence of `seq`''. See, for example, the [http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion#In_the_pr... Haskell wiki page].
This is not nice. The "right" solution is for `seq` to be an operation of a type class, something that was the case in Haskell originally, and
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: highest | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:6 simonpj]: then changed after ''extensive'' debate on the Haskell committee.
So currently we are stuck in the unsatisfactory situation that certain
optimisations, which have a generally very beneficial effect on performance, can change termination behaviour. Eta reduction/expansion is another.
In that general context I don't have a strong opinion about the `foldr2`
question. I'd consult the Core Libraries Committee.
Simon
Without a doubt, these are not nice. But we generally keep the danger under control. We make the compiler prove that eta expansion is safe before applying it (I'm not sure what happens with eta reduction). We hide `build` away from the normal user libraries to allow us to pretend it will only be used by people who have read the necessary documentation (yes, that documentation may need some improvement). But `foldr2`, `zipWith`, and `zip` are completely exposed, right in the Prelude, along with a `filter` for them to crash with! David -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: patch Priority: high | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * priority: highest => high * status: new => patch -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady
-------------------------------------+-------------------------------------
Reporter: dfeuer | Owner:
Type: bug | Status: patch
Priority: high | Milestone: 7.8.4
Component: | Version: 7.8.3
libraries/base | Keywords:
Resolution: | Architecture: Unknown/Multiple
Operating System: | Difficulty: Unknown
Unknown/Multiple | Blocked By:
Type of failure: Runtime | Related Tickets:
crash |
Test Case: |
Blocking: |
Differential Revisions: |
-------------------------------------+-------------------------------------
Comment (by Joachim Breitner
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: closed Priority: high | Milestone: 7.8.4 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: patch => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: closed Priority: high | Milestone: 7.10.1 Component: | Version: 7.8.3 libraries/base | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: crash | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by thoughtpolice): * milestone: 7.8.4 => 7.10.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9495: Do What I Mean RULES for foldr2 look shady -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: closed Priority: high | Milestone: 7.10.1 Component: libraries/base | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime crash | Unknown/Multiple Blocked By: | Test Case: Related Tickets: #9949 | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by hvr): * related: => #9949 Comment: as noted in #9949, the change in strictness breaks the common `zipWith f xs (tail xs)` idiom -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9495#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC