---
Video Title: Constructing Conditionals
Description: Theory of Computation
https://uvatoc.github.io/week3

7.3: Crafting Conditionals
Defining IF as a procedure

Nathan Brunelle and David Evans
University of Virginia
---

So the next thing we're going to add to
our programming language is we're going to

add conditionals, or if statements,
to our programming language.

So we'd like to be able to do something
like this.

I forgot a return.

Maybe we're going to return x and y and z
in this or something like that.

So I want to be able to have some chunk of
code where I say, if maybe some Boolean

was true, then I'm going to evaluate some
group of lines.

Otherwise, I'm going to do these other
lines instead.

So we'd like to have if statements that
are something like this.

So we're going to show that we can add if
statements to our program without actually

changing what's going
on by making what is a

user-defined procedure
that does if statements for us.

So we're going to use this syntactic sugar
that we just added in order to actually

talk about how we could perform conditionals
in our programming language in this way.

The way that this is
going to work is we're

essentially going to
have this if procedure.

Where the way that this if
procedure is going to work

is it's going to take
three bits as its argument.

We're going to have the condition of the
if.

So what bit we were using to actually
choose what bit we wanted to end up with.

And the way that this is going
to work is we're going to say

that if the condition was
true, then we want to return a.

And if the condition was false,
then we want to return b.

We take the condition.

We say, if that condition was true,
return A.

And if it was false, we want to return B.

This is an implementation of exactly that
happening.

That's perhaps easier to read than NAND.

So let's kind of step through to see
exactly what this if is doing.

So what we're doing is I'm first saying
I'm going to have the condition,

and then I'm also going to have the
inverse of the condition.

So here I've got the condition and then
not the condition.

Let's look at the situations for this if
where we want to return true.

So we want to return true whenever the
condition was true and A was true.

That is one situation where we want to
return true.

Another situation where we'd want to
return true is if the condition was false,

that is, not the condition was true,
and B was true.

So those are the only two ways I could
return true with this if.

I said if, cond, return A, else,
return B, then the only situations where

I'm going to return true was where the
condition and A were both true,

or when the condition was false and B was
true.

Every other situation, this is going to
return false.

If I'm saying if the condition is true,
return A.

That means if the condition
is true, then whatever.

A happens to be is
going to be the result.

So the only way where the condition is
true and we return true is when A was true.

On the other hand, if the
condition was false, then

we return whatever
happens to be the value of B.

So if the condition is
false, we return true

when B is true and
false when B was false.

So there are only two situations.

So if we look through
the truth table of this, there

are only two situations
where we end up returning true.

That's where the condition was true,
putting us into the if part of this if-else.

And then a was true, so we returned a,
thereby returning true.

On the other hand, if the
condition was false, that

put us in the else part
of this else statement.

So we return the value of B.

So the only way we
would return true when the

condition was false is
when B happened to be true.

So this is saying the only two ways that
we're going to return true with this if is

when the condition
and A were both true or

when the condition
was false but B was true.

So the result of this if
user-defined procedure here

matches what that if statement
is going to do up there.

Yes.

Our inputs are always bits.

So cond is just a bit.

So we have evaluated
whatever our condition is and we

have the bit that represents
whether it's true or false.

And then we pass that
into the function with our two

choices for the resulting bit
that we're choosing between.

And if that happened to
be true the return value

is going to match the
value of the first one.

Otherwise the return value is going to
match the value of the second one.

So perhaps part of the confusion here is
that all one bits are the same,

are equivalent, all zero bits are
equivalent.

So even though you never see return the
first thing, we're returning something

that's going to be
equivalent to the value

of the first thing
whenever this bit was one.

When the bit was one,
whatever the value of the first

thing is, that's going to match
the value that we returned.

When the condition was zero,
whatever the value of the second

thing is, is going to match
the value that we returned.

And we guaranteed that by basically just
looking at what are all of the situations

where the return value should
have been true, versus what

are all the situations where
the return value is false.

And we're going to write this expression
that's logically equivalent to that,

is what we ended up doing here.

Question.

Skipping lines of code
is not something that

we can actually do with
our programming model.

So we're going to talk about how this is
going to allow us to do something

equivalent to that, but we just haven't
gotten there yet.

I needed to set up that we can have this
if user-defined procedure first.

Question in the back.

So this is the result if the condition is
true.

This is the result if the condition is
false.

And if you're in either of these two
situations...

So the way to read this is to say that one
way that we're going to return true is by

saying our condition was true and the
first thing listed was also true.

The only other way to make it so that we
return true is if the condition was false

and the second thing that we provided was
true.

If we're in either of those two scenarios,
I don't care which, we return true.

Now that we have this, let's look at how
we can translate things.

So, we need to define our value for if,
which is going to be...

Let's take NAND up here.

And this was NOT COND NAND COND COND.

So this is NOT COND is equal to doing the
NAND of the condition with itself.

So now we have the opposite of the
condition.

So NAND A with NOT COND, NAND B with COND.

Nope, got these backwards.

Okay, so we're doing B with
NOT COND, A with COND,

and then we're going to
return the NAND of X and Y.

We're trying to eliminate this IF ELSE by
using our user-defined function instead.

So here, we're using W as our conditional.

So W being the AND of A and B,
that is our conditional here.

And what we're going
to do is we're not really

going to be able to skip
lines of code with this.

So the way that this typically
works in Python is you

say, if W, then do this stuff
and skip the next chunk.

Otherwise, do the opposite.

Instead, we're going
to pre-compute all of the

values that are in maybe
the IF and the ELSE.

But we're going to use our IF named
action, our IF procedure, in order to

assign our variables to have the right
value.

So what I can do here is I can say that X
from the condition that the IF was true,

well, that's going to be equal to this OR
AB.

However, X, where our IF
statement was false, is going

to be whatever we
calculated X to be in the ELSE.

So that's going to be AND AB.

And then what value should X be?

Well, if W was true,
then we want X to be the

value that we said X
should be when it was true.

Otherwise, we want X to be the value that
X should have been when X was false.

Whatever value X has right here was the
same as what X would have down here.

And now we can repeat this for all of our
other variables as well.

So we can say what should
Y have been when it was

true, when W was true, then
Y was going to be NOT A.

And when W was false, Y was going to be A
or B.

And then overall, we can figure out what
the value of Y should have been by saying

if W was true, then I
want to assign to the

variable Y the value
of the variable Y true.

Otherwise, I'm going to assign to the
variable Y the value of Y false.

And then we can do this for Z.

And we have now a function that is
equivalent to what we had before.

So anytime I have these if
statements, I can get rid of

those if statements by just
using this if named action.

So if statements can be converted to the
if procedure.

And procedures can be converted into NAND
gates.

So now programs with ifs can do everything
that programs with NANDs can do.

How many get that?

Yes.

So skipping lines is not
something that we can just add in

based on kind of the idea for
how this would end up in hardware.

So if we're trying to count gates or
something like that, there's no way that

we're going to be able to in our gate model
of representation say skip these gates.

So that's kind of the challenge that we're
running into here.

So without having some way where we can
actually skip lines of code or skip gates,

actually skipping lines is not something
we can do.

The best we can do is get something that's
functionally equivalent and say compute

everything and then pick which thing to
keep is essentially what's happening here.

So we know that any function that can be
computed with ifs, we can do with NANDs

instead, where each if is going to be one,
two, three, four NAND gates.

7.