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.

!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main

from onesharp.interpreter.interpreter import onesharp
from onesharp.tools.sanity import sanity
from onesharp.tools.ones import ones
from onesharp.programs.clear import clear
from onesharp.programs.move import move
from onesharp.programs.copy import copy
from onesharp.programs.successor import successor
from onesharp.programs.compare import compare
from onesharp.programs.add import add

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 a loop that involves cases on R1. At the end of the \(i\)th pass through the loop, we’ll have \(w_{i+1}\cdots w_n\) in R1, and its prefix \(w_{i}\cdots w_2 w_1\) will be in R2, but it will appear there reversed. Thus, after \(n\) passes through the loop, the desired reversal will be in R2. This is how the flowchart ends.

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 \(\one\), we write the same symbol \(\one\) 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 \(\hash\). 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.

reverse_idea = [
    ['top', 'cases', 1, 'move_back', 'one_found', 'hash_found'],
    ['one_found','111#'],
    ['goto', 'move_phase'],
    ['hash_found',  '111##'],
    ['goto', 'move_phase'],
    ['move_phase', move(2,3) + move(3,2)],
    ['goto', 'top'],
    ['move_back', move(2,1)]
]

We have here 8 segments. A segment is not the same what we called a line of a \(\one\hash\) 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 \(\one\hash^5\), 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 \(\one\) 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) make an “idea” for the desired program using the flowchart, an “idea” with special requirements that we discuss below

(d) call a Python program called sanity on the “idea” to get a \(\one\hash\) program which you can then run.

# example

rev = sanity(reverse_idea)

# This run 'sanity' on 'reverse_idea', calling the result 'rev'.
# We can refer to it in the rest of this notebook by 'rev'.
# For example we can display our new program
rev

'1#####1111111111111111111111###11###111###111#111###111##1###11#####11111 1###111###111##1111####111#11111 1####111#####11111 1###111###11##1111####11#11111 1####1111111111111111111111####11#####11111 1###111###1##1111####1#11111 1####'

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

onesharp(rev,['1####'])

'####1'

# Here is a way to write the program 'clear_1':
sanity([
    ['top', 'cases',1,'empty', 'one','hash'],
    ['empty', 'goto', 'end'],
    ['one','goto', 'top'],
    ['hash', 'goto', 'top'],
])

'1#####111###111###111###111###11111####111111####'

Invitation to Computability

Tools to help write programs

Contents

Tools to help write programs¶

Workflow¶

The inputs to `sanity`¶

Examples of segments:¶

How does Sanity work?¶

Further programs and exercises¶

	contents
1
2	#
3
4	1

Invitation to Computability

Tools to help write programs

Contents

Tools to help write programs¶

Workflow¶

The inputs to sanity¶

Examples of segments:¶

How does Sanity work?¶

Further programs and exercises¶

The inputs to `sanity`¶