Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save jmikedupont2/e0426221b24e63332d835b4652787c1a to your computer and use it in GitHub Desktop.
Save jmikedupont2/e0426221b24e63332d835b4652787c1a to your computer and use it in GitHub Desktop.
The only escape is
// untested ai generated from https://stackoverflow.com/a/275295/7026063
#include <iostream>
#include <ostream>
// Conditional template
template<bool C, typename A, typename B>
struct Conditional {
typedef A type;
};
template<typename A, typename B>
struct Conditional<false, A, B> {
typedef B type;
};
// EnableIf template
template<bool C, typename = void>
struct EnableIf { };
template<typename Type>
struct EnableIf<true, Type> {
typedef Type type;
};
// Identity template
template<typename T>
struct Identity {
typedef T type;
};
// TypeList template
template<typename...>
struct TypeList;
template<typename T, typename... TT>
struct TypeList<T, TT...> {
typedef T type;
typedef TypeList<TT...> tail;
};
template<>
struct TypeList<> { };
// GetSize template
template<typename List>
struct GetSize;
template<typename... Items>
struct GetSize<TypeList<Items...>> {
enum { value = sizeof...(Items) };
};
// AppendItem template
template<typename NewItem, typename List>
struct AppendItem;
template<typename NewItem, typename... Items>
struct AppendItem<NewItem, TypeList<Items...>> {
typedef TypeList<Items..., NewItem> type;
};
// PrependItem template
template<typename NewItem, typename List>
struct PrependItem;
template<typename NewItem, typename... Items>
struct PrependItem<NewItem, TypeList<Items...>> {
typedef TypeList<NewItem, Items...> type;
};
// GetItem template
template<typename List, int N, typename = void>
struct GetItem {
static_assert(N >= 0, "index cannot be negative");
static_assert(GetSize<List>::value > 0, "index too high");
typedef typename GetItem<typename List::tail, N-1>::type type;
};
template<typename List>
struct GetItem<List, 0> {
static_assert(GetSize<List>::value > 0, "index too high");
typedef typename List::type type;
};
// ReplaceItem template
template<typename List, int I, typename NewItem>
struct ReplaceItem {
static_assert(I >= 0, "index cannot be negative");
static_assert(GetSize<List>::value > 0, "index too high");
typedef typename PrependItem<typename List::type,
typename ReplaceItem<typename List::tail, I-1, NewItem>::type>
::type type;
};
template<typename NewItem, typename Type, typename... T>
struct ReplaceItem<TypeList<Type, T...>, 0, NewItem> {
typedef TypeList<NewItem, T...> type;
};
// FindItem template
template<typename List, template<typename, typename...> class Matcher, typename... Keys>
struct FindItem {
static_assert(GetSize<List>::value > 0, "Could not match any item.");
typedef typename List::type current_type;
typedef typename Conditional<Matcher<current_type, Keys...>::value,
Identity<current_type>,
FindItem<typename List::tail, Matcher, Keys...>>
::type::type type;
};
// Direction enum
enum Direction {
Left = -1,
Right = 1
};
// Rule template
template<typename OldState, typename Input, typename NewState, typename Output, Direction Move>
struct Rule {
typedef OldState old_state;
typedef Input input;
typedef NewState new_state;
typedef Output output;
static Direction const direction = Move;
};
// IsSame template
template<typename A, typename B>
struct IsSame {
enum { value = false };
};
template<typename A>
struct IsSame<A, A> {
enum { value = true };
};
// Configuration template
template<typename Input, typename State, int Position>
struct Configuration {
typedef Input input;
typedef State state;
enum { position = Position };
};
// Max template
template<int A, int B>
struct Max {
enum { value = A > B ? A : B };
};
// State template
template<int n>
struct State {
enum { value = n };
static char const* name;
};
template<int n>
char const* State<n>::name = "unnamed";
// QAccept and QReject states
struct QAccept {
enum { value = -1 };
static char const* name;
};
struct QReject {
enum { value = -2 };
static char const* name;
};
char const* QAccept::name = "qaccept";
char const* QReject::name = "qreject";
#define DEF_STATE(ID, NAME) \
typedef State<ID> NAME; \
template<> char const* State<ID>::name = #NAME;
// Input template
template<int n>
struct Input {
enum { value = n };
static char const* name;
template<int... I>
struct Generate {
typedef TypeList<Input<I>...> type;
};
};
template<int n>
char const* Input<n>::name = "unnamed";
typedef Input<-1> InputBlank;
template<> char const* Input<-1>::name = "_";
#define DEF_INPUT(ID, NAME) \
typedef Input<ID> NAME; \
template<> char const* Input<ID>::name = #NAME;
// Controller template
template<typename Config, typename Transitions, typename = void>
struct Controller {
typedef Config config;
enum { position = config::position };
typedef typename Conditional<
static_cast<int>(GetSize<typename config::input>::value) <= static_cast<int>(position),
AppendItem<InputBlank, typename config::input>,
Identity<typename config::input>>::type::type input;
typedef typename config::state state;
typedef typename GetItem<input, position>::type cell;
template<typename Item, typename State, typename Cell>
struct Matcher {
typedef typename Item::old_state checking_state;
typedef typename Item::input checking_input;
enum { value = IsSame<State, checking_state>::value &&
IsSame<Cell, checking_input>::value };
};
typedef typename FindItem<Transitions, Matcher, state, cell>::type rule;
typedef typename ReplaceItem<input, position, typename rule::output>::type new_input;
typedef typename rule::new_state new_state;
typedef Configuration<new_input, new_state, Max<position + rule::direction, 0>::value> new_config;
typedef Controller<new_config, Transitions> next_step;
typedef typename next_step::end_config end_config;
typedef typename next_step::end_input end_input;
typedef typename next_step::end_state end_state;
enum { end_position = next_step::end_position };
};
// Controller specialization for accept/reject states
template<typename Input, typename State, int Position, typename Transitions>
struct Controller<Configuration<Input, State, Position>, Transitions,
typename EnableIf<IsSame<State, QAccept>::value ||
IsSame<State, QReject>::value>::type> {
typedef Configuration<Input, State, Position> config;
enum { position = config::position };
typedef typename Conditional<
static_cast<int>(GetSize<typename config::input>::value) <= static_cast<int>(position),
AppendItem<InputBlank, typename config::input>,
Identity<typename config::input>>::type::type input;
typedef typename config::state state;
typedef config end_config;
typedef input end_input;
typedef state end_state;
enum { end_position = position };
};
// TuringMachine template
template<typename Input, typename Transitions, typename StartState>
struct TuringMachine {
typedef Input input;
typedef Transitions transitions;
typedef StartState start_state;
typedef Controller<Configuration<Input, StartState, 0>, Transitions> controller;
typedef typename controller::end_config end_config;
typedef typename controller::end_input end_input;
typedef typename controller::end_state end_state;
enum { end_position = controller::end_position };
};
// Helper to print TypeList
template<typename List>
struct PrintList {
static void print(std::ostream& os) {
if constexpr (GetSize<List>::value > 0) {
os << List::type::name;
if constexpr (GetSize<typename List::tail>::value > 0) {
PrintList<typename List::tail>::print(os);
}
}
}
};
// Define inputs for each character in the string
DEF_INPUT(1, T);
DEF_INPUT(2, h);
DEF_INPUT(3, e);
DEF_INPUT(4, _); // Space (distinct from InputBlank)
DEF_INPUT(5, o);
DEF_INPUT(6, n);
DEF_INPUT(7, l);
DEF_INPUT(8, y);
DEF_INPUT(9, s);
DEF_INPUT(10, c);
DEF_INPUT(11, a);
DEF_INPUT(12, p);
DEF_INPUT(13, f);
DEF_INPUT(14, r);
DEF_INPUT(15, m);
DEF_INPUT(16, C);
DEF_INPUT(17, plus);
DEF_INPUT(18, i);
DEF_INPUT(19, M);
DEF_INPUT(20, t);
DEF_INPUT(21, P);
DEF_INPUT(22, g);
// Define states
DEF_STATE(0, Start);
DEF_STATE(1, Write_T);
DEF_STATE(2, Write_h);
DEF_STATE(3, Write_e);
DEF_STATE(4, Write_o);
DEF_STATE(5, Write_n);
DEF_STATE(6, Write_l);
DEF_STATE(7, Write_y);
DEF_STATE(8, Write_s);
DEF_STATE(9, Write_c);
DEF_STATE(10, Write_a);
DEF_STATE(11, Write_p);
DEF_STATE(12, Write_f);
DEF_STATE(13, Write_r);
DEF_STATE(14, Write_m);
DEF_STATE(15, Write_C);
DEF_STATE(16, Write_plus1);
DEF_STATE(17, Write_plus2);
DEF_STATE(18, Write_i);
DEF_STATE(19, Write_s2);
DEF_STATE(20, Write_T2);
DEF_STATE(21, Write_e2);
DEF_STATE(22, Write_m2);
DEF_STATE(23, Write_p2);
DEF_STATE(24, Write_l2);
DEF_STATE(25, Write_a2);
DEF_STATE(26, Write_t3);
DEF_STATE(27, Write_e3);
DEF_STATE(28, Write_M);
DEF_STATE(29, Write_e4);
DEF_STATE(30, Write_t4);
DEF_STATE(31, Write_a3);
DEF_STATE(32, Write_P);
DEF_STATE(33, Write_r2);
DEF_STATE(34, Write_o2);
DEF_STATE(35, Write_g);
DEF_STATE(36, Write_r3);
DEF_STATE(37, Write_a4);
DEF_STATE(38, Write_m3);
DEF_STATE(39, Write_i2);
DEF_STATE(40, Write_n2);
DEF_STATE(41, Write_g2);
// Define transitions
typedef TypeList<
// Write "The only escape from C++ is TemplateMetaProgramming"
Rule<Start, InputBlank, Write_T, T, Right>,
Rule<Write_T, InputBlank, Write_h, h, Right>,
Rule<Write_h, InputBlank, Write_e, e, Right>,
Rule<Write_e, InputBlank, Write_, _, Right>,
Rule<Write_, InputBlank, Write_o, o, Right>,
Rule<Write_o, InputBlank, Write_n, n, Right>,
Rule<Write_n, InputBlank, Write_l, l, Right>,
Rule<Write_l, InputBlank, Write_y, y, Right>,
Rule<Write_y, InputBlank, Write_, _, Right>,
Rule<Write_, InputBlank, Write_e, e, Right>, // Second 'e'
Rule<Write_e, InputBlank, Write_s, s, Right>,
Rule<Write_s, InputBlank, Write_c, c, Right>,
Rule<Write_c, InputBlank, Write_a, a, Right>,
Rule<Write_a, InputBlank, Write_p, p, Right>,
Rule<Write_p, InputBlank, Write_e, e, Right>, // Third 'e'
Rule<Write_e, InputBlank, Write_, _, Right>,
Rule<Write_, InputBlank, Write_f, f, Right>,
Rule<Write_f, InputBlank, Write_r, r, Right>,
Rule<Write_r, InputBlank, Write_o, o, Right>, // Second 'o'
Rule<Write_o, InputBlank, Write_m, m, Right>,
Rule<Write_m, InputBlank, Write_, _, Right>,
Rule<Write_, InputBlank, Write_C, C, Right>,
Rule<Write_C, InputBlank, Write_plus1, plus, Right>,
Rule<Write_plus1, InputBlank, Write_plus2, plus, Right>,
Rule<Write_plus2, InputBlank, Write_, _, Right>,
Rule<Write_, InputBlank, Write_i, i, Right>,
Rule<Write_i, InputBlank, Write_s, s, Right>, // Second 's'
Rule<Write_s, InputBlank, Write_, _, Right>,
Rule<Write_, InputBlank, Write_T2, T, Right>, // Second 'T'
Rule<Write_T2, InputBlank, Write_e2, e, Right>, // Fourth 'e'
Rule<Write_e2, InputBlank, Write_m2, m, Right>, // Second 'm'
Rule<Write_m2, InputBlank, Write_p2, p, Right>, // Second 'p'
Rule<Write_p2, InputBlank, Write_l2, l, Right>, // Second 'l'
Rule<Write_l2, InputBlank, Write_a2, a, Right>, // Third 'a'
Rule<Write_a2, InputBlank, Write_t3, t, Right>,
Rule<Write_t3, InputBlank, Write_e3, e, Right>, // Fifth 'e'
Rule<Write_e3, InputBlank, Write_M, M, Right>,
Rule<Write_M, InputBlank, Write_e4, e, Right>, // Sixth 'e'
Rule<Write_e4, InputBlank, Write_t4, t, Right>, // Second 't'
Rule<Write_t4, InputBlank, Write_a3, a, Right>, // Fourth 'a'
Rule<Write_a3, InputBlank, Write_P, P, Right>,
Rule, InputBlank, Write_r2, r, Right>, // Second 'r'
Rule<Write_r2, InputBlank, Write_o2, o, Right>, // Third 'o'
Rule<Write_o2, InputBlank, Write_g, g, Right>,
Rule<Write_g, InputBlank, Write_r3, r, Right>, // Third 'r'
Rule<Write_r3, InputBlank, Write_a4, a, Right>, // Fifth 'a'
Rule<Write_a4, InputBlank, Write_m3, m, Right>, // Third 'm'
Rule<Write_m3, InputBlank, Write_i2, i, Right>, // Second 'i'
Rule<Write_i2, InputBlank, Write_n2, n, Right>, // Second 'n'
Rule<Write_n2, InputBlank, Write_g2, g, Right>, // Second 'g'
Rule<Write_g2, InputBlank, QAccept, InputBlank, Right>
> Rules;
// Define the Turing machine
typedef TuringMachine<TypeList<>, Rules, Start> StringWriter;
// Main function
int main() {
// Print the final tape
PrintList<StringWriter::end_input>::print(std::cout);
std::cout << std::endl;
// Verify the final state is QAccept
static_assert(IsSame<StringWriter::end_state, QAccept>::value, "Machine did not accept");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment