{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## The *NAND* Progamming language" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "To run this notebook, you will need to have installed Jupyter Notebook (which is part of the [Anaconda](https://www.anaconda.com/distribution/) distribution). For the graph visualization you will need:\n", "\n", "* [GraphViz](http://www.graphviz.org/) (and at least on Windows, make sure to have the executables on the path)\n", "\n", "* [Networkx](https://networkx.github.io/documentation/development/install.html), which you install via `conda install networkx` from the Anaconda prompt\n", "\n", "* [pydotplus](https://pypi.python.org/pypi/pydotplus), which you install with `conda install -c conda-forge pydotplus`" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In a NAND program, every line has the form:\n", "```\n", " foo := bar NAND baz\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "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)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "def EVAL(prog,x):\n", " n = max([int(var[2:]) for var in prog.split() if var[:2]=='x_' ])+1 # no of inputs\n", " m = max([int(var[2:]) for var in prog.split() if var[:2]=='y_' ])+1 # no of outputs\n", " \n", " varsval = { } # dictionary of value of \"workspace\" variables\n", " for i in range(n):\n", " varsval['x_'+str(i)] = int(x[i])\n", " for j in range(m):\n", " varsval['y_'+str(j)] = 0\n", " \n", " for line in prog.split('\\n'):\n", " if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines\n", " (var1,assign,var2,op,var3) = line.split()\n", " varsval[var1] = 1-varsval.get(var2,0)*varsval.get(var3,0)\n", " \n", " return ''.join( str(varsval['y_'+str(j)]) for j in range(m))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import operator\n", "\n", "def bold(s,justify=0):\n", " return \"\\x1b[1m\"+s.ljust(justify)+\"\\x1b[0m\"\n", "\n", "def red(s,justify=0):\n", " return \"\\x1b[31m\"+s.ljust(justify)+\"\\x1b[0m\"\n", "\n", "\n", "def green(s,justify=0):\n", " return \"\\x1b[32m\"+s.ljust(justify)+\"\\x1b[0m\"\n", "\n", "\n", "def blue(s,justify=0):\n", " return \"\\x1b[34m\"+s.ljust(justify)+\"\\x1b[0m\"\n", "\n", "def snapshots(prog,x,step=-1,cumulative=True):\n", " varnames = set()\n", " for line in prog.split('\\n'):\n", " if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines\n", " (var1,assign,var2,op,var3) = line.split()\n", " varnames.add(var1)\n", " varnames.add(var2)\n", " varnames.add(var3)\n", " \n", " n = max([int(var[2:]) for var in varnames if var[:2]=='x_' ])+1 # no of inputs\n", " m = max([int(var[2:]) for var in varnames if var[:2]=='y_' ])+1 # no of outputs\n", " t = len(varnames)\n", " \n", " def formatvarname(var,justify=0):\n", " if varsidx[var]t-m-1:\n", " return red(var,justify)\n", " return green(var,justify)\n", " \n", " def formatvarval(var,justify=0):\n", " s = str(varsval[var])\n", " if varsidx[var]t-m-1:\n", " return red(s,justify)\n", " return green(s,justify)\n", " \n", " varsidx = {}\n", " varsval = { } # dictionary of value of \"workspace\" variables\n", " \n", " for i in range(n):\n", " varsval['x_'+str(i)] = int(x[i])\n", " varsidx['x_'+str(i)] = i\n", " \n", " for j in range(m):\n", " varsval['y_'+str(j)] = 0\n", " varsidx['y_'+str(j)] = len(varnames)-m+j\n", " \n", " i = n\n", " for var in varnames:\n", " if var[:2]!='x_' and var[:2]!='y_':\n", " varsval[var]=0\n", " varsidx[var] = i\n", " i += 1\n", " \n", " sortednames = [s[0] for s in sorted(varsidx.items(), key=operator.itemgetter(1))]\n", " \n", " MAXLINELENGTH = 23\n", " MAXVARLENGTH = 5\n", " \n", " printout = \"\".ljust(MAXLINELENGTH)\n", " \n", " for var in sortednames:\n", " printout += formatvarname(var,MAXVARLENGTH) \n", "\n", " print(printout)\n", "\n", " printout = \"\".ljust(MAXLINELENGTH-2)\n", " for var in sortednames:\n", " printout += red(str(varsval[var]).ljust(MAXVARLENGTH))\n", " \n", " if (step==-1):\n", " step = len(prog.split('\\n'))\n", " j = 0\n", "\n", " for line in prog.split('\\n'):\n", " if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines\n", " if j>step:\n", " break\n", " (var1,assign,var2,op,var3) = line.split()\n", " varsval[var1] = 1-varsval.get(var2,0)*varsval.get(var3,0)\n", " \n", " printout = line.ljust(MAXLINELENGTH-2)+\": \"\n", " for var in sortednames:\n", " printout += formatvarval(var,MAXVARLENGTH)\n", " print(printout)\n", " \n", " return ''.join( str(varsval['y_'+str(j)]) for j in range(m))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "\n", "def represent(prog, verbose = True): \n", " MAXLINELENGTH = 23\n", " \n", " varnames = set()\n", " for line in prog.split('\\n'):\n", " if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines\n", " (var1,assign,var2,op,var3) = line.split()\n", " varnames.add(var1)\n", " varnames.add(var2)\n", " varnames.add(var3)\n", " \n", " n = max([int(var[2:]) for var in varnames if var[:2]=='x_' ])+1 # no of inputs\n", " m = max([int(var[2:]) for var in varnames if var[:2]=='y_' ])+1 # no of outputs\n", " t = len(varnames)\n", " \n", " def formatvar(i,justify=0):\n", " if it-m-1:\n", " return red(str(i),justify)\n", " return green(str(i),justify)\n", " \n", " \n", " \n", " varsidx = {}\n", " varsval = { } # dictionary of value of \"workspace\" variables\n", " \n", " for i in range(n):\n", " varsval['x_'+str(i)] = 0\n", " varsidx['x_'+str(i)] = i\n", " \n", " for j in range(m):\n", " varsval['y_'+str(j)] = 0\n", " varsidx['y_'+str(j)] = len(varnames)-m+j\n", " \n", " i = n\n", " for var in varnames:\n", " if var[:2]!='x_' and var[:2]!='y_':\n", " varsval[var]=0\n", " varsidx[var] = i\n", " i += 1\n", " \n", " sortednames = [s[0] for s in sorted(varsidx.items(), key=operator.itemgetter(1))]\n", " \n", " \n", " printout = bold(\"Variables: \")\n", " \n", " i=0\n", " \n", " for var in sortednames:\n", " printout += var + \"->\"+formatvar(i)+\" \" \n", " i += 1\n", "\n", " if (verbose): \n", " print(printout)\n", " \n", " printout = bold(\"Triples: \\n\")\n", "\n", " \n", " result = []\n", " \n", " for line in prog.split('\\n'):\n", " if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines\n", " (var1,assign,var2,op,var3) = line.split()\n", " a = varsidx[var1]\n", " b = varsidx[var2]\n", " c = varsidx[var3] \n", " result.append([a,b,c])\n", " printout += line.ljust(MAXLINELENGTH)+\" -> (\"+formatvar(a)+\",\"+formatvar(b)+\",\"+formatvar(c)+\") \\n\"\n", " \n", " if (verbose):\n", " print(printout)\n", " \n", " return result" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## An example NAND program " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The following program computes on input $x_0,x_1$ the XOR of $x_0$ and $x_1$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "i.e., outputs `1` on input `10` or `01` and output `0` on input `00` or `11`:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "xor = r'''\n", "u := x_0 NAND x_1\n", "v := x_0 NAND u\n", "w := x_1 NAND u\n", "y_0 := v NAND w\n", "''' " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "EVAL(xor,\"10\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Snapshots" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can print _snapshots_ of the values of the variables as we execute the program line by line:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "snapshots(xor,\"10\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "addtwo = '''\n", "u := x_0 NAND x_2\n", "v := x_0 NAND u\n", "w := x_2 NAND u\n", "y_0 := v NAND w\n", "c_1 := u NAND u\n", "u := x_1 NAND x_3\n", "v := x_1 NAND u\n", "w := x_3 NAND u\n", "z_1 := v NAND w\n", "z'_1 := u NAND u\n", "u := z_1 NAND c_1\n", "v := z_1 NAND u\n", "w := c_1 NAND u\n", "y_1 := v NAND w\n", "u := z'_1 NAND z'_1\n", "v := z_1 NAND c_1\n", "y_2 := u NAND v\n", "'''\n", "\n", "snapshots(addtwo,\"1011\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Representation" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "represent(xor);\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "atleasttwo = '''\n", "v_0 := x_0 NAND x_1 \n", "v_1 := x_0 NAND x_2 \n", "v_2 := x_1 NAND x_2 \n", "v_3 := v_2 NAND v_1\n", "notv_3 := v_3 NAND v_3 \n", "y_0 := notv_3 NAND v_0 \n", "''';" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "represent(atleasttwo);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph representation" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import networkx as nx" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import matplotlib\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "from IPython.display import Image" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import warnings\n", "warnings.filterwarnings(\"ignore\")\n", "\n", "# import matplotlib.cbook\n", "# warnings.filterwarnings(\"ignore\",category=matplotlib.cbook.mplDeprecation)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "def NAND2Graph(P):\n", " n = max([int(var[2:]) for var in P.split() if var[:2]=='x_' ])+1 # no of inputs\n", " m = max([int(var[2:]) for var in P.split() if var[:2]=='y_' ])+1 # no of outputs\n", " nodes = {}\n", " def uniquenode(v):\n", " idx = nodes.setdefault(v,-1)\n", " nodes[v] = nodes[v]+1\n", " return v+(\" \"*(idx+1))\n", " \n", " G = nx.DiGraph()\n", " for line in P.split('\\n'):\n", " if not line or line[0]=='#' or line[0]=='//': continue # ignore empty and commented out lines\n", " (var1,assign,var2,op,var3) = line.split()\n", " var1 = uniquenode(var1)\n", " G.add_node(var1)\n", " G.add_edge(var2,var1)\n", " G.add_edge(var3,var1)\n", " \n", " return G\n", " \n", " " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Programs as graphs" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can represent every program also as a _graph_:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "prog = r'''\n", "u := x_0 NAND x_1\n", "v := x_0 NAND u\n", "w := x_1 NAND x_0\n", "y_0 := v NAND w\n", "'''" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "G= NAND2Graph(prog)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "def draw_DAG(G):\n", " D = nx.drawing.nx_pydot.to_pydot(G)\n", " png_str = D.create_png()\n", " return Image(data=png_str)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "draw_DAG(G)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "EVAL(prog,\"11\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import math\n", "\n", "def index(k):\n", " r = math.floor(math.sqrt(k+1/4)-1/2)\n", " return (k-r*(r+1) if k <= (r+1)*(r+1) else (r+1)*(r+2)-k)\n", "\n", "def expand(nandpp,t,n):\n", " result = \"\"\n", " \n", " for k in range(t):\n", " i=index(k)\n", " validx = ('one' if i