---
Video Title: Computing Models and Syntactic Sugar
Description: Theory of Computation
https://uvatoc.github.io/week3

7.1: Computing Models and Syntactic Sugar
- Recap Computing Models: AON, NAND, Circuits
- Straightline Programs vs. Python

Nathan Brunelle and David Evans
University of Virginia
---

We've been talking about models of
computation.

And in particular, we've been talking
about two different models of computation,

which are these straight-line programs.

We could say x is equal to AND y with z.

So we add statements like that in these
straight-line programs.

And we talked about Boolean circuits,
where maybe we had these gates that were

meant to convey this idea of transistors
doing logic or something like that.

This is an AND gate here.

And then maybe we have y and z as inputs.

And then maybe the output is something
kind of like that x.

Straight-line programs kind of behave like
programming languages.

Boolean circuits kind of behave like
hardware.

And we talked about them being equivalent
in some ways.

And we explored some of
the more precise definitions of

what it actually means to
compute with Boolean circuits.

So what we're doing next
is we're going to kind of

expand primarily on this
idea of straight-line programs.

So these straight-line programs right now
are super, super stripped-down programming

languages, where all you can do is Boolean
logic with variables.

And what we're going to do is we're going
to sort of expand on these straight-line

programs, make them look more like
programming languages that you might be

familiar with, and show that none of these
changes that we've made actually change

anything in terms of what we are and are
not allowed to compute.

We're going to be kind of changing this
straight-line programming model to be

something that looks more like Python,
and show that that is actually secretly

the same computing
model, just with some

extra, what we end up
calling syntactic sugar.

That's why we have candy on this slide
today.

We're going to be talking about things
called syntactic sugar, which is changes

that you make to a programming language
that sort of change what the programming

language looks like, but doesn't actually
fundamentally change what it's doing.

So we're not changing the compute model,
we're just kind of making it nicer for

humans to use, is what syntactic sugar
means.

So let's do a refresher of where we're at.

So we have these and
or not, that's what AON

stands for, and or not
straight-line programs.

We saw this looks kind
of like Python, where we're

able to define functions
that take Boolean inputs.

We can do and or or not within our
programs and assign those values to

variables and then maybe
use those variables in order

to compute the value of
other variables and so forth.

And then eventually we'll end up returning
some result.

This was an example of this majority
function for straight-line programs.

We said that majority
was supposed to return one

if any two of the three
input bits were both one.

So basically, if greater
than or equal to two input bits

were one, then that means
that the majority were ones.

Otherwise, the majority weren't ones,
and we want to return zero.

So the way that we did this
is we kind of exhaustively

checked all three different
pairs that might be there.

We said that if the and
of one pair ended up

being one, that meant
both of them were one.

So if any of these three, so if this pair
was both one, or this pair was both one,

or this pair was both one, that meant the
majority was one.

But since we're only allowed
two inputs in our definition, we

had to split that or of three
things into two ors of two things.

And then we talked about these Boolean
circuits where we had and gates,

or gates, not gates.

We could have inputs that are going into
these gates and outputs that are coming

out of them, and we can kind
of take the outputs from some

gates and feed them in as
the inputs to subsequent gates.

And from there, we can build computations
as well.

So this was our other kind of
hardware-style compute model.

We also talked about this relationship
that we had between the two of them.

In particular, every single variable in
our straight-line program becomes a gate

in our Boolean circuit, so that we can
basically say that if I have a

straight-line program that's got some
number of lines, so for instance,

in this case, we have a
five-line program, that means that

I can build a Boolean circuit
with the same number of gates.

One, two, three, four, five gates.

So we had this relationship where I could
convert any straight-line program into a.

Boolean circuit, any Boolean circuit into
a straight-line program, and the size of

one was going to match the size of the
other.

By our definition of how we were allowed
to construct these programs, we basically

said all we could do is one binary operation
and then assign that to a variable.

So because of that,
every single binary

operation has a variable
and is on its own line.

So we could say that each operation is
sort of a gate.

We could also say
each variable is sort of a

gate, however you
prefer to think about it.

Each line is a gate.

Because based on our
definition, there's going

to be the same number
of each of those things.

Another way that we showed the equivalence
between two types of programs is we showed

this translation thing
with NAND straight-line

programs and these AND or
NOT straight-line programs.

We could take any AND or
NOT straight-line program and

compute exactly the same
function using just NANDs.

So anything that we could compute using
some combination of ANDs, ORs,

and NOTs in our program, we could compute
with just NANDs instead.

And the way that we did this was we
basically did some sort of translation

where if I had a NOT
before, so if I wanted to

do NOT A, I could
convert that into NAND AA.

If I wanted to do AND AB, I could convert
that one line AND into these two lines

that compute the same thing but use two
NANDs, but still exclusively NANDs.

So we knew that anything I could
do with AND or NOT programs,

I could do with NAND
straight-line programs as well.

These two are, in this sense, equivalent,
that any function that I can implement

using AND or NOT, I can implement with
NAND, and any function I can implement

with NAND, I can implement with AND or
NOT.

Today, as we're going through and trying
to add our syntactic sugar to our

programming language, we're going to be
working with this one.

So everything that we're going to do,
we're going to show that it can always be

converted to some NAND straight-line
program.

So we're only going to be using NANDs.

We might see ORs and NOTs and ANDs and
that sort of thing along the way,

but our ultimate goal is to show that all
of that is just extra stuff that helps us

read our code, but isn't
necessary for actually

expanding the power
of our computing model.

So our computing model is going to be NAND
straight-line, and we're going to show how

we can take other syntactic
sugar and convert that

back into that very strict
NAND straight-line program.

Let's talk a little bit about what we
might be adding for our syntactic sugar.

Most of us, according to our survey,
are familiar with Python.

Everybody should be
familiar with at least one

programming language,
whether that's Python or Java.

And both of those have some things that
are nice for computing that these

straight-line programs don't currently
have.

What are some... what's
some syntactic sugar that

you might want your
programming language to have?

Yes?

A for loop.

If.

Okay.

So if statements.

What else?

Okay, so maybe recursion.

So let me do something a little bit
simpler than recursion.

The only reason we don't have recursion
yet is because we don't have...

What should I call these?

Subroutines.

We haven't mentioned
at all how I can define

my own procedures or
my own subroutines yet.

So subroutines slash procedures.

What else?

What else might we want?

Yes?

Maybe different types.

What else?

Any other desires?

This is everything you could ever want in
a programming language.

Yeah?

A data structure?

Okay.

Okay.

Yes?

Okay, so inheritance,
like type inheritance

or object-orientedness
or something like that?

Yes?

Parallelism?

Some sort of threads or parallelism?

Okay, so I think this is a good list.

We're going to be talking about some of
these things.

We're certainly not going to be talking
about all of these things.

We'll talk about for loops eventually,
but not today.

We will talk about if statements.

We will do recursion subroutines and
procedures.

And we're going to kind of do like a data
structures type thing.

So these are some of the syntactic sugar
that we're going to introduce today.

And we'll be talking about today.

We will talk about each of the tamerated
catchers.