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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include <iostream>
#include "list/generator/make_list.h"
#include "runtime/list/for_each.h"
#include "src/machine.h"
using BLANK = machine::tape::BLANK;
// (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>, 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 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'>, 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 binary_increment (list (list 0 '() '() 1 'L') [...]))
using binary_increment = tav::List<
// [state] [read] [write] [next state] [head movement]
tav::List<tav::Size<0>, BLANK, BLANK, tav::Size<1>, tav::Char<'L'>>,
tav::List<tav::Size<0>, tav::Boolean<false>, tav::Boolean<false>, tav::Size<0>, tav::Char<'R'>>,
tav::List<tav::Size<0>, tav::Boolean<true>, tav::Boolean<true>, tav::Size<0>, tav::Char<'R'>>,
tav::List<tav::Size<1>, BLANK, tav::Boolean<true>, tav::Size<2>, tav::Char<'R'>>,
tav::List<tav::Size<1>, tav::Boolean<false>, tav::Boolean<true>, tav::Size<2>, tav::Char<'L'>>,
tav::List<tav::Size<1>, tav::Boolean<true>, tav::Boolean<false>, tav::Size<1>, tav::Char<'L'>>,
tav::List<tav::Size<2>, BLANK, BLANK, void, tav::Char<'L'>>,
tav::List<tav::Size<2>, tav::Boolean<false>, tav::Boolean<false>, tav::Size<2>, tav::Char<'R'>>,
tav::List<tav::Size<2>, tav::Boolean<true>, tav::Boolean<true>, tav::Size<2>, tav::Char<'R'>>
>;
const auto printField = [](const auto x) {
std::cout << x;
};
template <typename States>
void printStates() {
// (define position (car (head states)))
using position = tav::Car<tav::Head<States>>;
// (define tape (cdr (head states)))
using tape = tav::Cdr<tav::Head<States>>;
// (define prefix (make-list 3 " "))
using prefix = tav::MakeList<tav::Size<3>, tav::Char<' '>>;
// (for-each printField (concatenate prefix tape))
tav::runtime::for_each<tav::Concatenate<prefix, tape>>(printField);
std::cout << std::endl;
// (for-each printField
// (concatenate prefix
// (make-list position " ")
// (list "^")))
tav::runtime::for_each<tav::Concatenate<
prefix,
tav::MakeList<position, tav::Char<' '>>,
tav::List<tav::Char<'^'>>
>>(printField);
std::cout << std::endl;
printStates<tav::Tail<States>>();
}
template <>
void printStates<void>() { }
int main(int, char **) {
// (define mirror_tape (list 1 1 1 0 0 0 0))
using mirror_tape = tav::ListOfType<int, 1, 1, 1, 0, 0, 0, 0>;
std::cout << "1. Mirror"
<< std::endl;
printStates<
// (run mirror 1 mirror_tape 0)
machine::run<
mirror,
tav::Size<1>,
mirror_tape,
tav::Size<0>
>
>();
// (define busy_beaver_tape (make-list 13 0))
using busy_beaver_tape = tav::MakeList<tav::Size<13>, tav::Int<0>>;
std::cout << "2. Busy Beaver"
<< std::endl;
printStates<
// (run busy_beaver "A" busy_beaver_tape 6)
machine::run<
busy_beaver,
tav::Char<'A'>,
busy_beaver_tape,
tav::Size<6>
>
>();
// (define binary_increment_tape (list #t #f #t #f #t #f))
using binary_increment_tape = tav::ListOfType<bool, 1, 0, 1, 0, 1, 0>;
std::cout << "3. Binary Increment"
<< std::endl;
printStates<
// (run binary_increment 0 binary_increment_tape 0)
machine::run<
binary_increment,
tav::Size<0>,
binary_increment_tape,
tav::Size<0>
>
>();
}
|
