Search code examples
haskelloptimizationfunctional-programmingcompiler-constructioneta-expansion

Haskell - Eta reduction and Eta expansion


I've been studying functional program optimization, and have been digging into the GHC source. I (mostly) understand what eta reduction and eta expansion are. Eta reduction only removes redundant lambdas:

\x -> abs x
=>
abs

Eta expansion is the opposite of eta reduction and does things like this (correct me if I'm incorrect):

abs
=>
\x -> abs x
-----------------------------------------------
foo = abs
=>
foo x = abs x
-----------------------------------------------
foo = bar 100
bar x y = x + y
=>
foo y = bar 10 y
bar x y = x + y
-----------------------------------------------
etc...

What I don't get is how they don't get in each other's way and send the compiler into an infinite loop. For example, first, a value is eta expanded, and then it is eta reduced, and so on. So, how do the two optimizations not get in each other's way?


Solution

  • I think I found an answer. I found a thesis from a contributor to GHC (don't remember what it was called), and in it, it mentioned that GHC doesn't do eta reduction. Instead, it does eta expansion, and beta reduction (IIRC); Beta reduction does most of the job.