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)
Oh, I see now. If it doesn't fuse, it performs extra operations, because we want foldr1 rather than foldr, and foldr1 is not so nice for fusion. Whoops! That's no good! But we should take better advantage of the NOINLINE here with a few more rules. In particular, we *know* that && and || are tiny little functions, so we can inline them to our hearts' content: "and/cons" forall x y . and (x:xs) = x && and xs "or/cons" forall x y . or (x:xs) = x || or xs
On Tue, Aug 19, 2014 at 2:34 AM, David Feuer
Oh, I see now. If it doesn't fuse, it performs extra operations, because we want foldr1 rather than foldr, and foldr1 is not so nice for fusion. Whoops! That's no good! But we should take better advantage of the NOINLINE here with a few more rules. In particular, we *know* that && and || are tiny little functions, so we can inline them to our hearts' content:
"and/cons" forall x y . and (x:xs) = x && and xs "or/cons" forall x y . or (x:xs) = x || or xs
Aaaaand that's not quite right, for the same reason, and wrong names. What we need is probably: "and/cons" forall x1 x2 xs . and (x1:x2:xs) = x1 && and (x2:xs) "and/single" forall x . and [x] = x "or/cons" forall x1 x2 xs . or (x1:x2:xs) = x1 || or (x2:xs) "or/single" forall x . or [x] = x
On Mon, Aug 18, 2014 at 11:34 PM, David Feuer
"and/cons" forall x y . and (x:xs) = x && and xs "or/cons" forall x y . or (x:xs) = x || or xs
&& and || may be tiny, but inlining them a few hundred or thousand times in one place gets big. In general, open ended RULES like this can lead to a code explosion, strings turn into really long lists that if one of these RULES gets ahold of it it will turn your constant string into a huge amount of code even if they are just inlinings of && and ||. If the RULES are just restating the branches of the function, then the compiler already has that information at its disposal to decide whether to inline. A better idea is a worker wrapper split, where the wrapper pulls of a single argument (for when you know the list has at least one entry) and the worker takes the extra argument and can be written in a very fusible way and code expansion potential is capped. John -- John Meacham - http://notanumber.net/
On Tue, Aug 19, 2014 at 2:48 AM, John Meacham
A better idea is a worker wrapper split, where the wrapper pulls of a single argument (for when you know the list has at least one entry) and the worker takes the extra argument and can be written in a very fusible way and code expansion potential is capped.
I'm not sure I quite get what you mean there. Something like this? forall x1 xs . and (x1 : xs) = foldr (&&) x1 xs forall x1 . and [x1] = x1
| 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? I think it'd be fine to use foldr. Rewriting back to and/or is probably good when fusion doesn't happen, to avoid duplicating the loop at every call site. | Oh, I see now. If it doesn't fuse, it performs extra operations, | because we want foldr1 rather than foldr, and foldr1 is not so nice for | fusion. I don't understand that at all. I see no foldr1 in the current impl of and/or. Simon
On Tue, Aug 19, 2014 at 3:07 AM, Simon Peyton Jones
| Oh, I see now. If it doesn't fuse, it performs extra operations, | because we want foldr1 rather than foldr, and foldr1 is not so nice for | fusion.
I don't understand that at all. I see no foldr1 in the current impl of and/or.
That's because it's not there. I imagined it entirely. Sorry.
participants (3)
-
David Feuer -
John Meacham -
Simon Peyton Jones