aboutsummaryrefslogtreecommitdiff
path: root/example/turing/src/machine.h
blob: a30c6e30ec53e1c2abc35c67ef4408036228abbe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#ifndef TYPEASVALUE_EXAMPLE_TURING_SRC_MACHINE_H_
#define TYPEASVALUE_EXAMPLE_TURING_SRC_MACHINE_H_

#include "conditional/cond.h"

#include "state.h"
#include "tape.h"

namespace machine {

// (define (updatePosition direction position)
//   (cond ((= direction RIGHT) (+ position 1))
//         ((= direction LEFT)  (- Position 1))
//         (else                position)))
template <
	typename Direction,
	typename Position
>
using updatePosition = 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
	>
>;


// (define (simulate transition tape state position)
//   (if (= state FINAL)
//     tape
//     (let ((current_state (transition state
//                                      (readSymbol position tape))))
//       (simulate transition
//                 (current_state NEXT)
//                 (writeSymbol position
//                              (current_state WRITE)
//                              tape)
//                 (updatePosition (current_state MOVE)
//                                 position)))))
template <
	template<typename, typename> class Transition,
	typename                           State,
	typename                           Tape,
	typename                           Position
>
class simulate {
	static_assert(
		tav::Not<tav::LowerThan<Position, tav::Size<0>>>::value,
		"machine head position out of bounds"
	);

	private:
		template <typename Field>
		using current_state = typename Transition<
			State,
			tape::readSymbol<Position, Tape>
		>::template get<Field>;

	public:
		using type = tav::Eval<simulate<
			Transition,
			current_state<state::field::NEXT>,
			tape::writeSymbol<
				Position,
				current_state<state::field::WRITE>,
				Tape
			>,
			updatePosition<
				current_state<state::field::MOVE>,
				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)
//             state
//             tape
//             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_SRC_MACHINE_H_