---
Video Title: De-Sugaring Procedures
Description: Theory of Computation
https://uvatoc.github.io/week3

7.2: De-Sugaring Procedures
- Replacing Procedures with In-Lined Code
- Cost of Evaluating Procedures

Nathan Brunelle and David Evans
University of Virginia
---

We're going to start with these
subroutines or procedures.

So this was our and or not implementation
of the majority function.

But we mentioned that
we could take andsors

and nots and convert
them exclusively to nands.

And the way that we kind of imagined that
we would do this was something like that.

Where we said, since I know that I can
convert nots into nands, and I can do and

with nands and nots, where
that not can be converted

into a nand, I can do nands
with only ands, and so forth.

So we kind of had this implicitly that we
were thinking about things as having these

other procedures, where because we were
only allowed to use nand, we needed a

procedure to do not, since we didn't
directly have that.

And since we didn't
directly have and, we

needed a procedure
to do that, and so forth.

Where maybe as part of that procedure, we
wanted to use this other procedure for not.

So that was not
something that was naturally

part of our computing
model, so let's add that.

We didn't naturally
have this ability to

define other functions
and then use them later.

So we're going to add that in.

We're going to add in these procedures,
these subroutines, the ability for the

user to name their own procedures in this
case.

So in order to do this, what we're going
to need to show is kind of like when we

talked about when we gave a procedure for
how I could take an AND or NOT

straight-line program
and convert that into

an exclusively NAND
straight-line program.

What I had to do was give a
procedure for how I could substitute

every, let's say OR, for
exclusively NANDs, for just NANDs.

So we're going to do a similar thing here.

I'm going to show how I can take some sort
of program that has these procedures in it

and convert it into a program without the
procedures that computes the same function.

So it'll behave identically, but does not
have those procedures.

Before we jump all the way to majority,
which was a pretty complicated one,

a relatively complicated one, right now I
have AND.

I'm trying to write the
AND function with my NAND

straight-line program, and
I've used as a procedure NOT.

So the question is, how
can I convert this program

here that uses NOT into
one that only uses NANDs?

The idea is that when I
computed that NOT, I could

substitute in the body of this
procedure, whatever that was.

Every place I saw this NOT, I would
substitute in all of the statements that

were part of the body of this procedure,
making sure that when I used certain

variables, I only used variables that kind
of had fresh names.

Names that I hadn't ever
seen before, so we don't

get overriding accidentally
or that sort of thing.

Right here, it doesn't matter because we
don't actually have any variables in NOT.

We're just directly returning the result.

So in this case, I can simply substitute
NAND temp temp where I saw NOT of temp.

We're going to have this procedure for
translating procedures.

If we have code with procedures,
we're going to have our own procedure.

We're basically writing our own algorithm
for how I can translate that into an

equivalent program that does not have any
procedures in it.

Here is majority.

My goal is I have this program where I
have three procedures NOT and an OR,

and I want to remove all three
of those procedures so that

I'm computing the majority
function using exclusively NANDs.

So that's my goal.

How am I going to do that?

So basically, every single time I use some
procedure, I'm going to sort of paste in

the body of that procedure where I used
it.

Once I paste that in, the parameters that
I had inside that procedure, I'm going to

remove those and substitute in the arguments
I had when I called that procedure.

For instance, here I called the procedure
AND on A and B.

So when I copy in the body of AND...

This is a bad example because we have the
same variable.

Let's talk about this one where I have B
and C.

So when I copied in the body
for AND over here, every place

I saw an A when I copied
this in, I would write B instead.

And every place I saw B, I would write C
instead.

Because those were the arguments I gave
for these parameters.

So substitute the parameters for the
arguments I used in that invocation.

And then I would also need to make sure
that I have this temp variable in here.

And as you can see, I have like multiple
ANDs.

Which means that I'm going to end up with
multiple temps.

Just to make sure I don't
even have to worry about

me getting kind of
contamination of these variables.

Since this AND is assuming that there is
only that one temp variable.

And a different AND might kind of mess it
up.

Just to make sure that we don't have any
issues with that.

I'm going to make sure that
when I do that substitution,

all the variables inside the
body have unique names.

So I'm going to rename
all of the variables within the

