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

[Heinrich Apfelmus]

Eugene Kirpichov 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

I'm not sure your example program is enough to justify the conclusions.


The main advantage of the Church-encoding of  Maybe

    type Maybe' a = forall b . b -> (a -> b) -> b

is that the latter has the pattern match for failure / success built-in
when used as a monad

    m >>= g  = \nothing just -> m nothing (\x -> g x nothing just)

  VS

    m >>= g  = case m of
        Nothing -> Nothing
        Just x  -> g x

The algebraic data type has to check that the result was indeed  Just x
 whereas the Church-encoding can jump right to the success continuation.


The problem is that your tree doesn't really make use of this advantage.
For that, you need a completely left-biased tree, like for example

    Fork 1 (Fork 2 (Fork 3 ... Leaf) Leaf) Leaf

    testTree = fromList [1..100000]
    fromList = foldr (\x t -> Fork x t Leaf) Leaf

I've implemented this and posted it below your version at

    http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10686

I've used the  criterion  benchmarking package, so you can run this
straight out of the box.


Even then, the results are mixed. The Church-encoding shines in GHCi as
it should, but loses its advantage when the code is being compiled. I
guess we have to look at the core if we want to know what exactly is
going on.


PS: I'm not entirely sure I'm using  criterion  correctly, in particular
 concerning strictness. For instance, dropping the  fromJust  will
reduce the run-time of the "data Maybe" benchmark by 75%. Comments?


Regards,
apfelmus

--
http://apfelmus.nfshost.com