Algorithm description

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