CoreArity.hs 35.5 KB
 Austin Seipp committed Dec 03, 2014 1 2 3 4 {- (c) The University of Glasgow 2006 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998  simonpj@microsoft.com committed Jan 13, 2009 5   Simon Peyton Jones committed Sep 26, 2014 6  Arity and eta expansion  Austin Seipp committed Dec 03, 2014 7 -}  simonpj@microsoft.com committed Jan 13, 2009 8   Herbert Valerio Riedel committed May 15, 2014 9 {-# LANGUAGE CPP #-}  Simon Peyton Jones committed Sep 26, 2014 10 11  -- | Arity and eta expansion  simonpj@microsoft.com committed Jan 13, 2009 12 module CoreArity (  Simon Peyton Jones committed Sep 26, 2014 13 14  manifestArity, exprArity, typeArity, exprBotStrictness_maybe, exprEtaExpandArity, findRhsArity, CheapFun, etaExpand  simonpj@microsoft.com committed Jan 13, 2009 15 16 17 18 19 20 21  ) where #include "HsVersions.h" import CoreSyn import CoreFVs import CoreUtils  simonpj@microsoft.com committed Dec 24, 2009 22 import CoreSubst  simonpj@microsoft.com committed Nov 19, 2009 23 import Demand  simonpj@microsoft.com committed Jan 13, 2009 24 25 26 27 import Var import VarEnv import Id import Type  Simon Peyton Jones committed Sep 26, 2014 28 import TyCon ( initRecTc, checkRecTc )  simonpj@microsoft.com committed Jan 13, 2009 29 30 31 import Coercion import BasicTypes import Unique  ian@well-typed.com committed Oct 16, 2012 32 import DynFlags ( DynFlags, GeneralFlag(..), gopt )  simonpj@microsoft.com committed Jan 13, 2009 33 34 import Outputable import FastString  35 import Pair  Simon Peyton Jones committed Nov 12, 2013 36 import Util ( debugIsOn )  simonpj@microsoft.com committed Jan 13, 2009 37   Austin Seipp committed Dec 03, 2014 38 39 40 {- ************************************************************************ * *  simonpj@microsoft.com committed Jan 13, 2009 41  manifestArity and exprArity  Austin Seipp committed Dec 03, 2014 42 43 * * ************************************************************************  simonpj@microsoft.com committed Jan 13, 2009 44 45 46 47 48 49  exprArity is a cheap-and-cheerful version of exprEtaExpandArity. It tells how many things the expression can be applied to before doing any work. It doesn't look inside cases, lets, etc. The idea is that exprEtaExpandArity will do the hard work, leaving something that's easy for exprArity to grapple with. In particular, Simplify uses exprArity to  Simon Peyton Jones committed Sep 26, 2014 50 compute the ArityInfo for the Id.  simonpj@microsoft.com committed Jan 13, 2009 51 52 53 54  Originally I thought that it was enough just to look for top-level lambdas, but it isn't. I've seen this  Simon Peyton Jones committed Sep 26, 2014 55  foo = PrelBase.timesInt  simonpj@microsoft.com committed Jan 13, 2009 56 57 58  We want foo to get arity 2 even though the eta-expander will leave it unchanged, in the expectation that it'll be inlined. But occasionally it  Simon Peyton Jones committed Sep 26, 2014 59 isn't, because foo is blacklisted (used in a rule).  simonpj@microsoft.com committed Jan 13, 2009 60   Simon Peyton Jones committed Sep 26, 2014 61 62 Similarly, see the ok_note check in exprEtaExpandArity. So f = __inline_me (\x -> e)  simonpj@microsoft.com committed Jan 13, 2009 63 64 65 won't be eta-expanded. And in any case it seems more robust to have exprArity be a bit more intelligent.  Simon Peyton Jones committed Sep 26, 2014 66 But note that (\x y z -> f x y z)  simonpj@microsoft.com committed Jan 13, 2009 67 should have arity 3, regardless of f's arity.  Austin Seipp committed Dec 03, 2014 68 -}  simonpj@microsoft.com committed Jan 13, 2009 69 70  manifestArity :: CoreExpr -> Arity  Simon Peyton Jones committed Apr 24, 2014 71 72 -- ^ manifestArity sees how many leading value lambdas there are, -- after looking through casts  Simon Peyton Jones committed Sep 26, 2014 73 74 manifestArity (Lam v e) | isId v = 1 + manifestArity e | otherwise = manifestArity e  Simon Marlow committed Nov 02, 2011 75 manifestArity (Tick t e) | not (tickishIsCode t) = manifestArity e  Simon Peyton Jones committed Sep 26, 2014 76 77 manifestArity (Cast e _) = manifestArity e manifestArity _ = 0  simonpj@microsoft.com committed Jan 13, 2009 78   simonpj@microsoft.com committed Sep 24, 2010 79 ---------------  simonpj@microsoft.com committed Jan 13, 2009 80 81 82 83 exprArity :: CoreExpr -> Arity -- ^ An approximate, fast, version of 'exprEtaExpandArity' exprArity e = go e where  Simon Peyton Jones committed Sep 26, 2014 84 85 86  go (Var v) = idArity v go (Lam x e) | isId x = go e + 1 | otherwise = go e  Simon Marlow committed Nov 02, 2011 87  go (Tick t e) | not (tickishIsCode t) = go e  Simon Peyton Jones committed Jun 06, 2013 88  go (Cast e co) = trim_arity (go e) (pSnd (coercionKind co))  89  -- Note [exprArity invariant]  simonpj@microsoft.com committed Dec 24, 2009 90 91 92  go (App e (Type _)) = go e go (App f a) | exprIsTrivial a = (go f - 1) max 0 -- See Note [exprArity for applications]  Simon Peyton Jones committed Sep 26, 2014 93  -- NB: coercions count as a value argument  94   Simon Peyton Jones committed Sep 26, 2014 95  go _ = 0  simonpj@microsoft.com committed Aug 13, 2010 96   Simon Peyton Jones committed Jun 06, 2013 97 98  trim_arity :: Arity -> Type -> Arity trim_arity arity ty = arity min length (typeArity ty)  simonpj@microsoft.com committed Aug 13, 2010 99   simonpj@microsoft.com committed Sep 24, 2010 100 ---------------  Simon Peyton Jones committed Dec 12, 2013 101 typeArity :: Type -> [OneShotInfo]  simonpj@microsoft.com committed Aug 13, 2010 102 103 104 -- How many value arrows are visible in the type? -- We look through foralls, and newtypes -- See Note [exprArity invariant]  Simon Peyton Jones committed Sep 26, 2014 105 typeArity ty  Simon Peyton Jones committed Jun 06, 2013 106 107  = go initRecTc ty where  Simon Peyton Jones committed Sep 26, 2014 108  go rec_nts ty  eir@cis.upenn.edu committed Dec 11, 2015 109 110 111 112  | Just (bndr, ty') <- splitPiTy_maybe ty = if isIdLikeBinder bndr then typeOneShot (binderType bndr) : go rec_nts ty' else go rec_nts ty'  Simon Peyton Jones committed Apr 22, 2015 113   Simon Peyton Jones committed Sep 26, 2014 114  | Just (tc,tys) <- splitTyConApp_maybe ty  Simon Peyton Jones committed Jun 06, 2013 115 116 117  , Just (ty', _) <- instNewTyCon_maybe tc tys , Just rec_nts' <- checkRecTc rec_nts tc -- See Note [Expanding newtypes] -- in TyCon  Simon Peyton Jones committed Sep 26, 2014 118 119 -- , not (isClassTyCon tc) -- Do not eta-expand through newtype classes -- -- See Note [Newtype classes and eta expansion]  Simon Peyton Jones committed Jun 06, 2013 120 121 -- (no longer required) = go rec_nts' ty'  Simon Peyton Jones committed Sep 26, 2014 122 123 124  -- Important to look through non-recursive newtypes, so that, eg -- (f x) where f has arity 2, f :: Int -> IO () -- Here we want to get arity 1 for the result!  Simon Peyton Jones committed Jun 06, 2013 125 126 127  -- -- AND through a layer of recursive newtypes -- e.g. newtype Stream m a b = Stream (m (Either b (a, Stream m a b)))  simonpj@microsoft.com committed Aug 13, 2010 128   Simon Peyton Jones committed Jun 06, 2013 129 130  | otherwise = []  simonpj@microsoft.com committed Sep 24, 2010 131 132 133 134 135 136 137  --------------- exprBotStrictness_maybe :: CoreExpr -> Maybe (Arity, StrictSig) -- A cheap and cheerful function that identifies bottoming functions -- and gives them a suitable strictness signatures. It's used during -- float-out exprBotStrictness_maybe e  Simon Peyton Jones committed Nov 16, 2011 138  = case getBotArity (arityType env e) of  Simon Peyton Jones committed Sep 26, 2014 139 140  Nothing -> Nothing Just ar -> Just (ar, sig ar)  simonpj@microsoft.com committed Dec 21, 2010 141  where  Joachim Breitner committed Feb 17, 2014 142  env = AE { ae_ped_bot = True, ae_cheap_fn = \ _ _ -> False }  Joachim Breitner committed Dec 09, 2013 143  sig ar = mkClosedStrictSig (replicate ar topDmd) botRes  Simon Peyton Jones committed Nov 16, 2011 144  -- For this purpose we can be very simple  simonpj@microsoft.com committed Jan 13, 2009 145   Austin Seipp committed Dec 03, 2014 146 {-  simonpj@microsoft.com committed Sep 24, 2010 147 148 149 150 Note [exprArity invariant] ~~~~~~~~~~~~~~~~~~~~~~~~~~ exprArity has the following invariant:  Simon Peyton Jones committed Nov 09, 2011 151 152  (1) If typeArity (exprType e) = n, then manifestArity (etaExpand e n) = n  Simon Peyton Jones committed Sep 26, 2014 153   Simon Peyton Jones committed Nov 09, 2011 154 155  That is, etaExpand can always expand as much as typeArity says So the case analysis in etaExpand and in typeArity must match  Simon Peyton Jones committed Sep 26, 2014 156 157  (2) exprArity e <= typeArity (exprType e)  simonpj@microsoft.com committed Sep 24, 2010 158   Simon Peyton Jones committed Nov 09, 2011 159  (3) Hence if (exprArity e) = n, then manifestArity (etaExpand e n) = n  simonpj@microsoft.com committed Sep 24, 2010 160   Simon Peyton Jones committed Sep 26, 2014 161  That is, if exprArity says "the arity is n" then etaExpand really  Simon Peyton Jones committed Nov 09, 2011 162  can get "n" manifest lambdas to the top.  simonpj@microsoft.com committed Sep 24, 2010 163   Simon Peyton Jones committed Sep 26, 2014 164 165 Why is this important? Because - In TidyPgm we use exprArity to fix the *final arity* of  simonpj@microsoft.com committed Sep 24, 2010 166 167 168 169 170 171 172 173 174  each top-level Id, and in - In CorePrep we use etaExpand on each rhs, so that the visible lambdas actually match that arity, which in turn means that the StgRhs has the right number of lambdas An alternative would be to do the eta-expansion in TidyPgm, at least for top-level bindings, in which case we would not need the trim_arity in exprArity. That is a less local change, so I'm going to leave it for today!  simonpj@microsoft.com committed Aug 13, 2010 175 176 Note [Newtype classes and eta expansion] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  Gabor Greif committed Oct 08, 2013 177  NB: this nasty special case is no longer required, because  Simon Peyton Jones committed Jun 06, 2013 178 179 180 181  for newtype classes we don't use the class-op rule mechanism at all. See Note [Single-method classes] in TcInstDcls. SLPJ May 2013 -------- Old out of date comments, just for interest -----------  simonpj@microsoft.com committed Aug 13, 2010 182 We have to be careful when eta-expanding through newtypes. In general  Simon Peyton Jones committed Sep 26, 2014 183 it's a good idea, but annoyingly it interacts badly with the class-op  simonpj@microsoft.com committed Aug 13, 2010 184 rule mechanism. Consider  Simon Peyton Jones committed Sep 26, 2014 185   simonpj@microsoft.com committed Aug 13, 2010 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202  class C a where { op :: a -> a } instance C b => C [b] where op x = ... These translate to co :: forall a. (a->a) ~ C a $copList :: C b -> [b] -> [b]$copList d x = ... $dfList :: C b -> C [b] {-# DFunUnfolding = [$copList] #-} $dfList d =$copList d |> co@[b] Now suppose we have:  Simon Peyton Jones committed Sep 26, 2014 203  dCInt :: C Int  simonpj@microsoft.com committed Aug 13, 2010 204 205 206 207 208 209 210 211 212 213 214 215  blah :: [Int] -> [Int] blah = op ($dfList dCInt) Now we want the built-in op/$dfList rule will fire to give blah = $copList dCInt But with eta-expansion 'blah' might (and in Trac #3772, which is slightly more complicated, does) turn into blah = op (\eta. ($dfList dCInt |> sym co) eta)  Gabor Greif committed Jan 30, 2013 216 and now it is *much* harder for the op/$dfList rule to fire, because  simonpj@microsoft.com committed Aug 13, 2010 217 218 219 220 exprIsConApp_maybe won't hold of the argument to op. I considered trying to *make* it hold, but it's tricky and I gave up. The test simplCore/should_compile/T3722 is an excellent example.  Simon Peyton Jones committed Jun 06, 2013 221 -------- End of old out of date comments, just for interest -----------  simonpj@microsoft.com committed Aug 13, 2010 222 223   simonpj@microsoft.com committed Dec 24, 2009 224 225 226 Note [exprArity for applications] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When we come to an application we check that the arg is trivial.  Simon Peyton Jones committed Sep 26, 2014 227  eg f (fac x) does not have arity 2,  simonpj@microsoft.com committed Dec 24, 2009 228 229 230 231 232 233 234 235 236 237 238 239 240  even if f has arity 3! * We require that is trivial rather merely cheap. Suppose f has arity 2. Then f (Just y) has arity 0, because if we gave it arity 1 and then inlined f we'd get let v = Just y in \w. which has arity 0. And we try to maintain the invariant that we don't have arity decreases. * The max 0 is important! (\x y -> f x) has arity 2, even if f is unknown, hence arity 0  Austin Seipp committed Dec 03, 2014 241 242 ************************************************************************ * *  Simon Peyton Jones committed Sep 26, 2014 243  Computing the "arity" of an expression  Austin Seipp committed Dec 03, 2014 244 245 * * ************************************************************************  simonpj@microsoft.com committed Jan 13, 2009 246   simonpj@microsoft.com committed Apr 03, 2009 247 248 249 250 251 Note [Definition of arity] ~~~~~~~~~~~~~~~~~~~~~~~~~~ The "arity" of an expression 'e' is n if applying 'e' to *fewer* than n *value* arguments converges rapidly  simonpj@microsoft.com committed Jan 13, 2009 252   simonpj@microsoft.com committed Apr 03, 2009 253 Or, to put it another way  simonpj@microsoft.com committed Jan 13, 2009 254   simonpj@microsoft.com committed Apr 03, 2009 255 256  there is no work lost in duplicating the partial application (e x1 .. x(n-1))  simonpj@microsoft.com committed Jan 13, 2009 257   simonpj@microsoft.com committed Apr 03, 2009 258 259 In the divegent case, no work is lost by duplicating because if the thing is evaluated once, that's the end of the program.  simonpj@microsoft.com committed Jan 13, 2009 260   simonpj@microsoft.com committed Apr 03, 2009 261 Or, to put it another way, in any context C  simonpj@microsoft.com committed Jan 13, 2009 262   simonpj@microsoft.com committed Apr 03, 2009 263 264 265  C[ (\x1 .. xn. e x1 .. xn) ] is as efficient as C[ e ]  simonpj@microsoft.com committed Jan 13, 2009 266   simonpj@microsoft.com committed Apr 03, 2009 267 It's all a bit more subtle than it looks:  simonpj@microsoft.com committed Jan 13, 2009 268   Simon Peyton Jones committed Nov 11, 2011 269 270 271 Note [One-shot lambdas] ~~~~~~~~~~~~~~~~~~~~~~~ Consider one-shot lambdas  Simon Peyton Jones committed Sep 26, 2014 272  let x = expensive in \y z -> E  Simon Peyton Jones committed Nov 11, 2011 273 274 275 276 277 278 279 280 281 282 283 284 285 We want this to have arity 1 if the \y-abstraction is a 1-shot lambda. Note [Dealing with bottom] ~~~~~~~~~~~~~~~~~~~~~~~~~~ A Big Deal with computing arities is expressions like f = \x -> case x of True -> \s -> e1 False -> \s -> e2 This happens all the time when f :: Bool -> IO () In this case we do eta-expand, in order to get that \s to the top, and give f arity 2.  simonpj@microsoft.com committed Jan 13, 2009 286   simonpj@microsoft.com committed Apr 03, 2009 287 This isn't really right in the presence of seq. Consider  Simon Peyton Jones committed Sep 26, 2014 288  (f bot) seq 1  simonpj@microsoft.com committed Jan 13, 2009 289   Simon Peyton Jones committed Nov 11, 2011 290 This should diverge! But if we eta-expand, it won't. We ignore this  Simon Peyton Jones committed Nov 16, 2011 291 "problem" (unless -fpedantic-bottoms is on), because being scrupulous  Simon Peyton Jones committed Sep 26, 2014 292 would lose an important transformation for many programs. (See  Simon Peyton Jones committed Nov 16, 2011 293 Trac #5587 for an example.)  simonpj@microsoft.com committed Jan 13, 2009 294   Simon Peyton Jones committed Nov 11, 2011 295 Consider also  Simon Peyton Jones committed Sep 26, 2014 296  f = \x -> error "foo"  simonpj@microsoft.com committed Apr 03, 2009 297 Here, arity 1 is fine. But if it is  Simon Peyton Jones committed Sep 26, 2014 298 299 300  f = \x -> case x of True -> error "foo" False -> \y -> x+y  simonpj@microsoft.com committed Apr 03, 2009 301 then we want to get arity 2. Technically, this isn't quite right, because  Simon Peyton Jones committed Sep 26, 2014 302  (f True) seq 1  simonpj@microsoft.com committed Apr 03, 2009 303 304 305 306 should diverge, but it'll converge if we eta-expand f. Nevertheless, we do so; it improves some programs significantly, and increasing convergence isn't a bad thing. Hence the ABot/ATop in ArityType.  Simon Peyton Jones committed Nov 11, 2011 307 308 309 So these two transformations aren't always the Right Thing, and we have several tickets reporting unexpected bahaviour resulting from this transformation. So we try to limit it as much as possible:  Simon Peyton Jones committed Oct 21, 2011 310   Simon Peyton Jones committed Nov 11, 2011 311 312 313  (1) Do NOT move a lambda outside a known-bottom case expression case undefined of { (a,b) -> \y -> e } This showed up in Trac #5557  Simon Peyton Jones committed Oct 21, 2011 314   Simon Peyton Jones committed Sep 26, 2014 315  (2) Do NOT move a lambda outside a case if all the branches of  Simon Peyton Jones committed Nov 11, 2011 316 317  the case are known to return bottom. case x of { (a,b) -> \y -> error "urk" }  Simon Peyton Jones committed Sep 26, 2014 318 319  This case is less important, but the idea is that if the fn is going to diverge eventually anyway then getting the best arity  Simon Peyton Jones committed Nov 11, 2011 320  isn't an issue, so we might as well play safe  Simon Peyton Jones committed Oct 21, 2011 321   Simon Peyton Jones committed Mar 11, 2014 322  (3) Do NOT move a lambda outside a case unless  Simon Peyton Jones committed Nov 11, 2011 323  (a) The scrutinee is ok-for-speculation, or  Simon Peyton Jones committed Mar 11, 2014 324 325  (b) more liberally: the scrutinee is cheap (e.g. a variable), and -fpedantic-bottoms is not enforced (see Trac #2915 for an example)  Simon Peyton Jones committed Nov 11, 2011 326 327  Of course both (1) and (2) are readily defeated by disguising the bottoms.  Simon Peyton Jones committed Oct 21, 2011 328   simonpj@microsoft.com committed Apr 03, 2009 329 330 4. Note [Newtype arity] ~~~~~~~~~~~~~~~~~~~~~~~~  simonpj@microsoft.com committed Jan 13, 2009 331 332 333 Non-recursive newtypes are transparent, and should not get in the way. We do (currently) eta-expand recursive newtypes too. So if we have, say  Simon Peyton Jones committed Sep 26, 2014 334  newtype T = MkT ([T] -> Int)  simonpj@microsoft.com committed Jan 13, 2009 335 336  Suppose we have  Simon Peyton Jones committed Sep 26, 2014 337 338  e = coerce T f where f has arity 1. Then: etaExpandArity e = 1;  simonpj@microsoft.com committed Jan 13, 2009 339 340 341 that is, etaExpandArity looks through the coerce. When we eta-expand e to arity 1: eta_expand 1 e T  Simon Peyton Jones committed Sep 26, 2014 342 we want to get: coerce T (\x::[T] -> (coerce ([T]->Int) e) x)  simonpj@microsoft.com committed Jan 13, 2009 343   simonpj@microsoft.com committed Apr 03, 2009 344  HOWEVER, note that if you use coerce bogusly you can ge  Simon Peyton Jones committed Sep 26, 2014 345  coerce Int negate  simonpj@microsoft.com committed Apr 03, 2009 346 347  And since negate has arity 2, you might try to eta expand. But you can't decopose Int to a function type. Hence the final case in eta_expand.  Simon Peyton Jones committed Sep 26, 2014 348   simonpj@microsoft.com committed Dec 24, 2009 349 350 Note [The state-transformer hack] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  Simon Peyton Jones committed Sep 26, 2014 351 352 Suppose we have f = e  simonpj@microsoft.com committed Dec 24, 2009 353 354 where e has arity n. Then, if we know from the context that f has a usage type like  Simon Peyton Jones committed Sep 26, 2014 355  t1 -> ... -> tn -1-> t(n+1) -1-> ... -1-> tm -> ...  simonpj@microsoft.com committed Dec 24, 2009 356 357 then we can expand the arity to m. This usage type says that any application (x e1 .. en) will be applied to uniquely to (m-n) more args  Simon Peyton Jones committed Sep 26, 2014 358 359 360 361 Consider f = \x. let y = in case x of True -> foo False -> \(s:RealWorld) -> e  simonpj@microsoft.com committed Dec 24, 2009 362 363 364 365 366 367 368 where foo has arity 1. Then we want the state hack to apply to foo too, so we can eta expand the case. Then we expect that if f is applied to one arg, it'll be applied to two (that's the hack -- we don't really know, and sometimes it's false) See also Id.isOneShotBndr.  simonpj@microsoft.com committed Apr 03, 2009 369 370 371 372 373 374 375 376 377 Note [State hack and bottoming functions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ It's a terrible idea to use the state hack on a bottoming function. Here's what happens (Trac #2861): f :: String -> IO T f = \p. error "..." Eta-expand, using the state hack:  simonpj@microsoft.com committed Jan 13, 2009 378   simonpj@microsoft.com committed Apr 03, 2009 379 380 381  f = \p. (\s. ((error "...") |> g1) s) |> g2 g1 :: IO T ~ (S -> (S,T)) g2 :: (S -> (S,T)) ~ IO T  simonpj@microsoft.com committed Jan 13, 2009 382   simonpj@microsoft.com committed Apr 03, 2009 383 Extrude the g2  simonpj@microsoft.com committed Jan 13, 2009 384   simonpj@microsoft.com committed Apr 03, 2009 385 386  f' = \p. \s. ((error "...") |> g1) s f = f' |> (String -> g2)  simonpj@microsoft.com committed Jan 13, 2009 387   simonpj@microsoft.com committed Apr 03, 2009 388 Discard args for bottomming function  simonpj@microsoft.com committed Jan 13, 2009 389   simonpj@microsoft.com committed Apr 03, 2009 390 391  f' = \p. \s. ((error "...") |> g1 |> g3 g3 :: (S -> (S,T)) ~ (S,T)  simonpj@microsoft.com committed Jan 13, 2009 392   simonpj@microsoft.com committed Apr 03, 2009 393 394 395 396 397 398 399 400 Extrude g1.g3 f'' = \p. \s. (error "...") f' = f'' |> (String -> S -> g1.g3) And now we can repeat the whole loop. Aargh! The bug is in applying the state hack to a function which then swallows the argument.  simonpj@microsoft.com committed Aug 13, 2010 401 402 403 404 405 This arose in another guise in Trac #3959. Here we had catch# (throw exn >> return ()) Note that (throw :: forall a e. Exn e => e -> a) is called with [a = IO ()].  Simon Peyton Jones committed Sep 26, 2014 406 After inlining (>>) we get  simonpj@microsoft.com committed Aug 13, 2010 407 408 409  catch# (\_. throw {IO ()} exn)  Simon Peyton Jones committed Sep 26, 2014 410 We must *not* eta-expand to  simonpj@microsoft.com committed Aug 13, 2010 411 412 413 414  catch# (\_ _. throw {...} exn) because 'catch#' expects to get a (# _,_ #) after applying its argument to  Simon Peyton Jones committed Sep 26, 2014 415 a State#, not another function!  simonpj@microsoft.com committed Aug 13, 2010 416 417 418 419 420 421 422 423 424  In short, we use the state hack to allow us to push let inside a lambda, but not to introduce a new lambda. Note [ArityType] ~~~~~~~~~~~~~~~~ ArityType is the result of a compositional analysis on expressions, from which we can decide the real arity of the expression (extracted  simonpj@microsoft.com committed Oct 27, 2010 425 with function exprEtaExpandArity).  simonpj@microsoft.com committed Aug 13, 2010 426   Simon Peyton Jones committed Sep 26, 2014 427 Here is what the fields mean. If an arbitrary expression 'f' has  simonpj@microsoft.com committed Oct 27, 2010 428 ArityType 'at', then  simonpj@microsoft.com committed Aug 13, 2010 429   simonpj@microsoft.com committed Oct 27, 2010 430 431  * If at = ABot n, then (f x1..xn) definitely diverges. Partial applications to fewer than n args may *or may not* diverge.  simonpj@microsoft.com committed Aug 13, 2010 432   simonpj@microsoft.com committed Oct 27, 2010 433  We allow ourselves to eta-expand bottoming functions, even  Simon Peyton Jones committed Sep 26, 2014 434  if doing so may lose some seq sharing,  simonpj@microsoft.com committed Oct 27, 2010 435 436  let x = in \y. error (g x y) ==> \y. let x = in error (g x y)  simonpj@microsoft.com committed Aug 13, 2010 437   Simon Peyton Jones committed Sep 26, 2014 438 439  * If at = ATop as, and n=length as, then expanding 'f' to (\x1..xn. f x1 .. xn) loses no sharing,  Javran Cheng committed Mar 02, 2015 440  assuming the calls of f respect the one-shot-ness of  Simon Peyton Jones committed Sep 26, 2014 441  its definition.  simonpj@microsoft.com committed Oct 27, 2010 442   Herbert Valerio Riedel committed Dec 17, 2015 443  NB 'f' is an arbitrary expression, eg (f = g e1 e2). This 'f'  Simon Peyton Jones committed Sep 26, 2014 444  can have ArityType as ATop, with length as > 0, only if e1 e2 are  simonpj@microsoft.com committed Oct 27, 2010 445 446 447 448 449 450 451 452 453  themselves. * In both cases, f, (f x1), ... (f x1 ... f(n-1)) are definitely really functions, or bottom, but *not* casts from a data type, in at least one case branch. (If it's a function in one case branch but an unsafe cast from a data type in another, the program is bogus.) So eta expansion is dynamically ok; see Note [State hack and bottoming functions], the part about catch#  Simon Peyton Jones committed Sep 26, 2014 454 455 Example: f = \x\y. let v = in  simonpj@microsoft.com committed Oct 27, 2010 456 457 458 459  \s(one-shot) \t(one-shot). blah 'f' has ArityType [ManyShot,ManyShot,OneShot,OneShot] The one-shot-ness means we can, in effect, push that 'let' inside the \st.  simonpj@microsoft.com committed Aug 13, 2010 460 461 462  Suppose f = \xy. x+y  simonpj@microsoft.com committed Oct 27, 2010 463 Then f :: AT [False,False] ATop  Simon Peyton Jones committed Sep 26, 2014 464 465  f v :: AT [False] ATop f :: AT [] ATop  simonpj@microsoft.com committed Apr 03, 2009 466 467  -------------------- Main arity code ----------------------------  Austin Seipp committed Dec 03, 2014 468 469 -}  simonpj@microsoft.com committed Aug 13, 2010 470 -- See Note [ArityType]  Simon Peyton Jones committed Dec 12, 2013 471 data ArityType = ATop [OneShotInfo] | ABot Arity  simonpj@microsoft.com committed Aug 13, 2010 472  -- There is always an explicit lambda  simonpj@microsoft.com committed Oct 27, 2010 473  -- to justify the [OneShot], or the Arity  simonpj@microsoft.com committed Aug 13, 2010 474   simonpj@microsoft.com committed Apr 03, 2009 475 vanillaArityType :: ArityType  Simon Peyton Jones committed Sep 26, 2014 476 vanillaArityType = ATop [] -- Totally uninformative  simonpj@microsoft.com committed Apr 03, 2009 477   Simon Marlow committed Nov 02, 2011 478 -- ^ The Arity returned is the number of value args the  simonpj@microsoft.com committed Aug 13, 2010 479 -- expression can be applied to without doing much work  Simon Peyton Jones committed Nov 12, 2013 480 exprEtaExpandArity :: DynFlags -> CoreExpr -> Arity  simonpj@microsoft.com committed Aug 13, 2010 481 -- exprEtaExpandArity is used when eta expanding  Simon Peyton Jones committed Sep 26, 2014 482 -- e ==> \xy -> e x y  Simon Peyton Jones committed Nov 12, 2013 483 exprEtaExpandArity dflags e  Simon Peyton Jones committed Nov 16, 2011 484  = case (arityType env e) of  Simon Peyton Jones committed Nov 12, 2013 485 486  ATop oss -> length oss ABot n -> n  simonpj@microsoft.com committed Aug 13, 2010 487  where  Joachim Breitner committed Feb 17, 2014 488  env = AE { ae_cheap_fn = mk_cheap_fn dflags isCheapApp  ian@well-typed.com committed Oct 16, 2012 489  , ae_ped_bot = gopt Opt_PedanticBottoms dflags }  Simon Peyton Jones committed Nov 16, 2011 490   simonpj@microsoft.com committed Aug 13, 2010 491 492 getBotArity :: ArityType -> Maybe Arity -- Arity of a divergent function  simonpj@microsoft.com committed Oct 27, 2010 493 494 getBotArity (ABot n) = Just n getBotArity _ = Nothing  Simon Peyton Jones committed Nov 16, 2011 495   Simon Marlow committed Jan 16, 2012 496 mk_cheap_fn :: DynFlags -> CheapAppFun -> CheapFun  Simon Peyton Jones committed Nov 16, 2011 497 mk_cheap_fn dflags cheap_app  ian@well-typed.com committed Oct 16, 2012 498  | not (gopt Opt_DictsCheap dflags)  Simon Peyton Jones committed Nov 16, 2011 499 500 501 502 503 504  = \e _ -> exprIsCheap' cheap_app e | otherwise = \e mb_ty -> exprIsCheap' cheap_app e || case mb_ty of Nothing -> False Just ty -> isDictLikeTy ty  Simon Peyton Jones committed Nov 12, 2013 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530  ---------------------- findRhsArity :: DynFlags -> Id -> CoreExpr -> Arity -> Arity -- This implements the fixpoint loop for arity analysis -- See Note [Arity analysis] findRhsArity dflags bndr rhs old_arity = go (rhsEtaExpandArity dflags init_cheap_app rhs) -- We always call exprEtaExpandArity once, but usually -- that produces a result equal to old_arity, and then -- we stop right away (since arities should not decrease) -- Result: the common case is that there is just one iteration where init_cheap_app :: CheapAppFun init_cheap_app fn n_val_args | fn == bndr = True -- On the first pass, this binder gets infinite arity | otherwise = isCheapApp fn n_val_args go :: Arity -> Arity go cur_arity | cur_arity <= old_arity = cur_arity | new_arity == cur_arity = cur_arity | otherwise = ASSERT( new_arity < cur_arity ) #ifdef DEBUG pprTrace "Exciting arity" (vcat [ ppr bndr <+> ppr cur_arity <+> ppr new_arity  Simon Peyton Jones committed Dec 12, 2013 531  , ppr rhs])  Simon Peyton Jones committed Nov 12, 2013 532 533 534 535 536 537 538 539 540 541 542 543 544 545 #endif go new_arity where new_arity = rhsEtaExpandArity dflags cheap_app rhs cheap_app :: CheapAppFun cheap_app fn n_val_args | fn == bndr = n_val_args < cur_arity | otherwise = isCheapApp fn n_val_args -- ^ The Arity returned is the number of value args the -- expression can be applied to without doing much work rhsEtaExpandArity :: DynFlags -> CheapAppFun -> CoreExpr -> Arity -- exprEtaExpandArity is used when eta expanding  Simon Peyton Jones committed Sep 26, 2014 546 -- e ==> \xy -> e x y  Simon Peyton Jones committed Nov 12, 2013 547 548 549 rhsEtaExpandArity dflags cheap_app e = case (arityType env e) of ATop (os:oss)  Simon Peyton Jones committed Sep 26, 2014 550  | isOneShotInfo os || has_lam e -> 1 + length oss  Simon Peyton Jones committed Dec 12, 2013 551 552  -- Don't expand PAPs/thunks -- Note [Eta expanding thunks]  Simon Peyton Jones committed Nov 12, 2013 553 554 555 556  | otherwise -> 0 ATop [] -> 0 ABot n -> n where  Joachim Breitner committed Feb 17, 2014 557  env = AE { ae_cheap_fn = mk_cheap_fn dflags cheap_app  Simon Peyton Jones committed Nov 12, 2013 558 559 560 561 562  , ae_ped_bot = gopt Opt_PedanticBottoms dflags } has_lam (Tick _ e) = has_lam e has_lam (Lam b e) = isId b || has_lam e has_lam _ = False  simonpj@microsoft.com committed Oct 27, 2010 563   Austin Seipp committed Dec 03, 2014 564 {-  Simon Peyton Jones committed Nov 12, 2013 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 Note [Arity analysis] ~~~~~~~~~~~~~~~~~~~~~ The motivating example for arity analysis is this: f = \x. let g = f (x+1) in \y. ...g... What arity does f have? Really it should have arity 2, but a naive look at the RHS won't see that. You need a fixpoint analysis which says it has arity "infinity" the first time round. This example happens a lot; it first showed up in Andy Gill's thesis, fifteen years ago! It also shows up in the code for 'rnf' on lists in Trac #4138. The analysis is easy to achieve because exprEtaExpandArity takes an argument type CheapFun = CoreExpr -> Maybe Type -> Bool used to decide if an expression is cheap enough to push inside a lambda. And exprIsCheap' in turn takes an argument type CheapAppFun = Id -> Int -> Bool which tells when an application is cheap. This makes it easy to write the analysis loop. The analysis is cheap-and-cheerful because it doesn't deal with mutual recursion. But the self-recursive case is the important one.  Simon Peyton Jones committed Nov 16, 2011 593 594 595 596 597 598 599 Note [Eta expanding through dictionaries] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ If the experimental -fdicts-cheap flag is on, we eta-expand through dictionary bindings. This improves arities. Thereby, it also means that full laziness is less prone to floating out the application of a function to its dictionary arguments, which can thereby lose opportunities for fusion. Example:  Simon Peyton Jones committed Sep 26, 2014 600  foo :: Ord a => a -> ...  Simon Peyton Jones committed Nov 16, 2011 601  foo = /\a \(d:Ord a). let d' = ...d... in \(x:a). ....  Simon Peyton Jones committed Sep 26, 2014 602  -- So foo has arity 1  Simon Peyton Jones committed Nov 16, 2011 603 604 605  f = \x. foo dInt$ bar x  Simon Peyton Jones committed Sep 26, 2014 606 The (foo DInt) is floated out, and makes ineffective a RULE  Simon Peyton Jones committed Nov 16, 2011 607 608 609 610 611  foo (bar x) = ... One could go further and make exprIsCheap reply True to any dictionary-typed expression, but that's more work.  rodlogic committed Feb 09, 2015 612 See Note [Dictionary-like types] in TcType.hs for why we use  Simon Peyton Jones committed Nov 16, 2011 613 614 isDictLikeTy here rather than isDictTy  simonpj@microsoft.com committed Oct 27, 2010 615 616 Note [Eta expanding thunks] ~~~~~~~~~~~~~~~~~~~~~~~~~~~  Simon Peyton Jones committed Nov 12, 2013 617 618 619 620 621 We don't eta-expand * Trivial RHSs x = y * PAPs x = map g * Thunks f = case y of p -> \x -> blah  simonpj@microsoft.com committed Oct 27, 2010 622 623 When we see f = case y of p -> \x -> blah  Simon Peyton Jones committed Sep 26, 2014 624 should we eta-expand it? Well, if 'x' is a one-shot state token  simonpj@microsoft.com committed Oct 27, 2010 625 626 627 then 'yes' because 'f' will only be applied once. But otherwise we (conservatively) say no. My main reason is to avoid expanding PAPSs  Simon Peyton Jones committed Sep 26, 2014 628 629  f = g d ==> f = \x. g d x because that might in turn make g inline (if it has an inline pragma),  simonpj@microsoft.com committed Oct 27, 2010 630 which we might not want. After all, INLINE pragmas say "inline only  Simon Peyton Jones committed Jun 06, 2013 631 when saturated" so we don't want to be too gung-ho about saturating!  Austin Seipp committed Dec 03, 2014 632 -}  simonpj@microsoft.com committed Apr 03, 2009 633   simonpj@microsoft.com committed Aug 13, 2010 634 arityLam :: Id -> ArityType -> ArityType  Simon Peyton Jones committed Dec 12, 2013 635 arityLam id (ATop as) = ATop (idOneShotInfo id : as)  simonpj@microsoft.com committed Oct 27, 2010 636 arityLam _ (ABot n) = ABot (n+1)  simonpj@microsoft.com committed Aug 13, 2010 637 638  floatIn :: Bool -> ArityType -> ArityType  Simon Peyton Jones committed Dec 12, 2013 639 640 -- We have something like (let x = E in b), -- where b has the given arity type.  simonpj@microsoft.com committed Oct 27, 2010 641 642 floatIn _ (ABot n) = ABot n floatIn True (ATop as) = ATop as  Simon Peyton Jones committed Dec 12, 2013 643 floatIn False (ATop as) = ATop (takeWhile isOneShotInfo as)  simonpj@microsoft.com committed Oct 27, 2010 644  -- If E is not cheap, keep arity only for one-shots  simonpj@microsoft.com committed Aug 13, 2010 645   simonpj@microsoft.com committed Dec 21, 2010 646 arityApp :: ArityType -> Bool -> ArityType  simonpj@microsoft.com committed Aug 13, 2010 647 -- Processing (fun arg) where at is the ArityType of fun,  simonpj@microsoft.com committed Oct 27, 2010 648 -- Knock off an argument and behave like 'let'  simonpj@microsoft.com committed Dec 21, 2010 649 650 651 652 arityApp (ABot 0) _ = ABot 0 arityApp (ABot n) _ = ABot (n-1) arityApp (ATop []) _ = ATop [] arityApp (ATop (_:as)) cheap = floatIn cheap (ATop as)  simonpj@microsoft.com committed Aug 13, 2010 653 654  andArityType :: ArityType -> ArityType -> ArityType -- Used for branches of a 'case'  Simon Peyton Jones committed Dec 12, 2013 655 andArityType (ABot n1) (ABot n2)  simonpj@microsoft.com committed Oct 27, 2010 656 657 658 659  = ABot (n1 min n2) andArityType (ATop as) (ABot _) = ATop as andArityType (ABot _) (ATop bs) = ATop bs andArityType (ATop as) (ATop bs) = ATop (as combine bs)  Simon Peyton Jones committed Sep 26, 2014 660  where -- See Note [Combining case branches]  Simon Peyton Jones committed Dec 12, 2013 661 662 663  combine (a:as) (b:bs) = (a bestOneShot b) : combine as bs combine [] bs = takeWhile isOneShotInfo bs combine as [] = takeWhile isOneShotInfo as  simonpj@microsoft.com committed Dec 24, 2009 664   Austin Seipp committed Dec 03, 2014 665 {-  simonpj@microsoft.com committed Oct 27, 2010 666 667 Note [Combining case branches] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  Simon Peyton Jones committed Dec 12, 2013 668 Consider  simonpj@microsoft.com committed Oct 27, 2010 669 670 671 672 673  go = \x. let z = go e0 go2 = \x. case x of True -> z False -> \s(one-shot). e1 in go2 x  Simon Peyton Jones committed Dec 12, 2013 674 We *really* want to eta-expand go and go2.  simonpj@microsoft.com committed Oct 27, 2010 675 When combining the barnches of the case we have  Simon Peyton Jones committed Dec 12, 2013 676 677  ATop [] andAT ATop [OneShotLam] and we want to get ATop [OneShotLam]. But if the inner  simonpj@microsoft.com committed Oct 27, 2010 678 679 680 lambda wasn't one-shot we don't want to do this. (We need a proper arity analysis to justify that.)  Simon Peyton Jones committed Dec 12, 2013 681 682 So we combine the best of the two branches, on the (slightly dodgy) basis that if we know one branch is one-shot, then they all must be.  Austin Seipp committed Dec 03, 2014 683 -}  simonpj@microsoft.com committed Dec 24, 2009 684   simonpj@microsoft.com committed Apr 03, 2009 685 ---------------------------  simonpj@microsoft.com committed Dec 21, 2010 686 type CheapFun = CoreExpr -> Maybe Type -> Bool  Simon Peyton Jones committed Sep 26, 2014 687 688 689  -- How to decide if an expression is cheap -- If the Maybe is Just, the type is the type -- of the expression; Nothing means "don't know"  simonpj@microsoft.com committed Dec 21, 2010 690   Simon Peyton Jones committed Sep 26, 2014 691 data ArityEnv  Joachim Breitner committed Feb 17, 2014 692  = AE { ae_cheap_fn :: CheapFun  Simon Peyton Jones committed Nov 16, 2011 693 694  , ae_ped_bot :: Bool -- True <=> be pedantic about bottoms }  Simon Marlow committed Nov 02, 2011 695   Simon Peyton Jones committed Nov 16, 2011 696 697 698 699 arityType :: ArityEnv -> CoreExpr -> ArityType arityType env (Cast e co) = case arityType env e of  Simon Peyton Jones committed Nov 09, 2011 700 701 702 703 704  ATop os -> ATop (take co_arity os) ABot n -> ABot (n min co_arity) where co_arity = length (typeArity (pSnd (coercionKind co))) -- See Note [exprArity invariant] (2); must be true of  Simon Peyton Jones committed Sep 09, 2011 705 706 707  -- arityType too, since that is how we compute the arity -- of variables, and they in turn affect result of exprArity -- Trac #5441 is a nice demo  Simon Peyton Jones committed Nov 09, 2011 708 709  -- However, do make sure that ATop -> ATop and ABot -> ABot! -- Casts don't affect that part. Getting this wrong provoked #5475  Simon Peyton Jones committed Sep 09, 2011 710   Simon Peyton Jones committed Nov 16, 2011 711 arityType _ (Var v)  Simon Peyton Jones committed Jan 17, 2013 712  | strict_sig <- idStrictness v  Joachim Breitner committed Dec 09, 2013 713  , not \$ isNopSig strict_sig  simonpj@microsoft.com committed Apr 03, 2009 714  , (ds, res) <- splitStrictSig strict_sig  simonpj@microsoft.com committed Oct 27, 2010 715 716 717  , let arity = length ds = if isBotRes res then ABot arity else ATop (take arity one_shots)  simonpj@microsoft.com committed Apr 03, 2009 718  | otherwise  simonpj@microsoft.com committed Oct 27, 2010 719  = ATop (take (idArity v) one_shots)  simonpj@microsoft.com committed Aug 13, 2010 720  where  Simon Peyton Jones committed Sep 26, 2014 721  one_shots :: [OneShotInfo] -- One-shot-ness derived from the type  simonpj@microsoft.com committed Aug 13, 2010 722  one_shots = typeArity (idType v)  simonpj@microsoft.com committed Jan 13, 2009 723   Simon Peyton Jones committed Sep 26, 2014 724  -- Lambdas; increase arity  Simon Peyton Jones committed Nov 16, 2011 725 arityType env (Lam x e)  Joachim Breitner committed Feb 17, 2014 726  | isId x = arityLam x (arityType env e)  Simon Peyton Jones committed Nov 16, 2011 727  | otherwise = arityType env e  simonpj@microsoft.com committed Jan 13, 2009 728   Simon Peyton Jones committed Sep 26, 2014 729  -- Applications; decrease arity, except for types  Simon Peyton Jones committed Nov 16, 2011 730 731 732 arityType env (App fun (Type _)) = arityType env fun arityType env (App fun arg )  Joachim Breitner committed Feb 17, 2014 733  = arityApp (arityType env fun) (ae_cheap_fn env arg Nothing)  simonpj@microsoft.com committed Apr 03, 2009 734   Simon Peyton Jones committed Sep 26, 2014 735 736 737 738 739 740 741 742  -- Case/Let; keep arity if either the expression is cheap -- or it's a 1-shot lambda -- The former is not really right for Haskell -- f x = case x of { (a,b) -> \y. e } -- ===> -- f x y = case x of { (a,b) -> e } -- The difference is observable using 'seq' --  Simon Peyton Jones committed Nov 16, 2011 743 arityType env (Case scrut _ _ alts)  Simon Peyton Jones committed May 02, 2012 744  | exprIsBottom scrut || null alts  Simon Peyton Jones committed Oct 21, 2011 745  = ABot 0 -- Do not eta expand  Simon Peyton Jones committed Nov 11, 2011 746  -- See Note [Dealing with bottom (1)]  Simon Peyton Jones committed Oct 21, 2011 747 748  | otherwise = case alts_type of  Simon Peyton Jones committed Sep 26, 2014 749 750 751  ABot n | n>0 -> ATop [] -- Don't eta expand | otherwise -> ABot 0 -- if RHS is bottomming -- See Note [Dealing with bottom (2)]  Simon Peyton Jones committed Nov 11, 2011 752   Simon Peyton Jones committed Mar 11, 2014 753  ATop as | not (ae_ped_bot env) -- See Note [Dealing with bottom (3)]  Joachim Breitner committed Feb 17, 2014 754  , ae_cheap_fn env scrut Nothing -> ATop as  Simon Peyton Jones committed Mar 11, 2014 755 756  | exprOkForSpeculation scrut -> ATop as | otherwise -> ATop (takeWhile isOneShotInfo as)  Simon Peyton Jones committed Oct 21, 2011 757  where  Simon Peyton Jones committed Nov 16, 2011 758  alts_type = foldr1 andArityType [arityType env rhs | (_,_,rhs) <- alts]  simonpj@microsoft.com committed Apr 03, 2009 759   Simon Peyton Jones committed Sep 26, 2014 760 arityType env (Let b e)  Simon Peyton Jones committed Nov 16, 2011 761  = floatIn (cheap_bind b) (arityType env e)  simonpj@microsoft.com committed Jan 13, 2009 762 763 764  where cheap_bind (NonRec b e) = is_cheap (b,e) cheap_bind (Rec prs) = all is_cheap prs  Simon Peyton Jones committed Nov 16, 2011 765  is_cheap (b,e) = ae_cheap_fn env e (Just (idType b))  simonpj@microsoft.com committed Dec 21, 2010 766   Simon Peyton Jones committed Nov 16, 2011 767 768 arityType env (Tick t e) | not (tickishIsCode t) = arityType env e  Simon Marlow committed Nov 02, 2011 769   Simon Peyton Jones committed Nov 16, 2011 770 arityType _ _ = vanillaArityType  Simon Peyton Jones committed Sep 26, 2014 771   Austin Seipp committed Dec 03, 2014 772 {-  eir@cis.upenn.edu committed Dec 11, 2015 773 774 %************************************************************************ %* *  Simon Peyton Jones committed Sep 26, 2014 775  The main eta-expander  eir@cis.upenn.edu committed Dec 11, 2015 776 777 %* * %************************************************************************  simonpj@microsoft.com committed Jan 13, 2009 778   simonpj@microsoft.com committed Sep 24, 2010 779 780 We go for: f = \x1..xn -> N ==> f = \x1..xn y1..ym -> N y1..ym  Simon Peyton Jones committed Sep 26, 2014 781  (n >= 0)  simonpj@microsoft.com committed Sep 24, 2010 782   Simon Peyton Jones committed Sep 26, 2014 783 where (in both cases)  simonpj@microsoft.com committed Sep 24, 2010 784   Simon Peyton Jones committed Sep 26, 2014 785  * The xi can include type variables  simonpj@microsoft.com committed Sep 24, 2010 786   Simon Peyton Jones committed Sep 26, 2014 787  * The yi are all value variables  simonpj@microsoft.com committed Sep 24, 2010 788   Simon Peyton Jones committed Sep 26, 2014 789 790  * N is a NORMAL FORM (i.e. no redexes anywhere) wanting a suitable number of extra args.  simonpj@microsoft.com committed Sep 24, 2010 791 792 793  The biggest reason for doing this is for cases like  Simon Peyton Jones committed Sep 26, 2014 794 795 796  f = \x -> case x of True -> \y -> e1 False -> \y -> e2  simonpj@microsoft.com committed Sep 24, 2010 797   Simon Peyton Jones committed Jun 06, 2013 798 Here we want to get the lambdas together. A good example is the nofib  simonpj@microsoft.com committed Sep 24, 2010 799 800 801 802 803 804 805 806 807 808 809 810 811 812 program fibheaps, which gets 25% more allocation if you don't do this eta-expansion. We may have to sandwich some coerces between the lambdas to make the types work. exprEtaExpandArity looks through coerces when computing arity; and etaExpand adds the coerces as necessary when actually computing the expansion. Note [No crap in eta-expanded code] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The eta expander is careful not to introduce "crap". In particular, given a CoreExpr satisfying the 'CpeRhs' invariant (in CorePrep), it returns a CoreExpr satisfying the same invariant. See Note [Eta expansion and the CorePrep invariants] in CorePrep.  simonpj@microsoft.com committed Jan 13, 2009 813 814  This means the eta-expander has to do a bit of on-the-fly  Simon Peyton Jones committed Sep 26, 2014 815 simplification but it's not too hard. The alernative, of relying on  simonpj@microsoft.com committed Jan 13, 2009 816 817 818 a subsequent clean-up phase of the Simplifier to de-crapify the result, means you can't really use it in CorePrep, which is painful.  simonpj@microsoft.com committed Oct 29, 2009 819 820 821 Note [Eta expansion and SCCs] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Note that SCCs are not treated specially by etaExpand. If we have  Simon Peyton Jones committed Sep 26, 2014 822 823  etaExpand 2 (\x -> scc "foo" e) = (\xy -> (scc "foo" e) y)  simonpj@microsoft.com committed Oct 29, 2009 824 So the costs of evaluating 'e' (not 'e y') are attributed to "foo"  Peter Wortmann committed Dec 16, 2014 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840  Note [Eta expansion and source notes] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ CorePrep puts floatable ticks outside of value applications, but not type applications. As a result we might be trying to eta-expand an expression like (src<...> v) @a which we want to lead to code like \x -> src<...> v @a x This means that we need to look through type applications and be ready to re-add floats on the top.  Austin Seipp committed Dec 03, 2014 841 -}  simonpj@microsoft.com committed Oct 29, 2009 842   simonpj@microsoft.com committed Jan 13, 2009 843 844 845 846 847 848 849 850 851 852 -- | @etaExpand n us e ty@ returns an expression with -- the same meaning as @e@, but with arity @n@. -- -- Given: -- -- > e' = etaExpand n us e ty -- -- We should have that: -- -- > ty = exprType e = exprType e'  Simon Peyton Jones committed Sep 26, 2014 853 854 855 etaExpand :: Arity -- ^ Result should have this number of value args -> CoreExpr -- ^ Expression to expand -> CoreExpr  simonpj@microsoft.com committed Jan 13, 2009 856 -- etaExpand deals with for-alls. For example:  Simon Peyton Jones committed Sep 26, 2014 857 -- etaExpand 1 E  simonpj@microsoft.com committed Jan 13, 2009 858 859 -- where E :: forall a. a -> a -- would return  Simon Peyton Jones committed Sep 26, 2014 860 -- (/\b. \y::a -> E b y)  simonpj@microsoft.com committed Jan 13, 2009 861 862 863 864 865 866 867 -- -- It deals with coerces too, though they are now rare -- so perhaps the extra code isn't worth it etaExpand n orig_expr = go n orig_expr where  simonpj@microsoft.com committed Dec 24, 2009 868  -- Strip off existing lambdas and casts  simonpj@microsoft.com committed Apr 03, 2009 869  -- Note [Eta expansion and SCCs]  simonpj@microsoft.com committed Jan 13, 2009 870  go 0 expr = expr  871  go n (Lam v body) | isTyVar v = Lam v (go n body)