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:
- We might want to see
tmp
s unfolding in$wgo
. We could work around that by givingtmp
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). - 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.