#!/usr/bin/env python # coding: utf-8 # ## NAND++ overview # # 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. # # This notebook should be useful for you even if you view it statically, but might be even better if you play with on jupyter notebook. # ### What is NAND++? # # The right way to think about NAND++ is that it has the following two features compared to NAND: # # * 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). # # * 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. # # * 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): # In[1]: import math # Returns the value of the index variable i in iteration number k def index(k): r = math.floor(math.sqrt(k+1/4)-1/2) return (k-r*(r+1) if k <= (r+1)*(r+1) else (r+1)*(r+2)-k) # In[2]: [index(k) for k in range(20)] # 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: # # 1. In iteration $k$ we replace all references to $i$ with references to $index(k)$ # # 2. When we get to the end, if `loop` is equal to 0 then we go back to the beginning. # # One 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.) # 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: # # 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. # # The 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)$). # In[3]: # Gets as input a NAND program and a table of values of variables. # Runs an iteration of the program, updating the values of the variables as it proceeds def NANDinterpeter(prog,variables): for line in prog.split('\n'): (var1,_,var2,__,var3) = line.split() variables[var1] = 1-variables.get(var2,0)*variables.get(var3,0) # p.s. This code is a bit brittle: sensitive to spaces, comments, and other issues. # In[4]: # 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 # Works by repeatedly calling NAND def NANDPPinterpreter(prog,x): n = len(x) variables = {} for i in range(n): variables['x_'+str(i)]=x[i] variables['validx_'+str(i)]=1 k=0 while True: NANDprog = prog.replace( '_i','_'+str(index(k))) NANDinterpeter(NANDprog,variables) if variables.get('loop',0)==0: break k += 1 return variables.get('y_0',0) # assume one bit output # Let's try this out on the parity program from the lecture notes: # In[5]: parity = r'''tmpa := seen_i NAND seen_i tmpb := x_i NAND tmpa val := tmpb NAND tmpb ns := s NAND s y_0 := ns NAND ns u := val NAND s v := s NAND u w := val NAND u s := v NAND w seen_i := zero NAND zero stop := validx_i NAND validx_i loop := stop NAND stop''' # In[7]: NANDPPinterpreter(parity,[0,1,1,0,0,1,1]) # In[8]: NANDPPinterpreter(parity,[0,1,1,0,0,1,0,0,1]) # 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++. # ## Translating NAND<< to NAND++ # # 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.) # # 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. # # 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. # # Usng 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$. # ### Simulating `indexincreasing` # # 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. # # 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. # # This is just a finite function and so we can construct a NAND code for it (which you will see in the Python code below) # In[9]: def idxincreasing(prog): prog = "atstart_0 := zero NAND zero\n"+prog # ensure atstart is array (1,0,0,0,....) prog += r''' tempidx := breadcrumbs_i NAND indexincreasing notstart := atstart_i NAND atstart_i indexincreasing := notstart NAND tempidx breadcrumbs_i := zero NAND zero''' return prog # If we run it for the parity program, we get the following variant: # In[10]: parityidx = idxincreasing(parity) print(parityidx) # To see if it works, let's rerun this with a version of our interpeter that prints the `indexincreasing` variable: # In[11]: # 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 # Works by repeatedly calling NAND def NANDPPinterpreter(prog,x,track = []): n = len(x) variables = {} for i in range(n): variables['x_'+str(i)]=x[i] variables['validx_'+str(i)]=1 k=0 while True: NANDprog = prog.replace( '_i','_'+str(index(k))) NANDinterpeter(NANDprog,variables) if variables.get('loop',0)==0: break for v in track: print(v + " = "+ str(variables.get(v,0))) k += 1 return variables.get('y_0',0) # assume one bit output # In[12]: NANDPPinterpreter(parityidx,[0,1,1,0],["indexincreasing"]) # 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 # ## Configurations # # 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: # # * 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. # # * As we run more steps, we access more memory locations, and so the size of the configuration grows. # # * 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. # # * For every NAND++ program $P$, the $NEXT_P$ function computes the next configuration of the program $P$. # 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. # In[13]: import math # compute the next-step configuration # Inputs: # P: NAND++ program in list of 6-tuples representation (assuming it has an "indexincreasing" variable) # conf: encoding of configuration as a string using the alphabet "B","E","0","1". def next_step(P,conf): s = len(P) # numer of lines t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of "E","B") LOOP = 3 INDEXINCREASING = 5 ACTIVEIDX = block_enc_length -line_enc_length-1 # position of active flag FINALIDX = block_enc_length -line_enc_length-2 # position of final flag def getval(var,idx): if idx