- Libraries - Haskell.org

Fusion
by Simon Peyton Jones 20 Aug '14

20 Aug '14

David You've been doing all this work on improving fusion, and you probably have a very good idea now about how it works, and how GHC's libraries use phases and RULES to achieve it. A kind of design pattern, if you like; tips and tricks. I wonder if you'd feel able to write a GHC wiki page describing what you have learned, with examples and explanation about why it is done that way. If you did this, someone who follows in your footsteps wouldn't need to re-learn everything. And maybe someone will say "oh, there's one pattern you have omitted, here it is". Thanks Simon

4 4

Proposal: Add forkOSUnmasked to Control.Concurrent
by Edward Kmett 19 Aug '14

19 Aug '14

Joey Adams wrote a request a year or so ago to add forkOSUnmasked to Control.Concurrent -- | Like 'forkIOWithUnmask', but the child thread is a bound thread, as with 'forkOS'. forkOSWithUnmask :: ((forall a . IO a -> IO a) -> IO ()) -> IO ThreadId forkOSWithUnmask io = forkOS (io unsafeUnmask) http://www.haskell.org/pipermail/libraries/2013-June/020271.html but it received no discussion. (He didn't formally open a discussion period though). It has languished as a GHC trac ticket for a year now. https://ghc.haskell.org/trac/ghc/ticket/8010 Now that we do not have block there are situations where you can need this. I'm opening this up for bikeshedding. Thoughts? Discussion period: 2 weeks. -Edward

3 2

and / or
by David Feuer 19 Aug '14

19 Aug '14

First question: how bad would it be to use the Prelude definitions of and and or? I assume if there's a problem it's probably excessive duplication by the inliner? Second question: if that would be bad, why not rewrite them to foldr forms, then write them back, like other things do? Statement: if the current arrangement really is the best, then we should add two additional rules: "and/augment" forall (g::forall b.(Bool->b->b)->b->b) (xs::[Bool]) . and (augment g xs) = g (&&) (and xs) "or/augment" forall (g::forall b.(Bool->b->b)->b->b) (xs::[Bool]) . or (augment g) = g (||) (or xs)

3 6

transformers: remove instance MonadFix ExceptT and ErrorT
by Henning Thielemann 18 Aug '14

18 Aug '14

I propose to remove the MonadFix instance for the ExceptT transformer, because it gives the illusion that it can handle exceptions, which it cannot. The current implementation is: instance (MonadFix m) => MonadFix (ExceptT e m) where mfix f = ExceptT $ mfix $ \ a -> runExceptT $ f $ case a of Right x -> x Left _ -> error "mfix ExceptT: Left" You see, that it cannot handle the exception case. Whenever someone needs an mfix on ExceptT I strongly suggest that he first handles the exception, thus turning (ExceptT e m a) into plain (m a) and then calls 'mfix' only on (m a). I further propose to declare the MonadFix instance as non-implementable in a way suggested in [1]: class NoMonadFix m where instance (NoMonadFix m) => MonadFix (ExceptT e m) where mfix = error "unimplementable" where no instance of NoMonadFix exist and NoMonadFix is not exported. Whenever someone tries to call 'mfix' on 'ExceptT e m' he will get the type error, that a NoMonadFix instance on 'm' is missing and he will not be able to add it. [1] http://ghc.haskell.org/trac/ghc/ticket/9334#comment:9

7 11

Re: [GHC] #9434: GHC.List.reverse does not fuse
by David Feuer 18 Aug '14

18 Aug '14

