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/src/machine.h | 98 ++++++++++++++++++ example/turing/src/state.h | 64 ++++++++++++ example/turing/src/tape.h | 46 +++++++++ example/turing/turing.cc | 233 +++++++------------------------------------ 4 files changed, 243 insertions(+), 198 deletions(-) create mode 100644 example/turing/src/machine.h create mode 100644 example/turing/src/state.h create mode 100644 example/turing/src/tape.h (limited to 'example') diff --git a/example/turing/src/machine.h b/example/turing/src/machine.h new file mode 100644 index 0000000..2404d9a --- /dev/null +++ b/example/turing/src/machine.h @@ -0,0 +1,98 @@ +#ifndef TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_ +#define TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_ + +#include "conditional/cond.h" + +#include "state.h" +#include "tape.h" + +namespace machine { + +// (define (simulate transition tape state position) +// (if (= state FINAL) +// tape +// (let* ((current_symbol (readSymbol 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)))) +// (simulate transition +// (writeSymbol position next_symbol tape) +// next_state, +// next_position))) +template < + template class Transition, + typename State, + typename Tape, + typename Position +> +class simulate { + private: + using current_symbol = tape::readSymbol; + 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< + tav::IsEqualValue>, + tav::Add> + >, + tav::Branch< + tav::IsEqualValue>, + tav::Substract> + >, + tav::Else< + Position + > + >; + + static_assert( + tav::Not>>::value, + "next position out of bounds" + ); + + public: + using type = tav::Eval, + next_position + >>; +}; + +template < + template class Transition, + typename Tape, + typename Position +> +struct simulate { + typedef Tape type; +}; + +// (define (run program state tape position) +// (simulate (transition program) +// tape +// state +// position)) +template < + typename Program, + typename State, + typename Tape, + typename Position +> +using run = tav::Eval::template state, + State, + Tape, + Position +>>; + +} + +#endif // TYPEASVALUE_EXAMPLE_TURING_MACHINE_H_ diff --git a/example/turing/src/state.h b/example/turing/src/state.h new file mode 100644 index 0000000..f5bd7f2 --- /dev/null +++ b/example/turing/src/state.h @@ -0,0 +1,64 @@ +#ifndef TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_ +#define TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_ + +#include "type.h" +#include "list/list.h" +#include "list/operation/higher/find.h" + +namespace machine { + +namespace state { + +struct 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 (transition states) +// (lambda (state symbol) +// (findState state symbol states))) +template +struct transition { + template < + typename State, + typename Symbol + > + using state = findState; +}; + +} + +} + +#endif // TYPEASVALUE_EXAMPLE_TURING_SRC_STATE_H_ diff --git a/example/turing/src/tape.h b/example/turing/src/tape.h new file mode 100644 index 0000000..39814d8 --- /dev/null +++ b/example/turing/src/tape.h @@ -0,0 +1,46 @@ +#ifndef TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_ +#define TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_ + +#include "type.h" +#include "list/list.h" +#include "list/operation/replace_nth.h" +#include "conditional/if.h" + +namespace machine { + +namespace tape { + +// (define (readSymbol position tape) +// (if (= (length tape) position) +// '() +// (nth position tape))) +template < + typename Position, + typename Tape +> +using readSymbol = tav::If< + tav::IsEqualValue, Position>, + void, + tav::Nth +>; + +// (define (writeSymbol position symbol tape) +// (if (= (length tape) position) +// (append tape (list symbol)) +// (replace-nth position symbol tape))) +template < + typename Position, + typename Symbol, + typename Tape +> +using writeSymbol = tav::If< + tav::IsEqualValue, Position>, + tav::Append>, + tav::ReplaceNth +>; + +} + +} + +#endif // TYPEASVALUE_EXAMPLE_TURING_SRC_TAPE_H_ 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