From c15edae4532f53e7e5bac9dae125c360d93f848d Mon Sep 17 00:00:00 2001
From: Adrian Kummerlaender
Date: Sat, 21 Feb 2015 17:27:52 +0100
Subject: Separated Turing machine implementation into components * i.e.
 separate namespaces and headers for _Tape_ and _State_ functions * `void` is
 now used as the `BLANK` field value

---
 example/turing/src/machine.h                       |  98 +++++++++
 example/turing/src/state.h                         |  64 ++++++
 example/turing/src/tape.h                          |  46 ++++
 example/turing/turing.cc                           | 233 ++++-----------------
 .../generator/detail/generate_nested_structure.h   |   3 +
 src/list/operation/higher/find.h                   |   4 +-
 src/pair.h                                         |   2 +
 7 files changed, 250 insertions(+), 200 deletions(-)
 create mode 100644 example/turing/src/machine.h
 create mode 100644 example/turing/src/state.h
 create mode 100644 example/turing/src/tape.h

diff --git a/example/turing/src/machine.h b/example/turing/src/machine.h
new file mode 100644
index 0000000..2404d9a
--- /dev/null
+++ b/example/turing/src/machine.h
@@ -0,0 +1,98 @@
+#ifndef TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_
+#define TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_
+
+#include "conditional/cond.h"
+
+#include "state.h"
+#include "tape.h"
+
+namespace machine {
+
+// (define (simulate transition tape state position)
+//   (if (= state FINAL)
+//     tape
+//     (let* ((current_symbol (readSymbol position tape))
+//            (current_state  (transition state current_symbol))
+//            (direction      (nth MOVE  current_state))
+//            (next_symbol    (nth WRITE current_state))
+//            (next_state     (nth NEXT  current_state))
+//            (next_position  (cond ((= direction RIGHT) (+ position 1))
+//                                  ((= direction LEFT)  (- Position 1))
+//                                  (else                position))))
+//       (simulate transition
+//                 (writeSymbol position next_symbol tape)
+//                 next_state,
+//                 next_position)))
+template <
+	template<typename, typename> class Transition,
+	typename                           State,
+	typename                           Tape,
+	typename                           Position
+>
+class simulate {
+	private:
+		using current_symbol = tape::readSymbol<Position, Tape>;
+		using current_state  = Transition<State, current_symbol>;
+
+		using direction      = tav::Nth<state::field::MOVE,  current_state>;
+
+		using next_symbol    = tav::Nth<state::field::WRITE, current_state>;
+		using next_state     = tav::Nth<state::field::NEXT,  current_state>;
+		using next_position  = tav::Cond<
+			tav::Branch<
+				tav::IsEqualValue<direction, tav::Char<'R'>>,
+				tav::Add<Position, tav::Size<1>>
+			>,
+			tav::Branch<
+				tav::IsEqualValue<direction, tav::Char<'L'>>,
+				tav::Substract<Position, tav::Size<1>>
+			>,
+			tav::Else<
+				Position
+			>
+		>;
+
+		static_assert(
+			tav::Not<tav::LowerThan<next_position, tav::Size<0>>>::value,
+			"next position out of bounds"
+		);
+
+	public:
+		using type = tav::Eval<simulate<
+			Transition,
+			next_state,
+			tape::writeSymbol<Position, next_symbol, Tape>,
+			next_position
+		>>;
+};
+
+template <
+	template<typename, typename> class Transition,
+	typename                           Tape,
+	typename                           Position
+>
+struct simulate<Transition, void, Tape, Position> {
+	typedef Tape type;
+};
+
+// (define (run program state tape position)
+//   (simulate (transition program)
+//             tape
+//             state
+//             position))
+template <
+	typename Program,
+	typename State,
+	typename Tape,
+	typename Position
+>
+using run = tav::Eval<simulate<
+	state::transition<Program>::template state,
+	State,
+	Tape,
+	Position
+>>;
+
+}
+
+#endif // TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_
diff --git a/example/turing/src/state.h b/example/turing/src/state.h
new file mode 100644
index 0000000..f5bd7f2
--- /dev/null
+++ b/example/turing/src/state.h
@@ -0,0 +1,64 @@
+#ifndef TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_
+#define TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_
+
+#include "type.h"
+#include "list/list.h"
+#include "list/operation/higher/find.h"
+
+namespace machine {
+
+namespace state {
+
+struct field {
+	using ID    = tav::Size<0>;
+	using READ  = tav::Size<1>;
+	using WRITE = tav::Size<2>;
+	using NEXT  = tav::Size<3>;
+	using MOVE  = tav::Size<4>;
+};
+
+// (define (state_predicate id read)
+//   (lambda (state)
+//           (and (= id   (nth ID   state))
+//                (= read (nth READ state)))))
+template <
+	typename Id,
+	typename Read
+>
+struct state_predicate {
+	template <typename State>
+	using function = tav::And<
+		tav::IsEqualValue<Id,   tav::Nth<field::ID,   State>>,
+		tav::IsEqualValue<Read, tav::Nth<field::READ, State>>
+	>;
+};
+
+// (define (findState id read states)
+//   (find (state_predicate id read) states))
+template <
+	typename Id,
+	typename Read,
+	typename States
+>
+using findState = tav::Find<
+	state_predicate<Id, Read>::template function,
+	States
+>;
+
+// (define (transition states)
+//   (lambda (state symbol)
+//           (findState state symbol states)))
+template <typename States>
+struct transition {
+	template <
+		typename State,
+		typename Symbol
+	>
+	using state = findState<State, Symbol, States>;
+};
+
+}
+
+}
+
+#endif // TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_
diff --git a/example/turing/src/tape.h b/example/turing/src/tape.h
new file mode 100644
index 0000000..39814d8
--- /dev/null
+++ b/example/turing/src/tape.h
@@ -0,0 +1,46 @@
+#ifndef TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_
+#define TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_
+
+#include "type.h"
+#include "list/list.h"
+#include "list/operation/replace_nth.h"
+#include "conditional/if.h"
+
+namespace machine {
+
+namespace tape {
+
+// (define (readSymbol position tape)
+//   (if (= (length tape) position)
+//       '()
+//       (nth position tape)))
+template <
+	typename Position,
+	typename Tape
+>
+using readSymbol = tav::If<
+	tav::IsEqualValue<tav::Length<Tape>, Position>,
+	void,
+	tav::Nth<Position, Tape>
+>;
+
+// (define (writeSymbol position symbol tape)
+//   (if (= (length tape) position)
+//       (append tape (list symbol))
+//       (replace-nth position symbol tape)))
+template <
+	typename Position,
+	typename Symbol,
+	typename Tape
+>
+using writeSymbol = tav::If<
+	tav::IsEqualValue<tav::Length<Tape>, Position>,
+	tav::Append<Tape, tav::List<Symbol>>,
+	tav::ReplaceNth<Position, Symbol, Tape>
+>;
+
+}
+
+}
+
+#endif // TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_
diff --git a/example/turing/turing.cc b/example/turing/turing.cc
index e1384d8..f0087ed 100644
--- a/example/turing/turing.cc
+++ b/example/turing/turing.cc
@@ -1,228 +1,65 @@
 #include <iostream>
 
