This is a notebook with all sorts of general utility code that is used for the rest of the notebooks. Some of the code is duplicated from other notebooks. Eventually the authorative version should be here
def NAND(x,y):
"""Compute the NAND of two 0/1 valued variables."""
return 1 - x*y
def splitline(line):
foo,bar,blah, = filter(None,re.split('\s*=\s*NAND\s*\(\s*|\s*\,\s*|\s*\)\s*|\s+',line))
return (foo,bar,blah)
import re
def EVAL(prog,x):
"""Evaluate NAND program prog on input x."""
(n,m) = numinout(prog) # utility function to get num of inputs/outputs
vartable = defaultdict(int) # dictionary for variables
for i in range(n): vartable[f'X[{i}]']=x[i] # assign x[i] to variable "X[i]"
for line in filter(None,prog.split('\n')): # split into lines, throw out empty ones
# split to components of a line:
foo,bar,blah = splitline(line)
vartable[foo] = NAND(vartable[bar],vartable[blah])
return [vartable[f'Y[{j}]'] for j in range(m)]
# utility function
def numinout(prog):
'''Compute the number of inputs and outputs of a NAND program, given as a string of source code.'''
n = max([int(s[2:-1]) for s in re.findall(r'X\[\d+\]',prog)])+1
m = max([int(s[2:-1]) for s in re.findall(r'Y\[\d+\]',prog)])+1
return n,m
# Some utility functions
# (can ignore on first read, uses some Python trickery that's not so important for us)
from inspect import signature
def numarguments(f):
"""Number of arguments a Python function takes."""
return len(signature(f).parameters)
def runwith(f,*args):
"""Evaluate function f binding name to func"""
g = globals()
old = {}
new = {}
for j in range(0,len(args),2):
old[args[j]] = g[args[j]]
new[args[j]] = args[j+1]
# a little bit of an ugly hack
# if you know a nicer way, please let me know
try:
for name in new: g[name] = new[name]
res = f()
finally:
for name in old: g[name] = old[name]
return res
def NOT(a):
return NAND(a,a)
def AND(a,b):
return NOT(NAND(a,b))
def OR(a,b):
return NAND(NOT(a),NOT(b))
def one(a):
return NAND(a,NOT(a))
def zero(a):
return NOT(one(a))
def COPY(a):
return NOT(NOT(a))
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
#Use Graphviz to visualize circuits
import graphviz
from graphviz import Graph
from graphviz import Digraph
#Graphviz version
def gvnandcircuit(f):
"""Compute the graph representating a NAND circuit for a NAND program, given as a Python function."""
n = numarguments(f)
counter = 0 # to ensure unique temporary variables.
G = Digraph(graph_attr= {"rankdir":"LR"}, strict=False) # schem.Drawing(unit=.5)
def tempNAND(bar,blah):
nonlocal G, counter
var = f'Temp[{counter}]'
counter += 1
G.node(var,label="∧\u0305",shape='invhouse',orientation="90")
G.edge(bar,var)
G.edge(blah,var)
return var
for i in range(n):
G.node(f'X[{i}]',label=f'X[{i}]', fontcolor='blue',shape='circle')
outputs = runwith(lambda: f(*[f'X[{i}]' for i in range(n)]),'NAND',tempNAND)
if type(outputs)==str: outputs = [outputs] # make single output into singleton list
for j in range(len(outputs)):
G.node(f'out_{j}',label=f'Y[{j}]',fontcolor='red',shape='diamond')
G.edge(outputs[j],f'out_{j}')
return G
def nandcircuit(f,method="Graphviz"):
return gvnandcircuit(f) if method=="Graphviz" else sdnandcircuit(f)
def MAJ(a,b,c):
return NAND(NAND(NAND(NAND(a,b),NAND(a,c)),NAND(NAND(a,b),NAND(a,c))),NAND(b,c))
def LOOKUP(T,i):
l = len(i)
if l==1:
return IF(i[0],T[1],T[0])
return IF(i[l-1],LOOKUP(T[2**(l-1):],i[:-1]),LOOKUP(T[:2**(l-1)],i[:-1]))
# A more efficient IF .. not strictly necessary
def IF(cond,a,b):
notcond = NAND(cond,cond)
temp = NAND(b,notcond)
temp1 = NAND(a,cond)
return NAND(temp,temp1)
# generalize restrict to handle functions that take more than one array
def restrict(f,*numinputs):
"""Create function that restricts the function f to exactly given input lengths n0,n1,..."""
k = len(numinputs)
args = []
t = 0
for i in range(k):
if numinputs[i]: args = args + [", ".join(f'arg_{i}_{j}' for j in range(numinputs[i]))]
sig = ", ".join(args)
call = ", ".join(f"[{a}]" for a in args)
code = rf'''
def _temp({sig}):
return f({call})
'''
l = dict(locals())
exec(code,l)
return l["_temp"]
def funclookup(l):
return restrict(LOOKUP,2**l,l)
We can represent a NAND program in many ways including the string of its source code, as the graph corresponding to its circuit. One simple representation of a NAND program we will use is as the following:
We represent a NAND program of $t$ intermediate variables, $s$ lines, $n$ input variables, and $m$ input variables as a triple $(n,m,L)$ where $L$ is a list of $s$ triples of the form $(a,b,c)$ of numbers in $[n+t+m]$.
A triple $(a,b,c)$ corresponds to the line assigning to the variable corresponding $a$ the NAND of the variables corresponding to $b$ and $c$. We identify the first $n$ variables with the input and the last $m$ variables with the outputs.
We can again compute this representation using Python:
def nandrepresent(f,numargs=0):
"""Compute the list of triple representation for a NAND program, given by a Python function."""
n = numargs if numargs else numarguments(f)
counter = n # to ensure unique temporary variables.
L = [] # list of tuples
def tempNAND(bar,blah):
nonlocal L, counter
var = counter
counter += 1
L += [(var,bar,blah)]
return var
if(numargs):
outputs = runwith(lambda: f(range(n)), "NAND", tempNAND)
else:
outputs = runwith(lambda: f(*range(n)), "NAND", tempNAND)
if type(outputs)==int: outputs = [outputs] # make single output into singleton list
m = len(outputs)
# make sure outputs are last m variables
for j in range(m):
def flip(a):
nonlocal counter, outputs, j
if a==outputs[j]: return counter+j
return a
L = [(flip(a),flip(b),flip(c)) for (a,b,c) in L]
return (n,m,compact(L))
# utlity function
def compact(L):
"""Compact list of triples to remove unused variables."""
s = sorted(set.union(*[set(T) for T in L]))
return [ (s.index(a),s.index(b),s.index(c)) for (a,b,c) in L]
We can directly evaluate a NAND program based on its list of triples representation:
def EVALnand(prog,X):
"""Evaluate a NAND program from its list of triple representation."""
n,m,L = prog
vartable = X+[0]*(max(max(a,b,c) for (a,b,c) in L)-n+1)
for (a,b,c) in L:
vartable[a] = NAND(vartable[b],vartable[c])
return [vartable[-m+j] for j in range(m)]
def code2rep(code):
"""Transform code to triples representation"""
s = code.count("\n")
n = 0
varnums = {}
while code.find(f"X[{n}]")>= 0:
varnums[f"X[{n}]"] = n
n+=1
t = n
def getnum(var):
nonlocal t
if not var in varnums:
varnums[var]= t
t += 1
return varnums[var]
m = 0
while code.find(f"Y[{m}]")>= 0:
varnums[f"Y[{m}]"] = 3*s+m
m += 1
L = []
for line in code.split("\n"):
if not line.strip(): continue
foo,bar,blah, = filter(None,re.split('\s*=\s*NAND\s*\(\s*|\s*\,\s*|\s*\)\s*|\s+',line))
L.append([getnum(foo),getnum(bar),getnum(blah)])
return (n,m,compact(L))
def code2circuit(code, pruneit=True):
return rep2circuit(prune(code2rep(code))) if pruneit else rep2circuit(code2rep(code))
We can do some simple transformations to reduce the size of our programs/circuits. For example, if two gates have exactly the same inputs then we can identify them with one another. We can also use the equality NOT(NOT(a))=a, as well as remove unused variables.
def makeunique(prog):
"""Ensure that every working variable is only assigned a value once"""
n,m,L = prog
t = max([max(a,b,c) for (a,b,c)in L])+1
last = {i:i for i in range(n) }
res = []
maxval = len(L)+n
cur = n
outputs = {}
for (a,b,c) in L:
_b = last[b]
_c = last[c]
if a>= t-m:
outputs[a-t+m] = cur
_a = cur
last[a] = cur
cur += 1
res.append((_a,_b,_c))
def update(a):
nonlocal maxval
for (o,b) in list(outputs.items()):
if b==a: return maxval-m+o
return a
temp = [(update(a),b,c) for (a,b,c) in res]
return n,m,compact(temp)
def prune(prog):
"""Prune representation of program as tuples, removing duplicate lines and unused variables."""
n,m,L = makeunique(prog)
L = list(L)
def identify(L,e,f):
# identify vertex e with vertex f
def ident(k):
nonlocal e,f
return f if k==e else k
return [(ident(a),ident(b),ident(c)) for (a,b,c) in L]
t = max([max(a,b,c) for (a,b,c) in L])+1
while True:
neighborhood = {}
neighbors = {}
found = False
for (a,b,c) in L:
N = frozenset([b,c])
if a>=t-m: continue # don't remove output variables
if N in neighborhood: # there was prior duplicate line
L.remove((a,b,c))
L = identify(L,a,neighborhood[N])
found = True
break
if b==c and b in neighbors and len(neighbors[b])==1: # line is NOT of NOT of prior line
L.remove((a,b,c))
L = identify(L,a,next(iter(neighbors[b])))
found = True
break
neighborhood[N] = a
neighbors[a] = N
touched = {a: False for a in range(t)}
for (a,b,c) in L:
touched[b] = True
touched[c] = True
for d in range(n,t-m,1): # remove non output and input variables that are not used
if not touched[d]:
for (a,b,c) in L:
if a==d:
L.remove((a,b,c))
found =True
if not found: break
return (n,m,compact(L))
# Majority
def MAJ(a,b,c): return NAND(NAND(NAND(NAND(a,b),NAND(a,c)),NAND(NAND(a,b),NAND(a,c))),NAND(b,c))
We can use the list of triples representation as a starting point to obtain the NAND program as a list of lines of code, or as a circuit (i.e., directed acyclic graph).
# Graphviz version
def gvrep2circuit(P,sizeparam="11,5"):
"""Return circuit (i.e., graph) corresponding to NAND program P given in list of tuples representation."""
n,m,L = P
G = Digraph(graph_attr= {"rankdir":"LR"},strict=False)
last = {}
for i in range(n):
G.node(f"v{i}",label=f'X[{i}]', fontcolor='blue',shape='circle')
last[i] = f"v{i}"
t = n
ctr = n
for (a,b,c) in L:
G.node(f"v{ctr}",label='∧\u0305',shape='invhouse',orientation='90') # shape='none' image='NAND_gate.png')
if b in last: G.edge(last[b],f"v{ctr}")
if c in last: G.edge(last[c],f"v{ctr}")
last[a] = f"v{ctr}"
ctr += 1
t = max(t,a,b,c)
t += 1
for j in range(m):
G.node(f"out{t-m+j}",label=f'Y[{j}]',fontcolor='red',shape='diamond')
if (t-m+j) in last: G.edge(last[t-m+j],f"out{t-m+j}")
G.graph_attr.update(size=sizeparam, ratio="fill")
return G
def rep2code(P):
"""Return NAND code corresponding to NAND program P, given in list of tuples representation"""
n,m,L = P
code = ""
t = max([max(a,b,c) for (a,b,c) in L])+1
def var(a):
if a<n: return f"X[{a}]"
if a>=t-m: return f"Y[{a-t+m}]"
return f"Temp[{a-n}]"
for (a,b,c) in L:
code += f"{var(a)} = NAND({var(b)},{var(c)})\n"
return code
def rep2circuit(P,method="Graphviz"):
return gvrep2circuit(P) if method=="Graphviz" else sdrep2circuit(P)
We can now redefine the nandcircuit
and nandcode
functions to work as follows:
def nandcode(f,pruneit=False,numargs=0):
R = prune(nandrepresent(f,numargs)) if pruneit else nandrepresent(f,numargs)
return rep2code(R)
def nandcircuit(f, pruneit = False, method="Graphviz",numargs=0):
R = prune(nandrepresent(f,numargs)) if pruneit else nandrepresent(f,numargs)
return rep2circuit(R,method)
We can construct a NAND program $P$ that given the representation of a NAND program $Q$ and an input $x$, outputs $Q(x)$. We can obviously compute such a function since every finite function is computable by a NAND program, but it turns out we can do so in a program that is polynomial in the size of $P$ (even quasiliinear but we won't show that here).
We start with a reimplementation of NANDEVAL
in Python:
def GET(V,i): return V[i]
def UPDATE(V,i,b):
V[i]=b
return V
def NANDEVAL(n,m,L,X):
# Evaluate a NAND program from its list of triple representation.
s = len(L) # number of lines
t = max(max(a,b,c) for (a,b,c) in L)+1 # maximum index in L + 1
Vartable = [0] * t # we'll simply use an array to store data
# load input values to Vartable:
for i in range(n): Vartable = UPDATE(Vartable,i,X[i])
# Run the program
for (i,j,k) in L:
a = GET(Vartable,j)
b = GET(Vartable,k)
c = NAND(a,b)
Vartable = UPDATE(Vartable,i,c)
# Return outputs Vartable[t-m], Vartable[t-m+1],....,Vartable[t-1]
return [GET(Vartable,t-m+j) for j in range(m)]
Now transform this to work with the representation of L
as a binary string, namely as a sequence of $3s$ numbers in $[t]$, each represented as a string of length $\ell = \lceil \log 3s \rceil$.
from math import ceil, floor, log2
def triplelist2string(L):
"""Transform list of triples into its representation as a binary string"""
s = len(L)
ell = ceil(log2(3*s))
B = [0]*(3*s*ell)
FlatL = [a for T in L for a in T]
for i in range(3*s):
for j in range(ell):
B[ell*i + j] = floor(FlatL[i]/ 2**j) % 2
return B
We can now present NANDEVALBIN
which will be a Python function that evaluates a NAND program given the representation of the program as a binary string. (We assume the parameters $n,m,s,t$ are given: we could have assumed they are part of the string representation, but this only makes things messier.)
def NANDEVALBIN(n,m,s,t,B,X):
"""Evaluate nand program given its description as a binary array"""
ell = ceil(log2(3*s))
Vartable = [0] * (2**ell) # we'll simply use an array to store data
# load input values to Vartable:
for i in range(n): Vartable[i] = X[i]
# Run the program
for c in range(s):
i = [B[c*3*ell+d] for d in range(ell)]
j = [B[c*3*ell+ell+d] for d in range(ell)]
k = [B[c*3*ell+2*ell+d] for d in range(ell)]
a = GETB(Vartable,j)
b = GETB(Vartable,k)
c = NAND(a,b)
Vartable = UPDATEB(Vartable,i,c)
# Return outputs Vartable[t-m], Vartable[t-m+1],....,Vartable[t-1]
return [Vartable[t-m+j] for j in range(m)]
We'll need some utility functions to deal with the binary representation (you can ignore these at a first read)
# utility functions
def nandconst(b,x):
"""Transform 0 or 1 to NAND zero or one functions"""
if b: return one(x)
return zero(x)
def i2s(i,ell=0):
"""Transform integer to binary representation of length ell"""
if not ell: ell = ceil(log2(i))
return [floor(i/2**j) %2 for j in range(ell)]
def GETB(V,i):
return LOOKUP(V,i)
def EQUALB(j,i):
flag = zero(i[0]) # if flag is one then i is different from j
for t in range(len(j)):
if type(j[t])==int:
temp = NOT(i[t]) if j[t] else COPY(i[t])
else:
temp = OR(AND(j[t],NOT(i[t])),AND(NOT(j[t]),i[t]))
flag = OR(temp,flag)
return NOT(flag)
def UPDATEB(V,i,b):
ell = ceil(log2(len(V)))
UV = [0]*len(V)
for j in range(len(V)):
a = EQUALB(i2s(j,ell),i)
UV[j] = IF(a,b,V[j])
return UV
Now let's test this out on the XOR function
We now transform the Python program NANDEVALBIN into a NAND program. In fact, it turns out that all our python code can be thought of as "syntacic sugar" and hence we can do this transformation automatically.
Specifically, for every numbers $n,m,s,t$ we will construct a NAND program $P$ on $3s\ell+n$ inputs (for $\ell = \lceil \log_2(3s) \rceil$ that on input a string $B\in \{0,1\}^{3s\ell}$ and $x\in \{0,1\}^n$ outputs $P(x)$ where $P$ is the program represented by $B$.
To do so, we simply first restrict NANDEVALBIN
to the parameters $n,m,s,t$ and then run our usual "unsweetener" to extract the NAND code from it
def nandevalfunc(n,m,s,t):
"""Given n,m,s,t, return a function f that on input B,X returns the evaluation of the program encoded by B on X"""
ell = ceil(log2(3*s))
return restrict(lambda B,X: NANDEVALBIN(n,m,s,t,B,X),3*s*ell,n)
For example, let us set $n,m,s,t$ to be the parameters as in the XOR function
# Ignore this utility function in first and even second and third read
import inspect
import ast
import astor
def noop(f):
return f;
def runwithstate(f):
"""Modify a function f to take and return an argument state and make all names relative to state."""
tree = ast.parse(inspect.getsource(f))
tmp = ast.parse("def _temp(state):\n pass\n").body[0]
args = tmp.args
name = tmp.name
tree.body[0].args = args
tree.body[0].name = name
tree.body[0].decorator_list = []
class AddState(ast.NodeTransformer):
def visit_Name(self, node: ast.Name):
if node.id == "enandpp": return ast.Name(id="noop", ctx=Load())
new_node = ast.Attribute(ast.copy_location(ast.Name('state', ast.Load()), node), node.id,
ast.copy_location(ast.Load(), node))
return ast.copy_location(new_node, node)
tree = AddState().visit(tree)
tree.body[0].body = tree.body[0].body + [ast.parse("return state")]
tree = ast.fix_missing_locations(tree)
src = astor.to_source(tree)
# print(src)
exec(src,globals())
_temp.original_func = f
return _temp
def enandpp(f):
g = runwithstate(f)
def _temp1(X):
nonlocal g
return ENANDPPEVAL(g,X)
_temp1.original_func = f
_temp1.transformed_func = g
return _temp1
# ignore utility class in first and even second or third read
from collections import defaultdict
class NANDPPstate:
"""State of a NAND++ program."""
def __init__(self):
self.scalars = defaultdict(int)
self.arrays = defaultdict(lambda: defaultdict(int))
# eventually should make self.i non-negative integer type
def __getattr__(self,var):
g = globals()
if var in g and callable(g[var]): return g[var]
if var[0].isupper():
return self.arrays[var]
else:
return self.scalars[var]
def ENANDPPEVAL(f,X):
"""Evaluate an enhanced NAND++ function on input X"""
s = NANDPPstate()
for i in range(len(X)):
s.X[i] = X[i]
s.Xvalid[i] = 1
while True:
s = f(s)
if not s.loop: break
res = []
i = 0
while s.Yvalid[i]:
res += [s.Y[i]]
i+= 1
return res
def rreplace(s, old, new, occurrence=1): # from stackoverflow
li = s.rsplit(old, occurrence)
return new.join(li)
def ENANDPPcode(P):
"""Return ENAND++ code of given function"""
code = ''
counter = 0
class CodeENANDPPcounter:
def __init__(self,name="i"):
self.name = name
def __iadd__(self,var):
nonlocal code
code += f'\ni += {var}'
return self
def __isub__(self,var):
nonlocal code
code += f'\ni -= {var}'
return self
def __str__(self): return self.name
class CodeNANDPPstate:
def __getattribute__(self,var):
# print(f"getting {var}")
if var=='i': return CodeENANDPPcounter()
g = globals()
if var in g and callable(g[var]): return g[var]
if var[0].isupper():
class Temp:
def __getitem__(self,k): return f"{var}[{str(k)}]"
def __setitem__(s,k,v): setattr(self,f"{var}[{str(k)}]",v)
return Temp()
return var
def __init__(self):
pass
def __setattr__(self,var,val):
nonlocal code
if var=='i': return
if code.find(val)==-1:
code += f'\n{var} = {val}'
else:
code = rreplace(code,val,var)
s = CodeNANDPPstate()
def myNAND(a,b):
nonlocal code, counter
var = f'temp_{counter}'
counter += 1
code += f'\n{var} = NAND({a},{b})'
return var
s = runwith(lambda : P.transformed_func(s),"NAND",myNAND)
return code
In "vanilla" NAND++ we do not have the commands i += foo
and i -= foo
but rather i
travels obliviously according to the sequence $0,1,0,1,2,1,0,1,2,3,2,1,0,1,2,\ldots$
def index():
"""Generator for the values of i in the NAND++ sequence"""
i = 0
last = 0
direction = 1
while True:
yield i
i += direction
if i> last:
direction = -1
last = i
if i==0: direction = +1
[0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1]
def NANDPPEVAL(f,X):
"""Evaluate a NAND++ function on input X"""
s = NANDPPstate() # intialize state
# copy input:
for i in range(len(X)):
s.X[i] = X[i]
s.Xvalid[i] = 1
# main loop:
for i in index():
s.i = i
s = f(s)
if not s.loop: break
# copy output:
res = []
i = 0
while s.Yvalid[i]:
res += [s.Y[i]]
i+= 1
return res
def nandpp(f):
"""Modify python code to obtain NAND++ program"""
g = runwithstate(f)
def _temp1(X):
return NANDPPEVAL(g,X)
_temp1.original_func = f
_temp1.transformed_func = g
return _temp1
Here is the increment function in vanilla NAND++. Note that we need to keep track of an Array Visited
to make sure we only add the carry once per location.
def NANDPPcode(P):
"""Return NAND++ code of given function"""
code = ''
counter = 0
class CodeNANDPPstate:
def __getattribute__(self,var):
# print(f"getting {var}")
g = globals()
if var in g and callable(g[var]): return g[var]
if var =="i": return "i"
if var[0].isupper():
class Temp:
def __getitem__(self,k): return var+f"[{k}]"
def __setitem__(s,k,v):
setattr(self,var+f"[{k}]",v)
return Temp()
return var
def __init__(self):
pass
def __setattr__(self,var,val):
nonlocal code
# print(f"setting {var} to {val}")
if code.find(val)==-1:
code += f'{var} = {val}\n'
else:
code = rreplace(code,val,var)
s = CodeNANDPPstate()
def myNAND(a,b):
nonlocal code, counter
var = f'temp_{counter}'
counter += 1
code += f'{var} = NAND({a},{b})\n'
return var
s = runwith(lambda : P.transformed_func(s),"NAND",myNAND)
return code
# utility code - replace string from right, taken from stackoverflow
def rreplace(s, old, new, occurrence=1):
li = s.rsplit(old, occurrence)
return new.join(li)
from math import sqrt
def indexat(k):
return min([abs(k-int(r)*(int(r)+1)) for r in [sqrt(k)-0.5,sqrt(k)+0.5]])
def zoom(G,factor=4):
s1 = 11*factor
s2 = 5*factor
G.graph_attr.update(size=f"{s1},{s2}!", ratio="fill")
return G
def unroll__(P,n,m,T):
result = r'''
temp = NAND(X[0],X[0])
one = NAND(X[0],temp)
zero = NAND(one,one)
'''[1:]
for t in range(T // P.count('\n')):
i = indexat(t) # value of i in T-th iteration
valid = ('one' if i < n else 'zero' )
inp = ('X[i]' if i < n else 'zero')
out = ('Y[i]' if i < m else 'temp' )
result += P.replace('Xvalid[i]',valid).replace('X[i]',inp
).replace('Y[i]',out).replace('[i]',f'[{i}]')
return result
def unroll_(f,n,m,T=0):
if not T:
T = time(f,[0]*n)
P = NANDPPcode(f)
result = r'''
temp = NAND(X[0],X[0])
one = NAND(X[0],temp)
zero = NAND(one,one)
'''[1:]
for t in range(T // P.count('\n')):
i = indexat(t) # value of i in T-th iteration
valid = ('one' if i < n else 'zero' )
inp = ('X[i]' if i < n else 'zero')
out = ('Y[i]' if i < m else 'temp' )
result += P.replace('Xvalid[i]',valid).replace('X[i]',inp).replace('Y[i]',out).replace('[i]',f'[{i}]')
return result
def unroll(f,n,m,T=0):
'''Gets f = NAND PP program, T - time bound, n - number of inputs, m - number of outputs
Produces NAND program of O(T) lines that computes the restriction of f to inputs of length n and T steps'''
if not T:
T = time(f,[0]*n)
P = NANDPPcode(f)
lines = [l for l in P.split('\n') if l]
result = r'''
temp = NAND(X[0],X[0])
one = NAND(X[0],temp)
zero = NAND(one,one)
nothalted = NAND(X[0],temp)
halted = NAND(one,one)
'''[1:]
# assign_to = IF(halted,old_value,new_value)
IFCODE = r'''
iftemp_0 = NAND(new_value,nothalted)
iftemp_1 = NAND(assign_to,halted)
assign_to = NAND(iftemp_0,iftemp_1)
'''[1:]
UPDATEHALTED = r'''
halted = NAND(nothalted,loop)
nothalted = NAND(halted,halted)
'''[1:]
for t in range(T // len(lines)):
j = indexat(t)
for line in lines:
if j>= m:
line = line.replace('Y[i]','temp')
if j< n:
line = line.replace('Xvalid[i]','one')
else:
line = line.replace('Xvalid[i]','zero')
line = line.replace('X[i]','zero')
line = line.replace('[i]',f'[{j}]')
idx = line.find("=")
lefthand = line[:idx].strip()
righthand = line[idx+1:].strip()
result += "new_value = " + righthand + "\n"
result += IFCODE.replace("assign_to",lefthand)
result += UPDATEHALTED
return result
def time(f,x):
counter = 0
def tempNAND(a,b):
nonlocal counter
counter += 1
return 1 - a*b
runwith(lambda: f(x), "NAND", tempNAND)
return counter
from IPython.display import Image
from IPython.core.display import HTML
import functools
import graphviz
from graphviz import Graph
from graphviz import Digraph
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 math
import networkx as nx
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
from IPython.display import Image
import pydotplus
def nxgraph(G):
P = pydotplus.graph_from_dot_data(G.source)
return nx.drawing.nx_pydot.from_pydot(P)
import warnings
warnings.filterwarnings("ignore")
# import matplotlib.cbook
# warnings.filterwarnings("ignore",category=matplotlib.cbook.mplDeprecation)
def subscriptdigit(d):
return ["₀","₁","₂","₃","₄","₅","₆","₇","₈","₉"][d]
def subscript(s):
digits = ["0","1","2","3","4","5","6","7","8","9"]
return "".join([subscriptdigit(int(s[i])) if s[i] in digits else s[i] for i in range(len(s))])
def scale(G,sizeparam="10,5"):
G.graph_attr.update(size=sizeparam, ratio="fill")
return G
# Evaluate 3CNF φ on assignment x
# Both are represented as strings
def evalcnf(φ,x):
def varval(v):
return (1-int(x[int(v[2:])]) if v[0]=="¬" else int(x[int(v[1:])]))
for (v0,v1,v2) in getclauses(φ):
# print(c+str([varval(v0),varval(v1),varval(v2)]))
if not varval(v0)+varval(v1)+varval(v2): return False
return True
# Clause list of a 3CNF φ
def getclauses(φ):
clauses = φ.split("∧")
res = []
for c in clauses:
(v0,_,v1,_,v2) = c.strip()[1:-1].split()
res.append((v0.strip(),v1.strip(),v2.strip()))
return res
# number of variables of a formula φ
def numvars(φ):
for n in range(len(φ)-1,0,-1):
if φ.find('x'+str(n))>= 0: return n+1
raise Exception
def from_dimacs(cnf):
φ = ""
m = 0
n = 0
def var(idx): return f"x{int(idx)-1}" if int(idx)>0 else f"¬x{-int(idx)-1}"
for line in cnf.split("\n"):
if not line.strip() or line[0]=="c" or line[0]=="%" or line[0]=="0": continue
if line[0]=="p":
_,t,n_,m_ = line.split()
if t!="cnf": raise Exception("Only handle CNF!")
n = int(n_)
m = int(m_)
continue
a,b,c,_ = line.split()
if _ != "0": raise Exception("Only handle 3CNF!")
φ += f"({var(a)} ∨ {var(b)} ∨ {var(c)} ) ∧ "
φ = φ[:-3]
return φ
def from_dimacs_assign(assign):
avals = {}
n = 0
for a in assign.split():
if a == "v": continue
a = int(a)
if a>0:
avals[a-1] = "1"
n = max(n,a)
if a<0:
avals[-a-1] = "0"
n = max(n,-a)
if a == 0:
break
x = ""
for i in range(n):
x += avals[i]
return x
print("Finished running utility code")
Finished running utility code