aboutsummaryrefslogtreecommitdiff
path: root/example/turing
diff options
context:
space:
mode:
authorAdrian Kummerlaender2015-02-21 17:27:52 +0100
committerAdrian Kummerlaender2015-02-21 17:27:52 +0100
commitc15edae4532f53e7e5bac9dae125c360d93f848d (patch)
tree58a3ded412834ba730aea9ebe6874e4ee4920975 /example/turing
parenteffddfdd69cf9e5ec700aeda2980c0210575e320 (diff)
downloadTypeAsValue-c15edae4532f53e7e5bac9dae125c360d93f848d.tar
TypeAsValue-c15edae4532f53e7e5bac9dae125c360d93f848d.tar.gz
TypeAsValue-c15edae4532f53e7e5bac9dae125c360d93f848d.tar.bz2
TypeAsValue-c15edae4532f53e7e5bac9dae125c360d93f848d.tar.lz
TypeAsValue-c15edae4532f53e7e5bac9dae125c360d93f848d.tar.xz
TypeAsValue-c15edae4532f53e7e5bac9dae125c360d93f848d.tar.zst
TypeAsValue-c15edae4532f53e7e5bac9dae125c360d93f848d.zip
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
Diffstat (limited to 'example/turing')
-rw-r--r--example/turing/src/machine.h98
-rw-r--r--example/turing/src/state.h64
-rw-r--r--example/turing/src/tape.h46
-rw-r--r--example/turing/turing.cc233
4 files changed, 243 insertions, 198 deletions
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<typename, typename> class Transition,
+ typename State,
+ typename Tape,
+ typename Position
+>
+class simulate {
+ private:
+ using current_symbol = tape::readSymbol<Position, Tape>;
+ using current_state = Transition<State, current_symbol>;
+
+ using direction = tav::Nth<state::field::MOVE, current_state>;
+
+ using next_symbol = tav::Nth<state::field::WRITE, current_state>;
+ using next_state = tav::Nth<state::field::NEXT, current_state>;
+ using next_position = tav::Cond<
+ tav::Branch<
+ tav::IsEqualValue<direction, tav::Char<'R'>>,
+ tav::Add<Position, tav::Size<1>>
+ >,
+ tav::Branch<
+ tav::IsEqualValue<direction, tav::Char<'L'>>,
+ tav::Substract<Position, tav::Size<1>>
+ >,
+ tav::Else<
+ Position
+ >
+ >;
+
+ static_assert(
+ tav::Not<tav::LowerThan<next_position, tav::Size<0>>>::value,
+ "next position out of bounds"
+ );
+
+ public:
+ using type = tav::Eval<simulate<
+ Transition,
+ next_state,
+ tape::writeSymbol<Position, next_symbol, Tape>,
+ next_position
+ >>;
+};
+
+template <
+ template<typename, typename> class Transition,
+ typename Tape,
+ typename Position
+>
+struct simulate<Transition, void, Tape, Position> {
+ 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<simulate<
+ state::transition<Program>::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 <typename State>
+ using function = tav::And<
+ tav::IsEqualValue<Id, tav::Nth<field::ID, State>>,
+ tav::IsEqualValue<Read, tav::Nth<field::READ, State>>
+ >;
+};
+
+// (define (findState id read states)
+// (find (state_predicate id read) states))
+template <
+ typename Id,
+ typename Read,
+ typename States
+>
+using findState = tav::Find<
+ state_predicate<Id, Read>::template function,
+ States
+>;
+
+// (define (transition states)
+// (lambda (state symbol)
+// (findState state symbol states)))
+template <typename States>
+struct transition {
+ template <
+ typename State,
+ typename Symbol
+ >
+ using state = findState<State, Symbol, States>;
+};
+
+}
+
+}
+
+#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<tav::Length<Tape>, Position>,
+ void,
+ tav::Nth<Position, Tape>
+>;
+
+// (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<tav::Length<Tape>, Position>,
+ tav::Append<Tape, tav::List<Symbol>>,
+ tav::ReplaceNth<Position, Symbol, Tape>
+>;
+
+}
+
+}
+
+#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 <iostream>
-#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 <typename State>
- using function = tav::And<
- tav::IsEqualValue<Id, tav::Nth<state_field::ID, State>>,
- tav::IsEqualValue<Read, tav::Nth<state_field::READ, State>>
- >;
-};
-
-// (define (findState id read states)
-// (find (state_predicate id read) states))
-template <
- typename Id,
- typename Read,
- typename States
->
-using findState = tav::Find<
- state_predicate<Id, Read>::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<tav::Length<Tape>, Position>,
- symbol::BLANK,
- tav::Nth<Position, Tape>
->;
-
-// (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<tav::Length<Tape>, Position>,
- tav::Append<Tape, tav::List<Symbol>>,
- tav::ReplaceNth<Position, Symbol, Tape>
->;
-
-// (define (transition states)
-// (lambda (state symbol)
-// (findState state symbol states)))
-template <typename States>
-struct transition {
- template <
- typename State,
- typename Symbol
- >
- using state = findState<State, Symbol, States>;
-};
+#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<typename, typename> class Transition,
- typename Tape,
- typename State,
- typename Position
->
-class simulateTuringMachine {
- private:
- using current_symbol = readSymbolFromTape<Position, Tape>;
- using current_state = Transition<State, current_symbol>;
-
- using direction = tav::Nth<state_field::MOVE, current_state>;
-
- using next_symbol = tav::Nth<state_field::WRITE, current_state>;
- using next_state = tav::Nth<state_field::NEXT, current_state>;
- using next_position = tav::Cond<
- tav::Branch<
- std::is_same<direction, movement::RIGHT>,
- tav::Add<Position, tav::Size<1>>
- >,
- tav::Branch<
- std::is_same<direction, movement::LEFT>,
- tav::Substract<Position, tav::Size<1>>
- >,
- tav::Else<
- Position
- >
- >;
-
- static_assert(
- tav::Not<tav::LowerThan<next_position, tav::Size<0>>>::value,
- "next position out of bounds"
- );
-
- public:
- using type = tav::Eval<simulateTuringMachine<
- Transition,
- writeSymbolToTape<Position, next_symbol, Tape>,
- next_state,
- next_position
- >>;
-};
-
-template <
- template<typename, typename> class Transition,
- typename Tape,
- typename Position
->
-struct simulateTuringMachine<Transition, Tape, void, Position> {
- 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::Size<1>, tav::Int<1>, tav::Int<0>, tav::Size<2>, movement::RIGHT>,
- tav::List<tav::Size<1>, tav::Int<0>, tav::Int<0>, void, movement::NONE >,
- tav::List<tav::Size<2>, tav::Int<1>, tav::Int<1>, tav::Size<2>, movement::RIGHT>,
- tav::List<tav::Size<2>, tav::Int<0>, tav::Int<0>, tav::Size<3>, movement::RIGHT>,
- tav::List<tav::Size<3>, tav::Int<1>, tav::Int<1>, tav::Size<3>, movement::RIGHT>,
- tav::List<tav::Size<3>, tav::Int<0>, tav::Int<1>, tav::Size<4>, movement::LEFT >,
- tav::List<tav::Size<4>, tav::Int<1>, tav::Int<1>, tav::Size<4>, movement::LEFT >,
- tav::List<tav::Size<4>, tav::Int<0>, tav::Int<0>, tav::Size<5>, movement::LEFT >,
- tav::List<tav::Size<5>, tav::Int<1>, tav::Int<1>, tav::Size<5>, movement::LEFT >,
- tav::List<tav::Size<5>, tav::Int<0>, tav::Int<1>, tav::Size<1>, movement::RIGHT>
+ tav::List<tav::Size<1>, tav::Int<1>, tav::Int<0>, tav::Size<2>, tav::Char<'R'>>,
+ tav::List<tav::Size<1>, tav::Int<0>, tav::Int<0>, void, tav::Char<'N'> >,
+ tav::List<tav::Size<2>, tav::Int<1>, tav::Int<1>, tav::Size<2>, tav::Char<'R'>>,
+ tav::List<tav::Size<2>, tav::Int<0>, tav::Int<0>, tav::Size<3>, tav::Char<'R'>>,
+ tav::List<tav::Size<3>, tav::Int<1>, tav::Int<1>, tav::Size<3>, tav::Char<'R'>>,
+ tav::List<tav::Size<3>, tav::Int<0>, tav::Int<1>, tav::Size<4>, tav::Char<'L'> >,
+ tav::List<tav::Size<4>, tav::Int<1>, tav::Int<1>, tav::Size<4>, tav::Char<'L'> >,
+ tav::List<tav::Size<4>, tav::Int<0>, tav::Int<0>, tav::Size<5>, tav::Char<'L'> >,
+ tav::List<tav::Size<5>, tav::Int<1>, tav::Int<1>, tav::Size<5>, tav::Char<'L'> >,
+ tav::List<tav::Size<5>, 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<int, 1, 1, 1, 0, 0, 0, 0>;
// (define mirror_final_tape
-// (simulateTuringMachine (transition mirror)
-// mirror_initial_tape
-// 1
-// 0))
-using mirror_final_tape = tav::Eval<simulateTuringMachine<
- transition<mirror>::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::Char<'A'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>,
- tav::List<tav::Char<'A'>, tav::Int<1>, tav::Int<1>, tav::Char<'C'>, movement::LEFT >,
- tav::List<tav::Char<'B'>, tav::Int<0>, tav::Int<1>, tav::Char<'A'>, movement::LEFT >,
- tav::List<tav::Char<'B'>, tav::Int<1>, tav::Int<1>, tav::Char<'B'>, movement::RIGHT>,
- tav::List<tav::Char<'C'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, movement::LEFT >,
- tav::List<tav::Char<'C'>, tav::Int<1>, tav::Int<1>, void, movement::NONE >
+ tav::List<tav::Char<'A'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, tav::Char<'R'>>,
+ tav::List<tav::Char<'A'>, tav::Int<1>, tav::Int<1>, tav::Char<'C'>, tav::Char<'L'> >,
+ tav::List<tav::Char<'B'>, tav::Int<0>, tav::Int<1>, tav::Char<'A'>, tav::Char<'L'> >,
+ tav::List<tav::Char<'B'>, tav::Int<1>, tav::Int<1>, tav::Char<'B'>, tav::Char<'R'>>,
+ tav::List<tav::Char<'C'>, tav::Int<0>, tav::Int<1>, tav::Char<'B'>, tav::Char<'L'> >,
+ tav::List<tav::Char<'C'>, 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::Size<13>, 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<simulateTuringMachine<
- transition<busy_beaver>::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) {