fork(9) download
  1. #include <iostream>
  2.  
  3. #pragma mark - Tape
  4.  
  5. constexpr int Blank = -1;
  6.  
  7. template<int... xs>
  8. class Tape {
  9. public:
  10. using type = Tape<xs...>;
  11. constexpr static int length = sizeof...(xs);
  12. };
  13.  
  14. #pragma mark - Print
  15.  
  16. template<class T>
  17. void print(T);
  18.  
  19. template<>
  20. void print(Tape<>) {
  21. std::cout << std::endl;
  22. }
  23.  
  24. template<int x, int... xs>
  25. void print(Tape<x, xs...>) {
  26. if (x == Blank) {
  27. std::cout << "_ ";
  28. } else {
  29. std::cout << x << " ";
  30. }
  31. print(Tape<xs...>());
  32. }
  33.  
  34. #pragma mark - Concatenate
  35.  
  36. template<class, class>
  37. class Concatenate;
  38.  
  39. template<int... xs, int... ys>
  40. class Concatenate<Tape<xs...>, Tape<ys...>> {
  41. public:
  42. using type = Tape<xs..., ys...>;
  43. };
  44.  
  45. #pragma mark - Invert
  46.  
  47. template<class>
  48. class Invert;
  49.  
  50. template<>
  51. class Invert<Tape<>> {
  52. public:
  53. using type = Tape<>;
  54. };
  55.  
  56. template<int x, int... xs>
  57. class Invert<Tape<x, xs...>> {
  58. public:
  59. using type = typename Concatenate<
  60. typename Invert<Tape<xs...>>::type,
  61. Tape<x>
  62. >::type;
  63. };
  64.  
  65. #pragma mark - Read
  66.  
  67. template<int, class>
  68. class Read;
  69.  
  70. template<int n, int x, int... xs>
  71. class Read<n, Tape<x, xs...>> {
  72. public:
  73. using type = typename std::conditional<
  74. (n == 0),
  75. std::integral_constant<int, x>,
  76. Read<n - 1, Tape<xs...>>
  77. >::type::type;
  78. };
  79.  
  80. #pragma mark - N first and N last
  81.  
  82. template<int, class>
  83. class NLast;
  84.  
  85. template<int n, int x, int... xs>
  86. class NLast<n, Tape<x, xs...>> {
  87. public:
  88. using type = typename std::conditional<
  89. (n == sizeof...(xs)),
  90. Tape<xs...>,
  91. NLast<n, Tape<xs...>>
  92. >::type::type;
  93. };
  94.  
  95. template<int, class>
  96. class NFirst;
  97.  
  98. template<int n, int... xs>
  99. class NFirst<n, Tape<xs...>> {
  100. public:
  101. using type = typename Invert<
  102. typename NLast<
  103. n, typename Invert<Tape<xs...>>::type
  104. >::type
  105. >::type;
  106. };
  107.  
  108. #pragma mark - Write
  109.  
  110. template<int, int, class>
  111. class Write;
  112.  
  113. template<int pos, int x, int... xs>
  114. class Write<pos, x, Tape<xs...>> {
  115. public:
  116. using type = typename Concatenate<
  117. typename Concatenate<
  118. typename NFirst<pos, Tape<xs...>>::type,
  119. Tape<x>
  120. >::type,
  121. typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type
  122. >::type;
  123. };
  124.  
  125. #pragma mark - Move
  126.  
  127. template<int, class>
  128. class Hold;
  129.  
  130. template<int pos, int... xs>
  131. class Hold<pos, Tape<xs...>> {
  132. public:
  133. constexpr static int position = pos;
  134. using tape = Tape<xs...>;
  135. };
  136.  
  137. template<int, class>
  138. class Left;
  139.  
  140. template<int pos, int... xs>
  141. class Left<pos, Tape<xs...>> {
  142. public:
  143. constexpr static int position = typename std::conditional<
  144. (pos > 0),
  145. std::integral_constant<int, pos - 1>,
  146. std::integral_constant<int, 0>
  147. >::type();
  148.  
  149. using tape = typename std::conditional<
  150. (pos > 0),
  151. Tape<xs...>,
  152. Tape<Blank, xs...>
  153. >::type;
  154. };
  155.  
  156. template<int, class>
  157. class Right;
  158.  
  159. template<int pos, int... xs>
  160. class Right<pos, Tape<xs...>> {
  161. public:
  162. constexpr static int position = pos + 1;
  163.  
  164. using tape = typename std::conditional<
  165. (pos < sizeof...(xs) - 1),
  166. Tape<xs...>,
  167. Tape<xs..., Blank>
  168. >::type;
  169. };
  170.  
  171. #pragma mark - States
  172.  
  173. template <int>
  174. class Stop {
  175. public:
  176. constexpr static int write = -1;
  177. template<int pos, class tape> using move = Hold<pos, tape>;
  178. template<int x> using next = Stop<x>;
  179. };
  180.  
  181. #define ADD_STATE(_state_) \
  182. template<int> \
  183. class _state_ { };
  184.  
  185. #define ADD_RULE(_state_, _read_, _write_, _move_, _next_) \
  186. template<> \
  187. class _state_<_read_> { \
  188. public: \
  189.   constexpr static int write = _write_; \
  190.   template<int pos, class tape> using move = _move_<pos, tape>; \
  191.   template<int x> using next = _next_<x>; \
  192. };
  193.  
  194. #pragma mark - Machine
  195.  
  196. template<template<int> class, int, class>
  197. class Machine;
  198.  
  199. template<template<int> class State, int pos, int... xs>
  200. class Machine<State, pos, Tape<xs...>> {
  201. constexpr static int symbol = typename Read<pos, Tape<xs...>>::type();
  202. using state = State<symbol>;
  203.  
  204. template<int x>
  205. using nextState = typename State<symbol>::template next<x>;
  206.  
  207. using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type;
  208. using move = typename state::template move<pos, modifiedTape>;
  209.  
  210. constexpr static int nextPos = move::position;
  211. using nextTape = typename move::tape;
  212.  
  213. public:
  214. using step = Machine<nextState, nextPos, nextTape>;
  215. };
  216.  
  217. #pragma mark - Run
  218.  
  219. template<class>
  220. class Run;
  221.  
  222. template<template<int> class State, int pos, int... xs>
  223. class Run<Machine<State, pos, Tape<xs...>>> {
  224. using step = typename Machine<State, pos, Tape<xs...>>::step;
  225.  
  226. public:
  227. using type = typename std::conditional<
  228. std::is_same<State<0>, Stop<0>>::value,
  229. Tape<xs...>,
  230. Run<step>
  231. >::type::type;
  232. };
  233.  
  234. ADD_STATE(A);
  235. ADD_STATE(B);
  236. ADD_STATE(C);
  237. ADD_STATE(D);
  238.  
  239. ADD_RULE(A, Blank, 1, Right, B);
  240. ADD_RULE(A, 1, 1, Left, B);
  241.  
  242. ADD_RULE(B, Blank, 1, Left, A);
  243. ADD_RULE(B, 1, Blank, Left, C);
  244.  
  245. ADD_RULE(C, Blank, 1, Right, Stop);
  246. ADD_RULE(C, 1, 1, Left, D);
  247.  
  248. ADD_RULE(D, Blank, 1, Right, D);
  249. ADD_RULE(D, 1, Blank, Right, A);
  250.  
  251. using tape = Tape<Blank>;
  252. using machine = Machine<A, 0, tape>;
  253. using result = Run<machine>::type;
  254.  
  255. int main() {
  256. print(result());
  257. return 0;
  258. }
  259.  
Success #stdin #stdout 0s 3460KB
stdin
Standard input is empty
stdout
1 _ 1 1 1 1 1 1 1 1 1 1 1 1