{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter 4: Syntactic Sugar and Computing Every Function\n",
"\n",
"Code related to [Chapter 4: Syntactic Sugar and Computing Every Function](https://introtcs.org/public/lec_03a_computing_every_function.html) in __Introduction to Theoretical Computer Science__ by Boaz Barak. [](https://colab.research.google.com/github/boazbk/tcscode/blob/master/Chap_04_Syntactic_Sugar.ipynb)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"!wget https://raw.githubusercontent.com/boazbk/tcscode/master/Utilities.ipynb"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"!pip install schemdraw"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# utility code \n",
"%run \"Utilities.ipynb\"\n",
"from IPython.display import clear_output\n",
"clear_output()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## \"Desugar\" \n",
"\n",
"Function that convert a program using syntactic sugar to a program that does not use it"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import re\n",
"def desugar(code, func_name, func_args,func_body):\n",
" \"\"\"\n",
" Replaces all occurences of \n",
" foo = func_name(func_args) \n",
" with\n",
" func_body[x->a,y->b]\n",
" foo = [result returned in func_body] \n",
" \"\"\"\n",
" # Use `search and replace' to replace calls to a function with its code.\n",
" # Uses Python regular expressions to simplify the search and replace,\n",
" # see https://docs.python.org/3/library/re.html\n",
" \n",
" # regular expression for capturing a list of variable names separated by commas\n",
" arglist = \",\".join([r\"([a-zA-Z0-9\\_\\[\\]]+)\" for i in range(len(func_args))])\n",
" # regular expression for capturing a statement of the form\n",
" # \"variable = func_name(arguments)\"\n",
" regexp = fr'([a-zA-Z0-9\\_\\[\\]]+)\\s*=\\s*{func_name}\\({arglist}\\)\\s*$'\n",
" \n",
" while True:\n",
" m = re.search(regexp, code, re.MULTILINE)\n",
" if not m: break\n",
"\n",
" newcode = func_body \n",
"\n",
" # replace function arguments by the variables from the function invocation\n",
" for i in range(len(func_args)): \n",
" newcode = newcode.replace(func_args[i], m.group(i+2))\n",
" \n",
" # Splice the new code inside\n",
" newcode = newcode.replace('return', m.group(1) + \" = \")\n",
" code = code[:m.start()] + newcode + code[m.end()+1:]\n",
"\n",
" return code"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"temp = NAND(x,y)\n",
"z = NAND(y,c)\n",
"temp = NAND(z,x)\n",
"w = NAND(x,c)\n",
"\n"
]
}
],
"source": [
"blah = r'''temp = NAND(a,b)\n",
"return NAND(b,c)\n",
"'''\n",
"\n",
"code = r'''\n",
"z = blah(x,y)\n",
"w = blah(z,x)\n",
"'''\n",
"\n",
"print(desugar(code,\"blah\",['a','b'],blah))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def parse_func(code):\n",
" \"\"\"Parse a function definition into name, arguments and body\"\"\"\n",
" lines = [l.strip() for l in code.split('\\n')]\n",
" regexp = r'def\\s+([a-zA-Z\\_0-9]+)\\(([\\sa-zA-Z0-9\\_,]+)\\)\\s*:\\s*'\n",
" m = re.match(regexp,lines[0])\n",
" return m.group(1), m.group(2).split(','), '\\n'.join(lines[1:])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Some examples"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"notfunc = parse_func('''def NOT(a): \n",
" return NAND(a,a)\n",
"''')\n",
"\n",
"andfunc = parse_func('''def AND(a,b):\n",
" temp = NAND(a,b) \n",
" return NOT(temp)\n",
"''')\n",
"\n",
"orfunc = parse_func('''def OR(a,b):\n",
" temp1 = NOT(a)\n",
" temp2 = NOT(b) \n",
" return NAND(temp1,temp2)\n",
"''')\n",
"\n",
"\n",
"majcode= '''and1 = AND(X[0],X[1])\n",
"and2 = AND(X[0],X[2])\n",
"and3 = AND(X[1],X[2])\n",
"or1 = OR(and1,and2)\n",
"Y[0] = OR(or1,and3)\n",
"'''"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"and1 = AND(X[0],X[1])\n",
"and2 = AND(X[0],X[2])\n",
"and3 = AND(X[1],X[2])\n",
"temp1 = NOT(and1)\n",
"temp2 = NOT(and2)\n",
"or1 = NAND(temp1,temp2)\n",
"temp1 = NOT(or1)\n",
"temp2 = NOT(and3)\n",
"Y[0] = NAND(temp1,temp2)\n",
"\n"
]
}
],
"source": [
"tmp = desugar(majcode,*orfunc)\n",
"print(tmp)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"temp = NAND(X[0],X[1])\n",
"and1 = NOT(temp)\n",
"temp = NAND(X[0],X[2])\n",
"and2 = NOT(temp)\n",
"temp = NAND(X[1],X[2])\n",
"and3 = NOT(temp)\n",
"temp1 = NOT(and1)\n",
"temp2 = NOT(and2)\n",
"or1 = NAND(temp1,temp2)\n",
"temp1 = NOT(or1)\n",
"temp2 = NOT(and3)\n",
"Y[0] = NAND(temp1,temp2)\n",
"\n"
]
}
],
"source": [
"tmp = desugar(tmp,*andfunc)\n",
"print(tmp)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"temp = NAND(X[0],X[1])\n",
"and1 = NAND(temp,temp)\n",
"temp = NAND(X[0],X[2])\n",
"and2 = NAND(temp,temp)\n",
"temp = NAND(X[1],X[2])\n",
"and3 = NAND(temp,temp)\n",
"temp1 = NAND(and1,and1)\n",
"temp2 = NAND(and2,and2)\n",
"or1 = NAND(temp1,temp2)\n",
"temp1 = NAND(or1,or1)\n",
"temp2 = NAND(and3,and3)\n",
"Y[0] = NAND(temp1,temp2)\n",
"\n"
]
}
],
"source": [
"tmp = desugar(tmp,*notfunc)\n",
"print(tmp)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"C = prog2circuit(tmp)\n",
"schemdraw(C)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"schemdraw(C,[0,1,1])"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"majsmaller = r'''temp = NAND(X[0],X[1])\n",
"temp2 = NAND(X[0],X[2])\n",
"temp3 = NAND(X[1],X[2])\n",
"or1 = NAND(temp,temp2)\n",
"temp1 = NAND(or1,or1)\n",
"Y[0] = NAND(temp1,temp3)\n",
"'''"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"C = prog2circuit(majsmaller)\n",
"schemdraw(C)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"schemdraw(C,[1,1,0])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## More sugar\n",
"\n",
"Removing function calls that are used as sub-expressions can be done as follows"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"def desugar2(code, func_name, func_args, func_body):\n",
" \"\"\"De-sugaring of functions calls that are used as expressions inside other calls.\n",
" We create a temporary variable to store the results of such expressions.\"\"\"\n",
" code = desugar(code,func_name,func_args,func_body)\n",
" arglist = \",\".join([r\"([a-zA-Z0-9\\_]+)\" for i in range(len(func_args))])\n",
" regexp = fr'[\\s=\\(\\,]{func_name}\\({arglist}\\)\\s*'\n",
" counter = 0\n",
" while True:\n",
" m = re.search(regexp,code)\n",
" if not m: break\n",
" \n",
" newcode = func_body\n",
" for i in range(len(func_args)):\n",
" newcode = newcode.replace(func_args[i],m.group(i+1))\n",
" newvar = f'temp_unique_{counter}'\n",
" counter += 1\n",
" newcode = newcode.replace('return', newvar + \" = \")\n",
" i = code.rfind('\\n',0,m.start())\n",
" code = code[:i+1]+ newcode + code[i+1:m.start()+1] + newvar + code[m.end():]\n",
" \n",
" return code"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('AND', ['a', 'b'], 'temp = NAND(a,b)\\nreturn NAND(temp,temp)\\n')"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"andfunc = r'''def AND(a,b):\n",
" temp = NAND(a,b)\n",
" return NAND(temp,temp)\n",
"'''\n",
"\n",
"parse_func(andfunc)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'temp = NAND(x,y)\\nblah = NAND(temp,temp)\\n'"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"code = r'''blah = AND(x,y)'''\n",
"desugar(code,*parse_func(andfunc))"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('NAND', ['a', 'b'], 'temp = NAND(a,b)\\nreturn temp')"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nandfunc = r'''def NAND(a,b):\n",
"temp = NAND(a,b)\n",
"return temp'''\n",
"\n",
"parse_func(nandfunc)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"temp = NAND(x,y)\n",
"temp_unique_0 = NAND(temp,temp)\n",
"temp = NAND(z,w)\n",
"temp_unique_1 = NAND(temp,temp)\n",
"temp = NAND(temp_unique_0,temp_unique_1)\n",
"temp_unique_2 = NAND(temp,temp)\n",
"blah = temp_unique_2\n"
]
}
],
"source": [
"print(desugar2('blah = AND(AND(x,y),AND(z,w))',*parse_func(andfunc)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Even more sugar\n",
"\n",
"We could implement all our syntactic sugar constructs as \"search and replace\" but it is easier for us to \"piggy back\" on top of Python and use it to \"de-sugar\" our programs.\n",
"\n",
"The idea is that we can use \"symbolic execution\" and redefine `NAND()` to simply print out the NAND-CIRC code instead computing the NAND operation. This is best illustrated by an example."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"counter = 0\n",
"def NAND(a,b):\n",
" global counter\n",
" counter += 1\n",
" v = f'temp_{counter}'\n",
" print(f'{v} = NAND({a},{b})')\n",
" return v"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"temp_1 = NAND(X[0],X[1])\n",
"temp_2 = NAND(temp_1,temp_1)\n",
"temp_3 = NAND(X[0],X[1])\n",
"temp_4 = NAND(temp_3,temp_3)\n",
"temp_5 = NAND(X[1],X[1])\n",
"temp_6 = NAND(temp_5,temp_5)\n",
"temp_7 = NAND(temp_2,temp_2)\n",
"temp_8 = NAND(temp_4,temp_4)\n",
"temp_9 = NAND(temp_7,temp_8)\n",
"temp_10 = NAND(temp_9,temp_9)\n",
"temp_11 = NAND(temp_6,temp_6)\n",
"temp_12 = NAND(temp_10,temp_11)\n"
]
},
{
"data": {
"text/plain": [
"'temp_12'"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def NOT(a): \n",
" return NAND(a,a)\n",
"def AND(a,b):\n",
" temp = NAND(a,b) \n",
" return NOT(temp)\n",
"def OR(a,b):\n",
" temp1 = NOT(a)\n",
" temp2 = NOT(b) \n",
" return NAND(temp1,temp2)\n",
"\n",
"def MAJ(a,b,c):\n",
" and1 = AND(a,b)\n",
" and2 = AND(a,c)\n",
" and3 = AND(b,c)\n",
" or1 = OR(and1,and2)\n",
" return OR(or1,and3)\n",
"\n",
"MAJ('X[0]','X[1]','X[1]')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that this is a NAND-CIRC program to compute MAJ - we just have to replace `temp_19` with `Y[0]`. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we redefine `NAND` to its usual value, then we can use the same code to compute $MAJ$:"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def NAND(a,b): return 1-a*b\n",
"\n",
"MAJ(1,0,1)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.0"
}
},
"nbformat": 4,
"nbformat_minor": 4
}