It looks like the following works at least reasonably well: {-# INLINE[0] revFlip #-} revFlip :: (a -> b -> b) -> b -> a -> b revFlip f b a = f a b {-# NOINLINE[1] reverse #-} reverse :: [a] -> [a] reverse xs = rv xs [] where rv [] r = r rv (y:ys) r = rv ys (y:r) {-# RULES "reverse" [~1] forall xs . reverse xs = build $ \c n -> foldl (revFlip c) n xs "reversePlain" [1] forall xs . foldr (\v fn z -> fn ((revFlip (:)) z v)) id xs [] = reverse xs #-} The complicated reversePlain rule actually fires, at least in my tests. If we miss a few, that may not be a disaster. I'm not at all confident that there's anything to be done about your concern about beta reduced forms without totally hosing other optimizations. David Feuer On Fri, Aug 15, 2014 at 3:22 PM, Dan Doel <dan.doel(a)gmail.com> wrote: > Yeah, I realized that part of the idea is for (the new) foldl to be defined > in terms of foldr, then inline (or rewrite), fuse, and get optimized. So > maybe you can't delay the foldl inlining. > > But it should be possible to recognize the foldr definition of foldl and > rewrite back, as long as the definition of foldl has appropriately > recognizable combinators instead of just lambda expressions. > > > On Fri, Aug 15, 2014 at 3:13 PM, David Feuer <david.feuer(a)gmail.com> wrote: >> >> I forgot about the flip! I wonder if I can even avoid NOINLINEing the >> foldl if I noninliningFlip and then bring it back from the resulting foldr. >> I'll have to try tonight. Thanks! >> >> On Aug 15, 2014 12:57 PM, "Dan Doel" <dan.doel(a)gmail.com> wrote: >>> >>> Make foldl's inline phased, and see what happens? >>> >>> Presumably the reason it doesn't have a phase limit yet is that it never >>> participated in any fusion before, so there was never a reason to not just >>> inline. >>> >>> Other than that it seems like: >>> >>> reverse xs >>> => rewrite >>> build (\c n -> foldl (noinlineFlip c) n xs) >>> => inline >>> foldl (noinlineFlip (:)) [] xs >>> => rewrite >>> reverse xs >>> >>> where I assume you need a special flip which may or may not exist in >>> these modules already. >>> >>> >>> On Fri, Aug 15, 2014 at 12:46 PM, David Feuer <david.feuer(a)gmail.com> >>> wrote: >>>> >>>> Yes, but I'm not sure how to do that, especially because foldl doesn't >>>> have the phased NOINLINE that foldr does. >>>> >>>> On Aug 15, 2014 12:45 PM, "Dan Doel" <dan.doel(a)gmail.com> wrote: >>>>> >>>>> Isn't this kind of thing fixed for other functions by rewriting back >>>>> into the direct recursive definition if no fusion happens? >>>>> >>>>> >>>>> On Fri, Aug 15, 2014 at 11:41 AM, David Feuer <david.feuer(a)gmail.com> >>>>> wrote: >>>>>> >>>>>> I'm having trouble when it doesn't fuse—it ends up with duplicate >>>>>> bindings at the top level, because build gets inlined n times, and the >>>>>> result lifted out. Nothing's *wrong* with the code, except that there are >>>>>> multiple copies of it. >>>>>> >>>>>> On Aug 15, 2014 10:58 AM, "GHC" <ghc-devs(a)haskell.org> wrote: >>>>>>> >>>>>>> #9434: GHC.List.reverse does not fuse >>>>>>> >>>>>>> -------------------------------------+------------------------------------- >>>>>>> Reporter: dfeuer | Owner: >>>>>>> Type: bug | Status: new >>>>>>> Priority: normal | Milestone: >>>>>>> Component: | Version: 7.9 >>>>>>> libraries/base | Keywords: >>>>>>> Resolution: | Architecture: >>>>>>> Unknown/Multiple >>>>>>> Operating System: | Difficulty: Easy (less >>>>>>> than 1 >>>>>>> Unknown/Multiple | hour) >>>>>>> Type of failure: Runtime | Blocked By: >>>>>>> performance bug | Related Tickets: >>>>>>> Test Case: | >>>>>>> Blocking: | >>>>>>> Differential Revisions: | >>>>>>> >>>>>>> -------------------------------------+------------------------------------- >>>>>>> >>>>>>> Comment (by simonpj): >>>>>>> >>>>>>> Great. Just check that when fusion ''doesn't'' take place, the >>>>>>> result is >>>>>>> good. And do a `nofib` comparison for good luck. Then submit a >>>>>>> patch. >>>>>>> >>>>>>> Thanks for doing all this work on fusion, David. >>>>>>> >>>>>>> Simon >>>>>>> >>>>>>> -- >>>>>>> Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9434#comment:2> >>>>>>> GHC <http://www.haskell.org/ghc/> >>>>>>> The Glasgow Haskell Compiler >>>>>> >>>>>> >>>>>> _______________________________________________ >>>>>> ghc-devs mailing list >>>>>> ghc-devs(a)haskell.org >>>>>> http://www.haskell.org/mailman/listinfo/ghc-devs >>>>>> >>>>> >>> >

2 2

Polymorphism in the Prelude
by Richard Eisenberg 17 Aug '14

17 Aug '14

Hi libraries, Let me try to sum up the general sentiment I've seen: Having lots of polymorphism in the Prelude is great, but for two problems: 1) It's very confusing to novices. 2) In the case of using Control.Category definitions: kind-polymorphism is not portable I wish to ignore (2) for now, as it's a smaller concern given that it affects only a portion of the proposed changes. As a way to mitigate (1), I have been thinking of proposing something almost exactly along the lines of http://comments.gmane.org/gmane.comp.lang.haskell.glasgow.user/23719 (thanks for posting that link -- saved me from writing up the same thing!). But, after reading that thread, I tend to agree that tweaking the module system seems the wrong way to deal with helping novices. In designing my own libraries, my general guideline is to make the easy thing easy and make the hard thing only slightly less easy. Spurred on by Erik Hesselink's comment (http://www.haskell.org/pipermail/libraries/2014-June/023174.html) what if we just have two versions of `base` modules, the "normal" one that exports more monomorphic definitions (which novices are more likely to use) and a "Poly" one that exports more polymorphic definitions. For example: {{{ {-# LANGUAGE NoImplicitPrelude #-} import Prelude.Poly import Data.List.Poly import Data.Foldable import Control.Monad.Poly }}} and then it just works. Pros: - Not disruptive to current status quo. - No change in error messages for novices. - Can actually be implemented without *any* changes to `base` -- I could upload this solution to Hackage today. Cons: - Maintaining two copies of export lists. - Needs NoImplicitPrelude pragma. - Overhead of remembering which modules have a "Poly" version and which don't. - Somewhat ugly. Even as I write this, I'm not sure that this is at all a good idea. But, to me, it's really intriguing that the solution is achievable today, with no difficulty. I would wager that if these Poly modules were out in the wild today, we might all grumble at them, but I don't know if there would be a movement to change the Prelude. Richard

19 32

Maintenance release of haskell-cgi?
by John Alfred Nathanael Chee 16 Aug '14

16 Aug '14

Hackage trustees, haskell-cgi [1] doesn't build with ghc 7.8.3. Two pull requests exist on github [2,3] and the maintainer (cc'd) is unresponsive. Can someone do a proxy release of haskell-cgi? Thanks. [1] https://github.com/andersk/haskell-cgi [2] https://github.com/andersk/haskell-cgi/pull/7 [3] https://github.com/andersk/haskell-cgi/pull/6 -- Love in Jesus Christ, John Alfred Nathanael Chee http://www.biblegateway.com/ http://web.cecs.pdx.edu/~chee/

