[Haskell-cafe] Experiments with defunctionalization, church-encoding and CPS

[Derek Elkins]

On Tue, Oct 13, 2009 at 4:44 AM, Eugene Kirpichov <ekirpichov at gmail.com> wrote:
> I took a toy problem - find the first node satisfying a predicate in a
> binary tree, started with a naive Maybe-based implementation - and
> experimented with 3 ways of changing the program:
>  - Church-encode the Maybe
>  - Convert the program into CPS
>  - Defunctionalize the Church-encoded or CPS-transformed program
> http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10686
>
> The link points to code, a benchmark and conclusion.
>
> Conclusion:
>  - Haskell implements Maybe well enough that it is not possible to do better
>  - Defunctionalization and consequent optimization yields same
> performance as the one with Maybe
>  - Non-simplified CPS and Church-encoded representations do bad

You may find this collection of related papers interesting if you have
not already seen them:
http://lambda-the-ultimate.org/node/2423#comment-38384