Version: 0.5
The NAND-CIRC, NAND-TM, and NAND-RAM programming languages were designed to accompany the upcoming book "Introduction to Theoretical Computer Science". This is an appendix to this book, which is also available online as a Jupyter notebook in the boazbk/tcscode on Github.
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.
We use the following main models of computation in this book:
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.
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. 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.
A NAND-CIRC program is a sequence of lines. Every line in NAND-CIRC has the form
<varid> = NAND(<varid>,<varid>)
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.
Variables of the form X[<num>]
for a number <num>
are input variables, and variables of the form Y[<num>]
are output variables.
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]
.
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.
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:
We initialize the variables X[0]
... X[
$n-1$]
to $x_0,\ldots,x_{n-1}$ and all other variables to $0$.
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
At the end of the execution, output the values of the variables Y[0]
... Y[
$m-1$]
def parseline(line, numargs = 0):
"""Parse a line of the form foo = 'OP( bar1, bar2, bar3)'
to ['foo','OP','bar1','bar2','bar2'].
If numargs > number of arguments in line then add empty strings to the list as needed."""
i = line.find("=")
j = line.find("(")
k = line.find(")")
if i<0 or j<0 or k<0: raise Exception(f"Line not formatted properly: {line}")
args = [a.strip() for a in line[j+1:k].split(",")]
if len(args)<numargs: args += [""]*(numargs-len(args))
return [line[:i].strip() , line[i+1:j].strip()] + args
import re
def numinout(prog):
'''Compute the number of inputs and outputs of a NAND program, given as a string of source code.'''
n = max([int(s[2:-1]) for s in re.findall(r'X\[\d+\]',prog)])+1
m = max([int(s[2:-1]) for s in re.findall(r'Y\[\d+\]',prog)])+1
return n,m
def EVAL(code,X):
"""Evaluate code on input X."""
n,m = numinout(code) # helper function - get number of inputs and outputs
vtable = { f"X[{i}]":int(X[i]) for i in range(n)}
for line in code.split("\n"):
if not line: continue
foo,op,bar,blah = parseline(line)
vtable[foo] = 1-vtable[bar]*vtable[blah]
return [vtable[f"Y[{j}]"] for j in range(m)]
code = r'''temp_1 = NAND(X[0],X[1])
temp_2 = NAND(X[0],temp_1)
temp_3 = NAND(X[1],temp_1)
temp_4 = NAND(temp_2,temp_3)
temp_5 = NAND(temp_4,X[2])
temp_6 = NAND(temp_4,temp_5)
temp_7 = NAND(X[2],temp_5)
Y[0] = NAND(temp_6,temp_7)
'''
EVAL(code,"011")
[0]
NAND-CIRC is of course equivalent to Boolean circuits
# utility code
%run "Utilities.ipynb"
from IPython.display import clear_output
clear_output()
circuit(code)
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.
A NAND-TM program is a sequence of lines. Every line in NAND-TM except the last one has the form
<varid> = NAND(<varid>,<varid>)
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
.
(for example Bar[354]
or Foo[i]
).
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.
Variables of the form X[<idx>]
are input variables, and variables of the form Y[<idx>]
are output variables.
The last line of a NAND-TM program has the form MODANDJMP(<varid>,<varid>)
to be completed
to be completed
The NAND-RAM programming language allows indirection, hence using variables as pointer or index variables. 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.
The main features of NAND-RAM are the following:
Variables can hold values that are arbitrary non negative integers, rather than just zero or one.
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.
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
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.
The NAND-RAM programming language allows the following operations:
foo = bar
(assignment)foo = bar + baz
(addition)foo = bar - baz
(subtraction)foo = bar >> baz
(right shift: $foo \leftarrow \lfloor bar 2^{-baz} \rfloor$)foo = bar << baz
(left shift: $foo \leftarrow bar 2^{baz}$)foo = bar % baz
(modular reduction)foo = bar * baz
(multiplication)foo = bar / baz
(integer division: $foo \leftarrow \lfloor \tfrac{bar}{baz} \rfloor$)foo = BITAND(bar,baz)
(bitwise AND)foo = BITXOR(bar,baz)
(bitwise XOR)foo = bar > baz
(greater than)foo = bar < baz
(smaller than)foo = EQUAL(bar,baz)
(equality)foo = BOOL(bar)
(booleanize: foo
gets $0$ if bar equals $0$ and gets $1$ otherwise)We also use the following Boolean opertions (which apply BOOL
implicitly to their input):
foo = NAND(bar,baz)
foo = OR(bar,baz)
foo = AND(bar,baz)
foo = NOT(bar)
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).
We also have the following control flow operations:
if foo: ...code... endif
performs ...code...
(which is a sequence of lines that starts with a newline) if foo
is nonzero.
while foo: ...code... endwhile
performs ...code...
as long as foo
is nonzero.
do: ...code... until foo
performs ...code...
and if foo
is zero then it goes back and does it again until foo
becomes nonzero.
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.
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.
Zero default: Just like NAND-CIRC and NAND-TM all variables that have not been assigned a value are assigned zero.
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.
to be completed
to be completed
To be completed