-#include "type.h"
-#include "operation/math.h"
-#include "function/apply.h"
-
-#include "conditional/if.h"
-#include "conditional/cond.h"
-
-#include "list/operation/replace_nth.h"
-#include "list/operation/higher/find.h"
 #include "list/generator/make_list.h"
-
 #include "runtime/list/for_each.h"
 
-struct symbol {
-	struct BLANK { };
-};
-
-struct movement {
-	struct RIGHT { };
-	struct LEFT  { };
-	struct NONE  { };
-};
-
-// helper for easier state access
-struct state_field {
-	using ID    = tav::Size<0>;
-	using READ  = tav::Size<1>;
-	using WRITE = tav::Size<2>;
-	using NEXT  = tav::Size<3>;
-	using MOVE  = tav::Size<4>;
-};
-
-// (define (state_predicate id read)
-//   (lambda (state)
-//           (and (= id   (nth ID   state))
-//                (= read (nth READ state)))))
-template <
-	typename Id,
-	typename Read
->
-struct state_predicate {
-	template <typename State>
-	using function = tav::And<
-		tav::IsEqualValue<Id,   tav::Nth<state_field::ID,   State>>,
-		tav::IsEqualValue<Read, tav::Nth<state_field::READ, State>>
-	>;
-};
-
-// (define (findState id read states)
-//   (find (state_predicate id read) states))
-template <
-	typename Id,
-	typename Read,
-	typename States
->
-using findState = tav::Find<
-	state_predicate<Id, Read>::template function,
-	States
->;
-
-// (define (readSymbolFromTape position tape)
-//   (if (= (length tape) position)
-//       BLANK
-//       (nth position tape)))
-template <
-	typename Position,
-	typename Tape
->
-using readSymbolFromTape = tav::If<
-	tav::IsEqualValue<tav::Length<Tape>, Position>,
-	symbol::BLANK,
-	tav::Nth<Position, Tape>
->;
-
-// (define (writeSymbolToTape position symbol tape)
-//   (if (= (length tape) position)
-//       (append tape (list symbol))
-//       (replace-nth position symbol tape)))
-template <
-	typename Position,
-	typename Symbol,
-	typename Tape
->
-using writeSymbolToTape = tav::If<
-	tav::IsEqualValue<tav::Length<Tape>, Position>,
-	tav::Append<Tape, tav::List<Symbol>>,
-	tav::ReplaceNth<Position, Symbol, Tape>
->;
-
-// (define (transition states)
-//   (lambda (state symbol)
-//           (findState state symbol states)))
-template <typename States>
-struct transition {
-	template <
-		typename State,
-		typename Symbol
-	>
-	using state = findState<State, Symbol, States>;
-};
+#include "src/machine.h"
 
