This notebook gives an overview of the NAND++ language. We use Python code to illustrate some concepts, but you don't need to know Python at all to follow. In fact, in the first read I recommend you skip all the code cells.
This notebook should be useful for you even if you view it statically, but might be even better if you play with on jupyter notebook.
The right way to think about NAND++ is that it has the following two features compared to NAND:
All variables except the special index variable i
are arrays. Each variable in a line of code of NAND++ is either indexed by a fixed numerical index (as in foo_17
) or by the special index i
, (as in bar_i
). If an index is missing (as in blah
) we treat at as 0 (and so blah
and blah_0
refer to the same variable).
NAND is a straightline programming language that has no loops, and so if the program has $s$ lines then on every input it runs for exactly $s$ steps. NAND++ has the special loop
variable (which is the same as loop_0
, by our convention above), such that when an iteration ends, if loop
equals $1$, then the program starts from the beginning. An iteration of an $s$ lines NAND++ program takes $s$ steps, and the number of iterations such a programs takes depends on the input that it gets.
The special index variable i
either increases or decreases by one at the end of every iteration. It follows the following schedule $0,1,0,1,2,1,0,1,2,3,2,1,0,1,2,3,2,2,1,0,\ldots$. There is also a formula for this schedule. The only thing you have to remember about it is that it exists, and is not that complicated. In fact, we can write it in a couple of lines of math or Python (as shown in the next cell):
import math
# Returns the value of the index variable i in iteration number k
def index(k):
r = math.floor(math.sqrt(k+1/4)-1/2)
return (k-r*(r+1) if k <= (r+1)*(r+1) else (r+1)*(r+2)-k)
[index(k) for k in range(20)]
[0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1]
The code of a NAND++ program looks almost exactly like the code of a NAND program except for the presence of the index variable i
. The main difference is that when we run a NAND++ program we do two things:
In iteration $k$ we replace all references to $i$ with references to $index(k)$
When we get to the end, if loop
is equal to 0 then we go back to the beginning.
One more minor difference is that because the input in a NAND++ program does not have a fixed length, in addition to the variables x_0
, x_1
, ... that give us the bits of the input, we also have variables validx_0
,validx_1
, ... such that validx_
$j$ evaluates to $1$ if and only if $j$ is smaller than the length of the input. (Otherwise, the program would not be able to determine the length of the input.)
The above means that if we have an interpeter for NAND, we can write an interpreter for NAND++ by simply invoking it many times, using the search and replace as above. Here is some Python code that does that:
The function NANDinterpeter
gets a NAND program and a table of the values of its variables, and runs the NAND program to update this table.
The function NANDPPinterpeter
gets a NAND++ program P and an input x as input. It initializes a table corresponding to the input, and then continusly feeds the program P to the NAND interpeter (replacing in iteration $k$ the value of i
with $index(k)$).
# Gets as input a NAND program and a table of values of variables.
# Runs an iteration of the program, updating the values of the variables as it proceeds
def NANDinterpeter(prog,variables):
for line in prog.split('\n'):
(var1,_,var2,__,var3) = line.split()
variables[var1] = 1-variables.get(var2,0)*variables.get(var3,0)
# p.s. This code is a bit brittle: sensitive to spaces, comments, and other issues.
# Gets as input a NAND++ program and an input (as an array of 0/1 values) and returns the evaluation of the program on this input
# Works by repeatedly calling NAND
def NANDPPinterpreter(prog,x):
n = len(x)
variables = {}
for i in range(n):
variables['x_'+str(i)]=x[i]
variables['validx_'+str(i)]=1
k=0
while True:
NANDprog = prog.replace( '_i','_'+str(index(k)))
NANDinterpeter(NANDprog,variables)
if variables.get('loop',0)==0: break
k += 1
return variables.get('y_0',0) # assume one bit output
Let's try this out on the parity program from the lecture notes:
parity = r'''tmpa := seen_i NAND seen_i
tmpb := x_i NAND tmpa
val := tmpb NAND tmpb
ns := s NAND s
y_0 := ns NAND ns
u := val NAND s
v := s NAND u
w := val NAND u
s := v NAND w
seen_i := zero NAND zero
stop := validx_i NAND validx_i
loop := stop NAND stop'''
NANDPPinterpreter(parity,[0,1,1,0,0,1,1])
0
NANDPPinterpreter(parity,[0,1,1,0,0,1,0,0,1])
0
That's all there is to NAND++. It is an extremely simple programming language. The surprising thing is that it is equivalent to NAND<< and other more powerful languages. That is, ultimately we can implement NAND<< (or even Python) as "syntactic sugar" on top of NAND++.
NAND<< (and other such more powerful languages) are inherently more complex to describe. A fairly complete description of NAND<< is in Appendix A, but to write things in full formality and detail would require much more space. The specification of C,C++ or Python can run to hunderds of pages. The fact that the specification is long means that a full formal proof of the equivalence of NAND++ and NAND<< would be very long and detailed, and not that insightful. (This is not something specific for NAND++ and NAND<<, the full formal proof that Turing machines are equivalent to RAM machines, for example would be just as long.)
I do not expect you to know all this proof by heart, but to understand the key steps in it, which are illustrated in the lecture notes. In particular, the most significant step is the transformation, using the "breadcrumbs" technique, of a NAND++ that uses the i++
and i--
syntactic sugar, to the a program that does not use it.
The main component of that technique is the ability of a NAND++ program to know when an index is increasing or decreasing: that is create an indexincreasing
variable that is equal to $1$ when the index will be incremented in the next stepand equal to $0$ when the index will be decremented in the next step.
Usng this, to simulate the i--
operation we look at indexincreasing
: if it is equal to $0$ then we do nothing, if it is equal to $1$ then we mark the current location of i
using a special array marker_i
, and do nothing until we reach the same location with the value of indexincreasing
equal to $1$.
indexincreasing
¶I will not include here the Python code to implement all of the above sugar, but here is a Python function that modifies a NAND++ program $P$ to a NAND++ program $P'$ that has the indexincreasing
variable.
At one step we will want to assign to indexincreasing
the value F(atstart_i,breadcrumbs_i,indexincreasing)
where $F:\{0,1\}^3 \rightarrow \{0,1\}$ is defined as $F(1,\cdot,\cdot)=1$, $F(0,0,\cdot)=0$ and $F(0,1,a)=a$. That is, if we are at the beginning then indexincreasing
should be equal to $1$, if we reach a point we haven't seen before, then indexincreasing
should be equal to $0$, and otherwise it should stay the same.
This is just a finite function and so we can construct a NAND code for it (which you will see in the Python code below)
def idxincreasing(prog):
prog = "atstart_0 := zero NAND zero\n"+prog # ensure atstart is array (1,0,0,0,....)
prog += r'''
tempidx := breadcrumbs_i NAND indexincreasing
notstart := atstart_i NAND atstart_i
indexincreasing := notstart NAND tempidx
breadcrumbs_i := zero NAND zero'''
return prog
If we run it for the parity program, we get the following variant:
parityidx = idxincreasing(parity)
print(parityidx)
atstart_0 := zero NAND zero tmpa := seen_i NAND seen_i tmpb := x_i NAND tmpa val := tmpb NAND tmpb ns := s NAND s y_0 := ns NAND ns u := val NAND s v := s NAND u w := val NAND u s := v NAND w seen_i := zero NAND zero stop := validx_i NAND validx_i loop := stop NAND stop tempidx := breadcrumbs_i NAND indexincreasing notstart := atstart_i NAND atstart_i indexincreasing := notstart NAND tempidx breadcrumbs_i := zero NAND zero
To see if it works, let's rerun this with a version of our interpeter that prints the indexincreasing
variable:
# Gets as input a NAND++ program and an input (as an array of 0/1 values) and returns the evaluation of the program on this input
# Works by repeatedly calling NAND
def NANDPPinterpreter(prog,x,track = []):
n = len(x)
variables = {}
for i in range(n):
variables['x_'+str(i)]=x[i]
variables['validx_'+str(i)]=1
k=0
while True:
NANDprog = prog.replace( '_i','_'+str(index(k)))
NANDinterpeter(NANDprog,variables)
if variables.get('loop',0)==0: break
for v in track: print(v + " = "+ str(variables.get(v,0)))
k += 1
return variables.get('y_0',0) # assume one bit output
NANDPPinterpreter(parityidx,[0,1,1,0],["indexincreasing"])
indexincreasing = 1 indexincreasing = 0 indexincreasing = 1 indexincreasing = 1 indexincreasing = 0 indexincreasing = 0 indexincreasing = 1 indexincreasing = 1 indexincreasing = 1 indexincreasing = 0 indexincreasing = 0 indexincreasing = 0 indexincreasing = 1 indexincreasing = 1 indexincreasing = 1 indexincreasing = 1
0
You can see that we have a sequence of increasing once, then decreasing once, then increasing twice, then decreasing twice, and so on and so forth
The notion of configurations is just to encode the entire contents of the state of a NAND++ program. The exact details of a configurations are not as important as are the following high level points:
The state of a NAND++ program has components that are fixed independently of the input and the number of steps: the current line, the number of lines, and the values of all array locations that are indexed by an absolute numerical index such as foo_17
. It also has components that can grow as the number of steps grow: the value of the index variable i
, and the contents of the arrays in all the locations that i
has been to so far.
As we run more steps, we access more memory locations, and so the size of the configuration grows.
We use blocks to encode the configuration for convience. The size of each block is a constant (that depends on the number of lines in the program), but the number of blocks can grow. Block number $j$ contains the contents of all variables that are of the form foo_
$j$. If $j$ is equal to the current value of the index variable i
then this block is the active block, and the configuration contains a bit that marks this condition.
For every NAND++ program $P$, the $NEXT_P$ function computes the next configuration of the program $P$.
For every NAND++ program $P$, the $NEXT_P$ function maps one configuration to the next one. It can be implemented by fairly simple "search and replace". This is done in the Python code below, though again I would skip it in a first read.
import math
# compute the next-step configuration
# Inputs:
# P: NAND++ program in list of 6-tuples representation (assuming it has an "indexincreasing" variable)
# conf: encoding of configuration as a string using the alphabet "B","E","0","1".
def next_step(P,conf):
s = len(P) # numer of lines
t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables
line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line
block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of "E","B")
LOOP = 3
INDEXINCREASING = 5
ACTIVEIDX = block_enc_length -line_enc_length-1 # position of active flag
FINALIDX = block_enc_length -line_enc_length-2 # position of final flag
def getval(var,idx):
if idx<s: return int(blocks[idx][var])
return int(active[var])
def setval(var,idx,v):
nonlocal blocks, i
if idx<s: blocks[idx][var]=str(v)
blocks[i][var]=str(v)
blocks = [list(b[1:]) for b in conf.split("E")[:-1]] # list of blocks w/o initial "B" and final "E"
i = [j for j in range(len(blocks)) if blocks[j][ACTIVEIDX]=="1" ][0]
active = blocks[i]
p = int("".join(active[-line_enc_length:]),2) # current line to be executed
if p==s: return conf # halting configuration
(a,j,b,k,c,l) = P[p] # 6-tuple corresponding to current line# 6-tuple corresponding to current line
setval(a,j,1-getval(b,k)*getval(c,l))
new_p = p+1
new_i = i
if p==s-1: # last line
new_p = (s if getval(LOOP,0)==0 else 0)
new_i = (i+1 if getval(INDEXINCREASING,0) else i-1)
if new_i==len(blocks): # need to add another block and make it final
blocks[len(blocks)-1][FINALIDX]="0"
new_final = ["0"]*block_enc_length
new_final[FINALIDX]="1"
blocks.append(new_final)
blocks[i][ACTIVEIDX]="0" # turn off "active" flag in old active block
blocks[i][ACTIVEIDX+1:ACTIVEIDX+1+line_enc_length]=["0"]*line_enc_length # zero out line counter in old active block
blocks[new_i][ACTIVEIDX]="1" # turn on "active" flag in new active block
new_p_s = bin(new_p)[2:]
new_p_s = "0"*(line_enc_length-len(new_p_s))+new_p_s
blocks[new_i][ACTIVEIDX+1:ACTIVEIDX+1+line_enc_length] = list(new_p_s) # add binary representation of next line in new active block
return "".join(["B"+"".join(block)+"E" for block in blocks]) # return new configuration
The initial configuration encodes the input. The code below (which again you should skip in a first read) returns a string encoding this initial configuration
# return initial configuration of P with input x
def initial_conf(P,x):
s = len(P) # numer of lines
t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables
line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line
block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of "E","B")
# largest numerical index:
largest_idx = max([max((0 if tup[1]==s else tup[1]),(0 if tup[3]==s else tup[3]),(0 if tup[5]==s else tup[5])) for tup in P])
ACTIVEIDX = block_enc_length -line_enc_length-1 # position of active flag
FINALIDX = block_enc_length -line_enc_length-2 # position of final flag
INITIALIDX = block_enc_length -line_enc_length-3 # position of initial flag
num_blocks = max(len(x),largest_idx+1)
blocks = [["B"]+["0"]*block_enc_length+["E"] for i in range(num_blocks)]
blocks[0][1+INITIALIDX]="1"
blocks[0][1+ACTIVEIDX]="1"
blocks[num_blocks-1][FINALIDX]="1"
for i in range(len(x)):
blocks[i][1]=x[i]
blocks[i][3]="1"
return "".join(["".join(b) for b in blocks])
We also add a couple of "helper functions" to print nicely the configuration (and check if it's halting by simply checking if the next_step function does nothing on it or not). Once again, please ignore the code in a first read
def is_halting(P,conf):
newconf = next_step(P,conf)
return newconf==conf
def bold(s,justify=0):
return "\x1b[1m"+s.ljust(justify)+"\x1b[21m"
def underline(s,justify=0):
return "\x1b[4m"+s.ljust(justify)+"\x1b[24m"
def red(s,justify=0):
return "\x1b[31m"+s.ljust(justify)+"\x1b[0m"
def green(s,justify=0):
return "\x1b[32m"+s.ljust(justify)+"\x1b[0m"
def blue(s,justify=0):
return "\x1b[34m"+s.ljust(justify)+"\x1b[0m"
def print_conf(P,conf):
s = len(P) # numer of lines
t = max([max(tup[0],tup[2],tup[4]) for tup in P])+1 # number of variables
line_enc_length = math.ceil(math.log(s+1,2)) # num of bits to encode a line
block_enc_length = t+3+line_enc_length # num of bits to encode a block (without bookends of "E","B")
LOOP = 3
INDEXINCREASING = 5
ACTIVEIDX = block_enc_length -line_enc_length-2 # position of active flag
FINALIDX = block_enc_length -line_enc_length-3 # position of final flag
blocks = [list(b[1:]) for b in conf.split("E")[:-1]]
printout = "".join([red("B")+ "".join(b[0:t])+
blue("".join(b[t:t+3]))+green("".join(b[t+3:t+3+line_enc_length]))+
red("E") for b in blocks])
print(printout)
The function below translates a NAND++ program to the standard 6-tuple representation as given in the lecture notes. In this representation, a line of the form foo_
$j$ :=
bar_
$k$ NAND
blah_
$\ell$ is transformed into the 6-tuple $(a,j,b,k,c,\ell)$ where $a,b,c$ are the numbers corresponding to the identifiers foo
, bar
and blah
.
If one or more of the indices is not an absolute number but rather the special index i
then the corresponding element in the 6-tuple will be the number of lines $s$. (This cannot create any confusion since we cannot use absolute numerical indices larger than $s-1$ in the program.)
# Parse NAND++ program as sequence of 6-tuples
def parsepp(prog):
s = len(prog.split('\n'))
varsidx = { "x":0, "y":1, "validx":2, "loop": 3, "halted":4, "indexincreasing":5 }
def idxsub(var):
varsplit = var.split('_')
varid = varsidx.setdefault(varsplit[0],len(varsidx))
sub = (0 if len(varsplit)<2 else (int(varsplit[1]) if varsplit[1]!='i' else s))
return [varid,sub]
L = []
for line in prog.split('\n'):
(var1,_,var2,__,var3) = line.split()
L.append(idxsub(var1)+idxsub(var2)+idxsub(var3))
return L
L = parsepp(parityidx)
print(L)
[[6, 0, 7, 0, 7, 0], [8, 0, 9, 17, 9, 17], [10, 0, 0, 17, 8, 0], [11, 0, 10, 0, 10, 0], [12, 0, 13, 0, 13, 0], [1, 0, 12, 0, 12, 0], [14, 0, 11, 0, 13, 0], [15, 0, 13, 0, 14, 0], [16, 0, 11, 0, 14, 0], [13, 0, 15, 0, 16, 0], [9, 17, 7, 0, 7, 0], [17, 0, 2, 17, 2, 17], [3, 0, 17, 0, 17, 0], [18, 0, 19, 17, 5, 0], [20, 0, 6, 17, 6, 17], [5, 0, 20, 0, 18, 0], [19, 17, 7, 0, 7, 0]]
Here is the initial configuration of the parity program on the input "1011":
initial_conf(L,"1011")
'B10100000000000000000010100000EB00100000000000000000000000000EB10100000000000000000000000000EB10100000000000000000010000000E'
And here is the next configuration
next_step(L,_)
'B10100010000000000000010100001EB00100000000000000000000000000EB10100000000000000000000000000EB10100000000000000000010000000E'
And the one after that
next_step(L,_)
'B10100010100000000000010100010EB00100000000000000000000000000EB10100000000000000000000000000EB10100000000000000000010000000E'
And so we can also evaluate NAND++ programs by repeatedly applying the next step function as follows:
In the code below we use print_conf
to print the configurations with nice colors marking the components of each block:
The red B and E are the "begin block" and "end block" markers.
The black string corresponds to the contents of all the variables in that block
The three blue bits correspond to the "initial", "final", and "active" flags
The green bits correspond to the current line that is being executed. Note that they are always equal to 0 for non-active blocks.
Note also that the configuration grows with the execution (although in the case of the parity program not by much, since this program halts as soon as it reaches one spot beyond the input length).
# Evaluate a NAND++ program (represented as a list of tuples)
# By repeatedly applying the "next step" function
def eval_conf(L,x):
conf = initial_conf(L,x)
while not is_halting(L,conf):
print_conf(L,conf)
conf = next_step(L,conf)
return int(conf[2])
eval_conf(L,"101")
B10100000000000000000010100000EB00100000000000000000000000000EB10100000000000000000010000000E B10100010000000000000010100001EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100000000000010100010EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100000000000010100011EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100100000000010100100EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100110000000010100101EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100110000000010100110EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100110100000010100111EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100110110000010101000EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100110110000010101001EB00100000000000000000000000000EB10100000000000000000010000000E B10100010100111110000010101010EB00100000000000000000000000000EB10100000000000000000010000000E B10100010110111110000010101011EB00100000000000000000000000000EB10100000000000000000010000000E B10100010110111110000010101100EB00100000000000000000000000000EB10100000000000000000010000000E B10110010110111110000010101101EB00100000000000000000000000000EB10100000000000000000010000000E B10110010110111110010010101110EB00100000000000000000000000000EB10100000000000000000010000000E B10110010110111110010010101111EB00100000000000000000000000000EB10100000000000000000010000000E B10110110110111110010010110000EB00100000000000000000000000000EB10100000000000000000010000000E B10110110110111110011010000000EB00100000000000000000000100000EB10100000000000000000010000000E B10110110110111110011010000000EB00100010000000000000000100001EB10100000000000000000010000000E B10110110110111110011010000000EB00100010100000000000000100010EB10100000000000000000010000000E B10110110111111110011010000000EB00100010101000000000000100011EB10100000000000000000010000000E B10110110111011110011010000000EB00100010101000000000000100100EB10100000000000000000010000000E B10110110111001110011010000000EB00100010101000000000000100101EB10100000000000000000010000000E B11110110111001110011010000000EB01100010101000000000000100110EB10100000000000000000010000000E B11110110111001110011010000000EB01100010101000100000000100111EB10100000000000000000010000000E B11110110111001100011010000000EB01100010101000100000000101000EB10100000000000000000010000000E B11110110111001101011010000000EB01100010101000101000000101001EB10100000000000000000010000000E B11110110111001101011010000000EB01100010101001101000000101010EB10100000000000000000010000000E B11110110111001101011010000000EB01100010111001101000000101011EB10100000000000000000010000000E B11110110111001101011010000000EB01100010111001101000000101100EB10100000000000000000010000000E B11110110111001101011010000000EB01110010111001101000000101101EB10100000000000000000010000000E B11110110111001101011010000000EB01110010111001101010000101110EB10100000000000000000010000000E B11110110111001101011010000000EB01110010111001101010000101111EB10100000000000000000010000000E B11110110111001101011010000000EB01110110111001101010000110000EB10100000000000000000010000000E B11110110111001101011010000000EB01110110111001101011000000000EB10100000000000000000010100000E B11110110111001101011010000000EB01110110111001101011000000000EB10100010000000000000010100001E B11110110111001101011010000000EB01110110111001101011000000000EB10100010100000000000010100010E B11110110110001101011010000000EB01110110111001101011000000000EB10100010100000000000010100011E B11110110110101101011010000000EB01110110111001101011000000000EB10100010100100000000010100100E B11110110110101101011010000000EB01110110111001101011000000000EB10100010100100000000010100101E B11110110110101101011010000000EB01110110111001101011000000000EB11100010100100000000010100110E B11110110110101001011010000000EB01110110111001101011000000000EB11100010100100000000010100111E B11110110110101011011010000000EB01110110111001101011000000000EB11100010100100010000010101000E B11110110110101011011010000000EB01110110111001101011000000000EB11100010100100011000010101001E B11110110110100011011010000000EB01110110111001101011000000000EB11100010100100011000010101010E B11110110110100011011010000000EB01110110111001101011000000000EB11100010110100011000010101011E B11110110110100011011010000000EB01110110111001101011000000000EB11100010110100011000010101100E B11110110110100011011010000000EB01110110111001101011000000000EB11110010110100011000010101101E B11110110110100011011010000000EB01110110111001101011000000000EB11110010110100011010010101110E B11110110110100011011010000000EB01110110111001101011000000000EB11110010110100011010010101111E B11110110110100011011010000000EB01110110111001101011000000000EB11110110110100011010010110000E B11110110110100011011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000000000000000000001100000E B11110110110100011011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010000000000000001100001E B11110110110100011011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010100000000000001100010E B11110110111100011011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101000000000001100011E B11110110111000011011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101000000000001100100E B11110110111010011011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101010000000001100101E B10110110111010011011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101010000000001100110E B10110110111010111011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101010100000001100111E B10110110111010111011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101010110000001101000E B10110110111010111011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101010111000001101001E B10110110111010111011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010101010111000001101010E B10110110111010111011010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010111010111000001101011E B10110110111010111111010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010111010111100001101100E B10100110111010111111010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010111010111100001101101E B10100110111010111111010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010111010111110001101110E B10100110111010111111010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000010111010111110001101111E B10100110111010111111010000000EB01110110111001101011000000000EB11110110110100011011010000000EB00000110111010111110001110000E
0
And we see that the final output is indeed the parity of the input.