- Libraries - Haskell.org

Re: Proposal: Use uninterruptibleMask for cleanup actions in Control.Exception
by Eyal Lotem 02 Oct '14

02 Oct '14

Hey Simon, thanks for the reply! On Fri, Sep 5, 2014 at 6:39 PM, Simon Marlow <marlowsd(a)gmail.com> wrote: > Eyal, thanks for bringing up this issue. It's been at the back of my mind > for a while, but I've never really thought through the issues and > consequences of changes. So this is a good opportunity to do that. You > point out (in another email in the thread) that: > > A) Cases that were not interruptible will remain the same. > B) Cases that were interruptible were bugs and will be fixed. > > However, > > C) Some bugs will turn into deadlocks (unkillable threads) > > Being able to recover from bugs is an important property in large > long-running systems. So this is a serious problem. Hence why I always > treat uninterruptibleMask with the deepest suspicion. > Recovering from various kinds of failures makes a lot of sense. But how can you recover from arbitrary invariants of the program being broken? For example, if you use a bracket on some semaphore monitoring a global resource. How do you recover from a bug of leaking semaphore tokens? Recovering from crashes of whole processes whose internal state can be recovered to a fresh, usable state, is a great feature. Recovering from thread crashes that share arbitrary mutable state with other threads is not practical, I believe. > Let's consider the case where we have an interruptible operation in the > handler, and divide it into two (er three): > > 1. it blocks for a short bounded amount of time. > 2. It blocks for a long time > 3. It blocks indefinitely > > These are all buggy, but in different ways. Only (1) is fixed by adding > uninterruptibleMask. (2) is "fixed", but in exchange for an unresponsive > thread - also undesirable. (3) was a bug in the application code, and > turns into a deadlock with uninterruptibleMask, which is undesirable. > I think that (1) is by far the most common and is very prevalent. I think 0-time interruptible (that can block but almost never do) operations are the most common cleanup handlers. For (2) and (3), we need to choose the lesser evil: A) Deadlocks and/or unresponsiveness B) Arbitrary invariants being broken and leaks In my experience, A tends to manifest exactly where the bug is, and is therefore easy to debug and mostly a "performance bug" . B tends to manifest as difficult to explain behavior elsewhere from where the bug actually is, and is usually a "correctness bug", which is almost always worse. Therefore, I think A is a far far lesser evil than B, when (2) and (3) are involved. I'd like to reemphasize that this change will almost always fix the problem completely since the most common case is (1), and in rare cases, it will convert B to A, which is also, IMO, very desirable. > This is as far as I've got thinking through the issues so far. I wonder > to what extent the programmer can and should mitigate these cases, and how > much we can help them. I don't want unkillable threads, even when caused > by buggy code. > Cheers, > Simon > > > On 04/09/2014 16:46, Roman Cheplyaka wrote: > >> I find your arguments quite convincing. Count that as +1 from me. >> >> Roman >> >> >> >> _______________________________________________ >> Libraries mailing list >> Libraries(a)haskell.org >> http://www.haskell.org/mailman/listinfo/libraries >> >> -- Eyal

3 3

Proposal: (breaking change to avoid fragile breakage) change the definition of foldr2, zip, and zipWith
by David Feuer 01 Oct '14

01 Oct '14

