aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAdrian Kummerlaender2015-02-23 19:03:16 +0100
committerAdrian Kummerlaender2015-02-23 19:03:16 +0100
commit0dde43edac6817c3f0a237d25c2054c0ee75926c (patch)
tree037d04fd230f5aa613b6e8b3030e93973f5566b9
parent41b63eff7f76e6574ef238f821dad0212a619c2a (diff)
Added binary incrementer state table to Turing machine example
* reintroduced `BLANK` as the _BLANK_ symbol * fixed implicit tape expansion in `tape::readSymbol`
-rw-r--r--example/turing/README.md2
-rw-r--r--example/turing/src/state.h4
-rw-r--r--example/turing/src/tape.h16
-rw-r--r--example/turing/turing.cc33
4 files changed, 45 insertions, 10 deletions
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");
}