Re: [GHC] #13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators

[GHC]

#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators
-------------------------------------+-------------------------------------
        Reporter:  pacak             |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.2.1
       Component:  Compiler          |              Version:  8.2.1-rc2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Incorrect result  |  Unknown/Multiple
  at runtime                         |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by bgamari):

 > Why does it matter if we evaluate the same thunk twice? I'm lost.

 Well, I'm still not entirely certain what the problematic thunk looks
 like, but the program in question *does* rely on in-place modification of
 an array which would break if performed more than once.

 I believe the problem revolves around
 `Data.HashMap.Strict.unsafeInsertWith`, which, to paraphrase, does the
 following,
 {{{#!hs
 unsafeInsertWith :: (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
 unsafeInsertWith f k v (HashMap arr) = runST $ do
     marr <- unsafeThawArray# arr
     let some_index = {- some function of k -}
     old_v <- readArray# marr some_index
     writeArray# marr some_index (f old_v v)
     _ <- unsafeFreezeArray# marr
     return (HashMap arr)
 }}}

 That is, despite being a "pure" function, `unsafeInsertWith` take the
 array out of the `HashMap` which it was given, thaws it, modifies it,
 freezes it again, and then returns the same array as a "new" result. This
 means that if we have a thunk `unsafeInsertWith some_key some_value hm`
 which we enter twice, the multiple entry will be observable through the
 fact that the array element at `some_index` will be `f v (f v old_v)`,
 instead of `f v old_v` as was intended.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:25>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler