appendix_NAND_specs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NAND* programming languages specification\n",
    "\n",
    "_Version: 0.5_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The NAND-CIRC, NAND-TM, and NAND-RAM programming languages were designed to accompany the upcoming book [\"Introduction to Theoretical Computer Science\"](http://introtcs.org). This is an appendix to this book, which is also available online as a Jupyter notebook in the  [boazbk/tcscode](https://github.com/boazbk/tcscode) on Github. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The book is not a programming book, and readers can follow along without ever looking at the specifications of these programming languages. Still, for the sake of completeness, we provide these here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the following main models of computation in this book:\n",
    "\n",
    "####  <font color='blue'>Computing __finite__ functions with __nonuniform__ algorithms:</font>\n",
    "\n",
    "__Boolean Circuits__ and __NAND-CIRC__ straightline programs. We also use other variants that correspond to different gate sets.  These models are presented in [Chapter 3: Defining Computatoin](https://introtcs.org/public/lec_03_computation.html).\n",
    "\n",
    "#### <font color='blue'>Computing __unbounded input length__ functions with __uniform__ algorithms:</font>\n",
    "\n",
    "We have two main models, depending on the memory access. __Turing Machines__ have __sequential access__ to memory, and the programming language equivalent is __NAND-TM__. They are defined in [Chapter 6: Loops and infinity](https://introtcs.org/public/lec_06_loops.html). __RAM Machines__ have __random access__ (aka __indexed access__ or __indirect addressing__) to memory, and their programming language equivalent is __NAND-RAM__. They are defined in [Chapter 7: Equivalent models of computation](https://introtcs.org/public/lec_07_other_models.html). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The NAND-CIRC Programming Language"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A NAND-CIRC program is a sequence of lines. Every line in NAND-CIRC has the form \n",
    "\n",
    "`<varid> = NAND(<varid>,<varid>)`\n",
    "\n",
    "where `varid` (standing for _variable identifier_) is a sequence of letters, numbers,  underscores, and brackets (`[`,`]`). Only variables of the form `X[<num>]` and `Y[<num>]` can contain brackets. Moreover, all other variables identifiers must begin with a lowercase letter. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Variables of the form `X[<num>]` for a number `<num>` are _input variables_, and variables of the form `Y[<num>]` are _output variables_. \n",
    "\n",
    "For every valid NAND-CIRC program $P$, there must be some integers $n,m>0$ such that the input and output variables are  `X[0]` ... `X[`$n-1$`]` for some $n>0$ and `Y[0]` ... `Y[`$m-1$`]` for some $m>0$ and all of those appear in the program. (For example, if a program contains the variable `X[3]` then it must also contain `X[2]`,`X[1]`  and `X[0]`.\n",
    "\n",
    "An input variable can not appear on the lefthand side of the assignment operation `foo = NAND(bar,blah)`, and an output variable cannot appear on the righthand side of it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Evaluating a NAND-CIRC program:__ If $P$ is a NAND-CIRC program with $n$ inputs and $m$ outputs, and $x\\in \\{0,1\\}^n$, then the _output of $P$ on input $x$_, denoted by $P(x)$, is defined as the string $y\\in \\{0,1\\}^m$ which is the result of the following process:\n",
    "\n",
    "1. We initialize the variables `X[0]` ... `X[`$n-1$`]` to $x_0,\\ldots,x_{n-1}$ and all other variables to $0$.\n",
    "\n",
    "2. We run the program line by line, where a line of the form `foo = NAND(bar,blah)` is evaluated by assigning to the variable `foo` the NAND of the values of the variables `bar` and `blah`\n",
    "\n",
    "3. At the end of the execution, output the values of the variables `Y[0]` ... `Y[`$m-1$`]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Python implementation of NAND-CIRC evaluation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parseline(line, numargs = 0):\n",
    "    \"\"\"Parse a line of the form foo = 'OP( bar1, bar2, bar3)'\n",
    "       to ['foo','OP','bar1','bar2','bar2'].\n",
    "       If numargs > number of arguments in line then add empty strings to the list as needed.\"\"\"\n",
    "    i = line.find(\"=\")\n",
    "    j = line.find(\"(\")\n",
    "    k = line.find(\")\")\n",
    "    if i<0 or j<0 or k<0: raise Exception(f\"Line not formatted properly: {line}\")\n",
    "    args = [a.strip() for a in line[j+1:k].split(\",\")]\n",
    "    if len(args)<numargs: args += [\"\"]*(numargs-len(args))\n",
    "    return [line[:i].strip() , line[i+1:j].strip()] + args\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "def numinout(prog):\n",
    "    '''Compute the number of inputs and outputs of a NAND program, given as a string of source code.'''\n",
    "    n = max([int(s[2:-1]) for s in re.findall(r'X\\[\\d+\\]',prog)])+1\n",
    "    m = max([int(s[2:-1]) for s in re.findall(r'Y\\[\\d+\\]',prog)])+1\n",
    "    return n,m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def EVAL(code,X):\n",
    "    \"\"\"Evaluate code on input X.\"\"\"\n",
    "    n,m = numinout(code) # helper function - get number of inputs and outputs\n",
    "    vtable = { f\"X[{i}]\":int(X[i]) for i in range(n)}\n",
    "    for line in code.split(\"\\n\"):\n",
    "        if not line: continue\n",
    "        foo,op,bar,blah = parseline(line) \n",
    "        vtable[foo] =  1-vtable[bar]*vtable[blah]\n",
    "    \n",
    "    return [vtable[f\"Y[{j}]\"] for j in range(m)]            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "code = r'''temp_1 = NAND(X[0],X[1])\n",
    "temp_2 = NAND(X[0],temp_1)\n",
    "temp_3 = NAND(X[1],temp_1)\n",
    "temp_4 = NAND(temp_2,temp_3)\n",
    "temp_5 = NAND(temp_4,X[2])\n",
    "temp_6 = NAND(temp_4,temp_5)\n",
    "temp_7 = NAND(X[2],temp_5)\n",
    "Y[0] = NAND(temp_6,temp_7)\n",
    "'''\n",
    "EVAL(code,\"011\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NAND-CIRC and Boolean Circuits "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NAND-CIRC is of course equivalent to Boolean circuits"
   ]
  },
  {
   "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": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       "  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Created with matplotlib (https://matplotlib.org/) -->\r\n",
       "<svg height=\"215.877449pt\" version=\"1.1\" viewBox=\"0 0 458.193425 215.877449\" width=\"458.193425pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       " <defs>\r\n",
       "  <style type=\"text/css\">\r\n",
       "*{stroke-linecap:butt;stroke-linejoin:round;}\r\n",
       "  </style>\r\n",
       " </defs>\r\n",
       " <g id=\"figure_1\">\r\n",
       "  <g id=\"patch_1\">\r\n",
       "   <path d=\"M 0 215.877449 \r\n",
       "L 458.193425 215.877449 \r\n",
       "L 458.193425 0 \r\n",
       "L 0 0 \r\n",
       "z\r\n",
       "\" style=\"fill:none;\"/>\r\n",
       "  </g>\r\n",
       "  <g id=\"axes_1\">\r\n",
       "   <g id=\"patch_2\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 117.786669 74.326397 \r\n",
       "C 121.946698 74.326397 125.940597 72.901837 128.882181 70.368806 \r\n",
       "C 131.823765 67.835775 133.478093 64.396584 133.478093 60.814337 \r\n",
       "C 133.478093 57.232091 131.823765 53.792899 128.882181 51.259869 \r\n",
       "C 125.940597 48.726838 121.946698 47.302278 117.786669 47.302278 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_3\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 171.134999 60.252236 \r\n",
       "C 175.295027 60.252236 179.288927 58.827676 182.230511 56.294645 \r\n",
       "C 185.172095 53.761614 186.826422 50.322423 186.826422 46.740177 \r\n",
       "C 186.826422 43.15793 185.172095 39.718739 182.230511 37.185708 \r\n",
       "C 179.288927 34.652677 175.295027 33.228117 171.134999 33.228117 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_4\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 171.134999 119.929596 \r\n",
       "C 175.295027 119.929596 179.288927 118.505036 182.230511 115.972006 \r\n",
       "C 185.172095 113.438975 186.826422 109.999783 186.826422 106.417537 \r\n",
       "C 186.826422 102.83529 185.172095 99.396099 182.230511 96.863068 \r\n",
       "C 179.288927 94.330038 175.295027 92.905478 171.134999 92.905478 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_5\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 225.01056 118.806744 \r\n",
       "C 229.170588 118.806744 233.164488 117.382184 236.106072 114.849154 \r\n",
       "C 239.047656 112.316123 240.701983 108.876931 240.701983 105.294685 \r\n",
       "C 240.701983 101.712438 239.047656 98.273247 236.106072 95.740216 \r\n",
       "C 233.164488 93.207185 229.170588 91.782626 225.01056 91.782626 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_6\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 278.882355 167.223154 \r\n",
       "C 283.042383 167.223154 287.036283 165.798595 289.977867 163.265564 \r\n",
       "C 292.919451 160.732533 294.573779 157.293342 294.573779 153.711095 \r\n",
       "C 294.573779 150.128849 292.919451 146.689657 289.977867 144.156627 \r\n",
       "C 287.036283 141.623596 283.042383 140.199036 278.882355 140.199036 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_7\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 332.757916 137.384474 \r\n",
       "C 336.917945 137.384474 340.911844 135.959914 343.853428 133.426884 \r\n",
       "C 346.795012 130.893853 348.44934 127.454661 348.44934 123.872415 \r\n",
       "C 348.44934 120.290168 346.795012 116.850977 343.853428 114.317946 \r\n",
       "C 340.911844 111.784916 336.917945 110.360356 332.757916 110.360356 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_8\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 332.757916 197.062645 \r\n",
       "C 336.917945 197.062645 340.911844 195.638086 343.853428 193.105055 \r\n",
       "C 346.795012 190.572024 348.44934 187.132833 348.44934 183.550586 \r\n",
       "C 348.44934 179.96834 346.795012 176.529148 343.853428 173.996118 \r\n",
       "C 340.911844 171.463087 336.917945 170.038527 332.757916 170.038527 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_9\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 400.232293 167.223154 \r\n",
       "C 404.392321 167.223154 408.386221 165.798595 411.327805 163.265564 \r\n",
       "C 414.269389 160.732533 415.923716 157.293342 415.923716 153.711095 \r\n",
       "C 415.923716 150.128849 414.269389 146.689657 411.327805 144.156627 \r\n",
       "C 408.386221 141.623596 404.392321 140.199036 400.232293 140.199036 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_1\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 20.841613 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_2\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 101.913968 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_3\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 178.483564 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_4\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 86.403822 60.814337 \r\n",
       "M 141.009976 60.814337 \r\n",
       "L 144.462089 60.814337 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_5\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 97.387819 60.814337 \r\n",
       "L 97.387819 74.326397 \r\n",
       "L 117.786669 74.326397 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_6\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 97.387819 60.814337 \r\n",
       "L 97.387819 47.302278 \r\n",
       "L 117.786669 47.302278 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_7\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 86.403822 67.570367 \r\n",
       "L 97.387819 67.570367 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_8\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 86.403822 54.058308 \r\n",
       "L 97.387819 54.058308 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_9\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 20.841613 \r\n",
       "L 59.46623 37.44996 \r\n",
       "L 86.403822 54.058308 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_10\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 101.913968 \r\n",
       "L 59.46623 84.742167 \r\n",
       "L 86.403822 67.570367 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_11\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 139.752152 46.740177 \r\n",
       "M 194.358306 46.740177 \r\n",
       "L 197.810419 46.740177 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_12\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 150.736148 46.740177 \r\n",
       "L 150.736148 60.252236 \r\n",
       "L 171.134999 60.252236 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_13\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 150.736148 46.740177 \r\n",
       "L 150.736148 33.228117 \r\n",
       "L 171.134999 33.228117 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_14\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 139.752152 53.496206 \r\n",
       "L 150.736148 53.496206 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_15\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 139.752152 39.984147 \r\n",
       "L 150.736148 39.984147 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_16\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 20.841613 \r\n",
       "L 86.140395 30.41288 \r\n",
       "L 139.752152 39.984147 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_17\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 144.462089 60.814337 \r\n",
       "L 142.10712 57.155272 \r\n",
       "L 139.752152 53.496206 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_18\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 139.752152 106.417537 \r\n",
       "M 194.358306 106.417537 \r\n",
       "L 197.810419 106.417537 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_19\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 150.736148 106.417537 \r\n",
       "L 150.736148 119.929596 \r\n",
       "L 171.134999 119.929596 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_20\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 150.736148 106.417537 \r\n",
       "L 150.736148 92.905478 \r\n",
       "L 171.134999 92.905478 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_21\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 139.752152 113.173567 \r\n",
       "L 150.736148 113.173567 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_22\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 139.752152 99.661507 \r\n",
       "L 150.736148 99.661507 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_23\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 144.462089 60.814337 \r\n",
       "L 142.10712 80.237922 \r\n",
       "L 139.752152 99.661507 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_24\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 101.913968 \r\n",
       "L 86.140395 107.543767 \r\n",
       "L 139.752152 113.173567 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_25\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 193.627713 105.294685 \r\n",
       "M 248.233867 105.294685 \r\n",
       "L 251.68598 105.294685 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_26\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 204.611709 105.294685 \r\n",
       "L 204.611709 118.806744 \r\n",
       "L 225.01056 118.806744 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_27\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 204.611709 105.294685 \r\n",
       "L 204.611709 91.782626 \r\n",
       "L 225.01056 91.782626 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_28\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 193.627713 112.050714 \r\n",
       "L 204.611709 112.050714 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_29\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 193.627713 98.538655 \r\n",
       "L 204.611709 98.538655 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_30\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 197.810419 46.740177 \r\n",
       "L 195.719066 72.639416 \r\n",
       "L 193.627713 98.538655 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_31\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 197.810419 106.417537 \r\n",
       "L 195.719066 109.234126 \r\n",
       "L 193.627713 112.050714 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_32\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 247.499508 153.711095 \r\n",
       "M 302.105662 153.711095 \r\n",
       "L 305.557775 153.711095 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_33\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 258.483505 153.711095 \r\n",
       "L 258.483505 167.223154 \r\n",
       "L 278.882355 167.223154 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_34\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 258.483505 153.711095 \r\n",
       "L 258.483505 140.199036 \r\n",
       "L 278.882355 140.199036 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_35\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 247.499508 160.467125 \r\n",
       "L 258.483505 160.467125 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_36\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 247.499508 146.955066 \r\n",
       "L 258.483505 146.955066 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_37\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 251.68598 105.294685 \r\n",
       "L 249.592744 126.124875 \r\n",
       "L 247.499508 146.955066 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_38\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 178.483564 \r\n",
       "L 140.014073 169.475344 \r\n",
       "L 247.499508 160.467125 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_39\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 301.375069 123.872415 \r\n",
       "M 355.981223 123.872415 \r\n",
       "L 359.433336 123.872415 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_40\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 312.359066 123.872415 \r\n",
       "L 312.359066 137.384474 \r\n",
       "L 332.757916 137.384474 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_41\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 312.359066 123.872415 \r\n",
       "L 312.359066 110.360356 \r\n",
       "L 332.757916 110.360356 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_42\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 301.375069 130.628445 \r\n",
       "L 312.359066 130.628445 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_43\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 301.375069 117.116385 \r\n",
       "L 312.359066 117.116385 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_44\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 251.68598 105.294685 \r\n",
       "L 276.530525 111.205535 \r\n",
       "L 301.375069 117.116385 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_45\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 305.557775 153.711095 \r\n",
       "L 303.466422 142.16977 \r\n",
       "L 301.375069 130.628445 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_46\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 301.375069 183.550586 \r\n",
       "M 355.981223 183.550586 \r\n",
       "L 359.433336 183.550586 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_47\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 312.359066 183.550586 \r\n",
       "L 312.359066 197.062645 \r\n",
       "L 332.757916 197.062645 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_48\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 312.359066 183.550586 \r\n",
       "L 312.359066 170.038527 \r\n",
       "L 332.757916 170.038527 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_49\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 301.375069 190.306616 \r\n",
       "L 312.359066 190.306616 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_50\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 301.375069 176.794557 \r\n",
       "L 312.359066 176.794557 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_51\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 305.557775 153.711095 \r\n",
       "L 303.466422 165.252826 \r\n",
       "L 301.375069 176.794557 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_52\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 178.483564 \r\n",
       "L 166.951853 184.39509 \r\n",
       "L 301.375069 190.306616 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_53\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 368.849446 153.711095 \r\n",
       "M 423.4556 153.711095 \r\n",
       "L 426.907713 153.711095 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_54\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 379.833442 153.711095 \r\n",
       "L 379.833442 167.223154 \r\n",
       "L 400.232293 167.223154 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_55\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 379.833442 153.711095 \r\n",
       "L 379.833442 140.199036 \r\n",
       "L 400.232293 140.199036 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_56\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 368.849446 160.467125 \r\n",
       "L 379.833442 160.467125 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_57\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 368.849446 146.955066 \r\n",
       "L 379.833442 146.955066 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_58\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 359.433336 123.872415 \r\n",
       "L 364.141391 135.41374 \r\n",
       "L 368.849446 146.955066 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"line2d_59\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 359.433336 183.550586 \r\n",
       "L 364.141391 172.008855 \r\n",
       "L 368.849446 160.467125 \r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:round;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_10\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 22.868422 \r\n",
       "C 33.15285 22.868422 33.75158 22.654864 34.192964 22.274783 \r\n",
       "C 34.634349 21.894702 34.882351 21.379129 34.882351 20.841613 \r\n",
       "C 34.882351 20.304097 34.634349 19.788524 34.192964 19.408442 \r\n",
       "C 33.75158 19.028361 33.15285 18.814804 32.528638 18.814804 \r\n",
       "C 31.904426 18.814804 31.305695 19.028361 30.864311 19.408442 \r\n",
       "C 30.422926 19.788524 30.174924 20.304097 30.174924 20.841613 \r\n",
       "C 30.174924 21.379129 30.422926 21.894702 30.864311 22.274783 \r\n",
       "C 31.305695 22.654864 31.904426 22.868422 32.528638 22.868422 \r\n",
       "z\r\n",
       "\" style=\"stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_11\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 103.940777 \r\n",
       "C 33.15285 103.940777 33.75158 103.727219 34.192964 103.347138 \r\n",
       "C 34.634349 102.967057 34.882351 102.451484 34.882351 101.913968 \r\n",
       "C 34.882351 101.376452 34.634349 100.860879 34.192964 100.480797 \r\n",
       "C 33.75158 100.100716 33.15285 99.887159 32.528638 99.887159 \r\n",
       "C 31.904426 99.887159 31.305695 100.100716 30.864311 100.480797 \r\n",
       "C 30.422926 100.860879 30.174924 101.376452 30.174924 101.913968 \r\n",
       "C 30.174924 102.451484 30.422926 102.967057 30.864311 103.347138 \r\n",
       "C 31.305695 103.727219 31.904426 103.940777 32.528638 103.940777 \r\n",
       "z\r\n",
       "\" style=\"stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_12\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 32.528638 180.510373 \r\n",
       "C 33.15285 180.510373 33.75158 180.296815 34.192964 179.916734 \r\n",
       "C 34.634349 179.536653 34.882351 179.02108 34.882351 178.483564 \r\n",
       "C 34.882351 177.946048 34.634349 177.430475 34.192964 177.050394 \r\n",
       "C 33.75158 176.670312 33.15285 176.456755 32.528638 176.456755 \r\n",
       "C 31.904426 176.456755 31.305695 176.670312 30.864311 177.050394 \r\n",
       "C 30.422926 177.430475 30.174924 177.946048 30.174924 178.483564 \r\n",
       "C 30.174924 179.02108 30.422926 179.536653 30.864311 179.916734 \r\n",
       "C 31.305695 180.296815 31.904426 180.510373 32.528638 180.510373 \r\n",
       "z\r\n",
       "\" style=\"stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_13\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 137.244035 64.057232 \r\n",
       "C 138.242774 64.057232 139.200742 63.71554 139.906957 63.10741 \r\n",
       "C 140.613173 62.49928 141.009976 61.674363 141.009976 60.814337 \r\n",
       "C 141.009976 59.954312 140.613173 59.129395 139.906957 58.521265 \r\n",
       "C 139.200742 57.913135 138.242774 57.571443 137.244035 57.571443 \r\n",
       "C 136.245295 57.571443 135.287327 57.913135 134.581112 58.521265 \r\n",
       "C 133.874896 59.129395 133.478093 59.954312 133.478093 60.814337 \r\n",
       "C 133.478093 61.674363 133.874896 62.49928 134.581112 63.10741 \r\n",
       "C 135.287327 63.71554 136.245295 64.057232 137.244035 64.057232 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_14\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 190.592364 49.983071 \r\n",
       "C 191.591103 49.983071 192.549071 49.641379 193.255287 49.033249 \r\n",
       "C 193.961502 48.425119 194.358306 47.600202 194.358306 46.740177 \r\n",
       "C 194.358306 45.880151 193.961502 45.055234 193.255287 44.447104 \r\n",
       "C 192.549071 43.838974 191.591103 43.497282 190.592364 43.497282 \r\n",
       "C 189.593624 43.497282 188.635656 43.838974 187.929441 44.447104 \r\n",
       "C 187.223226 45.055234 186.826422 45.880151 186.826422 46.740177 \r\n",
       "C 186.826422 47.600202 187.223226 48.425119 187.929441 49.033249 \r\n",
       "C 188.635656 49.641379 189.593624 49.983071 190.592364 49.983071 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_15\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 190.592364 109.660431 \r\n",
       "C 191.591103 109.660431 192.549071 109.318739 193.255287 108.710609 \r\n",
       "C 193.961502 108.10248 194.358306 107.277563 194.358306 106.417537 \r\n",
       "C 194.358306 105.557511 193.961502 104.732594 193.255287 104.124465 \r\n",
       "C 192.549071 103.516335 191.591103 103.174643 190.592364 103.174643 \r\n",
       "C 189.593624 103.174643 188.635656 103.516335 187.929441 104.124465 \r\n",
       "C 187.223226 104.732594 186.826422 105.557511 186.826422 106.417537 \r\n",
       "C 186.826422 107.277563 187.223226 108.10248 187.929441 108.710609 \r\n",
       "C 188.635656 109.318739 189.593624 109.660431 190.592364 109.660431 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_16\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 244.467925 108.537579 \r\n",
       "C 245.466664 108.537579 246.424633 108.195887 247.130848 107.587757 \r\n",
       "C 247.837063 106.979627 248.233867 106.15471 248.233867 105.294685 \r\n",
       "C 248.233867 104.434659 247.837063 103.609742 247.130848 103.001612 \r\n",
       "C 246.424633 102.393482 245.466664 102.051791 244.467925 102.051791 \r\n",
       "C 243.469186 102.051791 242.511218 102.393482 241.805002 103.001612 \r\n",
       "C 241.098787 103.609742 240.701983 104.434659 240.701983 105.294685 \r\n",
       "C 240.701983 106.15471 241.098787 106.979627 241.805002 107.587757 \r\n",
       "C 242.511218 108.195887 243.469186 108.537579 244.467925 108.537579 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_17\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 298.33972 156.953989 \r\n",
       "C 299.33846 156.953989 300.296428 156.612298 301.002643 156.004168 \r\n",
       "C 301.708859 155.396038 302.105662 154.571121 302.105662 153.711095 \r\n",
       "C 302.105662 152.85107 301.708859 152.026153 301.002643 151.418023 \r\n",
       "C 300.296428 150.809893 299.33846 150.468201 298.33972 150.468201 \r\n",
       "C 297.340981 150.468201 296.383013 150.809893 295.676797 151.418023 \r\n",
       "C 294.970582 152.026153 294.573779 152.85107 294.573779 153.711095 \r\n",
       "C 294.573779 154.571121 294.970582 155.396038 295.676797 156.004168 \r\n",
       "C 296.383013 156.612298 297.340981 156.953989 298.33972 156.953989 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_18\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 352.215282 127.115309 \r\n",
       "C 353.214021 127.115309 354.171989 126.773617 354.878204 126.165487 \r\n",
       "C 355.58442 125.557358 355.981223 124.732441 355.981223 123.872415 \r\n",
       "C 355.981223 123.012389 355.58442 122.187472 354.878204 121.579343 \r\n",
       "C 354.171989 120.971213 353.214021 120.629521 352.215282 120.629521 \r\n",
       "C 351.216542 120.629521 350.258574 120.971213 349.552359 121.579343 \r\n",
       "C 348.846143 122.187472 348.44934 123.012389 348.44934 123.872415 \r\n",
       "C 348.44934 124.732441 348.846143 125.557358 349.552359 126.165487 \r\n",
       "C 350.258574 126.773617 351.216542 127.115309 352.215282 127.115309 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_19\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 352.215282 186.79348 \r\n",
       "C 353.214021 186.79348 354.171989 186.451789 354.878204 185.843659 \r\n",
       "C 355.58442 185.235529 355.981223 184.410612 355.981223 183.550586 \r\n",
       "C 355.981223 182.690561 355.58442 181.865644 354.878204 181.257514 \r\n",
       "C 354.171989 180.649384 353.214021 180.307692 352.215282 180.307692 \r\n",
       "C 351.216542 180.307692 350.258574 180.649384 349.552359 181.257514 \r\n",
       "C 348.846143 181.865644 348.44934 182.690561 348.44934 183.550586 \r\n",
       "C 348.44934 184.410612 348.846143 185.235529 349.552359 185.843659 \r\n",
       "C 350.258574 186.451789 351.216542 186.79348 352.215282 186.79348 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"patch_20\">\r\n",
       "    <path clip-path=\"url(#p9ab4529a5d)\" d=\"M 419.689658 156.953989 \r\n",
       "C 420.688397 156.953989 421.646365 156.612298 422.352581 156.004168 \r\n",
       "C 423.058796 155.396038 423.4556 154.571121 423.4556 153.711095 \r\n",
       "C 423.4556 152.85107 423.058796 152.026153 422.352581 151.418023 \r\n",
       "C 421.646365 150.809893 420.688397 150.468201 419.689658 150.468201 \r\n",
       "C 418.690919 150.468201 417.732951 150.809893 417.026735 151.418023 \r\n",
       "C 416.32052 152.026153 415.923716 152.85107 415.923716 153.711095 \r\n",
       "C 415.923716 154.571121 416.32052 155.396038 417.026735 156.004168 \r\n",
       "C 417.732951 156.612298 418.690919 156.953989 419.689658 156.953989 \r\n",
       "z\r\n",
       "\" style=\"fill:none;stroke:#000000;stroke-linejoin:miter;stroke-width:1.5;\"/>\r\n",
       "   </g>\r\n",
       "   <g id=\"text_1\">\r\n",
       "    <!-- $X[0]$ -->\r\n",
       "    <defs>\r\n",
       "     <path d=\"M 6.296875 72.90625 \r\n",
       "L 16.890625 72.90625 \r\n",
       "L 35.015625 45.796875 \r\n",
       "L 53.21875 72.90625 \r\n",
       "L 63.8125 72.90625 \r\n",
       "L 40.375 37.890625 \r\n",
       "L 65.375 0 \r\n",
       "L 54.78125 0 \r\n",
       "L 34.28125 31 \r\n",
       "L 13.625 0 \r\n",
       "L 2.984375 0 \r\n",
       "L 29 38.921875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-88\"/>\r\n",
       "     <path d=\"M 8.59375 75.984375 \r\n",
       "L 29.296875 75.984375 \r\n",
       "L 29.296875 69 \r\n",
       "L 17.578125 69 \r\n",
       "L 17.578125 -6.203125 \r\n",
       "L 29.296875 -6.203125 \r\n",
       "L 29.296875 -13.1875 \r\n",
       "L 8.59375 -13.1875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-91\"/>\r\n",
       "     <path d=\"M 31.78125 66.40625 \r\n",
       "Q 24.171875 66.40625 20.328125 58.90625 \r\n",
       "Q 16.5 51.421875 16.5 36.375 \r\n",
       "Q 16.5 21.390625 20.328125 13.890625 \r\n",
       "Q 24.171875 6.390625 31.78125 6.390625 \r\n",
       "Q 39.453125 6.390625 43.28125 13.890625 \r\n",
       "Q 47.125 21.390625 47.125 36.375 \r\n",
       "Q 47.125 51.421875 43.28125 58.90625 \r\n",
       "Q 39.453125 66.40625 31.78125 66.40625 \r\n",
       "z\r\n",
       "M 31.78125 74.21875 \r\n",
       "Q 44.046875 74.21875 50.515625 64.515625 \r\n",
       "Q 56.984375 54.828125 56.984375 36.375 \r\n",
       "Q 56.984375 17.96875 50.515625 8.265625 \r\n",
       "Q 44.046875 -1.421875 31.78125 -1.421875 \r\n",
       "Q 19.53125 -1.421875 13.0625 8.265625 \r\n",
       "Q 6.59375 17.96875 6.59375 36.375 \r\n",
       "Q 6.59375 54.828125 13.0625 64.515625 \r\n",
       "Q 19.53125 74.21875 31.78125 74.21875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-48\"/>\r\n",
       "     <path d=\"M 30.421875 75.984375 \r\n",
       "L 30.421875 -13.1875 \r\n",
       "L 9.71875 -13.1875 \r\n",
       "L 9.71875 -6.203125 \r\n",
       "L 21.390625 -6.203125 \r\n",
       "L 21.390625 69 \r\n",
       "L 9.71875 69 \r\n",
       "L 9.71875 75.984375 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-93\"/>\r\n",
       "    </defs>\r\n",
       "    <g transform=\"translate(24.088638 14.448642)scale(0.08 -0.08)\">\r\n",
       "     <use transform=\"translate(0 0.015625)\" xlink:href=\"#DejaVuSans-88\"/>\r\n",
       "     <use transform=\"translate(68.505859 0.015625)\" xlink:href=\"#DejaVuSans-91\"/>\r\n",
       "     <use transform=\"translate(107.519531 0.015625)\" xlink:href=\"#DejaVuSans-48\"/>\r\n",
       "     <use transform=\"translate(171.142578 0.015625)\" xlink:href=\"#DejaVuSans-93\"/>\r\n",
       "    </g>\r\n",
       "   </g>\r\n",
       "   <g id=\"text_2\">\r\n",
       "    <!-- $X[1]$ -->\r\n",
       "    <defs>\r\n",
       "     <path d=\"M 12.40625 8.296875 \r\n",
       "L 28.515625 8.296875 \r\n",
       "L 28.515625 63.921875 \r\n",
       "L 10.984375 60.40625 \r\n",
       "L 10.984375 69.390625 \r\n",
       "L 28.421875 72.90625 \r\n",
       "L 38.28125 72.90625 \r\n",
       "L 38.28125 8.296875 \r\n",
       "L 54.390625 8.296875 \r\n",
       "L 54.390625 0 \r\n",
       "L 12.40625 0 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-49\"/>\r\n",
       "    </defs>\r\n",
       "    <g transform=\"translate(24.088638 95.520997)scale(0.08 -0.08)\">\r\n",
       "     <use transform=\"translate(0 0.015625)\" xlink:href=\"#DejaVuSans-88\"/>\r\n",
       "     <use transform=\"translate(68.505859 0.015625)\" xlink:href=\"#DejaVuSans-91\"/>\r\n",
       "     <use transform=\"translate(107.519531 0.015625)\" xlink:href=\"#DejaVuSans-49\"/>\r\n",
       "     <use transform=\"translate(171.142578 0.015625)\" xlink:href=\"#DejaVuSans-93\"/>\r\n",
       "    </g>\r\n",
       "   </g>\r\n",
       "   <g id=\"text_3\">\r\n",
       "    <!-- $X[2]$ -->\r\n",
       "    <defs>\r\n",
       "     <path d=\"M 19.1875 8.296875 \r\n",
       "L 53.609375 8.296875 \r\n",
       "L 53.609375 0 \r\n",
       "L 7.328125 0 \r\n",
       "L 7.328125 8.296875 \r\n",
       "Q 12.9375 14.109375 22.625 23.890625 \r\n",
       "Q 32.328125 33.6875 34.8125 36.53125 \r\n",
       "Q 39.546875 41.84375 41.421875 45.53125 \r\n",
       "Q 43.3125 49.21875 43.3125 52.78125 \r\n",
       "Q 43.3125 58.59375 39.234375 62.25 \r\n",
       "Q 35.15625 65.921875 28.609375 65.921875 \r\n",
       "Q 23.96875 65.921875 18.8125 64.3125 \r\n",
       "Q 13.671875 62.703125 7.8125 59.421875 \r\n",
       "L 7.8125 69.390625 \r\n",
       "Q 13.765625 71.78125 18.9375 73 \r\n",
       "Q 24.125 74.21875 28.421875 74.21875 \r\n",
       "Q 39.75 74.21875 46.484375 68.546875 \r\n",
       "Q 53.21875 62.890625 53.21875 53.421875 \r\n",
       "Q 53.21875 48.921875 51.53125 44.890625 \r\n",
       "Q 49.859375 40.875 45.40625 35.40625 \r\n",
       "Q 44.1875 33.984375 37.640625 27.21875 \r\n",
       "Q 31.109375 20.453125 19.1875 8.296875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-50\"/>\r\n",
       "    </defs>\r\n",
       "    <g transform=\"translate(24.088638 172.090593)scale(0.08 -0.08)\">\r\n",
       "     <use transform=\"translate(0 0.015625)\" xlink:href=\"#DejaVuSans-88\"/>\r\n",
       "     <use transform=\"translate(68.505859 0.015625)\" xlink:href=\"#DejaVuSans-91\"/>\r\n",
       "     <use transform=\"translate(107.519531 0.015625)\" xlink:href=\"#DejaVuSans-50\"/>\r\n",
       "     <use transform=\"translate(171.142578 0.015625)\" xlink:href=\"#DejaVuSans-93\"/>\r\n",
       "    </g>\r\n",
       "   </g>\r\n",
       "   <g id=\"text_4\">\r\n",
       "    <!-- $Y[0]$ -->\r\n",
       "    <defs>\r\n",
       "     <path d=\"M -0.203125 72.90625 \r\n",
       "L 10.40625 72.90625 \r\n",
       "L 30.609375 42.921875 \r\n",
       "L 50.6875 72.90625 \r\n",
       "L 61.28125 72.90625 \r\n",
       "L 35.5 34.71875 \r\n",
       "L 35.5 0 \r\n",
       "L 25.59375 0 \r\n",
       "L 25.59375 34.71875 \r\n",
       "z\r\n",
       "\" id=\"DejaVuSans-89\"/>\r\n",
       "    </defs>\r\n",
       "    <g transform=\"translate(434.753425 155.918595)scale(0.08 -0.08)\">\r\n",
       "     <use transform=\"translate(0 0.015625)\" xlink:href=\"#DejaVuSans-89\"/>\r\n",
       "     <use transform=\"translate(61.083984 0.015625)\" xlink:href=\"#DejaVuSans-91\"/>\r\n",
       "     <use transform=\"translate(100.097656 0.015625)\" xlink:href=\"#DejaVuSans-48\"/>\r\n",
       "     <use transform=\"translate(163.720703 0.015625)\" xlink:href=\"#DejaVuSans-93\"/>\r\n",
       "    </g>\r\n",
       "   </g>\r\n",
       "  </g>\r\n",
       " </g>\r\n",
       " <defs>\r\n",
       "  <clipPath id=\"p9ab4529a5d\">\r\n",
       "   <rect height=\"201.477449\" width=\"442.682637\" x=\"7.2\" y=\"7.2\"/>\r\n",
       "  </clipPath>\r\n",
       " </defs>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<Figure size 491.87x259.971 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "circuit(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The NAND-TM Programming Language"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just like NAND-CIRC models circuits, NAND-TM models _Turing Machines_. NAND-TM introduces an index variable `i` that is initialized to $0$ and allows to index _arrays_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A NAND-TM program is a sequence of lines. Every line in NAND-TM except the last one has the form \n",
    "\n",
    "`<varid> = NAND(<varid>,<varid>)`\n",
    "\n",
    "where `varid` (standing for _variable identifier_) is a sequence of letters, numbers,  underscores, and brackets (`[`,`]`). Only variable identifiers starting with uppercase letters can contain brackets. If `<varid>` starts with an uppercase letter it must be of the form `<Name>[<idx>]` where `<Name>` is a sequence of letters, numbers, and underscores starting with an uppercase letter, and `<idx>` is either a sequence of numbers or the letter `i`.\n",
    "(for example `Bar[354]` or `Foo[i]`).\n",
    "\n",
    "Variables whose identifiers start with uppercase letters are known as _array variables_ and variables whose identifiers start with lowercase letters are known as _scalar variables_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Variables of the form `X[<idx>]`  are _input variables_, and variables of the form `Y[<idx>]` are _output variables_. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The last line of a NAND-TM program has the form `MODANDJMP(<varid>,<varid>)`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Execution of a NAND-TM program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "to be completed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python implementation of NAND-TM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "to be completed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The NAND-RAM programming language\n",
    "\n",
    "The NAND-RAM programming language allows _indirection_, hence using variables  as  _pointer_ or _index_ variables.\n",
    "Unlike the case of NAND-TM vs NAND-CIRC, NAND-RAM cannot compute functions that NAND-TM can not (and indeed any NAND-RAM program can be \"compiled\" to a NAND-TM program) but it can be polynomially faster."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main features of NAND-RAM are the following:\n",
    "\n",
    "* Variables can hold values that are _arbitrary non negative integers_, rather than just zero or one.\n",
    "\n",
    "* We use the convention that a variable whose name starts with a capital letter is an _array_ and a variable whose name starts with a lowercase letter is a _scalar_ variable.\n",
    "\n",
    "* If `Foo` is an array and `bar` is a scalar, then `Foo[bar]` denotes the integer stored in the `bar`-th location of the array `Foo`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NAND-RAM operations\n",
    "\n",
    "Unlike our previous programming languages, NAND-RAM is not as minimalistic and contains a larger number of operations, many of which are redundant, in the sense that they can be implemented using other operations. The one component NAND-RAM does _not_ contain (though it can be of course implemented as syntatic sugar) is function calls.  This is because we want to maintain the invariant that an execution of a single line of NAND-RAM corresponds to a single computational step.\n",
    "\n",
    "\n",
    "The NAND-RAM programming language allows the following operations:\n",
    "\n",
    "* `foo = bar` (assignment)\n",
    "* `foo = bar  + baz` (addition)\n",
    "* `foo = bar - baz` (subtraction)\n",
    "* `foo = bar >> baz` (right shift: $foo \\leftarrow \\lfloor bar 2^{-baz} \\rfloor$)\n",
    "* `foo = bar << baz` (left shift: $foo \\leftarrow bar 2^{baz}$)\n",
    "* `foo = bar % baz`  (modular reduction)\n",
    "* `foo = bar * baz` (multiplication)\n",
    "* `foo = bar / baz` (integer division: $foo \\leftarrow \\lfloor \\tfrac{bar}{baz} \\rfloor$)\n",
    "* `foo = BITAND(bar,baz)` (bitwise AND)\n",
    "* `foo = BITXOR(bar,baz)` (bitwise XOR)\n",
    "* `foo = bar > baz` (greater than)\n",
    "* `foo = bar < baz` (smaller than)\n",
    "* `foo = EQUAL(bar,baz)` (equality)\n",
    "* `foo = BOOL(bar)` (booleanize: `foo` gets $0$ if bar equals $0$ and gets $1$ otherwise)\n",
    "\n",
    "We also use the following Boolean opertions (which apply `BOOL` implicitly to their input):\n",
    "\n",
    "* `foo = NAND(bar,baz)`\n",
    "* `foo = OR(bar,baz)`\n",
    "* `foo = AND(bar,baz)`\n",
    "* `foo = NOT(bar)`\n",
    "\n",
    "In each one of the above `foo` , `bar` and `baz` denotes variables that are either of the form `scalarvar` or `Arrayvar[scalarvar]` or `Arrayvar[num]` (that is either a scalar variable or an array variable at a location indexed by a scalar variable or a numerical value).\n",
    "\n",
    "We also have the following __control flow__ operations:\n",
    "\n",
    "* `if foo: ...code... endif` performs `...code...` (which is a sequence of lines that starts with a newline) if  `foo` is nonzero.\n",
    "\n",
    "* `while foo: ...code... endwhile` performs `...code...` as long as `foo` is nonzero.\n",
    "\n",
    "* `do: ...code... until foo` performs `...code...` and if `foo` is zero then it goes back and does it again until `foo` becomes nonzero.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Invariant:__ Each scalar variable or an element of an array variable in NAND-RAM can only hold an integer that ranges between $0$ and $t+1$ where $t$ is the number of lines of code (that is computational steps) that have been executed so far.  Another way to think about it as that we initialize $t=1$ in the beginning of the execution, and every time we execute a line of code, we increment $t$ by one. \n",
    "\n",
    "__Overflow and underflow:__ In all the operatoins above, they would have resulted in assigning a value to `foo` that is smaller than zero, then we assign zero instead. If they would have resulted in assigning a value to `foo` that is larger than $t+1$, then we assign $t+1$ instead. Note that one can ensure that the latter case does not happen by prefacing the operation with a loop that runs for at least $T$ times, where $T$ is an uppper bound on the value that we'll need. For this reason, this overflow restriction is immaterial when discussing issues of _computability_ and only makes a difference when one want to measure _running time_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Zero default:__ Just like NAND-CIRC and NAND-TM  all variables that have not been assigned a value are assigned zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Definition:__ For a NAND-RAM program $P$ and input $x\\in \\{0,1\\}^*$, the _time_ that $P$ takes on input $x$ is defined as the number of NAND-RAM lines that are executed if $P$ is initialized with $x$ until it halts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Execution of a NAND-RAM program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "to be completed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python implementation of NAND-RAM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "to be completed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## NAND-RAM to NAND-TM compiler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be completed"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}