BACKGROUND TRAC: #9495 GHC's definition of foldr2 violates the spec of the Haskell Report, making some programs less defined than they should be, and does so in a way that is quite fragile, dependent on a number of different factors—that is, it is likely hard to debug. Details: The current "baseline" definition of foldr2 (before rewrite rules) does what the Report requires: foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c foldr2 k z = go where go [] _ys = z go _xs [] = z go (x:xs) (y:ys) = k x y (go xs ys) There are two rewrite rules, foldr2/left and foldr2/right, designed to allow foldr2 to fuse with build appearing in either the first or second list argument. foldr2/left is perfectly safe (as long as the build argument is legitimate). foldr2/right is not, as comments in the source partially explain. The problem shows up if you have something shaped like zip [1,7,42,5] (1:8:4:11:undefined) but where the second list (ending in undefined) is actually produced using build, and GHC chooses to fuse foldr2 with it. The Report requires the above to produce [(1,1),(7,8),(42,4),(5,11)], but GHC will instead produce (1,1):(7,8):(42,4):(5,11):_|_ This issue can make a program that works with -O0 fail with -O, and can cause fragility depending on exactly what fuses. SCOPE One obvious question is what kinds of build forms can cause problems. Many, like map and fromEnumTo, don't have enough power to be likely to cause trouble. Joachim Breitner, however, realized that the current implementation of filter has enough power to break things. So here's a complete example of code that will break with -O but not with -O0: {-# NOINLINE don'tFuse #-} don'tFuse = id p x = 100 `mod` x < 20 main = print $ zip (don'tFuse [10,9..1]) (filter p [10,9,..]) Things will only get worse if I succeed in my plan to bring unfoldr into the framework. SOLUTIONS 1. One solution, of course, is to eliminate unfoldr2/right, bringing GHC into compliance with the Report. I really like this idea, but Joachim thinks it is not worth the potential performance impact on code written before or without regard for the change. We both agree that a reasonable alternative is 3. Modify the baseline definition of unfoldr2 as follows: foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c foldr2 k z = go where go [] ys = ys `seq` z go _xs [] = z go (x:xs) (y:ys) = k x y (go xs ys) This should, we believe, make the baseline definition fail where the one fused by foldr2/right would fail, giving consistent semantics. WHAT MIGHT BREAK Code that currently works but will break with this change has two properties: 1. It relies on the asymmetry in foldr, zipWith, or zip to avoid running into bottom. 2. foldr2/right does not fire, either because the second list is not a good producer or because GHC applies the foldr2/left rule instead. That is, most of the code that this change will break is fragile under the current scheme. DISCUSSION PERIOD Standard two weeks.

3 4

Proposal: change the Bits instance for Bool to align with other basic types and support branchless calculations
by David Feuer 30 Sep '14

30 Sep '14

Currently, the (.&.) and (.|.) methods for Bool are short-circuiting, defined like this: instance Bits Bool where (.&.) = (&&) (.|.) = (||) Unlike the instances for Int, Word, etc., this gives short-circuiting behavior (conditionally lazy in the second operand). Unfortunately, this requires a conditional branch to implement, which can sometimes be bad. Since (&&) and (||) are readily available to anyone who wants short-circuiting, I propose that we use the following instead. Note that the Bits class does not specify anything about this aspect of instance behavior. x .&. y = tagToEnum# (dataToTag# x `andI#` dataToTag# y) x .|. y = tagToEnum# (dataToTag# x `orI#` dataToTag# y) The rest of the operations look like this: x `xor` y = tagToEnum# (dataToTag# x `xorI#` dataToTag# y) complement x = tagToEnum# (dataToTag# x `xorI#` 1#) shift x s = testBit x s rotate x _ = x -- I don't think we gain anything changing this one. bit 0 = True bit _ = False testBit x b = tagToEnum# (dataToTag# x `andI#` (dataToTag# b ==# 0#)) bitSizeMaybe _ = Just 1 bitSize _ = 1 isSigned _ = False popCount x = I# (dataToTag# x) instance FiniteBits Bool where finiteBitSize _ = 1 countTrailingZeros x = I# (dataToTag# x `xorI#` 1#) countLeadingZeros x = I# (dataToTag# x `xorI#` 1#)

9 40

Pre-proposal discussion: add a version of dropWhileEnd with different laziness properties to Data.List
by David Feuer 29 Sep '14

29 Sep '14

BACKGROUND: A somewhat common idiom I discovered digging around the GHC tree is the use of reverse . dropWhile p . reverse to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this: dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) [] This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used. CONCEPT: Add (by some name) a function that is lazy in the elements while strict in the spine: dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) [] This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap. If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like takeUntilLastSatisfying p = dropWhileEnd (not . p) which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

6 13

Discussion: Change the specification of rotateL for non-finite Bits, or move rotations to FiniteBits
by David Feuer 29 Sep '14

29 Sep '14

Problem: The documentation currently specifies that for non-finite Bits instances, rotate is the same as shift. This seems reasonable for Integer rotateR, but very strange for Integer rotateL. In particular: rotateL 5 (-1 :: Int) = -1 rotateL 5 (-1 :: Integer) = 16 Based on the concept that Integers represent two's complement out to infinity, rotating a negative integer left should fill with 1s, but it fills with 0s instead. Solutions: As stated in the subject, I think one reasonable solution is just to make rotateL fill with 1s for negative non-finite instances, and the other is to move rotations to FiniteBits, as was done with bitSize.

4 7

List of core libraries
by Thomas Miedema 29 Sep '14

29 Sep '14

