The HERMIT in the Stream

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

Introduction

Terminology

Shorcut Fusion

Three popular systems:

  foldr/build unfoldr/destroy Stream Fusion
Primitive Producer build unfoldr stream
Primitive Consumer foldr destroy unstream

Shorcut Fusion

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

Shorcut Fusion

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

Why does concatMap matter?

concatMap micro-benchmarks

Stream Fusion

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'

Stream Fusion

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'

Stream Fusion

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

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'))

Optimizing concatMap

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!

Rewriting concatMap to flatten

Stream Fusion provides a concatMap alternative which is readily fused.

flatten :: (a -> s) -> (s -> Step b s) -> Stream a -> Stream b

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.

Rewriting concatMap to flatten

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.

The Paper

HERMIT

cabal update
cabal install hermit
hermit Main.hs
image from http://www.angelfire.com/ks/larrycarter/LC/OldGuardCameron.html

Simplification

forall g s. concatMapS (\x -> Stream g s)
            =
            flatten (\x -> (x,s)) (\(x,s) -> fixStep x (g s))

Algorithm:

  1. Perform dead-let elimination, case reduction, β-reduction, non-work-duplicating let substitution, and unfold composition (.), application ($), and the identity function.

  2. Once, in a top-down manner:

    1. Apply the stream/unstream rule.
    2. Float a let inwards.
    3. Eliminate a case.
    4. Reduce a case on an inner stream.
    5. Float a case inwards.
  3. Unfold an application.

Details in the paper!

Desugaring

A list comprehension is a body and a series of clauses.

Haskell 98 Desugaring:

Desugaring - Branching

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!

Desugaring - Branching

[ 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!)

Performance - nofib

nofib benchmarks

ADPfusion

adpfusion benchmarks

Conclusion



Paper: http://www.ittc.ku.edu/~afarmer/concatmap-pepm14.pdf

These Slides: http://www.ittc.ku.edu/~afarmer/talks/concatmap-pepm14.html

Code: https://github.com/ku-fpg/hermit-streamfusion