Re: FoldrW/buildW issues
On Sep 12, 2014 2:35 PM, "Joachim Breitner" wrote: > Interesting. I assumed that some wrap.unwrap=id law would hold, or at > least some moral approximation (e.g. disregarding bottoms in an > acceptable manner). But if the wrappers have to do arbitrary stuff that > can arbitrarily interact with how the producer calls them, this becomes > a bit less appealing. No, nothing pleasant like that, I'm afraid. isoSimple is like that of course, but once it gets to foldl, the fusion rule is handing the builder a wrap/unwrap pair that isn't even close to that. > > 2. Somewhat related to the above, this framework has a huge amount of > > "wiggle room". There is very little to guide the choice of Wrap type. > > I guess that would be resolved by time and experience, if we’d employ > that scheme. But maybe we don’t. The only way I would imagine would be if it turned out there were a few types that could be composed somehow. But when I, experimentally, applied Dan Doel's scanl wrapper type combined with Simple to (!!), I just got wrong answers. > > Do you have any ideas? > > Directly related to foldrW, no. > > About list fusion and foldl in general, some half-baked. > > I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)" > function, semantically the identity, but tell the compiler not to share > the result of the computation. Using that in the definition of > foldl-as-foldr, one can get the same effect as Call Arity, but a bit > more reliable. I need to investigate if that solves the sumConcatInits > problem. How does that work exactly? Where do you stick the oneShot/why is it valid? > Another idea, probably with the same effect: What happens if we extend > build :: (forall b. (a -> b -> b) -> b -> b) -> [a] > to > buildI :: (forall b. (a -> b -> b) -> b -> (b -> b) -> b) -> [a] > where the extra argument is the identity, but magically „improves values > of type b“. So with > > enum = buildI $ \c n imp -> go 0 > where go i = imp $ case i of 100 -> n ; _ -> i `c` go (i+1) > > and > >foldl f a0 = foldrI (\x k a -> k (f x a)) id (\k a -> k a) a0 > > we might get good code (but this is half-baked and written as I go). It sounds a lot like the foldrW/buildW thing again, but maybe you can do better with it. > Shouldn’t this be on ghc-dev where others can join an, and people will > find it in the archives later? I prefer to reserve private mail to, > well, private matters :-) If you like. David ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: FoldrW/buildW issues
Hi, Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer: > On Sep 12, 2014 2:35 PM, "Joachim Breitner" > wrote: > > Interesting. I assumed that some wrap.unwrap=id law would hold, or > at > > least some moral approximation (e.g. disregarding bottoms in an > > acceptable manner). But if the wrappers have to do arbitrary stuff > that > > can arbitrarily interact with how the producer calls them, this > becomes > > a bit less appealing. > > No, nothing pleasant like that, I'm afraid. isoSimple is like that of > course, but once it gets to foldl, the fusion rule is handing the > builder a wrap/unwrap pair that isn't even close to that. and parametricity doesn’t help here? Note that due to the forall in the type of buildW, you can probably reason about what kind of values buildW can produce, as it can only use whatever the consumer handed to it. Maybe there is an invariant for that type, and the worker/wrapper pair is the identity for values that fulfill that invariant. > > > Do you have any ideas? > > > > Directly related to foldrW, no. > > > > About list fusion and foldl in general, some half-baked. > > > > I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)" > > function, semantically the identity, but tell the compiler not to share > > the result of the computation. Using that in the definition of > > foldl-as-foldr, one can get the same effect as Call Arity, but a bit > > more reliable. I need to investigate if that solves the sumConcatInits > > problem. > > How does that work exactly? Where do you stick the oneShot/ Quite simple, see the attached patch. I think I lost the corresponding patch to base due to the merge, but all it did was to write foldl k z xs = foldr (\v fn -> oneShot (\ z -> fn ( k z v ))) id xs z also see http://www.joachim-breitner.de/publications/CallArity-TFP.pdf §6.2. > why is it valid? Because the type of build allows the builder to use each result of the „constructor“ to be used once, and the whole result is called once, by foldl, with z as the argument. ... at least if the list is finite. If build re-uses a result, then because it builds an infinite list (e.g. in repeat x = build $ \c _ -> let r = x `c` r in r ) and I’m not quite sure if that is a problem. Probably not here, because foldl applied to an infinite list is is ⊥ anyways. But with others (e.g. scanl) I might be wrong and the oneShot trick might not work there. > > Another idea, probably with the same effect: What happens if we extend > > build :: (forall b. (a -> b -> b) -> b -> b) -> [a] > > to > > buildI :: (forall b. (a -> b -> b) -> b -> (b -> b) -> b) -> [a] > > where the extra argument is the identity, but magically „improves values > > of type b“. So with > > > > enum = buildI $ \c n imp -> go 0 > > where go i = imp $ case i of 100 -> n ; _ -> i `c` go (i+1) > > > > and > > > >foldl f a0 = foldrI (\x k a -> k (f x a)) id (\k a -> k a) a0 > > > > we might get good code (but this is half-baked and written as I go). > > It sounds a lot like the foldrW/buildW thing again, but maybe you can > do better with it. Yes, it is very much inspired by it, but possibly simpler, and much weaker: It doesn’t try to undo the continuation style of foldl, but only helps the compiler a bit. I don’t like it a lot, though. Gruß, Joachim -- Joachim Breitner e-Mail: m...@joachim-breitner.de Homepage: http://www.joachim-breitner.de Jabber-ID: nome...@joachim-breitner.de commit f70ff9094bb89d2711ddccd92251dcfa74f86002 Author: Joachim Breitner Date: Sun Jan 26 11:36:23 2014 + Add GHC.Prim.oneShot diff --git a/compiler/basicTypes/MkId.lhs b/compiler/basicTypes/MkId.lhs index 604163f..c6fcbae 100644 --- a/compiler/basicTypes/MkId.lhs +++ b/compiler/basicTypes/MkId.lhs @@ -141,7 +141,8 @@ ghcPrimIds seqId, magicDictId, coerceId, -proxyHashId +proxyHashId, +oneShotId ] \end{code} @@ -1040,7 +1041,7 @@ another gun with which to shoot yourself in the foot. \begin{code} lazyIdName, unsafeCoerceName, nullAddrName, seqName, realWorldName, voidPrimIdName, coercionTokenName, - magicDictName, coerceName, proxyName :: Name + magicDictName, coerceName, proxyName, oneShotName :: Name unsafeCoerceName = mkWiredInIdName gHC_PRIM (fsLit "unsafeCoerce#") unsafeCoerceIdKey unsafeCoerceId nullAddrName = mkWiredInIdName gHC_PRIM (fsLit "nullAddr#") nullAddrIdKey nullAddrId seqName = mkWiredInIdName gHC_PRIM (fsLit "seq") seqIdKey seqId @@ -1051,6 +1052,7 @@ coercionTokenName = mkWiredInIdName gHC_PRIM (fsLit "coercionToken#") coercionTo magicDictName = mkWiredInIdName gHC_PRIM (fsLit "magicDict") magicDictKey magicDictId coerceName= mkWiredInIdName gHC_PRIM (fsLit "coerce")coerceKey coerceId proxyName = mkWiredInIdName gHC_PRIM (fsLit "proxy#")proxyHashKey proxyHashId +oneShotName = mkWiredInId
Re: FoldrW/buildW issues
Joachim Breitner wrote: > Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer: > > On Sep 12, 2014 2:35 PM, "Joachim Breitner" > > wrote: > > > Interesting. I assumed that some wrap.unwrap=id law would hold, or > > at > > > least some moral approximation (e.g. disregarding bottoms in an > > > acceptable manner). But if the wrappers have to do arbitrary stuff > > that > > > can arbitrarily interact with how the producer calls them, this > > becomes > > > a bit less appealing. > > > > No, nothing pleasant like that, I'm afraid. isoSimple is like that of > > course, but once it gets to foldl, the fusion rule is handing the > > builder a wrap/unwrap pair that isn't even close to that. > > and parametricity doesn't help here? Note that due to the forall in the > type of buildW, you can probably reason about what kind of values buildW > can produce, as it can only use whatever the consumer handed to it. > Maybe there is an invariant for that type, and the worker/wrapper pair > is the identity for values that fulfill that invariant. > That seems reasonable, and I suspect without any proof that Takano Akio's wrapper for foldl and Dan Doel's wrapper for reverse probably satisfy it. Scans seem to be more of a challenge. It appears to me that Dan's scanl wrapper probably does *not* satisfy that requirement, and I don't know enough to have much chance of finding one that does. David ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: FoldrW/buildW issues
Which scanl wrapper are you referring to? The first one I figured out was quite wrong in certain ways. But I think the new one is less controversial; it's a lot like the reverse one. On Sun, Sep 14, 2014 at 1:03 PM, David Feuer wrote: > Joachim Breitner wrote: > >> Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer: >> > On Sep 12, 2014 2:35 PM, "Joachim Breitner" >> > wrote: >> > > Interesting. I assumed that some wrap.unwrap=id law would hold, or >> > at >> > > least some moral approximation (e.g. disregarding bottoms in an >> > > acceptable manner). But if the wrappers have to do arbitrary stuff >> > that >> > > can arbitrarily interact with how the producer calls them, this >> > becomes >> > > a bit less appealing. >> > >> > No, nothing pleasant like that, I'm afraid. isoSimple is like that of >> > course, but once it gets to foldl, the fusion rule is handing the >> > builder a wrap/unwrap pair that isn't even close to that. >> >> and parametricity doesn't help here? Note that due to the forall in the >> type of buildW, you can probably reason about what kind of values buildW >> can produce, as it can only use whatever the consumer handed to it. >> Maybe there is an invariant for that type, and the worker/wrapper pair >> is the identity for values that fulfill that invariant. >> > > That seems reasonable, and I suspect without any proof that Takano Akio's > wrapper for foldl and Dan Doel's wrapper for reverse probably satisfy it. > Scans seem to be more of a challenge. It appears to me that Dan's scanl > wrapper probably does *not* satisfy that requirement, and I don't know > enough to have much chance of finding one that does. > > David > > ___ > ghc-devs mailing list > ghc-devs@haskell.org > http://www.haskell.org/mailman/listinfo/ghc-devs > > ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: FoldrW/buildW issues
Your scanl wrapper might be right for scanl, but it does not satisfy the condition Joachim proposed. In particular, if we define (!!) :: [a] -> Int -> a xs !! n | n < 0 = error "Negative index." | otherwise = foldrW indexWrap indexCons (error "Large index.") xs n where indexCons x _ 0 = x indexCons _ r n = r (n-1) indexWrap = isoSimple then the simple test print $ (reverse $ eft 1 1000) !! 50 works just fine. If we replace isoSimple with scanlWrap isoSimple, then the test fails. That is, this produces wrap and unwrap so that wrap . unwrap is not much like the identity; it needs to interact with scanlCons in some fashion to work properly. This does not seem to be at all unusual for worker/wrapper pairs, but i believe it means we need to find a more general local correctness criterion than Joachim proposed, if I understood him correctly. David On Sun, Sep 14, 2014 at 2:08 PM, Dan Doel wrote: > Which scanl wrapper are you referring to? > > The first one I figured out was quite wrong in certain ways. But I think > the new one is less controversial; it's a lot like the reverse one. > > On Sun, Sep 14, 2014 at 1:03 PM, David Feuer > wrote: > >> Joachim Breitner wrote: >> >>> Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer: >>> > On Sep 12, 2014 2:35 PM, "Joachim Breitner" >>> > wrote: >>> > > Interesting. I assumed that some wrap.unwrap=id law would hold, or >>> > at >>> > > least some moral approximation (e.g. disregarding bottoms in an >>> > > acceptable manner). But if the wrappers have to do arbitrary stuff >>> > that >>> > > can arbitrarily interact with how the producer calls them, this >>> > becomes >>> > > a bit less appealing. >>> > >>> > No, nothing pleasant like that, I'm afraid. isoSimple is like that of >>> > course, but once it gets to foldl, the fusion rule is handing the >>> > builder a wrap/unwrap pair that isn't even close to that. >>> >>> and parametricity doesn't help here? Note that due to the forall in the >>> type of buildW, you can probably reason about what kind of values buildW >>> can produce, as it can only use whatever the consumer handed to it. >>> Maybe there is an invariant for that type, and the worker/wrapper pair >>> is the identity for values that fulfill that invariant. >>> >> >> That seems reasonable, and I suspect without any proof that Takano Akio's >> wrapper for foldl and Dan Doel's wrapper for reverse probably satisfy it. >> Scans seem to be more of a challenge. It appears to me that Dan's scanl >> wrapper probably does *not* satisfy that requirement, and I don't know >> enough to have much chance of finding one that does. >> >> David >> >> ___ >> ghc-devs mailing list >> ghc-devs@haskell.org >> http://www.haskell.org/mailman/listinfo/ghc-devs >> >> > ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: FoldrW/buildW issues
Hi, Am Sonntag, den 14.09.2014, 14:47 -0400 schrieb David Feuer: > Your scanl wrapper might be right for scanl, but it does not satisfy > the condition Joachim proposed. In particular, if we define > > (!!) :: [a] -> Int -> a > xs !! n > | n < 0 = error "Negative index." > | otherwise = foldrW indexWrap indexCons (error "Large index.") xs n > where > indexCons x _ 0 = x > indexCons _ r n = r (n-1) > indexWrap = isoSimple > > > then the simple test > > > print $ (reverse $ eft 1 1000) !! 50 > > > > works just fine. If we replace isoSimple with scanlWrap isoSimple, > then the test fails. That is, this produces wrap and unwrap so that > wrap . unwrap is not much like the identity; it needs to interact with > scanlCons in some fashion to work properly. This does not seem to be > at all unusual for worker/wrapper pairs, but i believe it means we > need to find a more general local correctness criterion than Joachim > proposed, if I understood him correctly. it would be easier to follow your discussion if you include concrete pointers to code in your mail, or include the code in question; i’m having trouble finding scanlWrap and scanlCons... (and so has Google). Anyways, the correctness criterion, if any, would relate scanlWrap with scanlCons and scanlNil; breakage due to using scanlWrap in a different consumer does not mean that we cannot find a (scanl-specific) invariant that allows us to prove fusion correct for foldrW/buidW fusion of scanl (as a consumer). Greetings, Joachim -- Joachim “nomeata” Breitner m...@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nome...@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nome...@debian.org signature.asc Description: This is a digitally signed message part ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: FoldrW/buildW issues
On Sep 12, 2014 2:35 PM, "Joachim Breitner" wrote: > I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)" > function, semantically the identity, but tell the compiler not to share > the result of the computation. Using that in the definition of > foldl-as-foldr, one can get the same effect as Call Arity, but a bit > more reliable. I need to investigate if that solves the sumConcatInits > problem. One nice thing about this idea (which sounds like it must be related to the "state hack", but is more explicit) is that it presumably applies also to similar situations in the State and ST monads, when a state transformer is only used once. Could you explain, perhaps, what compiler transformation this enables, and how you implemented it? It would be nice if the compiler could figure this out for itself, but I'm sure that's much too big a project for 7.10, whereas making sure foldl, scanl, mapAccumL, foldM, sum, etc., work really reliably seems important. And yes, I do think such a thing would probably work for scanl and such, assuming GHC's analysis can use the information properly—they're just state-transforming list producers. David ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: FoldrW/buildW issues
Hi, Am Mittwoch, den 24.09.2014, 16:37 -0400 schrieb David Feuer: > On Sep 12, 2014 2:35 PM, "Joachim Breitner" > wrote: > > I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)" > > function, semantically the identity, but tell the compiler not to > share > > the result of the computation. Using that in the definition of > > foldl-as-foldr, one can get the same effect as Call Arity, but a bit > > more reliable. I need to investigate if that solves the > sumConcatInits > > problem. > > One nice thing about this idea (which sounds like it must be related > to the "state hack", but is more explicit) is that it presumably > applies also to similar situations in the State and ST monads, when a > state transformer is only used once. Could you explain, perhaps, what > compiler transformation this enables, and how you implemented it? I guess it is used in various places, and I woudn’t know all of them. The one that I was aiming for was is this one case x of True -> z False -> \s(one-shot). e to \s(one-shot) . case x of True -> z s False -> e explained in Note [Combining case branches] at https://github.com/ghc/ghc/blob/master/compiler/coreSyn/CoreArity.lhs#L671 The implementation is attached to my previous mail. > It would be nice if the compiler could figure this out for itself, Well, that’s what I thought, and CallArity is what I came up with :-) Greetings, Joachim -- Joachim “nomeata” Breitner m...@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nome...@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nome...@debian.org signature.asc Description: This is a digitally signed message part ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
oneShot (was Re: FoldrW/buildW issues)
Just for the heck of it, I tried out an implementation of scanl using Joachim Breitner's magical oneShot primitive. Using the test scanlA :: (b -> a -> b) -> b -> [a] -> [b] scanlA f a bs = build $ \c n -> a `c` foldr (\b g x -> let b' = f x b in (b' `c` g b')) (const n) bs a scanlB :: (b -> a -> b) -> b -> [a] -> [b] scanlB f a bs = build $ \c n -> a `c` foldr (\b g -> oneShot (\x -> let b' = f x b in (b' `c` g b'))) (const n) bs a f :: Int -> Bool f 0 = True f 1 = False {-# NOINLINE f #-} barA = scanlA (+) 0 . filter f barB = foldlB (+) 0 . filter f with -O2 (NOT disabling Call Arity) the Core from barB is really, really beautiful: it's small, there are no lets or local lambdas, and everything is completely unboxed. This is much better than the result of barA, which has a local let, and which doesn't seem to manage to unbox anything. It looks to me like this could be a pretty good tool to have around. It certainly has its limits—it doesn't do anything nice with reverse . reverse or reverse . scanl f b . reverse, but it doesn't need to be perfect to be useful. More evaluation, of course, is necessary.to make sure it doesn't go wrong when used sanely. David ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: oneShot (was Re: FoldrW/buildW issues)
Wait, isn't call arity analysis meant to do this by itself now? On 7 October 2014 17:05, David Feuer wrote: > Just for the heck of it, I tried out an implementation of scanl using > Joachim Breitner's magical oneShot primitive. Using the test > > scanlA :: (b -> a -> b) -> b -> [a] -> [b] > scanlA f a bs = build $ \c n -> > a `c` > foldr (\b g x -> let b' = f x b in (b' `c` g b')) > (const n) > bs > a > > scanlB :: (b -> a -> b) -> b -> [a] -> [b] > scanlB f a bs = build $ \c n -> > a `c` > foldr (\b g -> oneShot (\x -> let b' = f x b in (b' `c` g b'))) > (const n) > bs > a > > f :: Int -> Bool > f 0 = True > f 1 = False > {-# NOINLINE f #-} > > barA = scanlA (+) 0 . filter f > barB = foldlB (+) 0 . filter f > > > with -O2 (NOT disabling Call Arity) the Core from barB is really, > really beautiful: it's small, there are no lets or local lambdas, and > everything is completely unboxed. This is much better than the result > of barA, which has a local let, and which doesn't seem to manage to > unbox anything. It looks to me like this could be a pretty good tool > to have around. It certainly has its limits—it doesn't do anything > nice with reverse . reverse or reverse . scanl f b . reverse, but it > doesn't need to be perfect to be useful. More evaluation, of course, > is necessary.to make sure it doesn't go wrong when used sanely. > > David > ___ > ghc-devs mailing list > ghc-devs@haskell.org > http://www.haskell.org/mailman/listinfo/ghc-devs > ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: oneShot (was Re: FoldrW/buildW issues)
Hi, Am Dienstag, den 07.10.2014, 03:05 -0400 schrieb David Feuer: > Just for the heck of it, I tried out an implementation of scanl using > Joachim Breitner's magical oneShot primitive. Using the test > > [..] > > with -O2 (NOT disabling Call Arity) the Core from barB is really, > really beautiful: it's small, there are no lets or local lambdas, and > everything is completely unboxed. This is much better than the result > of barA, which has a local let, and which doesn't seem to manage to > unbox anything. I cannot reproduce this here. In fact, I get identical core in both cases. Only when I do pass -fno-call-arity, A gets bad code, while B is still good. Maybe your example is too small? Greetings, Joachim -- Joachim “nomeata” Breitner m...@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nome...@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nome...@debian.org signature.asc Description: This is a digitally signed message part ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Re: oneShot (was Re: FoldrW/buildW issues)
Yes, and it does a very good job in many cases. In other cases, it's not as good. On Tue, Oct 7, 2014 at 7:59 AM, Sophie Taylor wrote: > Wait, isn't call arity analysis meant to do this by itself now? > > On 7 October 2014 17:05, David Feuer wrote: >> >> Just for the heck of it, I tried out an implementation of scanl using >> Joachim Breitner's magical oneShot primitive. Using the test >> >> scanlA :: (b -> a -> b) -> b -> [a] -> [b] >> scanlA f a bs = build $ \c n -> >> a `c` >> foldr (\b g x -> let b' = f x b in (b' `c` g b')) >> (const n) >> bs >> a >> >> scanlB :: (b -> a -> b) -> b -> [a] -> [b] >> scanlB f a bs = build $ \c n -> >> a `c` >> foldr (\b g -> oneShot (\x -> let b' = f x b in (b' `c` g b'))) >> (const n) >> bs >> a >> >> f :: Int -> Bool >> f 0 = True >> f 1 = False >> {-# NOINLINE f #-} >> >> barA = scanlA (+) 0 . filter f >> barB = foldlB (+) 0 . filter f >> >> >> with -O2 (NOT disabling Call Arity) the Core from barB is really, >> really beautiful: it's small, there are no lets or local lambdas, and >> everything is completely unboxed. This is much better than the result >> of barA, which has a local let, and which doesn't seem to manage to >> unbox anything. It looks to me like this could be a pretty good tool >> to have around. It certainly has its limits—it doesn't do anything >> nice with reverse . reverse or reverse . scanl f b . reverse, but it >> doesn't need to be perfect to be useful. More evaluation, of course, >> is necessary.to make sure it doesn't go wrong when used sanely. >> >> David >> ___ >> ghc-devs mailing list >> ghc-devs@haskell.org >> http://www.haskell.org/mailman/listinfo/ghc-devs > > ___ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs