aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--algorithm.txt168
1 files changed, 168 insertions, 0 deletions
diff --git a/algorithm.txt b/algorithm.txt
new file mode 100644
index 0000000..82e0d69
--- /dev/null
+++ b/algorithm.txt
@@ -0,0 +1,168 @@
+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 ]
+
+
+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 rule 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.tt1 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 and t1 (=sym) to tr1 and tr2 of last rule (using t2 as scratch)
+Move 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
+ 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 tr1 and 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
+
+Now: [t1 = qto, t2 = swrite, t3 = dir] and cursor is at t1.
+
+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