---
Video Title: Defining EVAL
Description: Theory of Computation
https://uvatoc.github.io/week4

9.2: Defining EVAL

Nathan Brunelle and David Evans
University of Virginia
---

Now we have everything we need in order to
define what our eval function looks like.

So we're going to have this eval function.

It's going to work on programs of S lines
with n inputs and m outputs.

And this eval function, what it's going to
do is it's going to take an input string.

And that input string is
going to be the number

of bits that's necessary
to represent our program.

So this was this roughly 4s log s number.

And then we have n bits.

Those are the n bits of the input.

This is saying we need to be given the
program.

This is saying we need to be given the
input to the program.

And then the output
of this is going to be m

bits, because we said
there were m output bits.

So the number of bits we're getting as
input to eval is the number of bits we

need to represent an S line
program, plus the number of

bits we need to represent
an n bit input, which is just n.

And then our output is m, for our m bits
of output.

So basically what this program is going to
do is it's going to say, well,

I'm going to assume that the first s of s
bits are going to be the program,

and then the remaining n bits of the input,
those are the inputs to that program.

And then our output is
going to be the result of

running that represented
program on the provided input.

And then maybe something if there's a
compile error.

If this is maybe like, I
referenced a variable

before assignment
or something like that.

So this is what our eval function is going
to look like.

Let's now actually look at how our eval
function is going to behave.

So basically, we're going to take the same
idea that we used for how your computer

executes code, and
we're going to do it in

this world where we
only have integers instead.

Since eval kind of has all of
these parameters defined, it

knows exactly which bits are
going to be the program bits.

It knows which bits are going to be the
input bits.

And from those program
bits, it can break those

up into the triple of
integers and so forth.

This is the lines of our program.

And let's say that our input is 0,
1.

For eval, n is 2 and m is 1.

So we have two inputs and one output.

The way that we're going to be giving the
input to eval is you would just take all

of these numbers that you see,
all of these integers you see from the

lines, convert those to bits, and then
concatenate them all together,

and then add a 0 and a 1 at the end of
that.

So that's what eval is going to see when
you give it input.

So then what we can do is we're going to
say, let's take our variables,

or we need to figure out what the value
for each of these variables is,

understanding the last m of them are going
to be output variables.

We're given two input variables.

So whatever those two
bits were after our program,

those go in as the values
of the first two variables.

So our inputs were 0 and 1.

So variable 0 gets bit 0, gets value 0.

So variable 1 gets value 1.

Next, what we do is we
say, variable 2, that's going

to get the result of doing
a NAND with 0 and 1.

So variable 2, we want to do 0 NAND 1.

2 is the result of NANDing 0 and 1.

So 0 NAND 1 is 1.

The next thing we have is 3.

It receives the result of doing a NAND
with 0 and 2.

2's value is 1.

0's value is 0.

So 3 gets the value of 0 NAND 1,
which is 1.

And then 4 gets the result of doing a NAND
on variables 1 with 2.

So that's 1 with 1.

So 1 NAND 1 is 0.

So the value of 4.

And then we have 5 receives the result of
doing a NAND on variable 3 with variable 4.

So that's 1 NAND 0.

So this becomes 1.

This, by the way, is a representation of
XOR.

This is that same representation we had a
few slides ago.

So you can see that
this did correctly give us

the result of 1 if we're
doing an XOR of 0 with 1.

This program is written in a
representation of a NAND straight line.

In the same way that this is a
representation of NAND straight line in

this Python-like thing,
this is a representation

of NAND straight line
as triples of integers.

And what eval is going
to do is it's going to take a

representation of NAND
straight line as a bunch of bits.

As this S plus N bits.

Let's try to write now
some pseudocode for

exactly what's going
on with this eval function.

So what we're going to need, the pieces
we're going to need for this eval function.

So we need the table that's going to hold
the variable values.

We're also going to have this function
that I'm going to call get.

What get does is it takes
the table and an index and

it returns the value of the
variable of that number.

So it gets the table and
the number, and it says,

here's the value that the
variable you numbered has.

And then I'm going to have update,
where what update does...

So kind of like git, we give it the table
and an index.

But then we're also going to give it a
single bit b, so a value b.

And what update does is it gives basically
a new table that is exactly the same as

the old one, except variable I's value has
been changed to be equal to b.

So the table holds the variables and their
values.

Git says, here's the value of variable I
in that table.

Update says, change the value of variable
I to be b in the table.

And here's your new table.

What we're going to be
able to do then is we can

sort of assemble these
together in some pseudocode.

We can assemble these pieces together in
some pseudocode.

Where what we're going to do is we're
going to say we have this table t.

We have our table t.

And I'm going to let little t be the size
of it.

Whatever that is.

So what I can do is I can say for each of
my inputs, for I and range n's,

I'm going to update my table so that the
value at position I was going to be input i.

