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:]
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
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)
from IPython.display import display, Markdown, Latex
def printmd(s):
display(Markdown(s))
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
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))
def lastnode(v):
idx = nodes.get(v,0)
return v+(" "*idx)
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)
var2 = lastnode(var2)
var3 = lastnode(var3)
G.add_node(var1)
G.add_edge(var2,var1)
G.add_edge(var3,var1)
return G
def EVALgraph(L,n,m,x):
t = max([max(triple) for triple in L])+1
s = len(L)+n
y = eval_triples(L,n,m,x)
G = nx.DiGraph()
avars = [0]*t
avars[:n]=x
avars[t-m:t] = y
lines = ["" for i in range(t)]
for i in range(n):
node = 'x_'+str(i)+' = '+str(x[i])
G.add_node(node)
lines[i]= node
l = 0
for (a,b,c) in L:
v = 1-avars[b]*avars[c]
node = "line_"+str(l)+" = "+str(v)
avars[a] = v
G.add_node(node)
lines[a]= node
if len(lines[b])>0:
G.add_edge(lines[b],node)
if len(lines[c])>0:
G.add_edge(lines[c],node)
l += 1
for j in range(m):
node = 'y_'+str(j)+' = '+str(y[j])
G.add_node(node)
G.add_edge(lines[t-m+j],node)
return G
def draw_eval(prog,s):
x = [int(a) for a in s]
[n,m,t] = params(prog)
L = triples(prog,n,m,t)
G = EVALgraph(L,n,m,x)
return draw_DAG(G)
def draw_DAG(G):
D = nx.drawing.nx_pydot.to_pydot(G)
png_str = D.create_png()
return Image(data=png_str)
def draw_graph(prog):
G = NAND2Graph(prog)
return draw_DAG(G)
%%html
<b>Clicker: click <em>GO</em> and 41</b><br></br>
<iframe src="http://free.timeanddate.com/countdown/i5vf6j5p/n43/cf11/cm0/cu4/ct1/cs1/ca0/co0/cr0/ss0/cac09f/cpc09f/pct/tcfff/fs100/szw576/szh243/iso2017-09-21T10:07:00" allowTransparency="true" frameborder="0" width="177" height="35"></iframe>'
blah = r'''
u := x_0 NAND x_1
v := x_0 NAND u
w := x_1 NAND u
u := x_0 NAND v
y_0 := v NAND w
'''
represent(blah);
$P=(V,X,Y,L)$ where
$V= \{$x_0, x_1, v, u, w, y_0$\}$
$X = ($x_0, x_1$)$
$Y =($y_0, $)$
$L = ( $(u,x_0,x_1), (v,x_0,u), (w,x_1,u), (u,x_0,v), (y_0,v,w)$)$
represent_canonical(blah);
Variables: x_0->0 x_1->1 v->2 u->3 w->4 y_0->5 Triples: u := x_0 NAND x_1 -> (3,0,1) v := x_0 NAND u -> (2,0,3) w := x_1 NAND u -> (4,1,3) u := x_0 NAND v -> (3,0,2) y_0 := v NAND w -> (5,2,4)
draw_graph(blah)
draw_eval(blah,"01")
atleasttwo = r'''
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(atleasttwo)
Variables: x_0->0 x_1->1 x_2->2 v_2->3 v_0->4 notv_3->5 v_1->6 v_3->7 y_0->8 Triples: v_0 := x_0 NAND x_1 -> (4,0,1) v_1 := x_0 NAND x_2 -> (6,0,2) v_2 := x_1 NAND x_2 -> (3,1,2) v_3 := v_2 NAND v_1 -> (7,3,6) notv_3 := v_3 NAND v_3 -> (5,7,7) y_0 := notv_3 NAND v_0 -> (8,5,4)
draw_graph(atleasttwo)
draw_eval(atleasttwo,"101")
draw_graph(xor)
Work in groups: Write NAND program for $XOR_4:\{0,1\}^4 \rightarrow \{0,1\}$. Draw the graph corresponding to program. Can you make it have depth at most 4?
xor4sweet = '''
def c := XOR(a,b) {
u := a NAND b
v := a NAND u
w := b NAND u
c := v NAND w
}
y_0 := XOR(XOR(x_0,x_1),XOR(x_2,x_3))
'''
print(xor4sweet)
xor4unsweet = '''
upu_0 := x_0 NAND x_1
upv_0 := x_0 NAND upu_0
upw_0 := x_1 NAND upu_0
unique_0 := upv_0 NAND upw_0
upu_0 := x_2 NAND x_3
upv_0 := x_2 NAND upu_0
upw_0 := x_3 NAND upu_0
unique_1 := upv_0 NAND upw_0
upu_0 := unique_0 NAND unique_1
upv_0 := unique_0 NAND upu_0
upw_0 := unique_1 NAND upu_0
y_0 := upv_0 NAND upw_0
'''
draw_graph(xor4unsweet)
draw_eval(xor4unsweet,"0110")