Skip to content

Cheapness Worker/Wrapper to support eta expansion

I'm currently going through the Call Arity paper (once again). The prime motivator is

e5'1 :: (Int -> Bool) -> Int
e5'1 f = sum (filter f [42..2014::Int])

= { Simplification, rewriting and inlining of `foldl (+) 0` }

e5'1 :: (Int -> Bool) -> Int
e5'1 f =
  let go x =
        let r = if x == 2014 then id else go (x+1) in
        if f x then \a -> r (a + x) else r
  in go 42 0

At which point Call Arity allows us to eta-expand r and go.

Here is an idea how to achieve the same without Call Arity, with a new, rather syntactical, transformation I call "cheapness Worker/Wrapper" (maybe we could do it as part of mkWWargs? Not sure). Specifically, a prior analysis pass like arity analysis spots that the expression f x is "in the way": It is not cheap and will prohibit go from eta-expanding. (Note that x == 2014 in r is cheap and I think if it wasn't for f x, arity analysis would already eta-expand go.) It marks that expression in some way and extracts a new let-binding:

e5'1 :: (Int -> Bool) -> Int
e5'1 f =
  let go x =
        let tmp = f x in
        let r = if x == 2014 then id else go (x+1) in
        if tmp then \a -> r (a + x) else r
  in go 42 0

Nothing interesting so far. But now we do a worker/wrapper transformation where we push tmp into the wrapper (Not doing strictness and CPR for clarity):

e5'1 :: (Int -> Bool) -> Int
e5'1 f =
  let 
      go = \x -> let tmp = f x in \a -> $wgo x tmp a
      $wgo x tmp a =
        let r y = if x == 2014 then y else go (x+1) y in
        if tmp then r (a + x) else r a
  in go 42 0

And then the wrapper can inline at call sites with the appropriate arity.

Problems with this approach:

  1. We might want to see tmps unfolding in $wgo. We could work around that by giving tmp a lambda-bound unfolding in $wgo, I believe. Otherwise, it would be good to specialise the call pattern $wgo x tmp a (but then we might just inline it as well).
  2. We duplicate f x to all call sites. In general, f could be a huge expression <expr>. Yuck, probably a deal-breaker. But maybe not: We could float out and bind <expr> outside the wrapper.
Edited by Sebastian Graf
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information