Basic programs#
We have seen the syntax of 1# instructions
in a previous notebook, along with the semantics
We turn to the simplest programs in the language.
!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main
from onesharp.interpreter.interpreter import *
\(\moveprog_{2,1}\)#
The first is a program called \(\moveprog_{2,1}\). It moves the contents of R2 onto the end of R1, emptying out R2 in the process. It is
It is more informative to exhibit this program as a chart with instruction numbers and glosses:
| 11##### | cases on R2 | |
| 111111### | R2 is empty; go forward 6 (we're done) | |
| 11111### | go forward 3 to instruction 6 (the brown section) | |
| 1## | first symbol is #: add # to R1 | |
| 1111#### | go backward 4 to instruction 1 (the top) | |
| 1# | add 1 to R1 | |
| 111111#### | go backward 6 to instruction 1 (the top) |
The program has seven instructions. We call these the lines of the program. Here is an explanation of what is going when we run \(\moveprog_{2,1}\). We start with words in the registers. The only registers mentioned in the program are R2 and R1. Let’s say that at the start \(x\) is the word in R2,and \(y\) is the word in R1.
This is our first look at a case statement \(\onett^k \hash^5\). Upon execution, if \(x = \eps\), we move to line 2. If \(x\) starts with \(\onett\), we delete it and go to line 3 and thence to line 6 and thus to the third section of the program. There is no significance to the colors; they are just there to help us read and understand the program. If instead \(x\) starts with \(\hash\), we would delete it and go to the second section, starting in line 4. That section ends in line 5, and from there we return to the top.
Our program is a loop. Each time through the loop we take a symbol from the start of whatever is in R2 and add the same symbol to the end of R1. As soon as R2 becomes empty, we transfer out of the program. We do this in line 2 by going forward 6 lines, to the first line out of our program. By going around the loop repeatedly, we transfer \(x\) symbol-by-symbol to the end of R1. At the end, the contents of R1 will be \(y\) followed by \(x\); soon we will write this as \(y+x\).
Whenever \(m\) and \(n\) are different numbers, we can build a similar program \(\moveprog_{m,n}\). This program would write the contents of Rm onto the end of Rn, emptying Rm in the process.
Modifying \(\moveprog_{2,1}\)#
Exercise 31
Write a program which takes the contents of R1 and adds them to the ends of both R2 and R3.
Exercise 32
Write a program \(\clearprog_1\) that clears out R1, leaving it empty. This program does not touch other registers.
Similarly, for each \(n\) there is a program \(\clearprog_n\) that clears out Rn. Is there a single program that clears out R\(n\) for all \(n\)?
Exercise 33
Write a program \(p\) that adds a \(\onett\) to the beginning of R1, assuming that R2 is empty. (For example, if R1 has \(\hash\hash\onett\) to start, then running \(p\) would result in R1 having \(\onett\hash\hash\onett\).)
onesharp(move_2_1, ['11#','####1##11111'])
'11#####1##11111'
The words in the brackets are the contents of registers 1 and 2 when we start. Again, our program moved the contents of R2 onto the end of R1, emptying R2. You should want to change the opening contents of R1 and R2 in the cell above before going on.
If you have an interpreter handy, you can parse this program and also get glosses.
parse(move_2_1)
['11#####', '111111###', '111###', '1##', '1111####', '1#', '111111####']
parse_explain(move_2_1)
\(\copyprog\)#
The second program in this section is called \(\copyprog\). Like \(\moveprog\), the \(\copyprog\) program is actually an infinite batch of programs. The difference between \(\moveprog\) and \(\copyprog\) for us is that when a register’s contents are \(\moveprog\)d, the register is left empty; but with \(\copyprog\), the register is left at the end with exactly what it had t the beginning.
In order to copy in this way, we need an auxiliary register, Rp. So while the \(\moveprog\) programs had two registers in their names, the \(\copyprog\) programs have three.
Here is our program when m = 1, n = 2, p = 3. That is, here is \(\copyprog_{1,2,3}\).
| 1##### | cases on R1 |
| 11111111### | go forward 8 to instruction 10 (the move3,1 part) |
| 1111### | go forward 4 to instruction 7 |
| 11## | add # to R2 |
| 111## | add # to R3 |
| 11111#### | go backward 5 to the top |
| 11# | add 1 to R2 |
| 111# | add 1 to R3 |
| 11111111#### | go backward 8 to the top |
| move3,1 | from earlier in this notebook |
The program is a loop, exactly like \(\moveprog_{m,n}\). Each time through, we not only replicate in Rn the first symbol of the word in Rm, but we also an additional copy into Rp. At the end, when Rm has been emptied, we return Rp to Rm and thus restore the original contents of Rm. But this only works as described when Rp was empty to begin with.
Exercise 34
Write a program which takes the contents of R1 and adds them to the ends of both R2 and R3.
Exercise 35
Write a program that clears out R1, leaving it empty.
Exercise 36
Write a program that clears R3 and then swaps the contents of R1 and R2 (using the now-empty R3).
Exercise 37
Write a program \(p\) that adds a \(\one\) to the beginning of R1, assuming that R2 is empty. (For example, if R1 has \(\hash\hash\one\) to start, then running \(p\) would result in R1 having \(\one\hash\hash\one\).) Of course, your program may use R2!
\(\writeprog\)#
We continue with a program \(\writeprog\) with the following properties:
When \(\writeprog\) is started with \(x\) in R1 and R2 empty, we eventually halt with a word \(y\) in R1 and all other registers empty.
Then \(y\) is a program, and running \(y\) with R1 empty results in \(x\) back in R1 and all other registers empty.
Before we explain \(\writeprog\), recall that running \(\onett\hash\hash\) adds a \(\onett\) to R1, and running \(\onett\hash\hash\) adds a \(\hash\).
As with \(\writeprog\) and \(\copyprog\), this program is a loop. Going symbol-by-symbol from the input in R1, \(\writeprog\) takes each \(\onett\) and adds \(\onett\hash\) to R2, and each \(\hash\) results in \(\onett\hash\hash\) in R2. These are instructions which would add \(\onett\) and \(\hash\) to R1. After the loop is done, the contents of R2 are moved back to R1.
The program \(\writeprog\) may be found in a chart.
| 1##### | cases on R1 |
| 111111111### | go forward 9 to the move2,1 part |
| 11111### | go forward 5: to the brown part |
| 11# | add 1 to R2 |
| 11## | add # to R2 |
| 11## | add # to R2 |
| 111111#### | go backward 6 (to the top) |
| 11# | add 1 to R2 |
| 11## | add # to R2 |
| 111111111#### | go backward 9 (to the top) |
| move2,1 | from earlier in this notebook |
Exercise 38
Why is the result of running \(\writeprog\) on a word \(x\) always a program, even if \(x\) is a word which is not a program?
Exercise 39
Modify \(\writeprog\) to get a program \(\writetotwo\) with the following feature: If \(\writetotwo\) is started with \(x\) in R1 and R2 empty, we eventually halt with a word \(y\) in R2 and all other registers empty; moreover, running \(y\) with R2 empty results in \(x\) back in R2 (not R1) and all other registers empty.
The \(+\) notation on words#
Definition 4
If \(x\) and \(y\) are words, then \(x + y\) is the concatenation of \(x\) followed by \(y\). For example,
This operation is associative: \(x + (y+z) = (x+y) + z\).
The empty word \(\eps\) is an identity element for it: \(x + \eps = x = \eps + x\). So we have a monoid
This means that we can “add” programs (since they are words). For example, let
This program \(q\) would take the contents of register 1, copy it into register 2 (using register 3), and then move register 2 back to register 1. So assuming that registers 2 and 3 were empty to begin with, running \(q\) with \(x\) in register \(1\) would give us \(x + x\) in register 1 at the end.
Exercise 40
Let’s take a word \(x\) and run \(\writeprog\) on it. Call the resulting program \(q\). Suppose that we run \(q\) on a word \(y\). Which do we get: \(x + y\) or \(y + x\)? That is, which is true?
Now let \(p\) be the program
copy_1_3_2 + write + move_3_1. Find an equation satisfied by \(p\). That is, fill in the blank
Now fill in another blank, where \(p\) again is
copy_1_3_2 + write + move_3_1: