0:00

[MUSIC]

Alright. In this segment, we're going to take the

same program we had in our previous segment and we're going to look at those

different kinds of expressions we saw more carefully and make sure we give them

a precise semantics so we know exactly what they mean.

So we're going to take the same program we had before, you see it here on the

Powerpoint slide, and we're going to really focus in on those expressions that

we had for each of the variables that we bound.

We're not doing this because I think you don't understand addition or what an

integer is or how a conditional expression works.

But because by giving the semantics to these things very carefully,

we'll be able to build on top of that and use the exact same ideas when we learn

more sophisticated and interesting language constructs in the near future.

So if we look at this program we see a bunch of different kinds of expressions

either explicitly in the program like 34 or a variable x or an addition as well as

a couple of things that we don't see in the program but would be the result of

evaluating some of those expressions like the bullion constants true and false.

So, in fact, I thought I would show those to you quickly and here's my program.

and I can go ahead and open the REPL here.

There really is a constant true. just like there's a constant 42.

And that's the result of things like conditional expressions so three less

than zero evaluates to the Boolean false. And if I include those variables that I

bound, then I can use those in less than

expressions as well. And I can ask is x less than y?

Turns out it's false, but if I ask is Y less than X, that evaluates to true.

So, we have these kinds of expressions as you might expect but we also have this

neat property that we can build expressions as big as we want.

So certain expressions like addition, less than and conditionals are built out

of smaller sub-expressions and that can nest as deep as you want.

So you can have an addition inside of another addition.

You can have a conditional inside of an addition.

You can have an addition inside of conditionals and that can go as deep as

you want, making expressions as big as we want.

So when we go to define the syntax and semantics of expressions, that definition

is going to have to be recursive because we're going to have to define it in terms

of those sub expressions. So there's a, a really important

methodology to what we're going to do right now and that is for every kind of

expression to ask ourselves the same three questions.

What is the syntax, i.e. how do you write it down?

What are the typing checking rules. In other words, what type does an

expression have, and what can cause it to fail to type check in which case you get

an error message. And then the third question is whether

the evaluation rules. Assuming it does type check, how does it

perform its computation in order to produce a result.

And we're going to call that result a value.

Of course, expressions might not produce a result that can also raise an

exceptionate run time or go into an infinite loop.

3:00

Okay, so let's start with the simplest kind of expression I can think of, which

is a variable. So we're going to ask three questions.

What is the syntax? The answer is it's any sequence of

letters or digits or underscores, except the first thing in that sequence can't be

a digit. The rules for variables in ML are pretty

similar to what they are in many programming languages.

The second question is, what are the type checking rules?

This is when we're using a variable, not when we are defining it with a variable

binding, but when we're using it as an expression, or as part of a larger

expression. So the answer is, the way you type check

a variable is you look it up in the static environment.

If you find it, whatever type it has in the static environment, that's the type

of the expression. If you don't find it, it doesn't type

check, and you get an error message. And then the third question was the

evaluation rules. Here it's similar to the type checking

rules, except we looked the variable up in the dynamic environment and we used

whatever value we find there. We don't have to worry about it not being

there, because in ML we only run programs that type check, so we know that variable

will be in the dynamic environment. Alright.

So, that's variables. Like I said, they're pretty simple.

Maybe even a little too simple. So let's next do addition expressions.

And these are our first example where the expression has sub expressions inside of

it. So the answers to all of our questions

are going to have to rely on the answers to the questions for the sub expressions.

So first, what's the syntax of an addition expression?

It's any expression where you have two other expressions with a plus symbol in

between them. That means you have an addition

expression. Okay, so what are the type checking

rules? But what you have to do given an addition

expression is you have to type check both of those sub-expressions E1 and E2.

And if they both have type int, then the addition expression has type int.

If either of them does not type check, or has a type other than int, then the

entire thing does not type check. See how the answer for the larger

expression is built out of the answer for the smaller expressions.

And similarly for our evaluation rules, we're going to take those two

subexpressions e1 and e2, evaluate them to values, let's call them v1 and v2

whatever they might be and then our overall result will be the sum of v1 and

v2 and again thanks to type checking I know v1 and v2 will be ints so I know

that it will always be possible to sum them.

Alright so that's addition, we all knew how addition worked.

Now, before I get to the more interesting one, which is conditional expressions,

let me talk a little bit more about these values.

So remember the result of evaluating something is a value.

So it turns out that every value is an expression but not every expression is a

value. So what we have are these certain kinds

of expressions, the values that are always going to evaluate to themselves.

So 42 evaluates to 42, true evaluates to true.

There's actually even one the result of that use command, we use in the REPL

produces this value left parenthesis right parenthesis that has type unit.

So, for each of these types there's a certain set of values and those are the

answers that we get when we have some expression of that type.

So, we know how 34 works. Its syntax is a sequence of digits.

Its typing rule is that it has type int. And its evaluation rule is that it's a

value and like all values it produces itself as its answer.

Okay, so those are the values.

Now let's do a more sophisticated one, which are the conditional expressions.

And I thought it would be more interesting to write this out rather than

just already have it up on the slide. And since my typing is much better than

my handwriting, I thought I would just open a text file in emacs and write it

there. So the syntax for a conditional

expression is if e1 then e2 else e3 where if then and else are keywords.

They're the actual syntax that explains what this is what construct this is.

And e1, e2, and e3 are sub expressions. So the same way an addition has two sub

expressions. A conditional has three sub expressions.

Now, the type checking is more interesting, and is different than with

addition expressions. so first e1 must have type bool.

It must be true or false, or a variable of type bool or a comparison or some

expression of type bool. e2 and e3 can have any type, let's call

it t but they must have the same type, t. So you can't have a then branch of one

type and an else branch of another type, because the result of our entire

expression might be either of them. And what we need is, the type of the

entire expression is also t. And last we have to evaluation rules.

And here we first evaluate e1 to a value, call it v1.

Since it type checked with typo, I actually know that v1 will be true or

false. If it's true evaluate e2 and that result

is the whole expressions result else evaluate e3 and that result is the whole

expressions result. And that is everything there is to know

about the syntax tight checking rules and evaluation rules of an if expression.