-// (define (simulateTuringMachine transition tape state position)
-//   (if (= state FINAL)
-//     tape
-//     (let* ((current_symbol (readSymbolFromTape position tape))
-//            (current_state  (transition state current_symbol))
-//            (direction      (nth MOVE  current_state))
-//            (next_symbol    (nth WRITE current_state))
-//            (next_state     (nth NEXT  current_state))
-//            (next_position  (cond ((= direction RIGHT) (+ position 1))
-//                                  ((= direction LEFT)  (- Position 1))
-//                                  (else                position))))
-//       (simulateTuringMachine transition
-//                              (writeSymbolToTape position next_symbol tape)
-//                              next_state,
-//                              next_position)))
-template <
-	template<typename, typename> class Transition,
-	typename                           Tape,
-	typename                           State,
-	typename                           Position
->
-class simulateTuringMachine {
-	private:
-		using current_symbol = readSymbolFromTape<Position, Tape>;
-		using current_state  = Transition<State, current_symbol>;
-
-		using direction      = tav::Nth<state_field::MOVE,  current_state>;
-
-		using next_symbol    = tav::Nth<state_field::WRITE, current_state>;
-		using next_state     = tav::Nth<state_field::NEXT,  current_state>;
-		using next_position  = tav::Cond<
-			tav::Branch<
-				std::is_same<direction, movement::RIGHT>,
-				tav::Add<Position, tav::Size<1>>
-			>,
-			tav::Branch<
-				std::is_same<direction, movement::LEFT>,
-				tav::Substract<Position, tav::Size<1>>
-			>,
-			tav::Else<
-				Position
-			>
-		>;
-
-		static_assert(
-			tav::Not<tav::LowerThan<next_position, tav::Size<0>>>::value,
-			"next position out of bounds"
-		);
-
-	public:
-		using type = tav::Eval<simulateTuringMachine<
-			Transition,
-			writeSymbolToTape<Position, next_symbol, Tape>,
-			next_state,
-			next_position
-		>>;
-};
-
-template <
-	template<typename, typename> class Transition,
-	typename                           Tape,
-	typename                           Position
->
-struct simulateTuringMachine<Transition, Tape, void, Position> {
-	typedef Tape type;
-};
-
-// (define mirror (list (list 1 1 0 2 RIGHT) [...]))
+// (define mirror (list (list 1 1 0 2 'R') [...]))
 using mirror = tav::List<
 //            [state]       [read]       [write]      [next state]  [head movement]
