# eta-expansion

**Simon Peyton-Jones
**
IMCEAEX-_O=MICROSOFT_OU=NORTHAMERICA_CN=RECIPIENTS_CN=428592@microsoft.com

*Tue, 29 Apr 2003 20:38:10 +0100*

|* v =3D \a1 ... an -> f a1 ... an
*|* =3D=3D=3D> v =3D \a1 ...an ... am -> f a1 ... an ...am
*|*=20
*|* assuming f has arity m > n.
*|*=20
*|* arity is something like "how many arguments can be applied, without
*|* perfoming work"
*|*=20
*|* My questions:
*|* 1) How do you compute this arity.
*
Take a look at ghc/compiler/coreSyn/CoreUtils.exprEtaExpandArity.
Basically, we just look for partial applications of functions with
already-known arity. We consider an expression to have arity N if
eta-expansion to put N lambdas at the front would not waste a
significant amoutn of work. So
(+) 3
would eta expand do
\x -> (+) 3 x
but (+) (g 3)
would not, unless g has arity greater than 1. The idea is to avoid
pushing an arbitrarily expensive redex (or in the worst case, bottom)
inside a lambda.
|* 2) What's the expression f in the general rule, is it a variable or
*|* a term, or could it be both?
*
As I mention above, it can be an expression, provided adding the lambda
doesn't duplicate work, even if the lambda is applied more than once.
|* In the same paper is the case-eta-expansion, but I don't understand
*|* the correctness of this transformation:
*|*=20
*|* case e of {p1 -> e1,...,pn -> en}
*|* =3D=3D=3D> \y -> case e of {p1 -> e1 y, ..., pn -> en y}
*|*=20
*|* The rhs is a WHNF, but the lhs isn't, so the rule
*|* can't be correct in general. For example, assume that e is bot.
*
Right. It's only done if 'e' is cheap (a variable, or something like
that).
Eta expansion is very important in practice, because it makes
head-normal forms show up more, which in turn makes more inlining
happen, which can be a really big win.
Simon