cn.cpp

// church numerals and lambda calculus in C++ using meta-template
// programming, everything evaluated at compile-time. This code should
// never be used in the real world. If I catch people using this for
// real-world code just because it's awesome I will track said people
// down and have a length discussion on why their existance is the
// reason I need to question the ethics of writing this code in the
// first place.

// all code is licensed under MIT under one condition, never actually
// use this code in real world programs, you can share it, and modify it
// and do what ever the fuck you want, except  well real world scenarios
// don't fucking do it. Yes, I'm talking to you boost developers, don't
// you dare get any ideas from this for boost::mpl

// oh yes you need C++11 for this mess...

// author: Dale Weiler
// email: [email protected]
// license: MIT (and that exception above)
// irc: freenode.org, nick: graphitemaster
// web: graphitemaster.github.com
// ... okay enough PI.


// some macros .. haha I'm a evil fucking bastard
// these ARE SUPPOSE TO HELP YOU UNDERSTAND
#define LAMBDA(X) typename X
#define CHUCH_NUMERAL_BRANCH_BEGIN(NAME)                   \
    struct NAME {
#define CHUCH_NUMERAL_RESULT_BEGIN(OUTPUT, LIST)           \
    template <LIST>                                        \
    CHUCH_NUMERAL_BRANCH_BEGIN(OUTPUT)
#define CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(INPUT, OUTPUT)   \
    typedef INPUT OUTPUT;
#define CHUCH_NUMERAL_BEGIN(NAME, FUNCTION, LIST)          \
    struct NAME {                                          \
        /* function input */                               \
        CHUCH_NUMERAL_RESULT_BEGIN(FUNCTION, LIST)
#define CHUCH_NUMERAL_SELECT(NAME, SELECT, APPLY, RESULT)  \
    typename NAME::template SELECT<APPLY>::RESULT
#define CHUCH_NUMERAL_CLOSE()               };
#define CHUCH_NUMERAL_RESULT_DEFINE_CLOSE() };
#define CHUCH_NUMERAL_BRANCH_CLOSE()        };
#define CHUCH_NUMERAL_RESULT_CLOSE()        }; };


// identity: f(x)=x
CHUCH_NUMERAL_BEGIN(Identity, Application, LAMBDA(X))
    CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(X, Result)
    CHUCH_NUMERAL_RESULT_DEFINE_CLOSE ()
CHUCH_NUMERAL_CLOSE()

// Zero is just the identity of a function where f(x)=x
// i.e Identity as defined above (dropping F)
CHUCH_NUMERAL_BEGIN(Zero, Application, LAMBDA(F))
    CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(Identity, Result) // drops F for zero
    CHUCH_NUMERAL_RESULT_DEFINE_CLOSE()
CHUCH_NUMERAL_CLOSE()

// heres some examples of how representing numbers can work
// we don't need these because later on we actually programically
// (using templates) create these chains
#if 0
    // For one we just apply the function F once so that the
    // application defines the result to be the input lambda
    // F exactly once.
    CHUCH_NUMERAL_BEGIN(One, Application, LAMBDA(F))
        CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(F, Result)
        CHUCH_NUMERAL_RESULT_DEFINE_CLOSE ()
    CHUCH_NUMERAL_CLOSE()

    // two .. now you see the encoding in the works
    // we just apply the input function twice as our
    // application. The result must be explicitly defined.
    CHUCH_NUMERAL_BEGIN(Two, Application, LAMBDA(F))
        CHUCH_NUMERAL_BRANCH_BEGIN(Result)
            CHUCH_NUMERAL_RESULT_BEGIN(Application, LAMBDA(X))
                CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(
                    CHUCH_NUMERAL_SELECT(
                        One,
                        Application,
                        F,
                        Result::template Application<X>::Result
                    ),
                    Previous
                )
                CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(
                    CHUCH_NUMERAL_SELECT(
                        F,
                        Application,
                        Previous,
                        Result
                    ),
                    Result
                )
            CHUCH_NUMERAL_RESULT_CLOSE()
        CHUCH_NUMERAL_BRANCH_CLOSE()
    CHUCH_NUMERAL_CLOSE()
#endif

// We accept the number in which we want to
// encode as N, This is simply recursivly applying this 
// template with N-1. To prevent infinite recursion a specialization
// is used which inherits the typedef'd result for Zero.
template <int N>
CHUCH_NUMERAL_BEGIN(Chuch, Application, LAMBDA(F))
    CHUCH_NUMERAL_BRANCH_BEGIN(Result)
        CHUCH_NUMERAL_RESULT_BEGIN(Application, LAMBDA(X))
            CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(
                CHUCH_NUMERAL_SELECT(
                    Chuch<N-1>,
                    Application,
                    F,
                    Result::template Application<X>::Result
                ),
                Previous
            )
            CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(
                CHUCH_NUMERAL_SELECT(
                    F,
                    Application,
                    Previous,
                    Result
                ),
                Result
            )
        CHUCH_NUMERAL_RESULT_CLOSE()
    CHUCH_NUMERAL_BRANCH_CLOSE()
CHUCH_NUMERAL_CLOSE()
// prevent recursion
template <>
CHUCH_NUMERAL_BRANCH_BEGIN(Chuch<0> : Zero)
CHUCH_NUMERAL_BRANCH_CLOSE()

// This is how we implement addition
// Addition m n = \f -> \x -> m f (n f x)
template <LAMBDA(M), LAMBDA(N)>
CHUCH_NUMERAL_BEGIN(Addition, Application, LAMBDA(F))
    CHUCH_NUMERAL_BRANCH_BEGIN(Result)
        CHUCH_NUMERAL_RESULT_BEGIN(Application, LAMBDA(X))
            CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(
                CHUCH_NUMERAL_SELECT(
                    N,
                    Application,
                    F,
                    Result::template Application<X>::Result
                ),
                Store
            )
            CHUCH_NUMERAL_RESULT_DEFINE_BEGIN(
                CHUCH_NUMERAL_SELECT(
                    M,
                    Application,
                    F,
                    Result::template Application<Store>::Result
                ),
                Result
            )
        CHUCH_NUMERAL_RESULT_CLOSE()
    CHUCH_NUMERAL_BRANCH_CLOSE()
CHUCH_NUMERAL_CLOSE()

// We just build off add for Multiplication (the operation of recursivly
// adding): e.g
// Multiplication m n = \f -> n (m f)
template <LAMBDA(M), LAMBDA(N)>
CHUCH_NUMERAL_BEGIN (
    Multiplication,
    // inherit the RESULT, thus we RESULT_CLOSE()
    Application :
        N::template Application <
            LAMBDA(M)::template Application<F>::Result
        >,
    LAMBDA(F)
)
CHUCH_NUMERAL_RESULT_CLOSE()

// and Exponentation is just the process of addig up a bunch of
// Multiplications recursivly..
// e.g
// Exponentation m n = n m
// it doesn't get any easier than this
template <LAMBDA(M), LAMBDA(N)>
struct Exponentation : N::template Application<M>::Result { };


// now we just need a way to decode this encoding of everything as
// a lambda function. This isn't too hard, just a compile-time
// incrementer, and some decode logic
template <typename T, int N>      struct DecodeValue     { const T value = N; };
template <typename T, typename A> struct DecodeIncrement { const T value = A::value + 1; };

// map the decode logic into the template layout of the church
// encoding.
struct DecodeMatch {
    template <typename T>
    struct Application {
        typedef DecodeIncrement<
                T,
                DecodeValue <T, 1>
        > Result;
    };
};

// Now we implement the deocder where the DecodeMatch is passed with
// the correct N (lambda) to get the Application Result. This result
// is a function itself which applies the DecodeIncrement 'N times
// This result can than be applied on DecodeValue<T, 0>. This also
// decodes with T as the type, technically you can decode the encoded
// value as ANY type, the power!
template <typename N, typename T = int>
struct ChuchDecode {
    enum {
        value = N::template Application<DecodeMatch>::Result::template Application<
            DecodeValue<T, 0>
        >::Result::value
    };
};

// here's a basic test-driver, which tests the ability to encode values
// as functions, as well as the three-basic mathematical operations:
// addition, multiplication and exponentation. subtraction isn't required
// since you can derive that from add using negated values.

// you will need to enable a large template depth on modern compilers
// to get this running, gcc/clang max out at 512 or so, this can be
// changed with -ftemplate-depth=2048 or higher depending on the values
// you're going to be using.

// this will take a long time to compile, so .. give it time .. a lot
// of time .. like 20 minutes.

// this also needs a LOT of ram, if you're going to be crazy about stuff
// make sure you have at least 16GB of physical ram available for
// the compiler ..
#include <iostream>
int main() {
    // now lets use this to evaluate some numbers with lambda calculus
    // and encoded numbers as functions themselfs (church numerals)
    std::cout << ChuchDecode<Chuch         <1024                   > >::value << std::endl; // should print 1024
    std::cout << ChuchDecode<Addition      <Chuch<1024>, Chuch<24> > >::value << std::endl; // should print 1048
    std::cout << ChuchDecode<Multiplication<Chuch<10>,   Chuch<10> > >::value << std::endl; // should print 100
    std::cout << ChuchDecode<Exponentation <Chuch<2>,    Chuch<9>  > >::value << std::endl; // should print 512
}