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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
|
Tape layout
===========
Imarker: [ 1 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 ]
Rules
- Each rule: [ 0 | tr1 | tr2 | tr3 | tr4 | qfrom | sread | qto | swrite | dir ]
Mmarker: [ 1 | qcurrent | t1 | t2 | t3 ]
Tape
- Each cell: [ 0 | head | tt1 | tt2 | sym ]
EXPLICITLY USED: sizeof(rule) == 2 * sizeof(cell)
Read input
==========
Write 1, move right a rule width
Go to tr1
Write 1
While nonzero:
Subtract 1 from tr1
Read into qfrom
Copy to tr4 (using tr3 as scratch)
Write 1 to tr3 ("should zero qfrom")
Go to tr4 and add 1
While nonzero:
Zero tr4
Subtract 1 from tr3
Write 1 to rightrule.tr1
Read into sread
Copy to sread+1 (scratch sread+2)
Write 1 to sread+2
Subtract 32 from sread+1 and go to sread+1
While nonzero:
Subtract 1 from sread+2
Zero sread+1 and go to sread+1
Go to sread+2
While nonzero:
Zero sread
Zero sread+2 and go to sread+2
Read into qto
Read into swrite
Copy to swrite+1 (scratch swrite+2)
Write 1 to swrite+2
Subtract 32 from swrite+1 and go to swrite+1
While nonzero:
Subtract 1 from swrite+2
Zero swrite+1 and go to swrite+1
Go to swrite+2
While nonzero:
Zero swrite
Zero swrite+2 and go to swrite+2
Read into dir
Subtract '=' (61) from dir
Go to tr4
Go to tr3
While nonzero:
Zero qfrom
Zero tr3 and go to tr3
Go to rightrule.tr1, which is 1 precisely if we didn't have EOF
Now at a zero tr1 that is one rule width too far.
So go one rule width left, at which point we are on the qcurrent of Mmarker.
Write 'S' (83), and go to Mmarker.0
Write 1
Set rightcell.head to 1
Go back to Mmarker.0
Main loop
=========
Precondition: cursor at Mmarker.0 and all temporaries are 0
Subtract 'H' from qcurrent (using t1 as scratch)
While qcurrent is nonzero:
Add 'H' to qcurrent
Go to Mmarker.0
Perform execution step
Subtract 'H' from qcurrent
Execution step
==============
Precondition: cursor at Mmarker.0 and all temporaries are 0
Find cell with head=1:
Set t1 to 1
While nonzero:
Zero current cell (leftrule.tt1), then move right a cell width; now at tt1
Set tt1 to 1
Move head to tt1 (multiplier -1) and tt2, move tt2 back to head
Now tt1 is not(head).
Go to tt1
Now at zero tt1, which means that head = 1; go to rule.0 for good measure.
Copy sym to tt1 (using tt2 as scratch)
Move tt1 over tt1's back to t1:
Go to tt2, set to 1
While nonzero:
Zero current cell (tt2)
Set leftcell.tt2 to 1
Move leftcell.0 to leftcell.tt2 (multiplier -1) and leftcell.tt1
Move leftcell.tt1 back to leftcell.0
Move tt1 to leftcell.tt1
Go to leftcell.tt2
Now at zero t2, and t1 is sym.
[t1 = sym; tt1 = tt2 = 0 for all cells]
Copy qcurrent to tr1 of last rule (using t2 as scratch)
Move t1 (=sym) to tr2 of last rule
Go to t2 (same offset as tr3), set to 1
While nonzero:
Zero current cell (rightrule.tr3), then move left a rule width; now at tr3
Zero tr3
[tr1 = qcurrent, tr2 = sym]
Copy qfrom to tr4 (using tr3 as scratch)
Copy tr1 to tr3 (using rule.0 as scratch)
[tr1 = qcurrent, tr2 = sym, tr3 = qcurrent, tr4 = qfrom]
Set tr3 to (qcurrent != qfrom): to(tr3) [- to(tr4) - to(tr3)] to(tr4) [to(tr3) + to(tr4) [-]]
Move tr3 to left-rule.tr3 (or T3 if leftmost rule)
[tr1 = qcurrent, tr2 = sym]
Copy sread to tr4 (using tr3 as scratch)
Copy tr2 to tr3 (using rule.0 as scratch)
[tr1 = qcurrent, tr2 = sym, tr3 = sym, tr4 = sread]
Set tr3 to (sym != sread): to(tr3) [- to(tr4) - to(tr3)] to(tr4) [to(tr3) + to(tr4) [-]]
Move tr3 to left-rule.tr4 (or T4 if leftmost rule)
[tr1 = qcurrent, tr2 = sym, prev.tr3 = q!=q, prev.tr4 = s!=s]
Move leftrule.tr3 to tr4 and leftrule.tr4 also to tr4
If tr4 is nonzero: zero tr4 and set tr3 to 1
[tr1 = qcurrent, tr2 = sym, tr3 = q!=q || s!=s]
Copy tr3 to leftrule.tr3 (using rule.0 as scratch)
[tr1 = qcurrent, tr2 = sym, tr3 = q!=q || s!=s, leftrule.tr3 = q!=q || s!=s]
While leftrule.0 is nonzero:
Zero tr3 and set tr4 to 1
Zero leftrule.0
Move tr4 to leftrule.0
[tr1 = qcurrent, tr2 = sym, tr3 = (q!=q || s!=s) && not_leftmost_rule, leftrule.tr3 = q!=q || s!=s]
Move tr1 to leftrule.tr1 and tr2 to leftrule.tr2 (or T1 and T2 if leftmost rule)
Go to tr3
Now at a tr3 that is zero. So either this is the last rule, or this rule matches.
Note that leftrule.tr3 is q!=q || s!=s, or in other words, 0 if the current rule matches and 1 otherwise.
While leftrule.tr3:
Apparently no rule matched, so crash().
Apparently leftrule.tr3 is zero, so the current rule matches.
Zero leftrule.tr1 and leftrule.tr2
Copy qto to tr2 (using tr1 as scratch)
Copy swrite to tr3 (using tr1 as scratch)
Copy dir to tr4 (using tr1 as scratch)
Go to rightrule.tr2, set to 1
While nonzero:
Now current cell (tr2) is 1
Move rule.0 to tr2 (multiplier -1) and tr3
Move tr3 back to rule.0
Move tr2 to rightrule.tr2
Move leftrule.tr2 to tr2, leftrule.tr3 to tr3, leftrule.tr4 to tr4
Go to rightrule.tr2 (or tt1 of second cell! Here we use that sizeof(rule) == 2 * sizeof(cell))
Now: [t1 = qto, t2 = swrite, t3 = dir] and cursor is at tt1 of second cell.
Zero qcurrent
Move t1 to qcurrent
Move t2 to t1 and t3 to t2
[t1 = swrite, t2 = dir]
Go to rightcell.tt1, set to 1
While nonzero:
Now current cell (tt1) is 1
Move head to tt1 (multiplier -1) and tt2
Move tt2 back to head
Move tt1 to rightcell.tt1
Move leftcell.tt1 to tt1 and leftcell.tt2 to tt2
Go to rightcell.tt1
Move left a cell width; then at tt1 of the cell where head=1 and [tt1 = swrite, tt2 = dir].
Zero sym
Move tt1 to sym
Move tt2 to cell.0 and tt1
Move cell.0 back to tt2
[tt1 = dir, tt2 = dir]
Go to tt1
While nonzero:
Subtract 1
While nonzero:
Apparently, dir was -1
Set cell.0 to 1 and go back to tt1
Zero tt1
[cell.0 = (dir == -1), tt1 = 0, tt2 = dir]
Go to tt2
While nonzero:
Add 1
While nonzero:
Apparently, dir was 1
Set tt1 to 1 and go back to tt2
Zero tt2
[cell.0 = (dir == -1), tt1 = (dir == 1), tt2 = 0]
Go to cell.0
While nonzero:
While leftcell.0:
Apparently we moved the head beyond the left end of the tape, so crash().
Move head to leftcell.head
Go back to cell.0 and zero cell.0
Go to tt1
While nonzero:
Move head to rightcell.head
Go back to tt1 and zero tt1
[cell.0 = 0, tt1 = 0, tt2 = 0] and head is in the correct spot.
Now go back to Mmarker:
Go to tt1 and set to 1
While nonzero:
Zero current cell (tt1)
Set leftcell.tt1 to 1
Move leftcell.0 to leftcell.tt1 (multiplier -1) and leftcell.tt2
Move leftcell.tt2 back to leftcell.0
Go to leftcell.tt1
Now at t1, so go to Mmarker.0
|
