[Template-haskell] On reifing functions and partial evaluation

[Duncan Coutts]

Ok, here's something pointless but fun: improving ghc's Ackerman
function micro-benchmark using Template Haskell and partial evaluation.

First the sensational headline:
ghc beats gcc by 57% on Ackerman benchmark, improved to 290% using
Template Haskell.

In my previous post I looked at a the generating extensions of a couple
simple non-recursive functions. The generating extension for the
Ackerman function is rather more complicated:

ack :: Int -> Int -> Int
ack m n =
  if m == 0 then n+1
            else if n == 0 then ack (m-1) 1
                           else ack (m-1) (ack m (n-1))

genex_ack :: Int -> ExpQ
genex_ack m = 
  if m == 0 then [| \n -> n + 1 |]
            else [| let genex_ack_m = \n -> 
                          if n == 0 then $(genex_ack (m-1)) 1
                                    else $(genex_ack (m-1)) (genex_ack_m (n-1))
                     in genex_ack_m |]

In particular it is complicated by the fact that genex_ack m calls
itself without decreasing m (for m > 0). We can't use $(genex_ack m) or
it would not terminate, hence memoising genex_ack m to use in the
recursive call. This could probably be done more elegantly/regularly.

So then we use it in our benchmark like so:

ack_4       = ack 4
genex_ack_4 = $(genex_ack 4)

and time it (in ghci, having compiled with ghc -O):

ack_4 1		: approx 100 sec
genex_ack_4 1	: approx 40  sec

for comparison with gcc-3.3.2 -O3 -fomit-frame-pointer (source taken
from http://www.bagley.org/~doug/shootout/bench/ackermann/)

(gcc) ack 4 1	: approx 157 sec


So there you have it, we can cheat with the best of them to improve our
scores on pointless micro-benchmarks. :-)

Duncan