diff options
Diffstat (limited to 'example/turing')
| -rw-r--r-- | example/turing/README.md | 2 | ||||
| -rw-r--r-- | example/turing/src/state.h | 4 | ||||
| -rw-r--r-- | example/turing/src/tape.h | 16 | ||||
| -rw-r--r-- | example/turing/turing.cc | 33 |
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"); } |