Introduction to NAND
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)
from IPython.display import display, Markdown, Latex
def printmd(s):
display(Markdown(s))
NAND is a pedagogical and mathematical tool. Will later see that many others would work just as well.
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[21m"
def underline(s,justify=0):
return "\x1b[4m"+s.ljust(justify)+"\x1b[24m"
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,highlight=[],modified=""):
v = str(varsval[var])
s = v
if var==modified:
s=underline(s,0)
if var in highlight:
s=bold(s,0)
j = max(0,justify-len(v))
if varsidx[var]<n:
return blue(s)+" "*j
if varsidx[var]>t-m-1:
return red(s)+" "*j
return green(s)+" "*j
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 = 25
MAXVARLENGTH = 5
printout = "".ljust(MAXLINELENGTH)
for var in sortednames:
printout += formatvarname(var,MAXVARLENGTH)
print(printout)
if (step==-1):
step = len(prog.split('\n'))+1
j = 0
modified = ""
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()
printout = (str(j)+". "+line).ljust(MAXLINELENGTH-2)+": "
for var in sortednames:
printout += formatvarval(var,MAXVARLENGTH,[var2,var3],modified)
modified = var1
if ((cumulative and j< step) or (j==step)):
print(printout)
j += 1
varsval[var1] = 1-varsval.get(var2,0)*varsval.get(var3,0)
printout = "".ljust(MAXLINELENGTH)
for var in sortednames:
printout += formatvarval(var,MAXVARLENGTH,[],modified)
if (((j<step) and cumulative) or (j==step)):
print(printout)
return ''.join( str(varsval['y_'+str(j)]) for j in range(m))
def represent(prog):
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 = "\n$P=(V,X,Y,L)$ where \n\n"
printout += "$V= \{$"
i=0
for var in sortednames:
printout += ""+var+"" + ('' if var==sortednames[-1] else ', ')
i += 1
printout += "$\}$ \n\n"
printout += "$X = ($"
for i in range(n):
printout += ""+sortednames[i]+"" + ('' if i==n-1 else ', ')
printout += "$)$ \n\n"
printout += "$Y =($"
for j in range(m):
printout += ""+sortednames[t-m+j]+"" + (', ' if j==m-1 else ', ')
printout += "$)$ \n\n"
printout += "$L = ( $"
first = True
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()
printout += ('' if first else ', ')+"("+var1+","+var2+","+var3+")"
first = False
printout +="$)$ \n\n"
printmd(printout)
return printout
def represent_canonical(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)
# modified to return nothing
# return result
def table(prog):
n = max([int(var[2:]) for var in prog.split() if var[:2]=='x_' ])+1 # no of inputs
values = {}
for i in range(2**n):
s = bin(i)[2:].rjust(n,'0')
values[s] = EVAL(prog,s)
LENGTH = 7
printout = '''
Input | Output
-------|---------
'''
for k in values:
printout += k.ljust(LENGTH)+"|"+values[k].ljust(LENGTH)+"\n"
printmd(printout)
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,"01")
'1'
mystery = r'''
foo := x_0 NAND x_0
bar := foo NAND x_1
baz := x_0 NAND x_2
y_0 := bar NAND baz
'''
What is mystery(101)
?
a. $0$
b. $1$
What function does mystery
compute?
table(mystery)
Input | Output |
---|---|
000 | 0 |
001 | 0 |
010 | 1 |
011 | 1 |
100 | 0 |
101 | 1 |
110 | 0 |
111 | 1 |
addtwo = r'''
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
'''
EVAL(addtwo,"1111") # 3 + 3
'011'
table(addtwo)
Input | Output |
---|---|
0000 | 000 |
0001 | 010 |
0010 | 100 |
0011 | 110 |
0100 | 010 |
0101 | 001 |
0110 | 110 |
0111 | 101 |
1000 | 100 |
1001 | 110 |
1010 | 010 |
1011 | 001 |
1100 | 110 |
1101 | 101 |
1110 | 001 |
1111 | 011 |
We can print snapshots of the values of the variables as we execute the program line by line:
snapshots(xor,"11")
x_0 x_1 u w v y_0 0. u := x_0 NAND x_1 : 1 1 0 0 0 0 1. v := x_0 NAND u : 1 1 0 0 0 0 2. w := x_1 NAND u : 1 1 0 0 1 0 3. y_0 := v NAND w : 1 1 0 1 1 0 1 1 0 1 1 0
'0'
snapshots(addtwo,"1011")
x_0 x_1 x_2 x_3 u w z_1 v z'_1 c_1 y_0 y_1 y_2 0. u := x_0 NAND x_2 : 1 0 1 1 0 0 0 0 0 0 0 0 0 1. v := x_0 NAND u : 1 0 1 1 0 0 0 0 0 0 0 0 0 2. w := x_2 NAND u : 1 0 1 1 0 0 0 1 0 0 0 0 0 3. y_0 := v NAND w : 1 0 1 1 0 1 0 1 0 0 0 0 0 4. c_1 := u NAND u : 1 0 1 1 0 1 0 1 0 0 0 0 0 5. u := x_1 NAND x_3 : 1 0 1 1 0 1 0 1 0 1 0 0 0 6. v := x_1 NAND u : 1 0 1 1 1 1 0 1 0 1 0 0 0 7. w := x_3 NAND u : 1 0 1 1 1 1 0 1 0 1 0 0 0 8. z_1 := v NAND w : 1 0 1 1 1 0 0 1 0 1 0 0 0 9. z'_1 := u NAND u : 1 0 1 1 1 0 1 1 0 1 0 0 0 10. u := z_1 NAND c_1 : 1 0 1 1 1 0 1 1 0 1 0 0 0 11. v := z_1 NAND u : 1 0 1 1 0 0 1 1 0 1 0 0 0 12. w := c_1 NAND u : 1 0 1 1 0 0 1 1 0 1 0 0 0 13. y_1 := v NAND w : 1 0 1 1 0 1 1 1 0 1 0 0 0 14. u := z'_1 NAND z'_1: 1 0 1 1 0 1 1 1 0 1 0 0 0 15. v := z_1 NAND c_1 : 1 0 1 1 1 1 1 1 0 1 0 0 0 16. y_2 := u NAND v : 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 0 1 0 0 1
'001'
mystery2 = '''
u := x_0 NAND x_0
v := x_1 NAND x_1
w := u NAND v
y_0 := w NAND w
'''
represent(mystery2);
$P=(V,X,Y,L)$ where
$V= \{$x_0, x_1, u, w, v, y_0$\}$
$X = ($x_0, x_1$)$
$Y =($y_0, $)$
$L = ( $(u,x_0,x_0), (v,x_1,x_1), (w,u,v), (y_0,w,w)$)$
What function does mystery2
compute?
a. OR
b. AND
c. NOR (NOT OR)
d. XOR
represent(mystery2);
$P=(V,X,Y,L)$ where
$V= \{$x_0, x_1, u, w, v, y_0$\}$
$X = ($x_0, x_1$)$
$Y =($y_0, $)$
$L = ( $(u,x_0,x_0), (v,x_1,x_1), (w,u,v), (y_0,w,w)$)$
represent(addtwo);
print(addtwo)
$P=(V,X,Y,L)$ where
$V= \{$x_0, x_1, x_2, x_3, u, w, z_1, v, z'_1, c_1, y_0, y_1, y_2$\}$
$X = ($x_0, x_1, x_2, x_3$)$
$Y =($y_0, y_1, y_2, $)$
$L = ( $(u,x_0,x_2), (v,x_0,u), (w,x_2,u), (y_0,v,w), (c_1,u,u), (u,x_1,x_3), (v,x_1,u), (w,x_3,u), (z_1,v,w), (z'_1,u,u), (u,z_1,c_1), (v,z_1,u), (w,c_1,u), (y_1,v,w), (u,z'_1,z'_1), (v,z_1,c_1), (y_2,u,v)$)$
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
mystery3 = '''
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
'''
def get_triples(x):
# this is just a temporary definition so the notebook doesn't complain
# the actual definition is below
print("Not yet defined")
return [[2,1,0]]
get_triples(mystery3)
[[3, 0, 1], [4, 0, 2], [5, 1, 2], [6, 5, 4], [7, 6, 6], [8, 7, 3]]
What function $\{0,1\}^3 \rightarrow \{0,1\}$ do the triples above represent?
a. $XOR_3$
b. Majority
c. Mux
d. $AND_3$
print(mystery3)
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_canonical(mystery3)
Variables: x_0->0 x_1->1 x_2->2 v_1->3 notv_3->4 v_0->5 v_2->6 v_3->7 y_0->8 Triples: v_0 := x_0 NAND x_1 -> (5,0,1) v_1 := x_0 NAND x_2 -> (3,0,2) v_2 := x_1 NAND x_2 -> (6,1,2) v_3 := v_2 NAND v_1 -> (7,6,3) notv_3 := v_3 NAND v_3 -> (4,7,7) y_0 := notv_3 NAND v_0 -> (8,4,5)
table(mystery3)
Input | Output |
---|---|
000 | 0 |
001 | 0 |
010 | 0 |
011 | 1 |
100 | 0 |
101 | 1 |
110 | 1 |
111 | 1 |
Given: Program $P$ in canonical list of triples representation, $n$,$m$, input $x$
Output: Evaluation of $P$ on $x$
def eval_triples(L,n,m,x):
t = max([max(triple) for triple in L])+1
vars = [0]*t
vars[:n] = x
for (a,b,c) in L:
vars[a] = 1-vars[b]*vars[c]
return vars[t-m:]
eval_triples(get_triples(xor),2,1,[1,0])
[1]
eval_triples(get_triples(addtwo),4,3,[0,1,0,1])
[0, 0, 1]
def triples(prog,n,m,t):
varsidx = {}
def varindex(var):
if var[:2]=='x_': return int(var[2:])
if var[:2]=='y_': return t-m+int(var[2:])
if var in varsidx: return varsidx[var]
return varsidx.setdefault(var,len(varsidx)+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()
result.append([varindex(var1),varindex(var2),varindex(var3)])
return result
triples(xor,2,1,6)
[[2, 0, 1], [3, 0, 2], [4, 1, 2], [5, 3, 4]]
triples(addtwo,4,3,13)
def params(prog):
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.update([var1,var2,var3])
t = len(varnames)
n = len([var for var in varnames if var[:2]=='x_'])
m = len([var for var in varnames if var[:2]=='y_'])
return [n,m,t]
def get_triples(prog):
[n,m,t] = params(prog)
return triples(prog,n,m,t)
get_triples(xor)