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.