Interpreters

Interpreters#

The programs of 1# can be run by hand. But they also can be run on an interpreter. An interpreter is itself a computer program, and to run a program on an interpreter, you will need to learn how to interact with it.

Online Javascript interpreter#

Here is an online interpreter for 1#. It was written in JavaScript by my former PhD students Robert Rose and David Sprunger.

To get started with it, enter 1#1##11#1# in the program editor box (the large box at the top). Then press ‘evaluate’ on the right. What happened is that the program executed the first instruction, 1#, adding a 1 to R1. Then it evaluated 1##, adding # to R1. Third, it executed 11#, adding 1 to R2. Finally, it executed 1#.

You can press the ‘evaluate’ button again, and it will execute the same program 1#1##11#1#, but this time it will execute it with words aleady in the registers. You can also physically add or change what is in the registers.

Python interpreter in this page#

The Javascript editor is convenient, and we hope you’ll at least try it out. It’s very basic, and most people would find it better to use an interpreter with more features, even if it means learning how to do so. For this, we have a Python interpreter. To use it, either download this notebook and run it locally, or else click on ‘Open in Colab’ at the top of this notebook. Then click on the triangle below. It should take some time (always less than a minute for me). Ignore all of the output on the screen, but look for a green check near where you clicked. This action loads a set of Python programs which are run in the backround in the rest of this notebook. You will not need to look at those programs.

You see below the interpreter. Even before learning how the language works, we want to see how to run programs by entering them into the interpreter along with inputs.

# @title Interpreter
program = '11#####111111###111###1##1111####1#111111####' #@param {type:"string"}
R1 = '#11###1' #@param {type:"string"}
R2 = '11111#' #@param {type:"string"}
#R3 = '' #@param {type:"string"}

## For more registers, add lines here like
## R4 = '' #@param {type:"string"}
## You also must modify the definition of 'a' below accordingly.

a = [R1,R2]
a = [remove_multiple_blanks(x) for x in a]

onesharp(program,a)

The first thing to do is to make everything nicer to look at by hiding the program above. To do this, click on the symbol to the left of the word Interpreter. This should cause the symbol to rotate, and it also should hide the code and make the display extend across your screen.

The top line of the interpreter should contain the following program of 1#

11#####111111###111###1##1111####1#111111####

If it does not contain this, feel free to copy and past the program above into the program box in the interpreter.