Hello core libraries committee, on the library submissions page on the Haskell wiki it says: "The core libraries ... define basic APIs that are expected to be available in any Haskell implementation." Is this list of those core libraries and their maintainers up-to-date: http://www.haskell.org/haskellwiki/Library_submissions#The_Core_Libraries I am asking, since GHC 7.8.3 also includes: * binary * bytestring * filepath * haskeline * hoopl * integer-gmp * terminfo * transformers But they are not core libraries. Is that correct? And GHC 7.8.3 doesn't include: * mtl * parallel * primitive * random * vector But they are core libraries. Is that correct? Cheers, Thomas

5 14

Re: [core libraries] List of core libraries
by Edward Kmett 28 Sep '14

28 Sep '14

Herbert: Heretofore I'd been treating filepath as owned by Neil Mitchell, but that statement does sound like he's handed it off to the libraries process, which would make it a core-libraries issue if he doesn't want to deal with it. I'm copying him on this thread to get his opinion. I've also copied Andy Gill, to see if he has any opinions on the state of who owns update responsibility for hpc itself. Andy, Neil: Thoughts? Thomas: Thanks for forcing this issue to attention. -Edward On Sun, Sep 28, 2014 at 2:14 PM, Herbert Valerio Riedel <hvriedel(a)gmail.com> wrote: > On 2014-09-28 at 19:40:25 +0200, Thomas Miedema wrote: > > [...] > > > Ok, final question: What about filepath and hpc? Their .cabal files list > > libraries(a)haskell.org as maintainer, which usually means the Core > Libraries > > Committee. Should filepath be added to that list, and the maintainer for > > both filepath and hpc be set to the Core Libraries Committee? If not, who > > maintains filepath? > > This is supposed to be an answer, but rather additional data-points: > > As far as filepath is concerned: > > http://community.haskell.org/~ndm/filepath/ > > states > > | The library is now part of the core Haskell libraries, and since GHC > | 6.6.1 has been shipped with all major compilers. While I am the > | original author, changes are now made through the library submissions > | process. > > as for Hpc, if you look at its changelog over at > > http://git.haskell.org/packages/hpc.git/shortlog > > it's been effectively maintained by GHC HQ for the last couple of > years... >

1 0

Proposal (long term): Remove (/=) from Eq; change the semantics of (==) for floating point
by David Feuer 25 Sep '14

25 Sep '14

As Edward Kmett explained to me, (/=) is currently needed in Eq to support IEEE floating point semantics for (==) and (/=). As I see it, those semantics are badly broken from the perspective of what Eq is supposed to mean, and really should be supported using special functions (eqIEEE and neqIEEE or whatever), whereas the most appropriate Eq instance for floating point would be something more like instance Eq Double where x == y = decodeFloat x == decodeFloat y If this is (eventually) done, that would allow us to remove (/=) from Eq, reducing its dictionary to a single member, (==), improving efficiency when the type is not statically known. David

7 9

Pre-Proposal: Add Validation somewhere easily accessible
by Joseph Abrahamson 25 Sep '14

25 Sep '14

The “purely applicative Either” is Either with a new Applicative interface which can no longer take a corresponding Monad interface. I have personally reinvented it over and over although it is perhaps commonly known as Validation: data Validation e a = Invalid e | Valid a deriving ( Show, Functor, … ) instance Monoid e => Applicative (Validation e) where pure = Valid Invalid e1 <*> Invalid e2 = Invalid (e1 <> e2) Invalid e1 <*> _ = Invalid e1 <*> Invalid e2 = Invalid e2 Valid f <*> Valid a = Valid (f a) -- No corresponding Monad It could be perhaps better implemented as a newtype wrapper over Either to facilitate rapid conversion to the more common type. Validation appears in its own package developed by Tony Morris and Nick Partridge. It also exists in Jonathan Sterling’s Vinyl package under the name Data.Vinyl.Idiom.Validation.Result. Gabriel Gonzalez has also told me that he’d be happy to add it to his `errors` package if a PR was made. The common use for Validation is to traverse over a structure and accumulate errors throughout it. In other words, failures should not halt the process and we can think of each operation as occurring in parallel. Not only is Validation a good example of an “Applicative without a Monad” its also a very useful practical type. I would like to build a proposal to include Validation in some form in a common package. Despite the misalignment with the name, `transformers` seems like a plausible target, though I fear changes to that package are rarely worth the pain. Suggestions on implementation and target package are welcome. Pending informative feedback, I will try to write a true proposal within 2 weeks. Thanks everyone, Joseph Joseph

10 20

Proposal: Add a few extra members to Foldable and Traversable classes
by David Feuer 21 Sep '14

21 Sep '14

To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose: Add `null` and `size` to the Foldable class. Default implementations: null = foldr (\_ _ -> False) True size = foldl' (\acc _ -> acc+1) 0 Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple. David

10 24