[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. 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. So to finish up lets have you do one. Which is to figure out what it is for less than comparisons. Try to work through it on your own. Just on a blank piece of paper. If you get stuck it's also in the reading notes associated with the lecture and then we can add some questions about it as well. So remember for all of these the details are less important than the fact that we always ask the same question. How do I write it down the syntax. What are the type checking rules. And then what are the evaluation rules.