The i-th input.

Preload the table with your input values.

Preload the first n values of your table
with the input values.

And then we can look at every single one
of our triples in our program.

And what we're going
to do is our triple I, j, k

says that I gets assigned
the nand of j with k.

So that's what our triple meant.

The variable numbered
I gets assigned the value

of variable j with the
value of variable k.

So what I'm going to
do is I'm going to get the

value of variable j by
looking up j in the table.

I'm going to get the value of variable k
by looking up k in the table.

And I'm going to say, in my table,
change the value of I so that it's the

result of doing our nand with those two
other values.

And then our outputs are just going to be,
give me the last m bits.

First, we're going to load input bits into
the table.

And the next thing we're
going to do is we're going to

say, read and write to the
table for each of the triples.

And then finally, we're going to say,
return the last m bits.

So these are our three steps.

We update the table to have all of the
inputs in it.

And then we get from the table the last
two things in each triple and then update

so that the nand of those goes to the
first thing in each triple.

And then when we're done, we just return
the last things.

So this is exactly the same pseudocode
that we saw before.

Exactly the same procedure we saw before,
just now in terms of these triples.

Yeah.

The output is always going to be in the
last m bits.

Yes.

So this is something
that we've already been

doing, is having our
outputs must be at the end.

So what we're going to do is now we can
talk about, we're going to show that we

can implement this eval thing using just
nand.

So we're going to use that idea of the
pseudocode, where we're just having this

table, we read values from the table,
we do nands on them, and then write that

value to the table over and over and over
again.

We're going to do that using only nands
now.

The first thing we're going to talk about
is git.

So basically our table
is just the way that we

thought of it before, was
kind of as a column of bits.

Something like this.

You can think of this as just a bit
string, though.

Instead of thinking of
these as columns, we're just

going to represent them
sideways, as a linear string.

So with git, what we're
giving you is I'm giving you the

string that represents
all of the bits in that table.

In order so the zeroth bit hold the value
of variable zero, the first bit was going

to represent the value of variable one,
and so forth.

The way that git works is I hand you the
bit string t and the variable's number I,

and it gives us, as the result,
the value of that variable i.

Does this look familiar?

Yeah.

Yeah, so this is basically just lookup.

So this is lookup, where what we need to
know is how big our index is for lookup.

How big is our index for lookup?

Yeah.

For lookup, our subscript was the size of
the index, not the size of the bit string.

So the log of the length of t is basically
what that would end up being.

So in this case, our lookup, if we say
that this l right here, this equals the

length of each variable, so the number of
bits we need to represent each variable,

this is lookup sub l.

This is the same as doing lookup sub l of
t with i.

How many gates do we need to do lookup?

This was roughly like 2 to the l gates,
is what we did.

To do lookup of k, I could do two lookups
of k minus 1, plus an if.

And then to do lookup of
k minus 1, I could do two

lookups of k minus 2 for
each of those, plus ifs for each.

And when we worked this out, we did this
proof, we talked two classes about this,

where we had 2 to the power l.

So we know we can do git because it's just
lookup described differently.

But it's exactly the same as lookup,
and the number of gates we need to

implement this we know to be 2 to the
power l.

So the next thing we want to talk about is
we want to talk about update.

The way that update is going to work is
update, we give it the table.

This sl, that's the table.

We give it the number of lines.

We give it the bit that we're going to be
changing some index in the table to.

And we give as output the new table.

Yeah, this should be 2 to the power l.

The way that update is supposed
to work is we want to change

the value of index I in the table
to be whatever that bit b was.

In this new table that
we're giving, every single bit

is going to be the same
except for one of the bits.

So when we compute this new table,
when we give the new table, that's going

to be exactly the same as the original
table, except one bit is going to be

different, and that is the bit at index I,
in this case.

Where the bit at index I is going to have
value b.

If value b was what was already there,
then it might not be any different.

There might be no different bits, but
it's going to differ by at most one bit.

When we do a lookup, we say look-up sub k,
the k represented the number of bits that

you needed to represent your index into
your string.

That means the length of your string was
two to the k.

So here, L represents the number of bits
we need to represent our variable,

which must have meant the number of
variables was roughly two to the L.

L is the number of bits we need per
variable.

Two to the L is going to be the number of
variables we have.

We have one bit per variable.

So two to the L is roughly the size of the
table.

When we looked at this pseudocode back
here, we have like a for loop.

For loops are not something we've talked
about how we can do.

So we don't know how to do a for loop with
NAND straight line yet.

But provided that we have kind of only a
finite number of iterations in our for

loop, we can just sort of unroll that
loop.

So if we knew in advance how many times we
would iterate through that loop,

we could just unroll it and just do the
stuff explicitly that exact number of times.

So instead of saying for I
going from zero up to four, we

could just say five times in a
row, copy-paste the same stuff.

So that's essentially
what we're going to