2 5

Am I missing something about unfoldr?
by David Feuer 15 Aug '14

15 Aug '14

The current definition: unfoldr :: (b -> Maybe (a, b)) -> b -> [a] unfoldr f b = case f b of Just (a,new_b) -> a : unfoldr f new_b Nothing -> [] I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this: unfoldrB f b c n = go b where go b = case f b of Just (a,new_b) -> a `c` go new_b Nothing -> n unfoldr f b = build (unfoldrB f b) then we get some really nice fusion: foldr c n (unfoldr f b) = foldr c n (build (unfoldrB f b)) = unfoldrB f b c n The list is gone, and there are no new closures or data structures in its place. As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.

4 10

Proposal: add unfoldr1 to the somewhere in base
by David Feuer 15 Aug '14

15 Aug '14

Way back in 2001, Shin-Cheng Mu proposed an unfoldr1 combinator: http://code.haskell.org/~dons/haskell-1990-2000/msg06775.html I discussed this a bit with shachaf in #haskell, and he noted that a similar function, with a slightly different but isomorphic type, appears in Edward Kmett's semigroups package as the unfoldr for NonEmpty. I propose that we add this. It can be written unfoldr1 :: (b -> (a, Maybe b)) -> b -> [a] unfoldr1 f b = go b where go b = case f b of (a, may_b) -> a : maybe [] go may_b With the appropriate RULES, it can be wrapped up in build and fuse properly. I'd love to see this written as an unfoldr instead. Does anyone know if that's possible?

2 4

Seeking comments on proposed fusion rules
by David Feuer 15 Aug '14

15 Aug '14

The rules: lpaste.net/108508 The boring explanation: As I mentioned earlier, we currently can't fuse things like foldr (x : build g) The foldr can't see the build. Earlier, I considered a simple cons/build rule that would rewrite x : build g to build (\c n -> x `c` g c n) I wasn't quite satisfied with this approach, largely because it treats foldr c n (x1 : x2 : ... : xn : build g) one way, and foldr c n ([x1, x2, ..., xn) : build g) another way. The former expands out the foldr, while the latter (via various rules involving augment) translates into a foldr over [x1, x2, ..., xn]. I therefore came up with the idea of translating x1:x2:...:xn:build g into [x1:x2:..:xn]++build g, and then letting the current rules do their thing. dolio and carter (in #ghc) were concerned about what would happen if fusion *didn't* occur, in which case the resulting code appears to be *worse*. So then I wrote some rules to fix that up, which actually look likely to be good rules in general. They turn [x1:x2:...:xn] ++ ys into x1:x2:...:xn:ys I ended up having to do more that I had originally expected in my rules, because they miss a phase they need (it may be possible to fix that; I'm not sure, because I'm very new to this business); I left comments showing each step of the translation. One thing of note is that I ended up using (by hand) the augment/augment rule that is commented out as probably not being useful. In my limited testing, the rules seem to do what they're supposed to (when I can understand the Core), and the profiler is very pleased.

3 5