-	tav::List<tav::Size<1>, tav::Int<1>, tav::Int<0>, tav::Size<2>, movement::RIGHT>,
-	tav::List<tav::Size<1>, tav::Int<0>, tav::Int<0>, void,         movement::NONE >,
-	tav::List<tav::Size<2>, tav::Int<1>, tav::Int<1>, tav::Size<2>, movement::RIGHT>,
-	tav::List<tav::Size<2>, tav::Int<0>, tav::Int<0>, tav::Size<3>, movement::RIGHT>,
-	tav::List<tav::Size<3>, tav::Int<1>, tav::Int<1>, tav::Size<3>, movement::RIGHT>,
-	tav::List<tav::Size<3>, tav::Int<0>, tav::Int<1>, tav::Size<4>, movement::LEFT >,
-	tav::List<tav::Size<4>, tav::Int<1>, tav::Int<1>, tav::Size<4>, movement::LEFT >,
-	tav::List<tav::Size<4>, tav::Int<0>, tav::Int<0>, tav::Size<5>, movement::LEFT >,
-	tav::List<tav::Size<5>, tav::Int<1>, tav::Int<1>, tav::Size<5>, movement::LEFT >,
-	tav::List<tav::Size<5>, tav::Int<0>, tav::Int<1>, tav::Size<1>, movement::RIGHT>
+	tav::List<tav::Size<1>, tav::Int<1>, tav::Int<0>, tav::Size<2>, tav::Char<'R'>>,
+	tav::List<tav::Size<1>, tav::Int<0>, tav::Int<0>, void,         tav::Char<'N'> >,
+	tav::List<tav::Size<2>, tav::Int<1>, tav::Int<1>, tav::Size<2>, tav::Char<'R'>>,
+	tav::List<tav::Size<2>, tav::Int<0>, tav::Int<0>, tav::Size<3>, tav::Char<'R'>>,
+	tav::List<tav::Size<3>, tav::Int<1>, tav::Int<1>, tav::Size<3>, tav::Char<'R'>>,
+	tav::List<tav::Size<3>, tav::Int<0>, tav::Int<1>, tav::Size<4>, tav::Char<'L'> >,
+	tav::List<tav::Size<4>, tav::Int<1>, tav::Int<1>, tav::Size<4>, tav::Char<'L'> >,
+	tav::List<tav::Size<4>, tav::Int<0>, tav::Int<0>, tav::Size<5>, tav::Char<'L'> >,
+	tav::List<tav::Size<5>, tav::Int<1>, tav::Int<1>, tav::Size<5>, tav::Char<'L'> >,
+	tav::List<tav::Size<5>, tav::Int<0>, tav::Int<1>, tav::Size<1>, tav::Char<'R'>>
 >;
 
 // (define mirror_initial_tape (list 1 1 1 0 0 0 0))
 using mirror_initial_tape = tav::ListOfType<int, 1, 1, 1, 0, 0, 0, 0>;
 
 // (define mirror_final_tape
-//   (simulateTuringMachine (transition mirror)
-//                          mirror_initial_tape
-//                          1
-//                          0))
-using mirror_final_tape = tav::Eval<simulateTuringMachine<
-	transition<mirror>::template state,
-	mirror_initial_tape,
+//   (run mirror
+//        1
+//        mirror_initial_tape
+//        0))
+using mirror_final_tape = machine::run<
+	mirror,
 	tav::Size<1>,
+	mirror_initial_tape,
 	tav::Size<0>
->>;
+>;
 
-// (define busy_beaver (list (list 'A' 0 1 'B' RIGHT) [...]))
+// (define busy_beaver (list (list 'A' 0 1 'B' 'R') [...]))
 using busy_beaver = tav::List<
 //            [state]         [read]       [write]      [next state]    [head movement]