do in order to mimic
this idea of for loops.

What we're going to do is we're going to
look at each bit in the table,

and we're essentially going
to say, if the index of that

bit was the one that I wanted
to change, then make it B.

Otherwise, leave it whatever it was
before.

Make it equal to bit B.

Otherwise, leave it whatever it was
before.

So in order to do this, we're going to use
this equal function where it tells me

whether or not two given bit strings were
equal, essentially.

And this equal is going to require roughly
a linear number of gates.

One of your homeworks is to figure out how
you can do equal with roughly a linear

number of gates in terms of the number of
input bits.

It looks kind of similar to compare.

Essentially, what we're going to do in
order to do our update is we're going to

say for each of the rows in our table,
which we said there's roughly two to the L

of those, we're going to say that if this
row is the row we were looking for,

so A is going to tell us whether or not I
was equal to J.

So I says, here's the row we're looking
for.

J says, here's the row I'm looking at.

If the number for the row
we're looking for matches the

number for the row we're
looking at, A is going to be one.

So A indicates whether or not we're
looking at the right row.

So we're going to say
if we're looking at the

right row, then we're
going to return the value B.

Otherwise, we're going to return the same
thing that was originally in our table.

B was the input to update.

B was this input to
update that told us what

the bit was we were
going to change things to.

So, if the row we're looking for is the
row we're looking at, then I'm going to

give as my result b, otherwise,
we didn't want to change that row.

So, in that case, I give whatever was there
before and assign that to some new table.

And then return the new table.

That's the idea.

We want to have this for-loop,
where we say for each row in the table,

if this was the row I'm looking for,
return b, otherwise, return the old value.

And then return whatever that new table is
that we just got.

And essentially what we can do is instead
of doing this as a for loop, we can just

have, say, 2 to the l lines where we've
done this.

Copied and pasted over and over and over
again.

So we do this explicitly where j is equal
to 0.

So I try this for 0.

And then I try this for 1.

And then I try this for 2.

And then I try it for 3.

And I just do it for every single row in
the table.

So we're just gonna have a bunch of these.

And now this is going to give us updates.

So these are now all of the pieces that we
need.

We know how to do git.

Because git, we said, was the same as
lookup.

And we knew that we could do update by
this procedure here.

And then when we go back
and we look at the pseudocode for

this, these were the only things
that we didn't know how to do.

So we can do sort of this for loop by this
loop unrolling thing, kind of explicitly.

We can do update.

We can do git.

Here we have update again.

We know how to do nan.

So all of these are pieces that we know
how to do.

So through some combination of loop
unrolling or using syntactic sugar that

we've defined this class or prior,
we can do all of these things with NAND.

Yeah, so... Right, so in
this case, notice how

here we basically have this new table.

So we're not allowed to reassign the values
of variables in our NAND straight line.

You have to invent a new variable every
single time.

But we can do that.

It didn't make sense to
do it there if I actually had

for loops because I can't
invent a new name for a thing.

But once we unroll that for loop,
not a problem anymore.

So, what we know now is that we can
compute any finite function with circuits.

We talked about that last time.

We can do any finite function with
circuits.

And in fact, if I wanted
to, I could even write a

function that evaluates
programs of a certain size.

So if you told me the size of
the programs you wanted me to

evaluate, I could write a
function that would do that for you.

That's what we talked about today.

So if we're going to try to use this to
actually build computers or something like

that, if we want to actually use these
ideas in order to actually implement

computers, we have these
questions about maybe, for whatever

function you're trying to
represent, how expensive is that?

I had to tell you how big the program was
that I wanted you to be able to simulate.

Did I tell you a big enough program?

How many... if I have a function,
my goal function that I'd like to

implement, was my implementation small
enough that you could actually evaluate it?

This is an important question that you're
going to want to ask when you're sort of

deciding what it is you want to maybe
implement in hardware.

How much hardware do you need to achieve
the goal function that you really want?

Some functions are more expensive than
others.

Maybe we want to know, what is the most
expensive function?

Can we come up with a
guarantee that some function is

going to be at least a
certain amount of expensive?

So maybe if I'm trying to actually
implement my eval circuit, what's the size

that it should be in order
to guarantee that I could

get every function that I
could implement with my eval?

Since I had to pick this size.

Which says that if I wanted
to be able to do every function

of a certain number of inputs,
how big should my eval be?

How many gates does my eval circuit
actually require in order to do that?

These are all follow-up questions we might
want to ask in order to figure out is this

actually going to be an efficient way to
compute?

We can do any finite function.

We can simulate programs of finite
functions.

Is this actually efficient?

We need to be able to
answer these questions

before we're going
to be able to do that.

So that's where we're going to pick up
next time.

We're going to talk about this
idea of complexity of functions

so that we can start to answer
some of those questions.

Ladies, please.

Thank you.

Once again.