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