{ "cells": [ { "cell_type": "markdown", "source": [ "## NAND++ overview\n", "\n", "This notebook gives an overview of the NAND++ language. We use Python code to illustrate some concepts, but you don't need to know Python at all to follow. In fact, in the first read I recommend you skip all the code cells.\n", "\nThis notebook should be useful for you even if you view it statically, but might be even better if you play with on jupyter notebook." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### What is NAND++?\n", "\n", "The right way to think about NAND++ is that it has the following two features compared to NAND:\n", "\n", "* All variables except the special index variable `i` are _arrays_. Each variable in a line of code of NAND++ is either indexed by a fixed numerical index (as in `foo_17`) or by the special index `i`, (as in `bar_i`). If an index is missing (as in `blah`) we treat at as 0 (and so `blah` and `blah_0` refer to the same variable).\n", "\n", "* NAND is a _straightline programming language_ that has no loops, and so if the program has $s$ lines then on every input it runs for exactly $s$ steps. NAND++ has the special `loop` variable (which is the same as `loop_0`, by our convention above), such that when an iteration ends, if `loop` equals $1$, then the program starts from the beginning. An _iteration_ of an $s$ lines NAND++ program takes $s$ steps, and the number of iterations such a programs takes depends on the input that it gets. \n", "\n* The special index variable `i` either increases or decreases by one at the end of every iteration. It follows the following schedule $0,1,0,1,2,1,0,1,2,3,2,1,0,1,2,3,2,2,1,0,\\ldots$. There is also a formula for this schedule. The only thing you have to remember about it is that it exists, and is not that complicated. In fact, we can write it in a couple of lines of math or Python (as shown in the next cell):" ], "metadata": {} }, { "cell_type": "code", "source": [ "import math\n", "\n", "# Returns the value of the index variable i in iteration number k\n", "def index(k):\n", " r = math.floor(math.sqrt(k+1/4)-1/2)\n", " return (k-r*(r+1) if k <= (r+1)*(r+1) else (r+1)*(r+2)-k)" ], "outputs": [], "execution_count": 1, "metadata": { "collapsed": true } }, { "cell_type": "code", "source": [ "[index(k) for k in range(20)]" ], "outputs": [ { "output_type": "execute_result", "execution_count": 2, "data": { "text/plain": [ "[0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1]" ] }, "metadata": {} } ], "execution_count": 2, "metadata": {} }, { "cell_type": "markdown", "source": [ "The code of a NAND++ program looks almost exactly like the code of a NAND program except for the presence of the index variable `i`. The main difference is that when we run a NAND++ program we do two things:\n", "\n", "1. In iteration $k$ we replace all references to $i$ with references to $index(k)$\n", "\n", "2. When we get to the end, if `loop` is equal to 0 then we go back to the beginning.\n", "\nOne more minor difference is that because the input in a NAND++ program does not have a fixed length, in addition to the variables `x_0`, `x_1`, ... that give us the bits of the input, we also have variables `validx_0`,`validx_1`, ... such that `validx_`$j$ evaluates to $1$ if and only if $j$ is smaller than the length of the input. (Otherwise, the program would not be able to determine the length of the input.)" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "The above means that if we have an interpeter for NAND, we can write an interpreter for NAND++ by simply invoking it many times, using the search and replace as above. Here is some Python code that does that:\n", "\n", "The function `NANDinterpeter` gets a NAND program and a table of the values of its variables, and runs the NAND program to update this table.\n", "\nThe function `NANDPPinterpeter` gets a NAND++ program P and an input x as input. It initializes a table corresponding to the input, and then continusly feeds the program P to the NAND interpeter (replacing in iteration $k$ the value of `i` with $index(k)$)." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Gets as input a NAND program and a table of values of variables. \n", "# Runs an iteration of the program, updating the values of the variables as it proceeds\n", "def NANDinterpeter(prog,variables):\n", " for line in prog.split('\\n'):\n", " (var1,_,var2,__,var3) = line.split()\n", " variables[var1] = 1-variables.get(var2,0)*variables.get(var3,0)\n", " \n", "# p.s. This code is a bit brittle: sensitive to spaces, comments, and other issues." ], "outputs": [], "execution_count": 3, "metadata": { "collapsed": true } }, { "cell_type": "code", "source": [ "# Gets as input a NAND++ program and an input (as an array of 0/1 values) and returns the evaluation of the program on this input\n", "# Works by repeatedly calling NAND\n", "def NANDPPinterpreter(prog,x):\n", " n = len(x)\n", " variables = {}\n", " for i in range(n):\n", " variables['x_'+str(i)]=x[i]\n", " variables['validx_'+str(i)]=1\n", " k=0\n", " while True:\n", " NANDprog = prog.replace( '_i','_'+str(index(k)))\n", " NANDinterpeter(NANDprog,variables)\n", " if variables.get('loop',0)==0: break\n", " k += 1\n", " \n", " return variables.get('y_0',0) # assume one bit output" ], "outputs": [], "execution_count": 4, "metadata": { "collapsed": true } }, { "cell_type": "markdown", "source": [ "Let's try this out on the parity program from the lecture notes:" ], "metadata": {} }, { "cell_type": "code", "source": [ "parity = r'''tmpa := seen_i NAND seen_i\n", "tmpb := x_i NAND tmpa\n", "val := tmpb NAND tmpb\n", "ns := s NAND s\n", "y_0 := ns NAND ns\n", "u := val NAND s\n", "v := s NAND u\n", "w := val NAND u\n", "s := v NAND w\n", "seen_i := zero NAND zero \n", "stop := validx_i NAND validx_i\n", "loop := stop NAND stop'''" ], "outputs": [], "execution_count": 5, "metadata": { "collapsed": true } }, { "cell_type": "code", "source": [ "NANDPPinterpreter(parity,[0,1,1,0,0,1,1])" ], "outputs": [ { "output_type": "execute_result", "execution_count": 7, "data": { "text/plain": [ "0" ] }, "metadata": {} } ], "execution_count": 7, "metadata": {} }, { "cell_type": "code", "source": [ "NANDPPinterpreter(parity,[0,1,1,0,0,1,0,0,1])" ], "outputs": [ { "output_type": "execute_result", "execution_count": 8, "data": { "text/plain": [ "0" ] }, "metadata": {} } ], "execution_count": 8, "metadata": {} }, { "cell_type": "markdown", "source": [ "That's all there is to NAND++. It is an extremely simple programming language. The surprising thing is that it is equivalent to NAND<< and other more powerful languages. That is, ultimately we can implement NAND<< (or even Python) as \"syntactic sugar\" on top of NAND++. " ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Translating NAND<< to NAND++\n", "\n", "NAND<< (and other such more powerful languages) are inherently more complex to describe. A fairly complete description of NAND<< is in Appendix A, but to write things in full formality and detail would require much more space. The specification of C,C++ or Python can run to hunderds of pages. The fact that the specification is long means that a full formal proof of the equivalence of NAND++ and NAND<< would be very long and detailed, and not that insightful. (This is not something specific for NAND++ and NAND<<, the full formal proof that Turing machines are equivalent to RAM machines, for example would be just as long.)\n", "\n", "I do not expect you to know all this proof by heart, but to understand the _key steps_ in it, which are illustrated in the lecture notes. In particular, the most significant step is the transformation, using the \"breadcrumbs\" technique, of a NAND++ that uses the `i++` and `i--` syntactic sugar, to the a program that does not use it. \n", "\n", "The main component of that technique is the ability of a NAND++ program to know when an index is increasing or decreasing: that is create an `indexincreasing` variable that is equal to $1$ when the index will be _incremented_ in the next stepand equal to $0$ when the index will be _decremented_ in the next step.\n", "\nUsng this, to simulate the `i--` operation we look at `indexincreasing`: if it is equal to $0$ then we do nothing, if it is equal to $1$ then we mark the current location of `i` using a special array `marker_i`, and do nothing until we reach the same location with the value of `indexincreasing` equal to $1$." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### Simulating `indexincreasing` \n", "\n", "I will not include here the Python code to implement all of the above sugar, but here is a Python function that modifies a NAND++ program $P$ to a NAND++ program $P'$ that has the `indexincreasing` variable.\n", "\n", "At one step we will want to assign to `indexincreasing` the value `F(atstart_i,breadcrumbs_i,indexincreasing)` where $F:\\{0,1\\}^3 \\rightarrow \\{0,1\\}$ is defined as $F(1,\\cdot,\\cdot)=1$, $F(0,0,\\cdot)=0$ and $F(0,1,a)=a$. That is, if we are at the beginning then `indexincreasing` should be equal to $1$, if we reach a point we haven't seen before, then `indexincreasing` should be equal to $0$, and otherwise it should stay the same.\n", "\nThis is just a finite function and so we can construct a NAND code for it (which you will see in the Python code below)" ], "metadata": {} }, { "cell_type": "code", "source": [ "def idxincreasing(prog):\n", " prog = \"atstart_0 := zero NAND zero\\n\"+prog # ensure atstart is array (1,0,0,0,....)\n", " prog += r'''\n", "tempidx := breadcrumbs_i NAND indexincreasing\n", "notstart := atstart_i NAND atstart_i\n", "indexincreasing := notstart NAND tempidx\n", "breadcrumbs_i := zero NAND zero'''\n", " return prog " ], "outputs": [], "execution_count": 9, "metadata": { "collapsed": true } }, { "cell_type": "markdown", "source": [ "If we run it for the parity program, we get the following variant:" ], "metadata": {} }, { "cell_type": "code", "source": [ "parityidx = idxincreasing(parity)\n", "print(parityidx)\n", " " ], "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "atstart_0 := zero NAND zero\n", "tmpa := seen_i NAND seen_i\n", "tmpb := x_i NAND tmpa\n", "val := tmpb NAND tmpb\n", "ns := s NAND s\n", "y_0 := ns NAND ns\n", "u := val NAND s\n", "v := s NAND u\n", "w := val NAND u\n", "s := v NAND w\n", "seen_i := zero NAND zero \n", "stop := validx_i NAND validx_i\n", "loop := stop NAND stop\n", "tempidx := breadcrumbs_i NAND indexincreasing\n", "notstart := atstart_i NAND atstart_i\n", "indexincreasing := notstart NAND tempidx\n", "breadcrumbs_i := zero NAND zero\n" ] } ], "execution_count": 10, "metadata": {} }, { "cell_type": "markdown", "source": [ "To see if it works, let's rerun this with a version of our interpeter that prints the `indexincreasing` variable: " ], "metadata": {} }, { "cell_type": "code", "source": [ "# Gets as input a NAND++ program and an input (as an array of 0/1 values) and returns the evaluation of the program on this input\n", "# Works by repeatedly calling NAND\n", "def NANDPPinterpreter(prog,x,track = []):\n", " n = len(x)\n", " variables = {}\n", " for i in range(n):\n", " variables['x_'+str(i)]=x[i]\n", " variables['validx_'+str(i)]=1\n", " k=0\n", " while True:\n", " NANDprog = prog.replace( '_i','_'+str(index(k)))\n", " NANDinterpeter(NANDprog,variables)\n", " if variables.get('loop',0)==0: break\n", " for v in track: print(v + \" = \"+ str(variables.get(v,0)))\n", " k += 1\n", " \n", " return variables.get('y_0',0) # assume one bit output" ], "outputs": [], "execution_count": 11, "metadata": { "collapsed": true } }, { "cell_type": "code", "source": [ "NANDPPinterpreter(parityidx,[0,1,1,0],[\"indexincreasing\"])" ], "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "indexincreasing = 1\n", "indexincreasing = 0\n", "indexincreasing = 1\n", "indexincreasing = 1\n", "indexincreasing = 0\n", "indexincreasing = 0\n", "indexincreasing = 1\n", "indexincreasing = 1\n", "indexincreasing = 1\n", "indexincreasing = 0\n", "indexincreasing = 0\n", "indexincreasing = 0\n", "indexincreasing = 1\n", "indexincreasing = 1\n", "indexincreasing = 1\n", "indexincreasing = 1\n" ] }, { "output_type": "execute_result", "execution_count": 12, "data": { "text/plain": [ "0" ] }, "metadata": {} } ], "execution_count": 12, "metadata": {} }, { "cell_type": "markdown", "source": [ "You can see that we have a sequence of increasing once, then decreasing once, then increasing twice, then decreasing twice, and so on and so forth" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Configurations\n", "\n", "The notion of _configurations_ is just to encode the entire contents of the state of a NAND++ program. The exact details of a configurations are not as important as are the following high level points:\n", "\n", "* The state of a NAND++ program has components that are fixed independently of the input and the number of steps: the current line, the number of lines, and the values of all array locations that are indexed by an absolute numerical index such as `foo_17`. It also has components that can grow as the number of steps grow: the value of the index variable `i`, and the contents of the arrays in all the locations that `i` has been to so far. \n", "\n", "* As we run more steps, we access more memory locations, and so the size of the configuration grows.\n", "\n", "* We use blocks to encode the configuration for convience. The size of each block is a constant (that depends on the number of lines in the program), but the number of blocks can grow. Block number $j$ contains the contents of all variables that are of the form `foo_`$j$. If $j$ is equal to the current value of the index variable `i` then this block is the _active_ block, and the configuration contains a bit that marks this condition.\n", "\n* For every NAND++ program $P$, the $NEXT_P$ function computes the next configuration of the program $P$." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "For every NAND++ program $P$, the $NEXT_P$ function maps one configuration to the next one. It can be implemented by fairly simple \"search and replace\". This is done in the Python code below, though again I would skip it in a first read. " ], "metadata": {} }, { "cell_type": "code", "source": [ "import math\n", "\n", "# compute the next-step configuration\n", "# Inputs:\n", "# P: NAND++ program in list of 6-tuples representation (assuming it has an \"indexincreasing\" variable)\n", "# conf: encoding of configuration as a string using the alphabet \"B\",\"E\",\"0\",\"1\".\n", "def next_step(P,conf):\n", " s = len(P) # numer of lines\n", " t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables\n", " line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line\n", " block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of \"E\",\"B\")\n", " LOOP = 3\n", " INDEXINCREASING = 5\n", " ACTIVEIDX = block_enc_length -line_enc_length-1 # position of active flag\n", " FINALIDX = block_enc_length -line_enc_length-2 # position of final flag\n", " \n", " def getval(var,idx):\n", " if idx