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