-	tav::List<tav::Char<'A'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>,
-	tav::List<tav::Char<'A'>, tav::Int<1>, tav::Int<1>, tav::Char<'C'>, movement::LEFT >,
-	tav::List<tav::Char<'B'>, tav::Int<0>, tav::Int<1>, tav::Char<'A'>, movement::LEFT >,
-	tav::List<tav::Char<'B'>, tav::Int<1>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>,
-	tav::List<tav::Char<'C'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::LEFT >,
-	tav::List<tav::Char<'C'>, tav::Int<1>, tav::Int<1>, void,           movement::NONE >
+	tav::List<tav::Char<'A'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, tav::Char<'R'>>,
+	tav::List<tav::Char<'A'>, tav::Int<1>, tav::Int<1>, tav::Char<'C'>, tav::Char<'L'> >,
+	tav::List<tav::Char<'B'>, tav::Int<0>, tav::Int<1>, tav::Char<'A'>, tav::Char<'L'> >,
+	tav::List<tav::Char<'B'>, tav::Int<1>, tav::Int<1>, tav::Char<'B'>, tav::Char<'R'>>,
+	tav::List<tav::Char<'C'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, tav::Char<'L'> >,
+	tav::List<tav::Char<'C'>, tav::Int<1>, tav::Int<1>, void,           tav::Char<'N'> >
 >;
 
 // (define busy_beaver_initial_tape (make-list 13 0))
 using busy_beaver_initial_tape = tav::MakeList<tav::Size<13>, tav::Int<0>>;
 
 // (define busy_beaver_final_tape
-//   (simulateTuringMachine (transition busy_beaver)
-//                          busy_beaver_initial_tape
-//                          'A'
-//                          6))
-using busy_beaver_final_tape = tav::Eval<simulateTuringMachine<
-	transition<busy_beaver>::template state,
-	busy_beaver_initial_tape,
+//   (run busy_beaver
+//        'A'
+//        busy_beaver_initial_tape
+//        6))
+using busy_beaver_final_tape = machine::run<
+	busy_beaver,
 	tav::Char<'A'>,
+	busy_beaver_initial_tape,
 	tav::Size<6>
->>;
+>;
 
 int main(int, char **) {
 	const auto printField = [](const int x) {
diff --git a/src/list/generator/detail/generate_nested_structure.h b/src/list/generator/detail/generate_nested_structure.h
index 84db78d..77fa0aa 100644
--- a/src/list/generator/detail/generate_nested_structure.h
+++ b/src/list/generator/detail/generate_nested_structure.h
@@ -1,6 +1,9 @@
 #ifndef TYPEASVALUE_SRC_LIST_GENERATOR_DETAIL_GENERATE_NESTED_STRUCTURE_H_
 #define TYPEASVALUE_SRC_LIST_GENERATOR_DETAIL_GENERATE_NESTED_STRUCTURE_H_
 
+#include "type.h"
+#include "operation/math.h"
+
 namespace tav {
 
 namespace detail {
diff --git a/src/list/operation/higher/find.h b/src/list/operation/higher/find.h
index aeb0c2a..e7ee9f2 100644
--- a/src/list/operation/higher/find.h
+++ b/src/list/operation/higher/find.h
@@ -1,10 +1,10 @@
 #ifndef TYPEASVALUE_SRC_LIST_OPERATION_HIGHER_FIND_H_
 #define TYPEASVALUE_SRC_LIST_OPERATION_HIGHER_FIND_H_
 
+#include "list/list.h"
+#include "list_index.h"
 #include "utility/predicate.h"
 #include "function/apply.h"
-#include "list/operation/nth.h"
-#include "list_index.h"
 
 namespace tav {
 
diff --git a/src/pair.h b/src/pair.h
index 8234382..6b2fe28 100644
--- a/src/pair.h
+++ b/src/pair.h
@@ -3,6 +3,8 @@
 
 #include <type_traits>
 
+#include "type.h"
+
 namespace tav {
 
 namespace detail { struct pair_tag { }; }
-- 
cgit v1.2.3