Fusing Stream Fusion's concatMap
Andrew Farmer - University of Kansas
Christian Höner zu Siederdissen - University of Vienna
Andy Gill - University of Kansas
PEPM 2014
January 21, 2014
List combinator pipelines are a common functional idiom.
sumOfEvensUpTo :: Int -> Int
sumOfEvensUpTo = foldl (+) 0 . filter even . enumFromTo 2
Fusion attempts to eliminate allocation and traversal of intermediate lists.
Shortcut (or Algebraic) Fusion systems are a popular, practical means of fusion.
Producer: combinator which produces a list
enumFromTo, repeat, replicate
Transformer: combinator which accepts a list and produces a new list
map, filter, concatMap
Consumer: combinator which accepts a list and produces a value
foldl, foldr, sum, product
Rewrite Rules: means of combining combinators
forall f g xs. map f (map g xs) = map (f . g) xs
Three popular systems:
foldr/build | unfoldr/destroy | Stream Fusion | |
Primitive Producer | build | unfoldr | stream |
Primitive Consumer | foldr | destroy | unstream |
Three popular systems:
foldr/build | unfoldr/destroy | Stream Fusion | |
Primitive Producer | build | unfoldr | stream |
Primitive Consumer | foldr | destroy | unstream |
Theoretical Limitations | zip | unzip | unzip |
Practical Limitations | foldl | filter | concatMap |
Three popular systems:
foldr/build | unfoldr/destroy | Stream Fusion | |
Primitive Producer | build | unfoldr | stream |
Primitive Consumer | foldr | destroy | unstream |
Theoretical Limitations | zip | unzip | unzip |
Practical Limitations | foldl | filter | concatMap |
A stream is a pair of generator function and state.
data Stream a where
Stream :: (s -> Step a s) -> s -> Stream a
data Step a s = Yield a s | Skip s | Done
We can convert to and from streams.
stream :: [a] -> Stream a
stream xs = Stream uncons xs
where uncons :: [a] -> Step a [a]
uncons [] = Done
uncons (x:xs) = Yield x xs
unstream :: Stream a -> [a]
unstream (Stream g s) = go s
where go s = case g s of
Done -> []
Skip s' -> go s'
Yield x s' -> x : go s'
List combinators are defined in terms of their stream counterparts.
map :: (a -> b) -> [a] -> [b]
map f = unstream . mapS f . stream
mapS :: (a -> b) -> Stream a -> Stream b
mapS f (Stream g s0) = Stream mapStep s0
where mapStep s = case g s of
Done -> Done
Skip s' -> Skip s'
Yield x s' -> Yield (f x) s'
Two traversals via map
are now fused into one by the compiler, automatically.
map f . map g
Unfold map
.
unstream . mapS f . stream . unstream . mapS g . stream
Recall that stream . unstream = id
unstream . mapS f . mapS g . stream
Inline everything, including the generator functions.
let go [] = []
go (x:xs) = f (g x) : go xs
in go
concatMap
permits nested list computations.
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = unstream . concatMapS (stream . f) . stream
concatMapS :: (a -> Stream b) -> Stream a -> Stream b
concatMapS f (Stream g s) = Stream g' (s, Nothing)
where
g' (s, Nothing) =
case g s of
Done -> Done
Skip s' -> Skip (s', Nothing)
Yield x s' -> Skip (s', Just (f x))
g' (s, Just (Stream g'' s'')) =
case g'' s'' of
Done -> Skip (s, Nothing)
Skip s' -> Skip (s, Just (Stream g'' s'))
Yield x s' -> Yield x (s, Just (Stream g'' s'))
Imagine the following pipeline.
foo :: Int -> Int
foo = foldl (+) 0 . concatMap (enumFromTo 1) . enumFromTo 1
-- foo 3 = sum [1,1,2,1,2,3]
Call-pattern specialization results in two mutually recursive functions.
go1 acc s = ... go2 acc s' g'' s'' ...
go2 acc s g'' s'' = case g'' s'' of
Done -> go1 acc s
Skip s' -> go2 acc s g'' s'
Yield x s' -> go2 (acc+x) s g'' s'
GHC cannot inline g''
due to it being lambda bound.
The definition of g''
is known statically, but in the wrong place!
Stream Fusion provides a concatMap
alternative which is readily fused.
flatten :: (a -> s) -> (s -> Step b s) -> Stream a -> Stream b
Breaks abstraction (must write hand-fused inner loop!)
Must be performance expert (see Section 6.3 in paper)
Coutts proposed the following rewrite.
forall g s. concatMapS (\x -> Stream g s) = flatten (\x -> s) g
The value of the outer stream (x
) cannot be free in g
.
Instead, we implement the following rewrite.
forall g s. concatMapS (\x -> Stream g s)
=
flatten (\x -> (x,s)) (\(x,s) -> fixStep x (g s))
fixStep :: a -> Step b s -> Step b (a, s)
fixStep _ Done = Done
fixStep a (Skip s) = Skip (a,s)
fixStep a (Yield b s) = Yield b (a,s)
This cannot be expressed as a GHC RULE.
Describes a modified transformation with fewer restrictions, and extends it to monadic streams.
Provides an implementation as a custom GHC optimization plugin using HERMIT, and details simplification steps necessary to enable the transformation in practice.
Gives novel translation scheme for list comprehensions to combinators which can be fused by Stream Fusion.
Applies modified Stream Fusion system to nofib suite, demonstrating its advantage over foldr/build in list-heavy code.
Demonstrates how modified system simplifies implementation of ADPfusion library, which is used to implement CYK-style parsers, with no loss of performance.
Toolkit for transforming GHC's Core Language.
Implemented as a GHC Core-to-Core Plugin.
Goal: Perform Equational Reasoning on real Haskell programs!
cabal update
cabal install hermit
hermit Main.hs
forall g s. concatMapS (\x -> Stream g s)
=
flatten (\x -> (x,s)) (\(x,s) -> fixStep x (g s))
Algorithm:
Perform dead-let elimination, case reduction, β-reduction, non-work-duplicating let substitution, and unfold composition (.
), application ($
), and the identity function.
Once, in a top-down manner:
stream
/unstream
rule.
Details in the paper!
A list comprehension is a body and a series of clauses.
Haskell 98 Desugaring:
Generator - concatMap
Guard - case expression
Let Binding - let expression
Parallel Comprehension - zip
Body - singleton list
Consider:
[ e | x <- xs, even x ]
This desugars to:
concatMap (\x -> case even x of
True -> [e]
False -> []) xs
unstream (concatMapS (\x -> case even x of
True -> Stream g s
False -> Stream g' s') (stream xs))
Branches cannot be merged!
[ e | x <- xs, even x ]
We instead desugar to filter
:
concatMap (\x -> [e]) (filter even xs)
unstream (concatMapS (\x -> Stream g s) (filterS even (stream xs)))
Invariant: Guards always preceeded by generator.
[ e | x <- xs, g, qs ] ==> [ e | x <- filter (\x -> g) xs, qs ]
When not present, add a unit generator.
[ e | g, qs ] ==> [ e | () <- [()], g, qs ]
concatMap (\() -> <<[ e | qs ]>>) (filter (\() -> g) [()])
(Similar issue for failing pattern matches. See the paper!)
Library for writing CYK-style parsers.
Uses Stream Fusion to deliver efficient code.
Previously made extensive use of flatten
.
Using concatMap
instead simplifies the implementation with no loss of performance.
Lots of little details involved in optimizing concatMap
.
Motivates a richer rewrite capability for GHC.
Work still necessary for an "always on" system.
Paper: http://www.ittc.ku.edu/~afarmer/concatmap-pepm14.pdf
These Slides: http://www.ittc.ku.edu/~afarmer/talks/concatmap-pepm14.html