From 0dde43edac6817c3f0a237d25c2054c0ee75926c Mon Sep 17 00:00:00 2001
From: Adrian Kummerlaender
Date: Mon, 23 Feb 2015 19:03:16 +0100
Subject: Added binary incrementer state table to Turing machine example *
 reintroduced `BLANK` as the _BLANK_ symbol * fixed implicit tape expansion in
 `tape::readSymbol`

---
 example/turing/README.md   |  2 +-
 example/turing/src/state.h |  4 ++--
 example/turing/src/tape.h  | 16 +++++++++++-----
 example/turing/turing.cc   | 33 +++++++++++++++++++++++++++++++--
 4 files changed, 45 insertions(+), 10 deletions(-)

(limited to 'example/turing')

diff --git a/example/turing/README.md b/example/turing/README.md
index 84be368..7e0f1b1 100644
--- a/example/turing/README.md
+++ b/example/turing/README.md
@@ -2,4 +2,4 @@
 
 …is an example implementation of the most conclusive demonstration of how _TypeAsValue_ may be used to perform arbitrary compile time computations: a _Turing machine_.
 
-It prints the initial and final tape states gained by evaluating both a _Mirror_ state transition table and the well known _Busy Beaver_ example.
+It prints the initial and final tape states gained by evaluating a _Mirror_ state transition table, a binary incrementer and the well known _Busy Beaver_ example.
diff --git a/example/turing/src/state.h b/example/turing/src/state.h
index 51fe347..fa3306b 100644
--- a/example/turing/src/state.h
+++ b/example/turing/src/state.h
@@ -42,8 +42,8 @@ template <
 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>>
+		tav::IsEqual<Id,   tav::Nth<field::ID,   State>>,
+		tav::IsEqual<Read, tav::Nth<field::READ, State>>
 	>;
 };
 
diff --git a/example/turing/src/tape.h b/example/turing/src/tape.h
index 39814d8..4f79bd9 100644
--- a/example/turing/src/tape.h
+++ b/example/turing/src/tape.h
@@ -10,6 +10,12 @@ namespace machine {
 
 namespace tape {
 
+struct BLANK {
+	typedef BLANK type;
+
+	static constexpr char value{'\0'};
+};
+
 // (define (readSymbol position tape)
 //   (if (= (length tape) position)
 //       '()
@@ -18,11 +24,11 @@ template <
 	typename Position,
 	typename Tape
 >
-using readSymbol = tav::If<
-	tav::IsEqualValue<tav::Length<Tape>, Position>,
-	void,
-	tav::Nth<Position, Tape>
->;
+using readSymbol = tav::Eval<tav::If<
+	tav::LowerThan<Position, tav::Length<Tape>>,
+	tav::utility::defer_eval<tav::Nth, Position, Tape>,
+	BLANK
+>>;
 
 // (define (writeSymbol position symbol tape)
 //   (if (= (length tape) position)
diff --git a/example/turing/turing.cc b/example/turing/turing.cc
index ab377e2..720697a 100644
--- a/example/turing/turing.cc
+++ b/example/turing/turing.cc
@@ -5,6 +5,8 @@
 
 #include "src/machine.h"
 
+using BLANK = machine::tape::BLANK;
+
 // (define mirror (list (list 1 1 0 2 'R') [...]))
 using mirror = tav::List<
 //            [state]       [read]       [write]      [next state]  [head movement]
@@ -31,13 +33,27 @@ using busy_beaver = tav::List<
 	tav::List<tav::Char<'C'>, tav::Int<1>, tav::Int<1>, void,           tav::Char<'N'> >
 >;
 
+// (define binary_increment (list (list 0 '() '() 1 'L') [...]))
+using binary_increment = tav::List<
+//            [state]       [read]               [write]              [next state]  [head movement]
+	tav::List<tav::Size<0>, BLANK,               BLANK,               tav::Size<1>, tav::Char<'L'>>,
+	tav::List<tav::Size<0>, tav::Boolean<false>, tav::Boolean<false>, tav::Size<0>, tav::Char<'R'>>,
+	tav::List<tav::Size<0>, tav::Boolean<true>,  tav::Boolean<true>,  tav::Size<0>, tav::Char<'R'>>,
+	tav::List<tav::Size<1>, BLANK,               tav::Boolean<true>,  tav::Size<2>, tav::Char<'R'>>,
+	tav::List<tav::Size<1>, tav::Boolean<false>, tav::Boolean<true>,  tav::Size<2>, tav::Char<'L'>>,
+	tav::List<tav::Size<1>, tav::Boolean<true>,  tav::Boolean<false>, tav::Size<1>, tav::Char<'L'>>,
+	tav::List<tav::Size<2>, BLANK,               BLANK,               void,         tav::Char<'L'>>,
+	tav::List<tav::Size<2>, tav::Boolean<false>, tav::Boolean<false>, tav::Size<2>, tav::Char<'R'>>,
+	tav::List<tav::Size<2>, tav::Boolean<true>,  tav::Boolean<true>,  tav::Size<2>, tav::Char<'R'>>
+>;
+
 template <
 	typename Initial,
 	typename Final
 >
 void printStates(const std::string& name) {
-	const auto printField = [](const int x) {
-		std::cout << x << " ";
+	const auto printField = [](const auto x) {
+		std::cout << x << ' ';
 	};
 
 	std::cout << name
@@ -80,4 +96,17 @@ int main(int, char **) {
 			tav::Size<6>
 		>
 	>("2. Busy Beaver");
+
+	// (define binary_increment_tape (list #t #f #t #f #t #f))
+	using binary_increment_tape = tav::ListOfType<bool, 1, 0, 1, 0, 1, 0>;
+
+	printStates<
+		binary_increment_tape,
+		machine::run<
+			binary_increment,
+			tav::Size<0>,
+			binary_increment_tape,
+			tav::Size<0>
+		>
+	>("3. Binary Increment");
 }
-- 
cgit v1.2.3