Code related to Chapter 5: Code as data, Data as code in Introduction to Theoretical Computer Science by Boaz Barak.
!wget https://raw.githubusercontent.com/boazbk/tcscode/master/Utilities.ipynb
!pip install schemdraw
# utility code
%run "Utilities.ipynb"
from IPython.display import clear_output
clear_output()
xorcode = r'''temp_0 = NAND(X[0],X[1])
temp_1 = NAND(X[0],temp_0)
temp_2 = NAND(X[1],temp_0)
Y[0] = NAND(temp_1,temp_2)
'''
len(xorcode)
107
code = r'''temp_0 = NAND(X[0],X[1])
t1 = NAND(temp_0,temp_0)
notx0 = NAND(X[0],X[0])
temp_1 = NAND(notx0,X[2])
t2 = NAND(temp_1,temp_1)
temp_2 = NAND(t1,t1)
temp_3 = NAND(t2,t2)
Y[0] = NAND(temp_2,temp_3)'''
def code2rep(code):
"""Map NAND-CODE to the list-of-triples representation."""
inputs = [] ; workspace = [] ; outputs = []
def parse(line): # extract 3 variables from line of code
return line[:line.find("=")].strip(), line[line.find("(")+1:line.find(",")].strip(), line[line.find(",")+1:line.find(")")].strip()
def addvar(var): # add variable to inputs/outputs/workspace lists
nonlocal inputs,workspace,outputs
if var[0]=='X':
if not var in inputs: inputs += [var]
elif var[0]=='Y':
if not var in outputs: outputs += [var]
elif not var in workspace:
workspace += [var]
# add all variables
for line in code.split('\n'):
for var in parse(line):
addvar(var)
variables = sorted(inputs) + workspace + sorted(outputs)
print(variables)
L = [] # list of triples
for line in code.split('\n'):
foo,bar,blah = parse(line)
L += [[variables.index(foo),variables.index(bar),variables.index(blah)]]
return (len(inputs),len(outputs),L)
code2rep(code)
['X[0]', 'X[1]', 'X[2]', 'temp_0', 't1', 'notx0', 'temp_1', 't2', 'temp_2', 'temp_3', 'Y[0]']
(3, 1, [[3, 0, 1], [4, 3, 3], [5, 0, 0], [6, 5, 2], [7, 6, 6], [8, 4, 4], [9, 7, 7], [10, 8, 9]])