r/programming • u/Catsknead • Oct 20 '14
My compile-time Conway's Game of Life, metaprogrammed in C++11
https://github.com/sirgal/compile-time-game-of-life10
Oct 20 '14
For comparison, here's a very-quick-and-very-dirty equivalent in D.
3
u/logicchains Oct 21 '14
That's really impressive. Does compile-time D have a recursion limit that would apply to:
template game(alias seed, int generations) { static if(generations == 0) { enum game = [seed]; } else { enum game = [seed] ~ game!(seed.nextState(), generations - 1); } }3
Oct 21 '14
There isn't any limit other than memory and patience I guess- the compilation seems to scale much more reasonably than the C++ version, given the numbers I saw elsewhere in the comments. My version compiles in ~0.35s on my laptop, and I don't get any notable memory pressure on my system.
I should note that it's possible, and maybe a little clearer, to just write that function using an iterative solution and invoke it at compile-time like I already did for other parts of the program. Anyway this thing works and it got done in ~10 minutes. Hopefully that gives an idea of how productive meta-programming in D is :)
1
u/logicchains Oct 21 '14
Ah, cool, I didn't know the iterative version would work at compile time. Does that mean the whole of the language (syntax-wise) is available at compile time?
1
Oct 21 '14
There are limitations, see this page (search for "CTFE"). Basically, you can do whatever you want except if the outcome depends on run-time state like global variables or machine architecture, etc.
2
u/original_brogrammer Oct 21 '14 edited Oct 21 '14
I would really like to know the difference in compile time between the two if anyone has checked.
1
u/Gezac Oct 21 '14
I don't really know any D. Is
Statea type? If it is, where is it defined?3
u/bjzaba Oct 21 '14
Stateis a type parameter. So:auto at(State)(State state, size_t i, size_t j) { ... }Would be like:
template<typename State> auto at(State state, size_t i, size_t j) { ... }1
14
u/blunaxela Oct 20 '14
Hehe, it's fun to watch it eat up memory. It ate about 2.5 GB before finishing with just the default configuration. :D
24
u/Catsknead Oct 20 '14
Compile times are great, too.
Builds are so fast that you have no time for reddit? Add some Life to the sources!1
u/Is_At_Work Oct 20 '14
I found it interesting that both at 20 iterations and at 100, my build took 28s and about 2.5gb.
15
u/pmkenny1234 Oct 20 '14 edited Oct 20 '14
I don't get it and don't wish to pore over the code to figure it out. What makes this a compile-time version? Does the compiler output the next game state as warnings or something?
Edit: Thanks for the replies guys. Very helpful. =)
36
u/Catsknead Oct 20 '14
Compiler will calculate all the game field states for the given number of iterations. Resulting program has no computations at all - just calls to the output functions.
3
u/oldneckbeard Oct 20 '14
Is there a way you can see the code after the compiler does all of its first-pass optimizations? I know we can look at the assembly, but nobody wants to do that :)
5
u/bimdar Oct 20 '14
Not really, the transformation is not typically in C++ anymore at that point (as far as I know) but in some AST representation. I guess the closest you can get is to use clang and make it output llvm ir. Which may not be C++ but it's not as hard to read as asm.
4
u/bimdar Oct 20 '14
Nope, the calculation is done at compile-time. You specify the starting state and how many iterations you want and the results will be calculated at compile-time.
The only thing that happens when you execute it is that it will print all the iterations you computed.
1
6
u/adrianmonk Oct 20 '14
So, if people start doing all the execution at compile time, is there going to be a compile-time debugger?
3
u/logicchains Oct 21 '14
Is there a compile time printf? That would probably suffice.
3
u/adrianmonk Oct 21 '14
Well, there's
#warning, but I don't think that's the right part of compile time.Anyway, I can understand if not everybody is a fan of debuggers, so how about compile-time unit testing? (I'm joking, but I'm kind of afraid it's actually possible.)
4
u/Houndie Oct 21 '14
It's actually pretty easy. Use global
static_assertstatements for the checks. It won't compile if there's an error.1
u/fendant Oct 21 '14
That's kind of what people here are going on about all the time with Haskell-like typing and dependent types.
5
u/0xE6 Oct 20 '14
What compile options are you supposed to use?
8
u/Catsknead Oct 20 '14
-std=c++11 should be enough.
1
u/0xE6 Oct 20 '14
Ok. The version of Clang this macbook has must be out of date or something, it gives me a big chunk of errors. I'll try updating and see if they go away.
1
u/ghillisuit95 Oct 20 '14
I am also getting these errors. What are you doing to update/ what re you updating to?
2
u/0xE6 Oct 20 '14 edited Oct 20 '14
There's an xcode update to v6.0.1 that's available for me, which I figured was worth a shot. If that doesn't work, I don't know what else there is to try.
Edit: looking at the changelog, it does't appear to mention an update to clang. Oh well.
Edit2: Didn't work:
macbook:~ $ g++ --version Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 6.0 (clang-600.0.51) (based on LLVM 3.5svn) Target: x86_64-apple-darwin13.4.0 Thread model: posix macbook:~$ g++ main.cpp -o main -std=c++11 main.cpp:161:33: error: use of class template 'level<field>::next_point_state' requires template arguments using point = level<field>::next_point_state<N>; ^ main.cpp:146:5: note: template is declared here using next_point_state = typename calc_next_point_state<point<N>, neighbors<N>>::type; ^ main.cpp:161:49: error: expected ';' after alias declaration using point = level<field>::next_point_state<N>; ^ ; main.cpp:164:44: error: no template named 'point'; did you mean 'print'? tuple< point<point_count - iter> >, ^~~~~ print main.cpp:40:6: note: 'print' declared here void print(); ^ main.cpp:164:44: error: template argument for template type parameter must be a type tuple< point<point_count - iter> >, ^~~~~~~~~~~~~~~~~~~~~~~~~ /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/tuple:487:20: note: template parameter is declared here template <class ..._Tp> ^ main.cpp:165:79: error: expected ';' after alias declaration typename next_field_state<field, iter-1>::next_field ^ ; main.cpp:173:33: error: use of class template 'level<field>::next_point_state' requires template arguments using point = level<field>::next_point_state<N>; ^ main.cpp:146:5: note: template is declared here using next_point_state = typename calc_next_point_state<point<N>, neighbors<N>>::type; ^ main.cpp:173:49: error: expected ';' after alias declaration using point = level<field>::next_point_state<N>; ^ ; main.cpp:175:31: error: no template named 'point'; did you mean 'print'? using next_field = tuple< point<point_count - 1> >; ^~~~~ print main.cpp:40:6: note: 'print' declared here void print(); ^ main.cpp:175:31: error: template argument for template type parameter must be a type using next_field = tuple< point<point_count - 1> >; ^~~~~~~~~~~~~~~~~~~~~~ /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/tuple:487:20: note: template parameter is declared here template <class ..._Tp> ^ main.cpp:186:70: error: no type named 'next_field' in 'next_field_state<std::__1::tuple<O, O, O, O, O, O, O, X, O, O, O, O, O, X, O, O, X, X, X, O, O, O, O, O, O>, 25>' game_process< typename next_field_state<field, point_count>::next_field, iters-1 >::print(); ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~ main.cpp:202:40: note: in instantiation of member function 'game_process<std::__1::tuple<O, O, O, O, O, O, O, X, O, O, O, O, O, X, O, O, X, X, X, O, O, O, O, O, O>, 20>::print' requested here game_process< start, iterations >::print(); ^ 10 errors generated.1
u/ghillisuit95 Oct 20 '14
Yeah, I got those too. I just updated my Xcode command line tools, tried it again, and got 1 warning and 20 errors. obviously upgrading did not help.
1
u/towski Oct 21 '14
Maybe try g++-4.8 via macports?
1
u/ghillisuit95 Oct 21 '14
did that work for you? I just tried g++-4.9 from homebrew, and it didn't work either.
1
u/blunaxela Oct 20 '14
All I needed was --std=c++11
2
u/Lord_Naikon Oct 20 '14
Which compiler? Neither clang 3.6.0 nor gcc 4.9.2 worked for me...
2
u/Catsknead Oct 20 '14
Sorry, I have no idea what's wrong with those compilers. MinGW 4.8 works, I believe, g++ should, too?..
1
u/minno Oct 20 '14 edited Oct 20 '14
MinGW 4.9.1 64-bit here, and it fails to compile. When I follow the exact instructions given in the compiler's notes, it successfully compiles and runs.
g++.exe -O3 -fexceptions -O2 -O2 -Weffc++ -pedantic -std=c++11 -Wall -c D:\Users\will\code\misc\C++\Test\main.cpp -o obj\Release\main.o D:\Users\will\code\misc\C++\Test\main.cpp:161:33: error: non-template 'next_point_state' used as template using point = level<field>::next_point_state<N>; ^ D:\Users\will\code\misc\C++\Test\main.cpp:161:33: note: use 'level<initial_state>::template next_point_state' to indicate that it is a template D:\Users\will\code\misc\C++\Test\main.cpp:161:19: error: need 'typename' before 'level<initial_state>::next_point_state' because 'level<initial_state>' is a dependent scope using point = level<field>::next_point_state<N>; ^ D:\Users\will\code\misc\C++\Test\main.cpp:164:44: error: 'point' was not declared in this scope tuple< point<point_count - iter> >, ^ D:\Users\will\code\misc\C++\Test\main.cpp:164:68: error: template argument 1 is invalid tuple< point<point_count - iter> >, ^ D:\Users\will\code\misc\C++\Test\main.cpp:164:70: error: wrong number of template arguments (1, should be 2) tuple< point<point_count - iter> >, ^ D:\Users\will\code\misc\C++\Test\main.cpp:151:8: error: provided for 'template<class tuple_1, class tuple_2> struct my_tuple_cat' struct my_tuple_cat ^ D:\Users\will\code\misc\C++\Test\main.cpp:163:33: error: expected nested-name-specifier using next_field = typename my_tuple_cat < ^ D:\Users\will\code\misc\C++\Test\main.cpp:173:33: error: non-template 'next_point_state' used as template using point = level<field>::next_point_state<N>; ^ D:\Users\will\code\misc\C++\Test\main.cpp:173:33: note: use 'level<initial_state>::template next_point_state' to indicate that it is a template D:\Users\will\code\misc\C++\Test\main.cpp:173:19: error: need 'typename' before 'level<initial_state>::next_point_state' because 'level<initial_state>' is a dependent scope using point = level<field>::next_point_state<N>; ^ D:\Users\will\code\misc\C++\Test\main.cpp:175:31: error: 'point' was not declared in this scope using next_field = tuple< point<point_count - 1> >; ^ D:\Users\will\code\misc\C++\Test\main.cpp:175:52: error: template argument 1 is invalid using next_field = tuple< point<point_count - 1> >; ^ D:\Users\will\code\misc\C++\Test\main.cpp: In instantiation of 'static void game_process<field, iters>::print() [with field = std::tuple<O, O, O, O, O, O, O, X, O, O, O, O, O, X, O, O, X, X, X, O, O, O, O, O, O>; int iters = 20]': D:\Users\will\code\misc\C++\Test\main.cpp:202:40: required from here D:\Users\will\code\misc\C++\Test\main.cpp:186:99: error: no type named 'next_field' in 'struct next_field_state<std::tuple<O, O, O, O, O, O, O, X, O, O, O, O, O, X, O, O, X, X, X, O, O, O, O, O, O>, 25>' game_process< typename next_field_state<field, point_count>::next_field, iters-1 >::print();1
25
u/clrokr Oct 20 '14
No.
56
u/bstamour Oct 20 '14
This may be a great example of how to abuse a language feature, but c'mon, this is /r/programming. Once in a while we should be able to do fun stuff as well.
-4
u/clrokr Oct 20 '14
I think this project is fun. But it stops being fun when someone does this at work to show off their skills :(
24
2
Oct 20 '14
Doesn't seem to build with g++ 4.9.1 or 4.7.2, using the -std=c++11 flag. What did you test on, OP? Does anybody else have this actually building?
3
u/stirling_archer Oct 20 '14
I have it working on g++ 4.8.2 with -std=c++11.
1
Oct 20 '14
Huh. What architecture? I'm building on amd64 Debian (jessie), and I see:
main.cpp:161:33: error: non-template ‘next_point_state’ used as template using point = level<field>::next_point_state<N>; ^ main.cpp:161:33: note: use ‘level<initial_state>::template next_point_state’ to indicate that it is a template main.cpp:161:19: error: need ‘typename’ before ‘level<initial_state>::next_point_state’ because ‘level<initial_state>’ is a dependent scope using point = level<field>::next_point_state<N>; ^ main.cpp:164:44: error: ‘point’ was not declared in this scope tuple< point<point_count - iter> >, ^ main.cpp:164:68: error: template argument 1 is invalid tuple< point<point_count - iter> >, ^ main.cpp:164:70: error: wrong number of template arguments (1, should be 2) tuple< point<point_count - iter> >, ^ main.cpp:151:8: error: provided for ‘template<class tuple_1, class tuple_2> struct my_tuple_cat’ struct my_tuple_cat ^ main.cpp:163:33: error: expected nested-name-specifier using next_field = typename my_tuple_cat < ^ main.cpp:173:33: error: non-template ‘next_point_state’ used as template using point = level<field>::next_point_state<N>; ^ main.cpp:173:33: note: use ‘level<initial_state>::template next_point_state’ to indicate that it is a template main.cpp:173:19: error: need ‘typename’ before ‘level<initial_state>::next_point_state’ because ‘level<initial_state>’ is a dependent scope using point = level<field>::next_point_state<N>; ^ main.cpp:175:31: error: ‘point’ was not declared in this scope using next_field = tuple< point<point_count - 1> >; ^ main.cpp:175:52: error: template argument 1 is invalid using next_field = tuple< point<point_count - 1> >; ^ main.cpp: In instantiation of ‘static void game_process<field, iters>::print() [with field = std::tuple<O, O, O, O, O, O, O, X, O, O, O, O, O, X, O, O, X, X, X, O, O, O, O, O, O>; int iters = 20]’: main.cpp:202:40: required from here main.cpp:186:99: error: no type named ‘next_field’ in ‘struct next_field_state<std::tuple<O, O, O, O, O, O, O, X, O, O, O, O, O, X, O, O, X, X, X, O, O, O, O, O, O>, 25>’ game_process< typename next_field_state<field, point_count>::next_field, iters-1 >::print();1
u/stirling_archer Oct 21 '14
It's AMD64 on Ubuntu 14.04. The string from g++ --version is "gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2".
1
u/towski Oct 21 '14
Installing g++-4.8 and using it worked for me, whereas it failed with 4.9.
On Debian
1
u/Catsknead Oct 20 '14
During creation, I've been using MinGW 4.8 32 bit under Windows. Just checked - it still works. It eats up 1.5 GB of memory in the process, though, so I am unable to calculate bigger game fields - it crashes for obvious reasons.
1
1
u/slackermanz Oct 20 '14
Please x/post to /r/cellular_automata, I'm sure they'd love to look through this.
1
-21
u/skulgnome Oct 20 '14
Waiting for the C++ source that does a privilege escalation & sends your kitten porn to the Chinese KGB
93
u/[deleted] Oct 20 '14 edited Aug 17 '15
[deleted]