Skip to content

Instantly share code, notes, and snippets.

@mattbierner

mattbierner/life_comonadic.cpp

Created November 3, 2014 00:25
Show Gist options
  • Save mattbierner/bbd2d4d07772273029c2 to your computer and use it in GitHub Desktop.
Save mattbierner/bbd2d4d07772273029c2 to your computer and use it in GitHub Desktop.
Download ZIP
c++ Compile Time Comonaic Life
Raw
life_comonadic.cpp
/**
* Conway's game of life implemented in C++ templates at compile time using Comonads.
*
* Logic based on: http://blog.emillon.org/posts/2012-10-18-comonadic-life.html
*/
#include <iostream>
/// Identity functor
template <typename X>
struct id {
using type = X;
};
/// Create a meta functor that returns `X` when invoked with any argument.
template <typename X>
struct constant {
template <typename>
struct apply {
using type = X;
};
};
/// End of list marker type
struct Nil { };
/// Lazy list of values
template <typename head, template<typename> class get_rest>
struct List {
using first = head;
using rest = typename get_rest<head>::type;
};
/// Get head of list `L`.
template <typename L>
using car = typename L::first;
/// Get rest of list `L`.
template <typename L>
using cdr = typename L::rest;
// Prepend element `X` on to a list `L`.
template <typename X, typename L>
using cons = List<X, constant<L>::template apply>;
/// Create a list from a parameter pack.
template <typename...>
struct ListFromParams;
template <typename X, typename... XS>
struct ListFromParams<X, XS...> {
using type = cons<X, typename ListFromParams<XS...>::type>;
};
template <>
struct ListFromParams<> {
using type = Nil;
};
template <typename... elements>
using list_from_params = typename ListFromParams<elements...>::type;
/// Append list `L1` onto `L2`.
template <typename L1, typename L2>
struct ListConcat {
template <typename>
struct ConcatImpl {
using type = typename ListConcat<cdr<L1>, L2>::type;
};
using type = List<car<L1>, ConcatImpl>;
};
template <typename L2>
struct ListConcat<Nil, L2> {
using type = L2;
};
template <typename L1, typename L2>
using concat = typename ListConcat<L1, L2>::type;
/// Reverse a list.
template <typename L>
struct Reverse {
using type = concat<
typename Reverse<cdr<L>>::type,
cons<car<L>, Nil>>;
};
template<>
struct Reverse<Nil> {
using type = Nil;
};
template <typename L>
using reverse = typename Reverse<L>::type;
/// Create a list of at most `count` elements from list `L`.
template <size_t count, typename L>
struct ListTake {
template <typename>
struct TakeImpl {
using type = typename ListTake<count - 1, cdr<L>>::type;
};
using type = List<car<L>, TakeImpl>;
};
template <typename L>
struct ListTake<0, L> {
using type = Nil;
};
template <size_t count>
struct ListTake<count, Nil> {
using type = Nil;
};
template <size_t count, typename L>
using take = typename ListTake<count, L>::type;
/// Perform a map operation on a list
template <template<typename> class F, typename L>
struct ListMap {
template <typename>
struct MapImpl {
using type = typename ListMap<F, cdr<L>>::type;
};
using type = List<typename F<car<L>>::type, MapImpl>;
};
template <template<typename> class F>
struct ListMap<F, Nil> {
using type = Nil;
};
template <template<typename> class F, typename L>
using map = typename ListMap<F, L>::type;
///
template <template<typename> class F, typename X>
struct Iterate {
template <typename L>
struct IterateImpl {
using type = List<typename F<L>::type, ::Iterate<F, X>::IterateImpl>;
};
using type = List<X, IterateImpl>;
};
template <template<typename> class F, typename X>
using iterate = typename Iterate<F, X>::type;
/// Infinite list of values
template <typename X>
using gen = iterate<id, X>;
///
template <template<typename> class F, typename X>
using iterate_rest = cdr<iterate<F, X>>;
/// 1D list Zipper
template <typename z>
struct go_left {
using type = typename z::left;
};
template <typename z>
struct go_right {
using type = typename z::right;
};
template<typename L, typename X, typename R>
struct Zipper {
using left = Zipper<cdr<L>, car<L>, cons<X, R>>;
using right = Zipper<cons<X, L>, car<R>, cdr<R>>;
using get = X;
template <typename val>
using put = Zipper<L, val, R>;
template <template<typename> class F>
using fmap = Zipper<
map<F, L>,
typename F<X>::type,
map<F, R>>;
template <size_t count>
using to_list = concat<
reverse<take<count, L>>,
concat<
cons<X, Nil>,
take<count, R>>>;
};
template <
template<typename> class left_mapper,
template<typename> class right_mapper,
typename z>
using move = Zipper<
iterate_rest<left_mapper, z>,
z,
iterate_rest<right_mapper, z>>;
template <typename z>
using duplicate = move<go_left, go_right, z>;
template <template<typename> class f, typename z>
using fmap = typename z::template fmap<f>;
template <typename z>
using get = typename z::get;
template <typename z, typename x>
using put = typename z::template put<x>;
/// 2d plane Zipper
template <typename plane>
struct go_up {
using type = typename plane::up;
};
template <typename plane>
struct go_down {
using type = typename plane::down;
};
template<typename z>
struct PlaneZipper {
using up = PlaneZipper<typename z::left>;
using down = PlaneZipper<typename z::right>;
using left = PlaneZipper<fmap<go_left, z>>;
using right = PlaneZipper<fmap<go_right, z>>;
using get = get<get<z>>;
template <typename val>
using put = PlaneZipper<put<z, put<typename z::get, val>>>;
template <template<typename> class F>
struct do_fmap {
template <typename X>
struct apply {
using type = fmap<F, X>;
};
};
template <template<typename> class F>
using fmap = PlaneZipper<fmap<do_fmap<F>::template apply, z>>;
};
template <typename z>
using horizontal = move<go_left, go_right, z>;
template <typename z>
using vertical = move<go_up, go_down, z>;
template <typename z>
struct go_horizontal {
using type = horizontal<z>;
};
template <typename z>
using duplicatePlane = PlaneZipper<fmap<go_horizontal, vertical<z>>>;
template <template<typename> class F, typename z>
using extendPlane = fmap<F, duplicatePlane<z>>;
/// Single cell in life.
template <bool alive>
struct Cell {
static const bool value = alive;
};
using DeadCell = Cell<false>;
using LiveCell = Cell<true>;
/// Get the number of living neighbors to the focus of the plane Zipper `z`.
template <typename z>
struct living_neighbors_count {
template <typename neighbor>
struct get_weight {
enum { value = neighbor::get::value };
};
enum { value =
get_weight<typename z::left>::value +
get_weight<typename z::right>::value +
get_weight<typename z::up>::value +
get_weight<typename z::down>::value +
get_weight<typename z::left::up>::value +
get_weight<typename z::left::down>::value +
get_weight<typename z::right::up>::value +
get_weight<typename z::right::down>::value };
};
/// Rules for Conway's game of life.
template <typename world>
struct life_rule {
using living = living_neighbors_count<world>;
using type = typename std::conditional<living::value == 2,
typename world::get,
Cell<living::value == 3>>::type;
};
template <typename world>
struct evolve {
using type = extendPlane<life_rule, world>;
};
/// Game generation
using inf_dead_list = gen<DeadCell>;
using dead_row = Zipper<inf_dead_list, DeadCell, inf_dead_list>;
using inf_dead_rows = gen<dead_row>;
using dead_plane = Zipper<inf_dead_rows, dead_row, inf_dead_rows>;
template <typename... values>
using line = Zipper<
inf_dead_list,
DeadCell,
concat<
list_from_params<values...>,
inf_dead_list>>;
using glider =
PlaneZipper<
Zipper<
inf_dead_rows,
dead_row,
concat<
list_from_params<
line<DeadCell, LiveCell, DeadCell>,
line<DeadCell, DeadCell, LiveCell>,
line<LiveCell, LiveCell, LiveCell>>,
inf_dead_rows>>>;
/// Printer
template <typename>
struct Print;
template <>
struct Print<Cell<true>> {
static void Do() {
std::cout << "X";
}
};
template <>
struct Print<Cell<false>> {
static void Do() {
std::cout << "-";
}
};
template <typename x, template<typename> class xs>
struct Print<List<x, xs>> {
static void Do() {
Print<car<List<x, xs>>>::Do();
Print<cdr<List<x, xs>>>::Do();
}
};
template <>
struct Print<Nil> {
static void Do() { /* noop */ }
};
template <typename l, typename x, typename r>
struct Print<Zipper<l, x, r>> {
static void Do() {
Print<typename Zipper<l, x, r>::template to_list<5>>::Do();
std::cout << "\n";
}
};
template <typename z>
struct Print<PlaneZipper<z>> {
static void Do() {
Print<typename z::template to_list<5>>::Do();
std::cout << "\n";
}
};
int main(int argc, const char * argv[]) {
Print<take<3, iterate<evolve, glider>>>::Do();
return 0;
}
@malkia
Copy link

malkia commented Nov 13, 2014

With g++ 4.8.3 (GCC, on cygwin64) I had to use "g++ --std=c++11 -fpermissive life.cpp" to get it to compiler. It took a while :), but it worked!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment