{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyMIIgx/A+TCmazJW+rausKy", "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "source": [ "# Simple programs\n", "\n", "We have seen the syntax of $\\one\\hash$ instructions \n", "[in a previous notebook](syntax-summary).\n", "We turn to the simplest programs in the language." ], "metadata": { "id": "8C7LMBIh5Hmr" } }, { "cell_type": "code", "source": [ "!python -m pip install -U setuptools\n", "!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main\n", "from onesharp.interpreter.interpreter import *" ], "metadata": { "id": "ZUEj49fx7gDq" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "## move_2_1\n", "\n", "The first is a program called ```move_2_1```. It is designed to move the contents of R2 onto the end of R1, emptying out R2 in the process. Written out in full it is \n", "\n", "```11#####111111###111###1##1111####1#111111####```\n", "\n", "But we have defined ```move_2_1``` to be this program, and so you can run it as shown below.\n", "\n", "You can try the program by entering the following line. In it\n" ], "metadata": { "id": "Q1NfvunUI9ui" } }, { "cell_type": "code", "source": [ "onesharp(move_2_1, ['11#','####1##11111'])" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "id": "JnrcdeAl_Kmm", "outputId": "3f228e38-08a4-4272-c30d-0d1a03639eab" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "'11#####1##11111'" ], "application/vnd.google.colaboratory.intrinsic+json": { "type": "string" } }, "metadata": {}, "execution_count": 7 } ] }, { "cell_type": "markdown", "source": [ "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." ], "metadata": { "id": "ZEn2WieG_RJY" } }, { "cell_type": "markdown", "source": [ "(content:parsing)=\n", "It is hard to understand a program of $\\one\\hash$, but we have tools to help. First, we can *parse* the program. Parsing means dividing the program into instructions." ], "metadata": { "id": "0YHJpDX7_pDf" } }, { "cell_type": "code", "source": [ "parse(move_2_1)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "vc_brPCuG_qG", "outputId": "a8c37f98-ab93-451e-ae5b-29dc38ef68db" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "['11#####', '111111###', '111###', '1##', '1111####', '1#', '111111####']" ] }, "metadata": {}, "execution_count": 6 } ] }, { "cell_type": "markdown", "source": [ "Even better, we can get an parse with glosses, as follows:" ], "metadata": { "id": "ezY3wZ1BHCq_" } }, { "cell_type": "code", "source": [ "parse_explain(move_2_1)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 269 }, "id": "S-4FiMeLHFcP", "outputId": "182a9974-e843-4eb4-f32c-ece4236b9eca" }, "execution_count": null, "outputs": [ { "output_type": "display_data", "data": { "text/plain": [ "" ], "text/html": [ "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
 instructionexplanation
111#####cases on R2
2111111###go forward 6 to instruction 8
3111###go forward 3 to instruction 6
41##add # to R1
51111####go backward 4 to instruction 1
61#add 1 to R1
7111111####go backward 6 to instruction 1
\n" ] }, "metadata": {} } ] }, { "cell_type": "markdown", "source": [ "The program ```move_2_1``` is a loop, and we can further add to the explanations in the chart.\n" ], "metadata": { "id": "iv_DHKDpHK1A" } }, { "cell_type": "code", "source": [ "#@title\n", "j = [['11#####', 'cases on R2', ],\n", " ['111111###', \"register 2 is empty: go forward 6 to instruction 8 (we're done)\"],\n", " ['111###', 'first symbol is a 1: go forward 3 to instruction 6 (to the tan section)'],\n", " ['1##', 'first symbol is a #: add # to R1'],\n", " ['1111####', 'go backward 4 to instruction 1 (to the top)'],\n", " ['1#', 'add 1 to R1'],\n", " ['111111####', 'go backward 6 to instruction 1 (to the top)']\n", "]\n", " \n", "df = pd.DataFrame(j,columns=[\"instruction\", 'explanation'])\n", "df.index = np.arange(1, len(df) + 1)\n", "df.style.set_properties(**{'border': '1.3px solid green',\n", " 'color': 'magenta'})\n", "n = len(df.columns)\n", "df.style.set_properties(**{'text-align': 'left'})\n", "#df.style.apply(lambda x: [\"background-color: red\"]*n if x['instruction']== 'Reading' else [\"background-color: white\"]*n, axis = 1)\n", "#df.style.apply(lambda x: [\"background-color: #B0E0E6\"]*n if x['instruction'] in ['1##','1111####'] elif [\"background-color: #D4B48C\"]*n if x['instruction'] in ['1#','111111####'] else [\"background-color: #FFFFCC\"]*n, axis = 1)\n", "df.style.apply(lambda x: [\"background-color: #B0E0E6\"]*n if x['instruction'] in ['1##','1111####'] else [\"background-color: #FFFFCC\"]*n, axis = 1)\n", "df.style.apply(lambda x: \n", " [\"background-color: #B0E0E6\"]*n if x['instruction'] in ['1##','1111####'] \n", " else [\"background-color: #D4B48C\"]*n if x['instruction'] in ['1#','111111####']\n", " else [\"background-color: #FFFFCC\"]*n, axis = 1)\n" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 269 }, "id": "r0RbyVhEHLNl", "outputId": "a7cdbc5d-2467-4373-f008-083cdbdbbfa1", "cellView": "form" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "" ], "text/html": [ "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
 instructionexplanation
111#####cases on R2
2111111###register 2 is empty: go forward 6 to instruction 8 (we're done)
3111###first symbol is a 1: go forward 3 to instruction 6 (to the tan section)
41##first symbol is a #: add # to R1
51111####go backward 4 to instruction 1 (to the top)
61#add 1 to R1
7111111####go backward 6 to instruction 1 (to the top)
\n" ] }, "metadata": {}, "execution_count": 9 } ] }, { "cell_type": "markdown", "source": [ "\n", "\n", "If R2 is empty, it goes to line 8. Since the program itself only has 7 lines, this means that we have transferred *out* of the program. We say that the program *halts* at that point.\n", "\n", "If the first symbol of R2 is a 1, then the second instruction after the case instruction at the top transfers us down to line 6. This part of the program would then add a 1 to R1 and return to the very beginning of the program.\n", "\n", "If the first symbol of R2 is a #, then we delete that # and go three steps forward, to line 4. This part of the program would then add a # to R1 and return to the very beginning of the program.\n", "\n", "The point is that by going around loop repeatedly, we transfer the contents of R2 symbol-by-symbol to R1.\n", "Similarly, whenever m and n are different numbers, we can build a program ```move_m_n```. This program would write the contents of Rm onto the end of Rn, emptying Rm in the process.\n", "\n", "\n", "\n" ], "metadata": { "id": "QTzah7w_HPuf" } }, { "cell_type": "markdown", "source": [ "## Modifying ```move_2_1```\n", "\n", "Suppose we want to modify ```move_2_1``` to get ```move_3_4```, a program which would copy the contents of R3 onto the end of R4 (and empty R4) in the process. Here is a way to do this which shows off some command-line tools that are part of the working environment of this course." ], "metadata": { "id": "zwwhQ5vhHSTG" } }, { "cell_type": "code", "source": [ "parse(move_2_1)" ], "metadata": { "id": "OF19Znw8HW6K" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "When you enter the cell above, you get the program ```move_2_1``` as a Python *list* of instructions. We have seen the explanation of this parse above. What we want to do in ```move_3_4``` is to change the overall \"case\" instruction in the beginning from ```11#####``` to ```111#####```. And each time our program writes to a register, we want that register to be R4, not R1. So we make two changes." ], "metadata": { "id": "v3a4Q88MHZfr" } }, { "cell_type": "code", "source": [ "unparse(pre_program)" ], "metadata": { "id": "nUBPolu9HbSo" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "We can check this out by entering it into the interpreter. We could either copy the output line (without the quotes), and go up to the top of this notebook. Alternatively, we could move the interpreter down to here using an up-arrow command that you will need to find.\n" ], "metadata": { "id": "4lB7XVf6HfvT" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Write a program which takes the contents of R1 and adds them to the ends of *both* R2 and R3.\n", "```" ], "metadata": { "id": "-6HzTRCIHirm" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Write a program that clears out R1, leaving it empty.\n", "```" ], "metadata": { "id": "RwKmd0ubHnBp" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Write a program that clears R3 and then swaps the contents of R1 and R2 (using the now-empty R3).\n", "```\n" ], "metadata": { "id": "vGMfoJ02HqNX" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "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!\n", "```" ], "metadata": { "id": "F3QwMdfwHtDq" } }, { "cell_type": "markdown", "source": [ "## copy\n", "\n", "The second program in this notebook is called ```copy```.\n", "Like ```move```, the ```copy``` program is actually an infinite batch of programs. \n", "\n", "```{attention}\n", "The difference between moving and copying\n", "for us is that when a register's contents are moved, the\n", "register is left empty; but if the contents are copied,\n", "then the register is left at the end with exactly what it had\n", "at the beginning.\n", "```\n", "\n", "In order to copy in this way, we need an auxilliary register.\n", "So while the ```move``` programs had two registers in their names, the ```copy``` programs have three.\n", "\n", "

\n", "Here is the idea behind copying Rm to Rn. We use\n", "an auxilliary register, say Rp. We move Rm into Rn and Rp\n", "at the same time, and then be move Rp back to Rm.\n", "Of course, when we do this, we should have Rp empty to start\n", "with. \n", "

\n", "Here is our program when m = 1, n = 2, p = 3:" ], "metadata": { "id": "Yo0sbjZhEPD7" } }, { "cell_type": "code", "source": [ "copy_1_2_3" ], "metadata": { "id": "2_qToGIXEpts" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "## write" ], "metadata": { "id": "5hyC35yaEKLl" } }, { "cell_type": "markdown", "source": [ "We construct with \n", "a program $\\writeprog$ with \n", "the following properties:\n", "\n", "1. When $\\writeprog$ is started with $x$ in R1 \n", "and R2 empty, we eventually halt with a\n", "word $y$\n", "in $\\Rone$ and all other registers empty.\n", "\n", "2. Then $y$ is a program, and running\n", "$y$ with $\\Rone$ empty results in $x$ back in $\\Rone$ and all\n", "other registers empty." ], "metadata": { "id": "UDDObujTBXCl" } }, { "cell_type": "code", "source": [ "write" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "id": "t6q0JLmoBjf3", "outputId": "cdcc65f6-2ef1-4794-c1a1-65e648c73b8f" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "'1#####111111111###11111###11#11##11##111111####11#11##111111111####11#####111111###111###1##1111####1#111111####'" ], "application/vnd.google.colaboratory.intrinsic+json": { "type": "string" } }, "metadata": {}, "execution_count": 10 } ] }, { "cell_type": "markdown", "source": [ "Here is the explicated parse:" ], "metadata": { "id": "KRZFyRqsBmnY" } }, { "cell_type": "code", "source": [ "parse_explain(write)" ], "metadata": { "id": "sz9wLnNOBo7h" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Even more informatively, here is a table:\n", "\n", "

\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
1##### Cases on R1
111111111### Go forward 9:\n", " to move2,1 part
11111###Go forward 5:\n", "to the brown part
11# Add 1 to R2: 1## adds # to R1
11## Add # to R2
11## Add # to R2
111111#### Go backward 6 (to\n", "the top)
11# Add 1 to R2: 1# adds 1 to R1
11## Add # to R2
111111111#### Go backward 9\n", "(to the top)
move2,1 from earlier in this notebook
\n", "
" ], "metadata": { "id": "VAUQmglUB1D5" } }, { "cell_type": "markdown", "source": [ "It should be emphasized that $\\writeprog$ reads from R1 \n", "and writes to R2; it makes no\n", "use of any other register." ], "metadata": { "id": "fHwPPO5uCHEe" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Why is the result of running $\\writeprog$ on a word $x$ always a program,\n", "even if $x$ is a word which is not a program?\n", "```" ], "metadata": { "id": "HMCCxIdhCRjS" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Modify $\\writeprog$\n", " to get a program $\\writetotwo$\n", "with the following feature:\n", " If $\\writetotwo$ is started with $x$ in R1 \n", "and R2 empty, we eventually halt with a\n", "word\n", "$y$\n", "in R2 and all other registers empty; moreover, running\n", "$y$ with R2 empty results in $x$ back in R2 (not R1) and all\n", "other registers empty.\n", "```" ], "metadata": { "id": "5tzhskcfDPff" } }, { "cell_type": "markdown", "source": [ "# The $+$ notation on words\n", "\n", "```{prf:definition}\n", "If $x$ and $y$ are words, then $x + y$ is the *concatenation* of $x$ followed by $y$. For example,\n", "\n", "$$\n", "\\one\\hash\\one + \\hash \\hash = \\one\\hash\\one \\hash \\hash.\n", "$$\n", "\n", "This operation is associative: $x + (y+z) = (x+y) + z$. \n", "\n", "The *empty word* $\\eps$ is an identity element for it:\n", "$x + \\eps = x = \\eps + x$.\n", "So we have a [*monoid*](https://en.wikipedia.org/wiki/Monoid)\n", "\n", "$$\n", "(\\words, +, \\eps)\n", "$$\n", "```\n", "\n", "This means that we can \"add\" programs (since they are words). For example, let \n", "\n", "$$\n", "q = \\copyprog_{1,2,3} + \\moveprog_{2,1}\n", "$$\n", "\n", "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." ], "metadata": { "id": "h1qurP6ejmTN" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Let's take a word $x$ and run $\\writeprog$ on it. Call the resulting program $p$. If we run $p$ on a word $y$, which do we get: $x + y$ or $y + x$?\n", "```" ], "metadata": { "id": "dJfue0k_DPtm" } } ] }