procedure body so that
they're sort of fresh variables.

They're new names that I've never seen
before.

Let's do an example of this with our
majority functions.

Let's kind of see how this works.

So here I have that same code that is
computing majority.

The first thing I'm going to do is I'm
going to try to remove NOT.

So I'm going to make it so that I can just
not have that procedure NOT anymore.

So how can I rewrite everything that used
NOT so that it's not using NOT before?

So what I'm going to do, our procedure
said I paste in.

So instead of using NOT here, I'm going to
paste in the body of NOT.

In this case, that was NAND AA.

But I need to make sure that I substituted
the variables that were used inside the

body, so that the parameters that were used
inside the body for the argument we gave.

So since we were computing NOT of TMP, A
was understood to be TMP inside this body.

So I want to replace TMP here.

And now this is computing the same function,
the same AND, but now without NOTs.

And now we can repeat the same thing here.

I can do here, this should be NAND of A
with A.

And then this should be NAND of B with B.

So now I have completely defined majority
without using NOT at all.

So I have eliminated the need for that
subroutine.

Now hopefully if we run this, we'll still
get the same result.

So here we are calling that on 1,
0, 0s.

The majority is not 1, so we're getting
the right answer.

So the next thing we're going to do is I'm
going to try to eliminate AND.

So we've eliminated NOT, so now let's
eliminate AND.

This one's going to be a little bit more
complicated.

Because there's more stuff involved.

So let's go ahead and I'm
going to comment out this

code, so we get red highlighting
where all the ANDs are.

So I need to compute the value for AND1,
but now without using AND.

The value of AND1 needs
to be assigned to the return

value, what the return
value for that AND was.

And then I need this line of code
beforehand in order to compute that thing.

Now in order to make sure that this
variable isn't going to interfere with any

other variables that I might
have had within my program,

I'm just going to make sure
that this has a unique name.

So maybe I'm going to say that this is the
first AND temp.

That way I just know that it's something
fresh, that I've never used this before.

And now I can change...

I need to change these to match.

So now I've removed that first AND, and I
can do something similar for these others.

So I can say that I need AND2.

AND2 temp is going to be equal to NAND.

And in this case I'm using B and C.

And now I can do NAND on AND2 temp with
AND2 temp.

And finally the same for the last one.

So the AND3 temp is equal to the NAND of A
with C.

And then AND3 is going to be equal to NAND
on AND3 temp.

NAND on AND3 temp.

AND AND3 temp.

And unless I made
mistakes in this translation, we

should now have majority
without using any ANDs.

So we got the right answer again.

Okay, so we're going to move on.

If you feel like you really want to see,
or you can come see me after class,

and I would be happy to go over that with
you.

But for now, let's go to the next thing.

Okay, so we mentioned that in our original
translation for how we could go from our

straight line programs to gates, every
single line in our program became one gate.

That is not necessarily going to be the
case anymore.

Once I have these procedures, we've added
in this syntactic sugar of procedures,

but we have lost this property that every
single line is a gate.

So it is not necessarily the case that we
could just say, like, 1, 2, 3,

4, 5, 6, 7, 8, 9, 10, 11, is the number of
gates it's going to take for us to do

majority if we implement it in this way,
and try to convert that into a circuit.

The reason for that is because once we do
this translation, so that we have our

procedures, we substitute
out our procedures, each

of these procedures might
represent multiple gates.

So each of these ANDs was actually not one
gate, it was two.

We can see that over here.

That was two gates.

So each of these represents two.

Each of these represents three gates.

So if we were to actually figure out how
many gates are we using for majority when

we have these procedures, the best we can
guarantee, at least, right now,

is we would have two for each
AND, and then three for each.

OR, so that is six for the AND,
six for the OR, so 12 gates.

If we're starting to talk about what is
the efficiency of this, how much time is

it going to take, what
resources do we need in

order to compute our
function, that has changed.

This is one of these cases where we have
kind of changed the efficiency of things

based on just our
syntactic sugar, how efficient

that translation might be
from our syntactic sugar.

So now we have procedures.

Our straight line programs
have procedures now,

and we know we haven't
changed our compute model.

And this one is just a challenge...

So we have 3,000 people to adapt,
We are back.