Last active
August 10, 2016 11:44
-
-
Save sekrasoft/2115f523a171c64cf764cb02197b24d9 to your computer and use it in GitHub Desktop.
Compile-time Church numerals (C++98)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Church numerals | |
namespace Church { | |
// zero = \f x -> x | |
template <template <typename> class f, typename x> struct Zero { | |
typedef x value; | |
}; | |
// succ = \n -> \f x -> f (n f x) | |
template <template <template <typename> class, typename> class n> struct Succ { | |
template <template <typename> class f, typename x> struct churchValue { | |
typedef typename f<typename n<f, x>::value>::value value; | |
}; | |
}; | |
// sum = \m n -> \f x -> m f (n f x) | |
template <template <template <typename> class, typename> class m, template <template <typename> class, typename> class n> struct Sum { | |
template <template <typename> class f, typename x> struct churchValue { | |
typedef typename m<f, typename n<f,x>::value>::value value; | |
}; | |
}; | |
// mul = \m n -> \f x -> m (\y -> n f y) x | |
template <template <template <typename> class, typename> class m, template <template <typename> class, typename> class n> struct Mul { | |
template <template <typename> class f, typename x> struct churchValue { | |
template <typename y> struct L { | |
typedef typename n<f,y>::value value; | |
}; | |
typedef typename m<L, x>::value value; | |
}; | |
}; | |
} | |
// Natural numbers | |
namespace Naturals { | |
// Natural n = n | |
template <int n> struct Natural { | |
static const int value = n; | |
}; | |
// Succ n = Natural (n+1) | |
template <typename n> struct Succ { | |
typedef Natural<n::value + 1> value; | |
}; | |
} | |
// conversion from int to Church numerals and from Church numerals to int | |
namespace conversion { | |
// churchToInt n = n succ 0 | |
template <template <template <typename> class, typename> class n> struct churchToInt { | |
typedef typename n<Naturals::Succ, Naturals::Natural<0> >::value naturalValue; | |
static const int value = naturalValue::value; | |
}; | |
// intToChurch n = \f x -> Church.succ (intToChurch (n-1)) | |
template <int n> struct intToChurch { | |
template <template <typename> class f, typename x> struct previousValue { | |
typedef typename intToChurch<n-1>::template churchValue<f, x>::value value; | |
}; | |
template <template <typename> class f, typename x> struct churchValue { | |
typedef typename Church::Succ<previousValue>::template churchValue<f, x>::value value; | |
}; | |
}; | |
// intToChurch 0 = Church.zero | |
template <> struct intToChurch<0> { | |
template <template <typename> class f, typename x> struct churchValue { | |
typedef typename Church::Zero<f, x>::value value; | |
}; | |
}; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include "church.h" | |
// five = conversion.intToChurch 5 | |
template <template <typename> class f, typename x> struct five { | |
typedef typename conversion::intToChurch<5>::churchValue<f, x>::value value; | |
}; | |
// three = conversion.intToChurch 3 | |
template <template <typename> class f, typename x> struct three { | |
typedef typename conversion::intToChurch<3>::churchValue<f, x>::value value; | |
}; | |
// mul_5_3 = Church.mul five three | |
template <template <typename> class f, typename x> struct mul_5_3 { | |
typedef typename Church::Mul<five, three>::churchValue<f, x>::value value; | |
}; | |
// sum_5_3 = Church.sum five three | |
template <template <typename> class f, typename x> struct sum_5_3 { | |
typedef typename Church::Sum<five, three>::churchValue<f, x>::value value; | |
}; | |
// int_... = conversion.churchToInt ... | |
const int int_five = conversion::churchToInt<five>::value; | |
const int int_three = conversion::churchToInt<three>::value; | |
const int int_mul_5_3 = conversion::churchToInt<mul_5_3>::value; | |
const int int_sum_5_3 = conversion::churchToInt<sum_5_3>::value; | |
int main() { | |
std::cout << int_five << " * " << int_three << " = " << int_mul_5_3 << std::endl; | |
std::cout << int_five << " + " << int_three << " = " << int_sum_5_3 << std::endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Результат исполнения: