Tools to help write programs¶

The main tool here is a Python program called Sanity. This tool makes it easier for someone to organize 1# programs and to write them without having to count lines for all of the forward- and backward-transfer statements.

The concept and the name come from Jon Bowman, who once took my class and felt that construction 1# programs by hand was crazy, and that counting all the 1's in a long expression "made his eyeballs bleed."

To start, run the next code cell to install the 1# Python package in your Colab environment. Then run the second code cell to import the functions from the 1# package which are used in this notebook.

As a way to show what the tool does, we'll go through an example. Let's write a program that takes a word

$$w = w_1 w_2 \cdots w_n$$

in R1 and reverses it.
Here is a flowchart for the program which we'll write:

Our program will work as follows. It processes the letters in $w$ in order, using the loop shown in the top part of the flowchart.

At the end of the $i$th iteration, we'll have $w_{i+1}\cdots w_n$ in R1, and its prefix will be in R2 backwards: $w_{i}\cdots w_2 w_1$.
Let's now consider what happens when we run the $(i+1)$-st iteration of the loop. We have cases on the first symbol of R1, and we know that this is $w_{i+1}$. If that first symbol is a 1, we write it into R3, and then we move R2 onto the end of R3 (emptying out R2) and then R3 is moved back go R2. On the assumption that R2 had $w_{i}\cdots w_2 w_1$ before this iteration, it now has $w_{i+1} w_{i}\cdots w_2 w_1$. The same thing happens if the first symbol in R1 was #. Finally, if R1 was empty, we would go to the bottom of the flowchart. In this case, R2 would have $w_{n}\cdots w_2 w_1$. (This is what we want; it is the original input reversed.) And the flowchart indicates that we should move R2 back into R1. So we are done.

With this in mind, have a look at the following Python list called 'reverse_idea'. It is a list of 8 arrays, and each of them is of a special form.

We have here 8 segments. A segment is not the same what we called a line of a 1# program. As the name suggests, a segment corresponds to a sequence of lines. For example, segments 6 and 8 each contain move programs that are bigger than a single instruction. Segments 2, 4 5, and 6 each begin with a label. Labels are strings that other parts of the program could point to. For example, the first segment is a case statement 1#####, and it also contains the information that if R1 is empty, we should go to whichever segmet has the label "move_phase". (That would be the segment named 'move_stuff_around'.) The first segment also tells us that if R1 begins with 1 we should (delete is and) go to the segment containing 'first-is_one'. Note also that 'goto' is not a label.

Also, note that a segment is not quite the samething as an item in the flowchart. But this is pretty close.

Workflow¶

The workflow in this notebook is that you will need to

(a) think about things deeply enough to make a correct flowchart

(b) draw that flowchart, either with pencil and paper or with some tool (as I did here)

(c) call a Python program called sanity on reverse_idea to get a 1# program which you can then run.

Now the program which we just constructed can be run, as usual:

The inputs to sanity¶

{admonition}
:class: attention

A segment is a Python list: it must be surrounded by square brackects.

A segment can be snippet of ```1#``` code surrounded by quotes.  

A segment can be a Python expression like 
```move_3_1 + move_2_1```
that denotes a ```1#`````` word.  (These expressions must be defined before you run ```sanity```, or you will get an error.)

A segment can have ```add1``` or ```add#``` followed by a number (without quotes).  This number is a register number.

A segment may be the word 'cases' followed by a number and then three labels.

A segment may optionally begin with a *label* like 'top', or 'moveback', and then it either consists of a snippet of ```1#``` code surrounded by single quotes, or a Python expression that denotes a snippet of ```1#`````` code.

{admonition}
:class: attention

A label may be a word of English, and it may have the underscore symbol, but it should not have spaces.  It must be surrounded by quotes.  

A label must not begin with ```1``` or ```1#```, and it must not be one of the strings 'goto', 'end', 'add1', or 'add#'.

*Labels are optional*, except a "cases" instruction
must have a number and then three labels.   The number is for a register.   So "cases on register 17" would correspond to 
a segment with the number 17 as its third entry.

Another label which may be used is 'goto'.
A use of 'goto' must be followed either by a label or the word 'end'.



Every label used inside a 'cases' or 'goto' statement must be the first label in some segment.  Otherwise, ```sanity``` will raise an error.

Here is another example

Examples of segments:¶

['top','cases',1,'empty', 'one_found','hash_found'],
['empty', 'goto', 'moveback'],
['one_found', 'add1', 2],
['111#111##'],
['goto', 'top'],
['hash_found', 'add#', 2],
['111#111##111##'],
['goto', 'end'],
['moveback', move(3,1)+move(2,1)]

Further programs and exercises¶