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/turing.cc | 233 +++++++---------------------------------------- 1 file changed, 35 insertions(+), 198 deletions(-) (limited to 'example/turing/turing.cc') 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 -#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 - using function = tav::And< - tav::IsEqualValue>, - tav::IsEqualValue> - >; -}; - -// (define (findState id read states) -// (find (state_predicate id read) states)) -template < - typename Id, - typename Read, - typename States -> -using findState = tav::Find< - state_predicate::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, Position>, - symbol::BLANK, - tav::Nth ->; - -// (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, Position>, - tav::Append>, - tav::ReplaceNth ->; - -// (define (transition states) -// (lambda (state symbol) -// (findState state symbol states))) -template -struct transition { - template < - typename State, - typename Symbol - > - using state = findState; -}; +#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 class Transition, - typename Tape, - typename State, - typename Position -> -class simulateTuringMachine { - private: - using current_symbol = readSymbolFromTape; - using current_state = Transition; - - using direction = tav::Nth; - - using next_symbol = tav::Nth; - using next_state = tav::Nth; - using next_position = tav::Cond< - tav::Branch< - std::is_same, - tav::Add> - >, - tav::Branch< - std::is_same, - tav::Substract> - >, - tav::Else< - Position - > - >; - - static_assert( - tav::Not>>::value, - "next position out of bounds" - ); - - public: - using type = tav::Eval, - next_state, - next_position - >>; -}; - -template < - template class Transition, - typename Tape, - typename Position -> -struct simulateTuringMachine { - 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::Int<1>, tav::Int<0>, tav::Size<2>, movement::RIGHT>, - tav::List, tav::Int<0>, tav::Int<0>, void, movement::NONE >, - tav::List, tav::Int<1>, tav::Int<1>, tav::Size<2>, movement::RIGHT>, - tav::List, tav::Int<0>, tav::Int<0>, tav::Size<3>, movement::RIGHT>, - tav::List, tav::Int<1>, tav::Int<1>, tav::Size<3>, movement::RIGHT>, - tav::List, tav::Int<0>, tav::Int<1>, tav::Size<4>, movement::LEFT >, - tav::List, tav::Int<1>, tav::Int<1>, tav::Size<4>, movement::LEFT >, - tav::List, tav::Int<0>, tav::Int<0>, tav::Size<5>, movement::LEFT >, - tav::List, tav::Int<1>, tav::Int<1>, tav::Size<5>, movement::LEFT >, - tav::List, tav::Int<0>, tav::Int<1>, tav::Size<1>, movement::RIGHT> + tav::List, tav::Int<1>, tav::Int<0>, tav::Size<2>, tav::Char<'R'>>, + tav::List, tav::Int<0>, tav::Int<0>, void, tav::Char<'N'> >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<2>, tav::Char<'R'>>, + tav::List, tav::Int<0>, tav::Int<0>, tav::Size<3>, tav::Char<'R'>>, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<3>, tav::Char<'R'>>, + tav::List, tav::Int<0>, tav::Int<1>, tav::Size<4>, tav::Char<'L'> >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<4>, tav::Char<'L'> >, + tav::List, tav::Int<0>, tav::Int<0>, tav::Size<5>, tav::Char<'L'> >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Size<5>, tav::Char<'L'> >, + tav::List, 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; // (define mirror_final_tape -// (simulateTuringMachine (transition mirror) -// mirror_initial_tape -// 1 -// 0)) -using mirror_final_tape = tav::Eval::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::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>, - tav::List, tav::Int<1>, tav::Int<1>, tav::Char<'C'>, movement::LEFT >, - tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'A'>, movement::LEFT >, - tav::List, tav::Int<1>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>, - tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::LEFT >, - tav::List, tav::Int<1>, tav::Int<1>, void, movement::NONE > + tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, tav::Char<'R'>>, + tav::List, tav::Int<1>, tav::Int<1>, tav::Char<'C'>, tav::Char<'L'> >, + tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'A'>, tav::Char<'L'> >, + tav::List, tav::Int<1>, tav::Int<1>, tav::Char<'B'>, tav::Char<'R'>>, + tav::List, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, tav::Char<'L'> >, + tav::List, 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::Int<0>>; // (define busy_beaver_final_tape -// (simulateTuringMachine (transition busy_beaver) -// busy_beaver_initial_tape -// 'A' -// 6)) -using busy_beaver_final_tape = tav::Eval::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) { -- cgit v1.2.3