{
"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",
"#### Computing __finite__ functions with __nonuniform__ algorithms:\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",
"#### Computing __unbounded input length__ functions with __uniform__ algorithms:\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",
"` = NAND(,)`\n",
"\n",
"where `varid` (standing for _variable identifier_) is a sequence of letters, numbers, underscores, and brackets (`[`,`]`). Only variables of the form `X[]` and `Y[]` can contain brackets. Moreover, all other variables identifiers must begin with a lowercase letter. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Variables of the form `X[]` for a number `` are _input variables_, and variables of the form `Y[]` 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)\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"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",
"` = NAND(,)`\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 `` starts with an uppercase letter it must be of the form `[]` where `` is a sequence of letters, numbers, and underscores starting with an uppercase letter, and `` 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[]` are _input variables_, and variables of the form `Y[]` are _output variables_. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The last line of a NAND-TM program has the form `MODANDJMP(,)`"
]
},
{
"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
}