NANDshift_language.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The NAND<< Programming language\n",
    "\n",
    "_Version: 0.2_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The NAND<< programming language was 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/nandnotebooks](https://github.com/boazbk/nandnotebooks) on Github. \n",
    "\n",
    "The NAND++ programming language is defined in [Chapter 7: \"Equivalent models of computation\"](https://introtcs.org/public/lec_07_other_models.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our models of computation can be thought of as follows:\n",
    "\n",
    "\n",
    "* NAND language: _non uniform_, _finite_ model - equivalent to _Boolean circuits_.\n",
    "\n",
    "* NAND++ language: _uniform_ model with _sequential_ or _oblivious_ (depending on the flavor) memory access - equivalent to _Turing machines_.\n",
    "\n",
    "* NAND<< language: _uniform model_ with _random access memory_ - equivalent to _RAM machines_ and (if one does not care about polynomial factors) to Turing machines as well."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook will eventually contain code to evaluate NAND<< programs, as well as to transform NAND<< code to NAND++ code. At the moment however we just have the specification of the language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The NAND<< programming language\n",
    "\n",
    "The NAND<< (pronounced \"NAND shift\") programming language allows _indirection_, hence using variables  as  _pointer_ or _index_ variables.\n",
    "Unlike the case of NAND++ vs NAND, NAND<< cannot compute functions that NAND++ can not (and indeed any NAND<< program can be \"compiled to a NAND++ program) but it can be polynomially faster."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main features of NAND<< 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<< operations\n",
    "\n",
    "Unlike our previous programming languages, NAND<< 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<< 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<< corresponds to a single computational step.\n",
    "\n",
    "\n",
    "The NAND<< 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]` (that is either a scalar variable or an array variable at a location indexed by a scalar variable).\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<< 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 and NAND++, all variables that have not been assigned a value are assigned zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__No `loop` variable:__ Since NAND<< contains the `while` and `do` loops, we do not need an explicit `loop` variable. We can imitate the same semantics by simply using\n",
    "\n",
    "```\n",
    "do:\n",
    "  ...program code...\n",
    "  notloop = NOT(loop)\n",
    "until notloop\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ignore in first read: utility code for NAND++\n",
    "\n",
    "We use some utility code, which you can safely ignore in first read, to allow us to write NAND++ code in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# utility code \n",
    "%run \"NAND programming language.ipynb\"\n",
    "from IPython.display import clear_output\n",
    "clear_output()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ignore this utility function in first and even second and third read\n",
    "import inspect\n",
    "import ast\n",
    "import astor\n",
    "\n",
    "def noop(f):\n",
    "    return f;\n",
    "\n",
    "def runwithstate(f):\n",
    "    \"\"\"Modify a function f to take and return an argument state and make all names relative to state.\"\"\"\n",
    "    tree = ast.parse(inspect.getsource(f))\n",
    "    tmp = ast.parse(\"def _temp(state):\\n    pass\\n\").body[0]\n",
    "    args = tmp.args\n",
    "    name = tmp.name\n",
    "    tree.body[0].args = args\n",
    "    tree.body[0].name = name\n",
    "    tree.body[0].decorator_list = []\n",
    "    \n",
    "\n",
    "    class AddState(ast.NodeTransformer):\n",
    "        def visit_Name(self, node: ast.Name):\n",
    "            if node.id == \"enandpp\": return ast.Name(id=\"noop\", ctx=Load())\n",
    "            new_node = ast.Attribute(ast.copy_location(ast.Name('state', ast.Load()), node), node.id,\n",
    "                                     ast.copy_location(ast.Load(), node))\n",
    "            return ast.copy_location(new_node, node)\n",
    "        \n",
    "    tree = AddState().visit(tree)\n",
    "    tree.body[0].body = tree.body[0].body + [ast.parse(\"return state\")]\n",
    "    tree = ast.fix_missing_locations(tree)\n",
    "    src = astor.to_source(tree)\n",
    "    # print(src)\n",
    "    exec(src,globals())\n",
    "    _temp.original_func = f\n",
    "    return _temp\n",
    "\n",
    "    \n",
    "def enandpp(f):\n",
    "    g = runwithstate(f)\n",
    "    def _temp1(X):\n",
    "        nonlocal g\n",
    "        return ENANDPPEVAL(g,X)\n",
    "    _temp1.original_func = f\n",
    "    _temp1.transformed_func = g\n",
    "    return _temp1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ignore utility class in first and even second or third read\n",
    "\n",
    "from  collections import defaultdict\n",
    "class NANDPPstate:\n",
    "    \"\"\"State of a NAND++ program.\"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.scalars = defaultdict(int)\n",
    "        self.arrays  = defaultdict(lambda: defaultdict(int))\n",
    "        # eventually should make self.i non-negative integer type\n",
    "        \n",
    "    def __getattr__(self,var):\n",
    "        g =  globals()\n",
    "        if var in g and callable(g[var]): return g[var]\n",
    "        if var[0].isupper():\n",
    "            return self.arrays[var]\n",
    "        else:\n",
    "            return self.scalars[var]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ENANDPPEVAL(f,X):\n",
    "    \"\"\"Evaluate an enhanced NAND++ function on input X\"\"\"\n",
    "    s = NANDPPstate()\n",
    "    for i in range(len(X)):\n",
    "        s.X[i] = X[i]\n",
    "        s.Xvalid[i] = 1\n",
    "    while True:\n",
    "        s = f(s)\n",
    "        if not s.loop: break\n",
    "    res = []\n",
    "    i = 0\n",
    "    while s.Yvalid[i]: \n",
    "        res += [s.Y[i]]\n",
    "        i+= 1\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rreplace(s, old, new, occurrence=1): # from stackoverflow\n",
    "    li = s.rsplit(old, occurrence)\n",
    "    return new.join(li)\n",
    "\n",
    "    \n",
    "        \n",
    "def ENANDPPcode(P):\n",
    "    \"\"\"Return ENAND++ code of given function\"\"\"\n",
    "    \n",
    "    code = ''\n",
    "    counter = 0\n",
    "    \n",
    "    class CodeENANDPPcounter:\n",
    "        def __init__(self,name=\"i\"): \n",
    "            self.name = name\n",
    "        \n",
    "        def __iadd__(self,var):\n",
    "            nonlocal code\n",
    "            code += f'\\ni += {var}'\n",
    "            return self\n",
    "        \n",
    "        def __isub__(self,var):\n",
    "            nonlocal code\n",
    "            code += f'\\ni -= {var}'\n",
    "            return self\n",
    "        \n",
    "        def __str__(self): return self.name\n",
    "    \n",
    "    class CodeNANDPPstate:\n",
    "    \n",
    "    \n",
    "        def __getattribute__(self,var):\n",
    "            # print(f\"getting {var}\")\n",
    "            if var=='i': return CodeENANDPPcounter()\n",
    "            g =  globals()\n",
    "            if var in g and callable(g[var]): return g[var]\n",
    "            if var[0].isupper():  \n",
    "                class Temp:\n",
    "                    def __getitem__(self,k):  return f\"{var}[{str(k)}]\"\n",
    "                    def __setitem__(s,k,v): setattr(self,f\"{var}[{str(k)}]\",v)            \n",
    "                return Temp()\n",
    "            return var\n",
    "    \n",
    "        def __init__(self):\n",
    "            pass\n",
    "    \n",
    "        def __setattr__(self,var,val):\n",
    "            nonlocal code\n",
    "            if var=='i': return\n",
    "            if code.find(val)==-1:\n",
    "                code += f'\\n{var} = {val}'\n",
    "            else:\n",
    "                code = rreplace(code,val,var)\n",
    "    \n",
    "    s = CodeNANDPPstate()\n",
    "    \n",
    "    def myNAND(a,b):\n",
    "        nonlocal code, counter\n",
    "        var = f'temp_{counter}'\n",
    "        counter += 1\n",
    "        code += f'\\n{var} = NAND({a},{b})'\n",
    "        return var\n",
    "    \n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "    s = runwith(lambda : P.transformed_func(s),\"NAND\",myNAND) \n",
    "    \n",
    "    return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@enandpp\n",
    "def inc():\n",
    "    carry = IF(started,carry,one(started))\n",
    "    started = one(started)\n",
    "    Y[i] = XOR(X[i],carry)\n",
    "    carry = AND(X[i],carry)\n",
    "    Yvalid[i] = one(started)\n",
    "    loop = COPY(Xvalid[i])\n",
    "    i += loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def index():\n",
    "    \"\"\"Generator for the values of i in the NAND++ sequence\"\"\"\n",
    "    i = 0\n",
    "    last = 0\n",
    "    direction  = 1\n",
    "    while True:\n",
    "        yield i\n",
    "        i += direction\n",
    "        if i> last: \n",
    "            direction = -1\n",
    "            last = i\n",
    "        if i==0: direction = +1\n",
    "            \n",
    "a = index()\n",
    "[next(a) for i in range(20)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def NANDPPEVAL(f,X):\n",
    "    \"\"\"Evaluate a NAND++ function on input X\"\"\"\n",
    "    s = NANDPPstate() # intialize state\n",
    "    \n",
    "    # copy input:\n",
    "    for i in range(len(X)): \n",
    "        s.X[i] = X[i]\n",
    "        s.Xvalid[i] = 1\n",
    "        \n",
    "    # main loop:\n",
    "    for  i in index(): \n",
    "        s.i = i\n",
    "        s = f(s)\n",
    "        if not s.loop: break\n",
    "    \n",
    "    # copy output:\n",
    "    res = [] \n",
    "    i = 0\n",
    "    while s.Yvalid[i]: \n",
    "        res += [s.Y[i]]\n",
    "        i+= 1\n",
    "    return res\n",
    "\n",
    "\n",
    "\n",
    "def nandpp(f):\n",
    "    \"\"\"Modify python code to obtain NAND++ program\"\"\"\n",
    "    g = runwithstate(f)\n",
    "    def _temp1(X):\n",
    "        return NANDPPEVAL(g,X)\n",
    "    _temp1.original_func = f\n",
    "    _temp1.transformed_func = g\n",
    "    return _temp1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@nandpp\n",
    "def inc():\n",
    "    carry = IF(started,carry,one(started))\n",
    "    started = one(started)\n",
    "    Y[i] = IF(Visited[i],Y[i],XOR(X[i],carry))\n",
    "    Visited[i] = one(started)\n",
    "    carry = AND(X[i],carry)\n",
    "    Yvalid[i] = one(started)\n",
    "    loop = Xvalid[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here is the \"vanilla NAND++\" version of XOR:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@nandpp\n",
    "def vuXOR():\n",
    "    Yvalid[0] = one(X[0])\n",
    "    Y[0] = IF(Visited[i],Y[0],XOR(X[i],Y[0]))\n",
    "    Visited[i] = one(X[0])\n",
    "    loop = Xvalid[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vuXOR([1,0,0,1,0,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def NANDPPcode(P):\n",
    "    \"\"\"Return NAND++ code of given function\"\"\"\n",
    "    \n",
    "    code = ''\n",
    "    counter = 0\n",
    "    \n",
    "    \n",
    "    class CodeNANDPPstate:\n",
    "    \n",
    "    \n",
    "        def __getattribute__(self,var):\n",
    "            # print(f\"getting {var}\")\n",
    "            g =  globals()\n",
    "            if var in g and callable(g[var]): return g[var]\n",
    "            if var[0].isupper():  \n",
    "                class Temp:\n",
    "                    def __getitem__(self,k):  return var+\"[i]\"\n",
    "                    def __setitem__(s,k,v):   \n",
    "                        setattr(self,var+\"[i]\",v)            \n",
    "                return Temp()\n",
    "            return var\n",
    "    \n",
    "        def __init__(self):\n",
    "            pass\n",
    "    \n",
    "        def __setattr__(self,var,val):\n",
    "            nonlocal code\n",
    "            # print(f\"setting {var} to {val}\")\n",
    "            if code.find(val)==-1:\n",
    "                code += f'\\n{var} = {val}'\n",
    "            else:\n",
    "                code = rreplace(code,val,var)\n",
    "    \n",
    "    s = CodeNANDPPstate()\n",
    "    \n",
    "    def myNAND(a,b):\n",
    "        nonlocal code, counter\n",
    "        var = f'temp_{counter}'\n",
    "        counter += 1\n",
    "        code += f'\\n{var} = NAND({a},{b})'\n",
    "        return var\n",
    "    \n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "    s = runwith(lambda : P.transformed_func(s),\"NAND\",myNAND) \n",
    "    \n",
    "    return code\n",
    "\n",
    "\n",
    "# utility code - replace string from right, taken from stackoverflow\n",
    "def rreplace(s, old, new, occurrence=1): \n",
    "    li = s.rsplit(old, occurrence)\n",
    "    return new.join(li)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(NANDPPcode(inc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}