Link to the the Google Colaboratory notebook

- The Google Colaboratory notebook has the advantage that you can run PyRamPl code from it without having to install PyRamPL or even Python on your local system.
- You first need to copy it to your google drive
- You can also download it to your local device and open it as a Jupyter notebook (if you have it installed with your Python).

- The
**PyRamPL**package can be installed on your local system by running the following command from the command line`pip install pyrampl`

- Or you may try running one of the following commands from this notebook.
- If you are running it from a Jupyter notebook on your local system, then it will be installed on your device.

In [1]:

```
# To install from this notebook, run this cell.
%pip install pyrampl
# This should also work:
#!pip install --upgrade pyrampl
# After installation, you have to restart this notebook.
# Make sure to comment the %pip or !pip lines above to avoid reinstall each time you run this notebook.
# To uninstall the package use:
#%pip uninstall pyrampl
# or
#!pip uninstall pyrampl
```

**After installation, you may need to restart this notebook.**

**PyRamPL**is a simple Python package for simulating Random Access Memory Machine programs within the context of an introductory course on computational models.- It is a lightweight package especially designed for small RAM programs, such as those that are presented in introductory academic courses on the theory of computation.
- It can be a useful companion for theoretical courses on
computation models and languages who wish also to engage
the students with some programming experience and skills.
- It was designed to be used in such a course by the author (Hebrew book at http://samyzaf.com/afl.pdf).
- It enables students to easily experiment with RAM programs for their exercises, and to test correctness of their solutions.

- It also provide an opportunity for students to get a taste of how programming looks like while learning theoretical computation course.
- There are many different definitions of a RAM machine in the literature but from an educational perspective most of them are adequate for presenting a computational model resembling a modern computer system and its associated assembly programming language.
WARNING! Our current very

**early version of PyRamPL**is not yet making good syntactical checks, so make sure to write your RAM programs correctly or else you will not get any meaningful feedback! Since RAM programs have a very simple syntax we do not expect this to be a real problem.

Instruction | Description |
---|---|

$a=b$ | Load register $b$ to register $a$ |

$a=i$ | Load integer $i$ to register $a$ |

$a = b+c$ | Add $b$ and $c$ and store the result in $a$ |

$a=b-c$ | Subtraction |

$a = b * c$ | Multiplication |

JUMP(i) | Jump to instruction i (PC = i) |

JZERO(r, i) | If $r=0$ jump to instruction i |

JPOS(r, i) | If $r>0$ jump to instruction i |

JE(a, b, i) | If $a=b$ jump to instruction i |

HALT | Stop the program |

</font>

The following RAM program computes the integer quotient and a remainder ($y_1$ and $y_2$) after dividing $x_1$ by $x_2$

```
PROGRAM DIVMOD(x1, x2 : y1, y2)
1. r1 = x1
2. r2 = x2
3. r0 = r2 - r1
4. JPOS(r0, 8)
5. r3 = r3 + 1
6. r1 = r1 - r2
7. JUMP(3)
8. y1 = r3
9. y2 = r1
10. HALT
```

- The common practice is to build a
**Flow Diagram**for your algorithm before you actually write the RAM program. - In the following flow diagram for
`DIVMOD`

we have also added instruction labels that correspond to the RAM code (these are normally not part of a flow diagram) to make it easier to comprehend the RAM program.

- After installing the
**PyRamPl**package, you need to import it. - The following command imports
**PyRamPl**to your Python interpreter. - We have also imported a few IPython display utilities for displaying Markdown and LaTeX tables.

In [2]:

```
from pyrampl import *
from IPython.display import display, Markdown, Latex
```

In [3]:

```
code = """
PROGRAM DIVMOD(x1, x2 : y1, y2)
1. r1 = x1
2. r2 = x2
3. r0 = r2 - r1
4. JPOS(r0, 8)
5. r3 = r3 + 1
6. r1 = r1 - r2
7. JUMP(3)
8. y1 = r3
9. y2 = r1
10. HALT
"""
```

In [4]:

```
DIVMOD = Ram("DIVMOD", code)
```

In [5]:

```
y1, y2 = DIVMOD(17,5)
print(f"Dividing 17 by 5 result: y1={y1}, y2={y2}")
```

Dividing 17 by 5 result: y1=3, y2=2

- Note that we first define our RAM program as text string
`code`

, and then create a`Ram`

object by invoking the`Ram`

Python class. - The
`Ram`

class accepts two arguments:- Machine name
- Program text or file name for the program text

- If we put our program text in a file like divmod.ram,
we can also create our machine object with a command such as
`DIVMOD = Ram("DIVMOD", "divmod.ram")`

- In all examples we use capital letter names for the
`Ram`

objects. Usually identical to their internal names.

- As we already have addition and multiplication in our base RAM instructions, we now show how to build a RAM machine for the exponential function.
- Lets first start with a flow diagram for the exponential function

In [6]:

```
code = """
PROGRAM EXP(x1, x2 : y1, y2)
1. r1 = x1
2. r2 = x2
3. JZERO(r1, 9)
4. r3 = 1
5. JZERO(r2, 14)
6. r3 = r3 * r1
7. r2 = r2 - 1
8. JUMP(5)
9. JZERO(r2, 12)
10. y1 = 0
11. JUMP(15)
12. y2 = 1
13. JUMP(15)
14. y1 = r3
15. HALT
"""
```

- As you can see, our
`EXP`

version has two outputs $y_1$ and $y_2$ - The first one holds the exponential result if the input is legal.
- In case of an illegal input like $x_1=x_2=0$, the second output will be set to $y_2=1$

In [7]:

```
EXP = Ram("EXP", code)
```

In [8]:

```
y1,y2 = EXP(2,5)
print(f"y1={y1}, y2={y2}")
```

y1=32, y2=0

In [9]:

```
y1,y2 = EXP(0,0)
print(f"y1={y1}, y2={y2}")
```

y1=0, y2=1

- Once we have built a RAM machine such as
`DIVMOD`

, we can use it as an instruction within a new RAM machine. - Formally, a RAM machine which used other RAM machine is called
**Generalized RAM Machine**, but there is a Theorem that assures that for every generalized RAM machine there is an equivalent RAM machine - The following flow diagram for the
`PRIME`

algorithm is using the`DIVMOD`

instruction which we have defined above.

In [10]:

```
code = """
PROGRAM PRIME(x1 : y1)
1. y1 = 1
2. r1 = x1 - 3
3. JPOS(r1, 5)
4. HALT
5. r0 = 2
6. r1,r2 = DIVMOD(x1,r0)
7. JZERO(r2, 11)
8. r0 = r0 + 1
9. JE(r0, x1, 12)
10. JUMP(6)
11. y1 = 0
12. HALT
"""
```

In [11]:

```
PRIME = Ram("PRIME", code)
y = PRIME(19)
print(f"y={y}")
```

y=1

- A simple way to observe and comprehend a RAM machine is by looking at snapshots of its register values.
- A snapshot consists of all the current values of input, memory, and output registers.
- A
**computation table**consists of the full sequence of all the machine snapshots from its start to end. - The
**PyRamPL**package contains a special method for displaying this table as a markdown table (so you need to run it inside a markdown viewer such as an Ipython Jupyter Notebook) - I the following example we display the computation table of the RAM machine
`PRIME`

for the input $x_1=7$.

In [12]:

```
display_table(PRIME, 7)
```

Frame | Instruction | x1 | r0 | r1 | r2 | y1 |
---|---|---|---|---|---|---|

0 | Init | 7 | 0 | 0 | 0 | 0 |

1 | 1. y1 = 1 | 7 | 0 | 0 | 0 | 1 |

2 | 2. r1 = x1 - 3 | 7 | 0 | 4 | 0 | 1 |

3 | 3. JPOS(r1, 5) | 7 | 0 | 4 | 0 | 1 |

4 | 5. r0 = 2 | 7 | 2 | 4 | 0 | 1 |

5 | 6. r1,r2 = DIVMOD(x1,r0) | 7 | 2 | 3 | 1 | 1 |

6 | 7. JZERO(r2, 11) | 7 | 2 | 3 | 1 | 1 |

7 | 8. r0 = r0 + 1 | 7 | 3 | 3 | 1 | 1 |

8 | 9. JE(r0, x1, 12) | 7 | 3 | 3 | 1 | 1 |

9 | 10. JUMP(6) | 7 | 3 | 3 | 1 | 1 |

10 | 6. r1,r2 = DIVMOD(x1,r0) | 7 | 3 | 2 | 1 | 1 |

11 | 7. JZERO(r2, 11) | 7 | 3 | 2 | 1 | 1 |

12 | 8. r0 = r0 + 1 | 7 | 4 | 2 | 1 | 1 |

13 | 9. JE(r0, x1, 12) | 7 | 4 | 2 | 1 | 1 |

14 | 10. JUMP(6) | 7 | 4 | 2 | 1 | 1 |

15 | 6. r1,r2 = DIVMOD(x1,r0) | 7 | 4 | 1 | 3 | 1 |

16 | 7. JZERO(r2, 11) | 7 | 4 | 1 | 3 | 1 |

17 | 8. r0 = r0 + 1 | 7 | 5 | 1 | 3 | 1 |

18 | 9. JE(r0, x1, 12) | 7 | 5 | 1 | 3 | 1 |

19 | 10. JUMP(6) | 7 | 5 | 1 | 3 | 1 |

20 | 6. r1,r2 = DIVMOD(x1,r0) | 7 | 5 | 1 | 2 | 1 |

21 | 7. JZERO(r2, 11) | 7 | 5 | 1 | 2 | 1 |

22 | 8. r0 = r0 + 1 | 7 | 6 | 1 | 2 | 1 |

23 | 9. JE(r0, x1, 12) | 7 | 6 | 1 | 2 | 1 |

24 | 10. JUMP(6) | 7 | 6 | 1 | 2 | 1 |

25 | 6. r1,r2 = DIVMOD(x1,r0) | 7 | 6 | 1 | 1 | 1 |

26 | 7. JZERO(r2, 11) | 7 | 6 | 1 | 1 | 1 |

27 | 8. r0 = r0 + 1 | 7 | 7 | 1 | 1 | 1 |

28 | 9. JE(r0, x1, 12) | 7 | 7 | 1 | 1 | 1 |

29 | 12. HALT | 7 | 7 | 1 | 1 | 1 |

In [13]:

```
display_table(EXP, 5, 2)
```

Frame | Instruction | x1 | x2 | r1 | r2 | r3 | y1 | y2 |
---|---|---|---|---|---|---|---|---|

0 | Init | 5 | 2 | 0 | 0 | 0 | 0 | 0 |

1 | 1. r1 = x1 | 5 | 2 | 5 | 0 | 0 | 0 | 0 |

2 | 2. r2 = x2 | 5 | 2 | 5 | 2 | 0 | 0 | 0 |

3 | 3. JZERO(r1, 9) | 5 | 2 | 5 | 2 | 0 | 0 | 0 |

4 | 4. r3 = 1 | 5 | 2 | 5 | 2 | 1 | 0 | 0 |

5 | 5. JZERO(r2, 14) | 5 | 2 | 5 | 2 | 1 | 0 | 0 |

6 | 6. r3 = r3 * r1 | 5 | 2 | 5 | 2 | 5 | 0 | 0 |

7 | 7. r2 = r2 - 1 | 5 | 2 | 5 | 1 | 5 | 0 | 0 |

8 | 8. JUMP(5) | 5 | 2 | 5 | 1 | 5 | 0 | 0 |

9 | 5. JZERO(r2, 14) | 5 | 2 | 5 | 1 | 5 | 0 | 0 |

10 | 6. r3 = r3 * r1 | 5 | 2 | 5 | 1 | 25 | 0 | 0 |

11 | 7. r2 = r2 - 1 | 5 | 2 | 5 | 0 | 25 | 0 | 0 |

12 | 8. JUMP(5) | 5 | 2 | 5 | 0 | 25 | 0 | 0 |

13 | 5. JZERO(r2, 14) | 5 | 2 | 5 | 0 | 25 | 0 | 0 |

14 | 14. y1 = r3 | 5 | 2 | 5 | 0 | 25 | 25 | 0 |

15 | 15. HALT | 5 | 2 | 5 | 0 | 25 | 25 | 0 |

In [14]:

```
display_table(DIVMOD, 18, 5)
```

Frame | Instruction | x1 | x2 | r0 | r1 | r2 | r3 | y1 | y2 |
---|---|---|---|---|---|---|---|---|---|

0 | Init | 18 | 5 | 0 | 0 | 0 | 0 | 0 | 0 |

1 | 1. r1 = x1 | 18 | 5 | 0 | 18 | 0 | 0 | 0 | 0 |

2 | 2. r2 = x2 | 18 | 5 | 0 | 18 | 5 | 0 | 0 | 0 |

3 | 3. r0 = r2 - r1 | 18 | 5 | -13 | 18 | 5 | 0 | 0 | 0 |

4 | 4. JPOS(r0, 8) | 18 | 5 | -13 | 18 | 5 | 0 | 0 | 0 |

5 | 5. r3 = r3 + 1 | 18 | 5 | -13 | 18 | 5 | 1 | 0 | 0 |

6 | 6. r1 = r1 - r2 | 18 | 5 | -13 | 13 | 5 | 1 | 0 | 0 |

7 | 7. JUMP(3) | 18 | 5 | -13 | 13 | 5 | 1 | 0 | 0 |

8 | 3. r0 = r2 - r1 | 18 | 5 | -8 | 13 | 5 | 1 | 0 | 0 |

9 | 4. JPOS(r0, 8) | 18 | 5 | -8 | 13 | 5 | 1 | 0 | 0 |

10 | 5. r3 = r3 + 1 | 18 | 5 | -8 | 13 | 5 | 2 | 0 | 0 |

11 | 6. r1 = r1 - r2 | 18 | 5 | -8 | 8 | 5 | 2 | 0 | 0 |

12 | 7. JUMP(3) | 18 | 5 | -8 | 8 | 5 | 2 | 0 | 0 |

13 | 3. r0 = r2 - r1 | 18 | 5 | -3 | 8 | 5 | 2 | 0 | 0 |

14 | 4. JPOS(r0, 8) | 18 | 5 | -3 | 8 | 5 | 2 | 0 | 0 |

15 | 5. r3 = r3 + 1 | 18 | 5 | -3 | 8 | 5 | 3 | 0 | 0 |

16 | 6. r1 = r1 - r2 | 18 | 5 | -3 | 3 | 5 | 3 | 0 | 0 |

17 | 7. JUMP(3) | 18 | 5 | -3 | 3 | 5 | 3 | 0 | 0 |

18 | 3. r0 = r2 - r1 | 18 | 5 | 2 | 3 | 5 | 3 | 0 | 0 |

19 | 4. JPOS(r0, 8) | 18 | 5 | 2 | 3 | 5 | 3 | 0 | 0 |

20 | 8. y1 = r3 | 18 | 5 | 2 | 3 | 5 | 3 | 3 | 0 |

21 | 9. y2 = r1 | 18 | 5 | 2 | 3 | 5 | 3 | 3 | 3 |

22 | 10. HALT | 18 | 5 | 2 | 3 | 5 | 3 | 3 | 3 |

- The following RAM program shows how we can code Euclid's GCD algorithm within the limited bound of the RAP program syntax.
- Note that it uses the
`DIVMOD`

machine which we defined earlier in two different places (re rectangles) - It is not fully complete, as it avoids checking zero division issues.

In [15]:

```
code = """
PROGRAM GCD(x1, x2 : y1)
1. r1 = x1
2. r2 = x2
3. JZERO(r1, 11)
4. JZERO(r2, 13)
5. r0 = r1 - r2
6. JPOS(r0, 15)
7. r0 = r2 - r1
8. JPOS(r0, 17)
9. y1 = r1
10. HALT
11. y1 = r2
12. HALT
13. y1 = r1
14. HALT
15. r3, r1 = DIVMOD(r1, r2)
16. JUMP(3)
17. r3, r2 = DIVMOD(r2, r1)
18. JUMP(4)
19. HALT
"""
```

In [16]:

```
GCD = Ram("GCD", code)
```

In [17]:

```
y = GCD(72,54)
print(f"The greatest common divisor of 72 and 54 is {y}")
```

The greatest common divisor of 72 and 54 is 18

In [18]:

```
code = """
PROGRAM MAX4(x1, x2, x3, x4 : y1)
1. y1 = x1
2. r0 = y1 - x2
3. JPOS(r0,5)
4. y1 = x2
5. r0 = y1 - x3
6. JPOS(r0,8)
7. y1 = x3
8. r0 = y1 - x4
9. JPOS(r0,11)
10. y1 = x4
11. HALT
"""
```

In [19]:

```
MAX4 = Ram("MAX4", code)
```

In [20]:

```
MAX4(2, 26, 9, 4)
```

Out[20]:

26

- The
`GETBIT`

and`SETBIT`

are important for simulating a Turing machine by a RAM machine. - The Turing machine tape is represented by a binary string encoded as an integer number.
- The
`GETBIT`

functions extracts the binary bit of an integer at a given place. - For example: $41 = 101001_2$.
- Therefore GETBIT(41,0) = 1, GETBIT(41,1) = 0, GETBIT(41,2) = 0, GETBIT(41,3) = 1, etc.
- The
`SETBIT`

function sets the bit of an integer at a given location. - For example: SETBIT(41,2,1) = 45.

In [21]:

```
code1 = """
PROGRAM GETBIT(x1, x2 : y1)
1. r1 = x1
2. r2 = x2
3. r1,r0 = DIVMOD(r1, 2)
4. JZERO(r2, 7)
5. r2 = r2 -1
6. JUMP(3)
7. y1 = r0
8. HALT
"""
```

In [22]:

```
code2 = """
PROGRAM SETBIT(x1, x2, x3 : y1)
1. r0 = GETBIT(x1, x2)
2. JE(r0, x3, 9)
3. r1,r2 = EXP(2, x2)
4. JPOS(x3, 7)
5. y1 = x1 - r1
6. HALT
7. y1 = x1 + r1
8. HALT
9. y1 = x1
10. HALT
"""
```

In [23]:

```
GETBIT = Ram("GETBIT", code1)
SETBIT = Ram("SETBIT", code2)
```

In [24]:

```
y1 = SETBIT(41, 2, 1)
print(y1)
```

45

In [25]:

```
display_table(SETBIT,9, 2, 1)
```

Frame | Instruction | x1 | x2 | x3 | r0 | r1 | r2 | y1 |
---|---|---|---|---|---|---|---|---|

0 | Init | 9 | 2 | 1 | 0 | 0 | 0 | 0 |

1 | 1. r0 = GETBIT(x1, x2) | 9 | 2 | 1 | 0 | 0 | 0 | 0 |

2 | 2. JE(r0, x3, 9) | 9 | 2 | 1 | 0 | 0 | 0 | 0 |

3 | 3. r1,r2 = EXP(2, x2) | 9 | 2 | 1 | 0 | 4 | 0 | 0 |

4 | 4. JPOS(x3, 7) | 9 | 2 | 1 | 0 | 4 | 0 | 0 |

5 | 7. y1 = x1 + r1 | 9 | 2 | 1 | 0 | 4 | 0 | 13 |

6 | 8. HALT | 9 | 2 | 1 | 0 | 4 | 0 | 13 |

- This section is relevant for students with Python programming experience.
- We present few examples on how you can perform more thorough tests on your RAM programs
- Notes:
**ic**stands for the instruction counter**vardict**stands for the variables dictionary (input/memory/output)

In [26]:

```
DIVMOD.init(17,5)
DIVMOD.run()
frames = DIVMOD.frames
for ic,instruction,vardict in frames:
y1 = vardict['y1']
y2 = vardict['y2']
print(f"{ic:<5} {instruction:<20} y1={y1} y2={y2}")
```

- You may isolate one or more registers and watch its progress

In [27]:

```
for ic,instruction,vardict in frames:
r0 = vardict['r0']
r1 = vardict['r1']
r2 = vardict['r2']
r3 = vardict['r3']
print(f"ic={ic:<4} : {instruction:<16} : r0 ={r0:<3} : r1 = {r1:<3} : r2 = {r2:<3} : r3 = {r3:<3}")
```