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') 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 using function = tav::And< - tav::IsEqualValue>, - tav::IsEqualValue> + tav::IsEqual>, + tav::IsEqual> >; }; 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, Position>, - void, - tav::Nth ->; +using readSymbol = tav::Eval>, + tav::utility::defer_eval, + 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::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, BLANK, BLANK, tav::Size<1>, tav::Char<'L'>>, + tav::List, tav::Boolean, tav::Boolean, tav::Size<0>, tav::Char<'R'>>, + tav::List, tav::Boolean, tav::Boolean, tav::Size<0>, tav::Char<'R'>>, + tav::List, BLANK, tav::Boolean, tav::Size<2>, tav::Char<'R'>>, + tav::List, tav::Boolean, tav::Boolean, tav::Size<2>, tav::Char<'L'>>, + tav::List, tav::Boolean, tav::Boolean, tav::Size<1>, tav::Char<'L'>>, + tav::List, BLANK, BLANK, void, tav::Char<'L'>>, + tav::List, tav::Boolean, tav::Boolean, tav::Size<2>, tav::Char<'R'>>, + tav::List, tav::Boolean, tav::Boolean, 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; + + printStates< + binary_increment_tape, + machine::run< + binary_increment, + tav::Size<0>, + binary_increment_tape, + tav::Size<0> + > + >("3. Binary Increment"); } -- cgit v1.2.3