To run this notebook, you will need to have installed Jupyter Notebook (which is part of the Anaconda distribution). For the graph visualization you will need:
In a NAND program, every line has the form:
foo := bar NAND baz
The NAND
operation takes two bits $a,b \in \{0,1\}$ and outputs $1-a\cdot b = NOT(a\;AND\; b)$ (or $\overline{a \wedge v}$ in logic notation)
def EVAL(prog,x):
n = max([int(var[2:]) for var in prog.split() if var[:2]=='x_' ])+1 # no of inputs
m = max([int(var[2:]) for var in prog.split() if var[:2]=='y_' ])+1 # no of outputs
varsval = { } # dictionary of value of "workspace" variables
for i in range(n):
varsval['x_'+str(i)] = int(x[i])
for j in range(m):
varsval['y_'+str(j)] = 0
for line in prog.split('\n'):
if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines
(var1,assign,var2,op,var3) = line.split()
varsval[var1] = 1-varsval.get(var2,0)*varsval.get(var3,0)
return ''.join( str(varsval['y_'+str(j)]) for j in range(m))
import operator
def bold(s,justify=0):
return "\x1b[1m"+s.ljust(justify)+"\x1b[0m"
def red(s,justify=0):
return "\x1b[31m"+s.ljust(justify)+"\x1b[0m"
def green(s,justify=0):
return "\x1b[32m"+s.ljust(justify)+"\x1b[0m"
def blue(s,justify=0):
return "\x1b[34m"+s.ljust(justify)+"\x1b[0m"
def snapshots(prog,x,step=-1,cumulative=True):
varnames = set()
for line in prog.split('\n'):
if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines
(var1,assign,var2,op,var3) = line.split()
varnames.add(var1)
varnames.add(var2)
varnames.add(var3)
n = max([int(var[2:]) for var in varnames if var[:2]=='x_' ])+1 # no of inputs
m = max([int(var[2:]) for var in varnames if var[:2]=='y_' ])+1 # no of outputs
t = len(varnames)
def formatvarname(var,justify=0):
if varsidx[var]<n:
return blue(var,justify)
if varsidx[var]>t-m-1:
return red(var,justify)
return green(var,justify)
def formatvarval(var,justify=0):
s = str(varsval[var])
if varsidx[var]<n:
return blue(s,justify)
if varsidx[var]>t-m-1:
return red(s,justify)
return green(s,justify)
varsidx = {}
varsval = { } # dictionary of value of "workspace" variables
for i in range(n):
varsval['x_'+str(i)] = int(x[i])
varsidx['x_'+str(i)] = i
for j in range(m):
varsval['y_'+str(j)] = 0
varsidx['y_'+str(j)] = len(varnames)-m+j
i = n
for var in varnames:
if var[:2]!='x_' and var[:2]!='y_':
varsval[var]=0
varsidx[var] = i
i += 1
sortednames = [s[0] for s in sorted(varsidx.items(), key=operator.itemgetter(1))]
MAXLINELENGTH = 23
MAXVARLENGTH = 5
printout = "".ljust(MAXLINELENGTH)
for var in sortednames:
printout += formatvarname(var,MAXVARLENGTH)
print(printout)
printout = "".ljust(MAXLINELENGTH-2)
for var in sortednames:
printout += red(str(varsval[var]).ljust(MAXVARLENGTH))
if (step==-1):
step = len(prog.split('\n'))
j = 0
for line in prog.split('\n'):
if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines
if j>step:
break
(var1,assign,var2,op,var3) = line.split()
varsval[var1] = 1-varsval.get(var2,0)*varsval.get(var3,0)
printout = line.ljust(MAXLINELENGTH-2)+": "
for var in sortednames:
printout += formatvarval(var,MAXVARLENGTH)
print(printout)
return ''.join( str(varsval['y_'+str(j)]) for j in range(m))
def represent(prog, verbose = True):
MAXLINELENGTH = 23
varnames = set()
for line in prog.split('\n'):
if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines
(var1,assign,var2,op,var3) = line.split()
varnames.add(var1)
varnames.add(var2)
varnames.add(var3)
n = max([int(var[2:]) for var in varnames if var[:2]=='x_' ])+1 # no of inputs
m = max([int(var[2:]) for var in varnames if var[:2]=='y_' ])+1 # no of outputs
t = len(varnames)
def formatvar(i,justify=0):
if i<n:
return blue(str(i),justify)
if i>t-m-1:
return red(str(i),justify)
return green(str(i),justify)
varsidx = {}
varsval = { } # dictionary of value of "workspace" variables
for i in range(n):
varsval['x_'+str(i)] = 0
varsidx['x_'+str(i)] = i
for j in range(m):
varsval['y_'+str(j)] = 0
varsidx['y_'+str(j)] = len(varnames)-m+j
i = n
for var in varnames:
if var[:2]!='x_' and var[:2]!='y_':
varsval[var]=0
varsidx[var] = i
i += 1
sortednames = [s[0] for s in sorted(varsidx.items(), key=operator.itemgetter(1))]
printout = bold("Variables: ")
i=0
for var in sortednames:
printout += var + "->"+formatvar(i)+" "
i += 1
if (verbose):
print(printout)
printout = bold("Triples: \n")
result = []
for line in prog.split('\n'):
if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines
(var1,assign,var2,op,var3) = line.split()
a = varsidx[var1]
b = varsidx[var2]
c = varsidx[var3]
result.append([a,b,c])
printout += line.ljust(MAXLINELENGTH)+" -> ("+formatvar(a)+","+formatvar(b)+","+formatvar(c)+") \n"
if (verbose):
print(printout)
return result
The following program computes on input $x_0,x_1$ the XOR of $x_0$ and $x_1$.
i.e., outputs 1
on input 10
or 01
and output 0
on input 00
or 11
:
xor = r'''
u := x_0 NAND x_1
v := x_0 NAND u
w := x_1 NAND u
y_0 := v NAND w
'''
EVAL(xor,"10")
We can print snapshots of the values of the variables as we execute the program line by line:
snapshots(xor,"10")
addtwo = '''
u := x_0 NAND x_2
v := x_0 NAND u
w := x_2 NAND u
y_0 := v NAND w
c_1 := u NAND u
u := x_1 NAND x_3
v := x_1 NAND u
w := x_3 NAND u
z_1 := v NAND w
z'_1 := u NAND u
u := z_1 NAND c_1
v := z_1 NAND u
w := c_1 NAND u
y_1 := v NAND w
u := z'_1 NAND z'_1
v := z_1 NAND c_1
y_2 := u NAND v
'''
snapshots(addtwo,"1011")
represent(xor);
atleasttwo = '''
v_0 := x_0 NAND x_1
v_1 := x_0 NAND x_2
v_2 := x_1 NAND x_2
v_3 := v_2 NAND v_1
notv_3 := v_3 NAND v_3
y_0 := notv_3 NAND v_0
''';
represent(atleasttwo);
import networkx as nx
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
from IPython.display import Image
import warnings
warnings.filterwarnings("ignore")
# import matplotlib.cbook
# warnings.filterwarnings("ignore",category=matplotlib.cbook.mplDeprecation)
def NAND2Graph(P):
n = max([int(var[2:]) for var in P.split() if var[:2]=='x_' ])+1 # no of inputs
m = max([int(var[2:]) for var in P.split() if var[:2]=='y_' ])+1 # no of outputs
nodes = {}
def uniquenode(v):
idx = nodes.setdefault(v,-1)
nodes[v] = nodes[v]+1
return v+(" "*(idx+1))
G = nx.DiGraph()
for line in P.split('\n'):
if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines
(var1,assign,var2,op,var3) = line.split()
var1 = uniquenode(var1)
G.add_node(var1)
G.add_edge(var2,var1)
G.add_edge(var3,var1)
return G
We can represent every program also as a graph:
prog = r'''
u := x_0 NAND x_1
v := x_0 NAND u
w := x_1 NAND x_0
y_0 := v NAND w
'''
G= NAND2Graph(prog)
def draw_DAG(G):
D = nx.drawing.nx_pydot.to_pydot(G)
png_str = D.create_png()
return Image(data=png_str)
draw_DAG(G)
EVAL(prog,"11")
import math
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)
def expand(nandpp,t,n):
result = ""
for k in range(t):
i=index(k)
validx = ('one' if i<n else 'zero')
result += nandpp.replace('validx_i',validx).replace('x_i',('x_i' if i < n else 'zero')).replace('_i','_'+str(i))
return result
[index(k) for k in range(10)]
parity = '''one_0 := zero_0 NAND zero_0
tmp_1 := seen_i NAND seen_i
unique_66 := seen_i NAND seen_i
unique_68 := unique_66 NAND unique_66
unique_67 := unique_68 NAND unique_68
unique_69 := one_0 NAND one_0
upnb_0 := unique_67 NAND unique_67
upu_0 := unique_64 NAND upnb_0
upv_0 := unique_69 NAND unique_67
unique_64 := upu_0 NAND upv_0
unique_70 := unique_64 NAND unique_64
upnb_0 := unique_67 NAND unique_67
upu_0 := seen_i NAND upnb_0
upv_0 := unique_70 NAND unique_67
seen_i := upu_0 NAND upv_0
tmp_2 := x_i NAND tmp_1
val_0 := tmp_2 NAND tmp_2
ns_0 := s_0 NAND s_0
y_0 := ns_0 NAND ns_0
u_0 := val_0 NAND s_0
v_0 := s_0 NAND u_0
w_0 := val_0 NAND u_0
s_0 := v_0 NAND w_0
stop_0 := validx_i NAND validx_i
loop := stop_0 NAND stop_0
'''
prog = expand(parity,6,2)
print(prog)
EVAL(prog,"011")
G= NAND2Graph(prog)
draw_DAG(G)