Accorring to Greenspun’s Tenth Rule of Programming: any sufficiently complicated C or Fortran program contains an ad hoc, informally specified, bug-ridden, slow implementation of half of Common Lisp.

That guy’s damn right! I think that I’ve just implemented one.

Recently, I was traveling in the train with a friend and we were talking about programming languages. So I’ve told him why C++ is among my favorite languages and what I think are its killer features. One of them were templates, and I mentioned that while java generics are implemented only by inserting cast byte code instructions at the right places, C++ templates are a turing-complete functional programming language.

He looked very surprised about that, so I have written a small example for demonstration, the compile-time factorial algorithm

#include <iostream>

// general formula for all N
template<int N>
struct factorial {
    static const int value = N * factorial<N - 1>::value;
};

// specialization for 0
template<>
struct factorial<0> {
    static const int value = 1;
};

int main() {
    typedef factorial<7> fac;
    std::cout << fac::value << std::endl;
}

The nice thing about this compile-time algorithm is, that its run-time complexity is O(1), as the generated machine code only prints the result (5040), which is computed at compile-time:

105                            .loc 1 18 0
106 0083 C745F8B0              movl    $5040, -8(%ebp)
106      130000
107                            .loc 1 19 0
108 008a 8B45F8                movl    -8(%ebp), %eax
109 008d 89442404              movl    %eax, 4(%esp)
110 0091 C7042400              movl    $_ZSt4cout, (%esp)
^^ std::cout
110      000000
111 0098 E8FCFFFF              call    _ZNSolsEi
^^ std::basic_ostream<char, std::char_traits<char> >::operator<<(int)