{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# CS 121 Extra Programming assignment\n", "\n", "This assignment is worth __40 bonus points__. You can work on this assignment in teams of __up to four students__. You have until __Thursday December 6th 11:59pm__ to submit it. There are no late days for this submission.\n", "\n", "You shold not work on this assignment for its point value. Rather work on it if you:\n", "\n", "1. Enjoy coding\n", "\n", "2. Feel like you have a solid grasp of all other material in this course. (Otherwise you're better off spending your time on the theoretical components)\n", "\n", "\n", "You will submit this assignment through gradescope. \n", "\n", "See [this piazza post](https://piazza.com/class/jip1o0z9lav4rs?cid=1287) for more information.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Background: The BrainFuck Programming Language\n", "\n", "The _BrainFuck Programming Language_ (see [Wikipedia](https://en.wikipedia.org/wiki/Brainfuck), henceforth BF for brevity and decency's sake) is a Turing complete programming language that has only eight simple commands.\n", "The name of this language comes from the fact that BF programs tend to look like this:\n", "\n", "```\n", ">>,[>>,]\n", "<<\n", "[\n", "[<<]>>>>[<<[>+<<+>-]>>\n", "[>+<<<<[->]>[<]>>-]<<<\n", "[[-]>>[>+<-]>>[<<<+>>>-]]\n", ">>[[<+>-]>>]<]<<[>>+<<-]<<\n", "]\n", ">>>>[.>>]\n", "```\n", "\n", "(as you probably guessed immediately, this is a program performs that performs the _bubble sort_; credit: [Daniel Cristofani](http://www.hevanet.com/cristofd/brainfuck/bsort.b))\n", "\n", "BF is Turing complete. In particular, the following is a BF interpreter in BF (taken from this [paper by Mazonka and Cristofani](https://arxiv.org/abs/cs/0311032v1) ):\n", "\n", "```\n", ">>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[\n", "->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<\n", "]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>\n", "+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-\n", "[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[\n", ">->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]\n", "```\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The question\n", "\n", "Your goal in this assignment is to implement the proof of the Cook Levin Theorem for BF.\n", "\n", "Specifically, you will need to write a Python function `BF2NAND` such that if `P` is a string describing a BF program and `n` and `t` are integers then `BF2NAND(P,n,t)` will output the code of an $8n$-bit input and one-bit output NAND program $Q$ that satisfies the following. If\n", "\n", "* `P` is a string which is the source code of a BF program which takes `n` bytes as input. We assume that first instructions of the program are to read these bytes into the memory array (this corresponds to having `n` copies of the pair of instructions `,>` in the beginning of the program, and having no other `,` instructions in the program).\n", "\n", "* `t` is an upper bound on the number of steps that the program `P` takes on every input of `n` bytes. Moreover, we assume that the program `P` outputs a single byte, which at the end of the program (which always happen within at most `t` steps) is at the first position of the memory array. \n", "\n", "Then the output of `BF2NAND(P,n,t)` will be a _NAND program_ $Q$ that takes $8n$ input bits and output a single bit, and has the property that for every $x\\in \\{0,1\\}^{8n}$, $Q(x)=1$ if and only if the BF program `P`, when given as input the $n$ bytes $x$, outputs a nonzero byte. \n", "\n", "(We don't care what the output of `BF2NAND` is if it is given a string that does not code a valid BF program, or that encodes a program that does not satisfy the above assumptions.)\n", "\n", "You will get 85% of the credit if you restrict yourself to only working for _balanced BF programs_. A BF program is _balanced_ if every loop in it (i.e., everything inside `[...]`) has an equal number of `<` and `>` operations, and so in the end of the loop the data pointer is in the same position that it started." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Some extras\n", "\n", "As in the last assignment, we might award bonus points to the team that manages to output the shortest NAND programs for a given BF input, though we urge you to first get a working sample before optimizing. Once again you should remember Knuth's quote _\"Premature optimization is the root of all evil.\"_ \n", "\n", "While you are guaranteed that no loop in the BF program will iterate more than `t` steps, you might use smarter analysis or benchmarking to get better bounds, and hence output smaller NAND code. For example, you can hardcode certain BF idioms such as `[-]`.\n", "\n", "Since [Boaz's repository](https://github.com/boazbk/nandnotebooks/) already contains code that transforms NANDSAT to 3NAND and through there to 3SAT and INDEPENDENT SET, you can combine it with your code to transform a BF program `P` into a graph `G` and a number `k` such that `G` has an independent set of size `k` if and only if there is an input that causes `P` to output `1` within at most `t` steps. Feel free to post images of such graphs (with the BF code that they came from) on Piazza for other students to see and also enclode them in your submission. We might again give some bonus points to particularly impressive images.\n" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "gxUGb5l4tYRD" }, "source": [ "## Detailed roblem Statement\n", "\n", "The input will be a BF program $Q$ and parameters $n$ and $t$, and the output will be a NAND program $P$ with $8n$ inputs and one output such that for every string $x$ of $8n$ bits (i.e., $n$ bytes), if $Q$ on input $x$ outputs $1$ within $t$ steps then $P(x)=1$ and otherwise $P(x)=0$. Since a BF program actually takes in a char (0-255) for every input, let us treat this as taking the bits into our NAND program with least significant bit first.\n", "\n", "\n", "### BF specification\n", "\n", "We will be using the original BF standard. A specification can be found [here](https://github.com/brain-lang/brainfuck/blob/master/brainfuck.md). BF can be thought of as a tape, where each cell can hold an unsigned 8 bit integer. There are 8 basic instructions.\n", "\n", "| Instruction | Description |\n", "|-----|-----|\n", "| `>` | move the pointer right |\n", "| `<` | move the pointer left |\n", "| `+` | increment the current cell |\n", "| `-` | decrement the current cell |\n", "| `.` | output the value of the current cell |\n", "| `,` | **replace** the value of the current cell with input |\n", "| `[` | jump to the **matching** `]` instruction if the current value is zero |\n", "| `]` | jump to the **matching** `[` instruction if the current value is **not** zero |\n", "\n", "We will treat the `.` as the output of our BF program and the items read in with `,` as the input of our BF program. All of the BF programs we will be testing will read in using `,` sequentially and outputting the first cell on the tape with `.`.\n", "\n", "\n", "### Example\n", "\n", "The main objective is to convert a BF program with $n$ inputs and $1$ output limited to $t$ operations into a NAND program that takes in $8n$ inputs and $1$ output, where the output of the NAND program is the least significant bit of the first BF output.\n", "\n", "__Input__: \n", "\n", "* A BF program that just increments the 8 bit input by 1, and then returns the same. Sample code that does this is as follows (the BF interpreter ignores all of the symbols that aren't in the language) The program can be written as ```,+.```.\n", "\n", "* Other parameters are $n = 1$, $t = 100$.\n", "\n", "__Output__:\n", "\n", "A possible output would just be the following NAND program:\n", "```\n", " y[0] = XOR(x[0], 1)\n", " ```\n", " where we used `1` and `XOR` as syntactic sugar that corresponds to the actual NAND implementation of those operations." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "U88itQDVt60g" }, "source": [ "## BF EVAL in Python\n", "\n", "Before we convert BF to NAND we still want a built-in evaluator that we know is correct. Some sample programs and outputs are provided.\n" ] }, { "cell_type": "code", "execution_count": 163, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 191 }, "colab_type": "code", "id": "J99cFmH2uIkA", "outputId": "5abbc6a5-8e5b-46db-a4e3-daab3b290962" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Requirement already satisfied: bfi in /anaconda3/lib/python3.6/site-packages (1.0.2)\n", "\u001b[33mYou are using pip version 18.0, however version 18.1 is available.\n", "You should consider upgrading via the 'pip install --upgrade pip' command.\u001b[0m\n", "Cloning into 'nandprogramming'...\n", "warning: redirecting to https://github.com/wfus/nandprogramming.git/\n", "remote: Enumerating objects: 29, done.\u001b[K\n", "remote: Counting objects: 100% (29/29), done.\u001b[K\n", "remote: Compressing objects: 100% (21/21), done.\u001b[K\n", "remote: Total 29 (delta 14), reused 17 (delta 8), pack-reused 0\u001b[K\n", "Unpacking objects: 100% (29/29), done.\n" ] } ], "source": [ "!pip install bfi\n", "!rm -rf nandprogramming\n", "!git clone http://www.github.com/wfus/nandprogramming\n", "!mv nandprogramming/nandutil.py .\n", "%load nandutil.py" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": {}, "colab_type": "code", "id": "aJrW1DYZurIG" }, "outputs": [], "source": [ "import bfi\n", "from nandutil import NANDProgram\n", "from nandutil import EVAL\n", "from nandutil import TRUTH\n", "\n", "def int2str(*args):\n", " return \"\".join([str(chr(arg)) for arg in args])\n", "\n", "def str2int(output):\n", " \"\"\"Converts the string BF output to a list of integers\"\"\"\n", " int_st = [int(ord(char)) for char in output]\n", " return int_st\n", "\n", "def run(bf_prog, *args):\n", " \"\"\"Takes in a BF program and a list of integers and runs it. Returns the output\n", " as a list of integers.\"\"\"\n", " bf_input = int2str(*args)\n", " ret = bfi.interpret(bf_prog, input_data=bf_input,\n", " tape_size=1000, buffer_output=True)\n", " return str2int(ret)\n", "\n", "def sanitize(bf_prog_string):\n", " \"\"\"Sanitize a brainfuck program string by removing all unnecessary symbols\"\"\"\n", " vocabulary = [',', '.', '>', '<', '+', '-', '[', ']']\n", " return \"\".join([a for a in bf_prog_string if a in vocabulary])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": {}, "colab_type": "code", "id": "Y88VkIC3utWN" }, "outputs": [], "source": [ "add2 = \"\"\"\n", ",>,< read in two inputs\n", ">>[-] zero out 3rd cell\n", "< move to 2nd cell\n", "[<+>>+<-] ???\n", "< go back to 1st cell\n", ">>[<+>-] move 3rd cell to 2nd cell\n", "<< move back to first cell\n", ". print result\n", "\"\"\"\n", "\n", "notequal = \"\"\"\n", "x = first cell\n", "y = second cell\n", "tmp0 = third cell\n", "tmp1 = fourth cell\n", "checks if x is equal to y\n", "\n", ",>,<\n", ">>[-] zero out third cell\n", ">[-] zero out fourth cell\n", "<<<[>>>+<<<-] ???\n", ">[>>-<+<-] ???\n", ">[<+>-] ???\n", ">[<<<+>>>[-]] ???\n", "<<<. print out output\n", "\"\"\"\n", "\n", "\n", "read_2_print_2 = \"\"\"\n", ",>,< read and go back to 0th cell\n", ".>. print out those two cells\n", "\"\"\"\n", "\n", "read_1_increment = \"\"\"\n", ",\n", "+\n", ".\n", "\"\"\"\n", "\n", "read_1_increment_2 = \"\"\"\n", ",\n", "++\n", ".\n", "\"\"\"" ] }, { "cell_type": "code", "execution_count": 166, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 34 }, "colab_type": "code", "id": "TJIWrSsljvco", "outputId": "4ebbd330-9d72-48a7-9116-de8b402a29de" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[5]\n" ] } ], "source": [ "print(run(add2, 2, 3))" ] }, { "cell_type": "code", "execution_count": 167, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 69 }, "colab_type": "code", "id": "lwDsu6swdnXp", "outputId": "be4619e4-6461-454d-9ec6-085406335bf6" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0]\n", "[0]\n", "[1]\n" ] } ], "source": [ "print(run(notequal, 1, 1))\n", "print(run(notequal, 123, 123))\n", "print(run(notequal, 4, 10))" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "GIHIRrB-xu6h" }, "source": [ "## BF to NAND\n", "\n", "Now we need to actually convert BF program into a NAND program. We are guaranteed that we know the brainfuck program will get $n$ $8$ bit inputs, and return $1$ eight bit output. We want to construct a NAND program that takes in these $n$ $8$ bit inputs with least significant digit first, and returns a $1$ bit output corresponding to the least significant digit of the output." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "colab": {}, "colab_type": "code", "id": "DJiumCayvRwr" }, "outputs": [], "source": [ "def BF2NAND(bf_prog, n, t):\n", " # TODO: Implement BF to nand where t is the number of steps\n", " # and t is the number of steps we must simulate the brainfuck\n", " # program with.\n", " raise NotImplementedError" ] } ], "metadata": { "colab": { "name": "Brainfuck.ipynb", "provenance": [], "version": "0.3.2" }, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.5" } }, "nbformat": 4, "nbformat_minor": 2 }