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
111
112
113
114
115
116
117
118
|
#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)
// (cons '(position . tape)
// '())
// (let ((current_state (transition state
// (readSymbol position tape))))
// (cons '(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::Cons<
tav::Pair<Position, Tape>,
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> {
using type = tav::Cons<
tav::Pair<Position, Tape>,
void
>;
};
// (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_
|