The other two lines are the inputs to two registers. The registers are called R1 and R2. The inputs are the same kind of mathematical object as the program: they are words on the alphabet {1,#}. In this book, words are just sequences composed of the symbols 1 and #, such as 11###11#1 and #1###1###111#11. We’ll have more to say about and programs soon.

Click on the arrow to run the program on the inputs, and look at the output at the bottom of the interpreter box.

Instead of clicking on the arrow, you also could type shift-return on a keyboard. This also will run the program on the inputs.

Modify the inputs to R1 and R2, but keep the program the same.

The empty word is a perfectly good word, so you could also enter it into R1 or R2 just by leaving the register blank or by entering one or more spaces. In fact, spaces are ignored in 1#.

You can modify \(R1\) and \(R2\) as many times as you like.

What you should find after doing this is that the output is the input in \(R1\) followed by the input in \(R2\). We also will say concatenated instead of followed by.

The overall point is that the program 11#####111111###111###1##1111####1#111111#### may be run on words which are input in the registers. This program does not change when we run it. Our little interpreter didn’t show the step-by-step behavior of the register machine, it only showed the final output. We’ll return to the soon, after we understand what the program is doing. It turns out that this program is composed of seven instructions. We’ll get to the instructions soon, but first we have an exercise for you to try.

Exercise 24

Just below, you’ll see another 1# program. It takes its input from the first two registers. Enter some words in R1 and R2 input boxes, and then run the program. Your job is to try to figure out what the program does.

1##### 11111111### 1111### 111## 1111## 11111#### 111# 1111# 11111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 1111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111####

Exercise 25

Again, start with 1 in R1 and R2, 1# in R3, and the other registers empty. What happens in each register if we run 111##? Try to figure this out for yourself, and then check your work by actually running the program.

Exercise 26

As before, start with \(\one\) in R1 and R2, \(\mathtt{1\#}\) in R3, and the other registers empty. What happens in each register if we run the same program \(\mathtt{111\#\#}\) from the previous exercise?

Exercise 27

Write a program which, when started with all registers empty, gives 1# in R1 and R2, 1# in R3, and the other registers empty.

Running programs in code cells#

Because notebooks like this are composed of cells, we also want to run programs in a command-line fashion.

To do this, click on an open area and get a Python cell. You now have a Python environment at your disposal, and in particular you can run the programs loaded in when you entered a button at the top of this notebook.

There are two Python program that run 1# programs. They are step_by_step and onesharp. These are illustrated in the next two cells. Both of these programs are written in Python, not in 1#. They both require as inputs a 1# program followed by a sequence of words composed of the symbols 1 and #.

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

step_by_step('1#11#####1###1###',['1#1','#'])

The last computation started with two inputs. Try changing those inputs to see what happens. We have not discussed ``halting’’ yet; for this, see this notbook If you want to read ahead, please do so. As practice with the definition of halt, you might try yourself to predict what will happen before running it. You can add the symbols \(\mathtt{1}\) or \(\mathtt{\#}\), and you also can delete symbols. But you should not delete the quote marks. Also, you can change the program the same way. The idea is that you should explore this function step_by_step by trying it out on simple inputs.

Here is an explanation of the form of the command step_by_step that we have been using.

The first argument could be a 1# program surrounded by single quotes or double-quotes. If you use single quotes, you need to be sure to use the correct ones; on my screen they look straight, not slanted. You could also use a concatenation of quoted expressions (see below). But if you forget the quotes, you will get an error because the Python program that is running all of this will balk at 1# expressions without quotes around them.

In addition, you can name expressions ahead of time using assignment statements like

p = '1#'

and then enter (for example)

step_by_step(p,['11']).

The program step_by_step begins with a parse of your program, and so if you input a word that is not a sequence of 1# expressions, it will stop without further ado.

The second argument to step_by_step is a list of words. A list in Python is enclosed by square brackets [ and ], not by parentheses. The words that go in the list are used in R1, R2, … in that order. It is understood that any register not represented by any input starts with the empty string. You can also represent the empty string by ‘ ‘. And the empty list of registers is denoted by two square brackets with nothing inside, [ ].

All in all, the examples below show different formats for the input to our function step_by_step.

p= '1#'
q = '#1'
step_by_step(p,[q,q,p])

So far in this notebook, we have only seen the function step_by_step. If we want to run things “in one fell swoop”, we could use the function onesharp(p,[r1,r2, . . ., rn]). It also takes two arguments, the first a program and the second a (possibly-empty) sequence of input words.

Attention

There is an important difference between the inputs to the Javascript interpreter and the inputs to the command-line program onesharp.

In the Javascript interpreter, the programs and input words are understood to be strings of symbols. One need not put quotes around them. In fact, doing so would give an error.

On the other hand, in the command-line tool, we need to take care to indicate (to the Python program that is being executed) that we are dealing with strings. So we need to puth quotes around the programs and the input words. (Alternatively, we could name a program by using an assignment statement, but in that statement we again need the quotes.) Also, in the second argument of onesharp, we need to use a list of words. This is a sequence of strings (again with quotes) enclosed in square brackets and separated by commas.

Useful command-line tools#

These are Python functions which you can call in a code cell, provide that you have run the very first cell in a notebook, the cell that loads in the relevant definitions.

Instruction	Meaning
`onesharp(p,[r1, . . .,rn])`	runs `p` on the list of words `[r1, . . .,rn]`
`step_by_step(p,[r1, . . .,rn])`	parses p and shows all steps in the run
`parse(p)`	expresses `p` as a list of instructions
`parse_explain(p)`	gives a table of `parse(p)` with glosses
`unparse(p)`	inverse of `parse(p)`

Useful operations inside a Jupyter notebook#

Similarly, here are some things that you should know how to do. You may find instructions on this by searching for tutorial help on Jupyter notebooks.

Stop a program that is either in an infinite loop or otherwise is going too long.
Insert code cells above or below the current cell.
Insert text cells above or below the current cell.
Add a comment to a cell using # as the first character in a line.
Delete a cell.
Open a new notebook.

Tip

You need to know the commands of 1# well to go forward.

You don’t need to know much about Python, but it would help to know the basics of strings and lists. Some exercises will ask you to write Python code, and if you want to solve them you of course would need to know more.

It would be good to read about the basics of Jupyter notebooks.