Hi everyone. Welcome to the new kind of concept in this programming languages course called types. Type is a very important concept in this course and actually in programming languages. Why? We'll see what we want to do with types and what we want to guarantee or check using types in our programs. You may want to read chapter 19, type systems in the textbook. So let's have some questions and answers series. In this lecture, we are going to have many questions and following the flow of questions and answers. I hope you can get the idea about why we want to have types in programming languages. Let's look at this example. Open, 1 plus 2, close. What is the value of the following expression? You should know, right? Yeah, a possible wrong answer is 0. Why? Another wrong answer could be 42, because 42 is the ultimate answer to the universe. According to the what? The book, Hitchhiker's Guide to the Galaxy. But no, no, no. 42 is not the ultimate answer to the universe. 1 plus 2 is 3. We know that, it's a simple mathematic expression. How about this? What is the value of the following expression, open and a lambda expression for the identity function plus 1 plus 8. What's going to be the result? A wrong answer is error. It is not an error. It could be an error but actually it's a trick question because this expression is not really an expression, right? So in order to answer those questions like is it an expression or not, we need a language, right? So this is our language grammar for today's lecture. You should understand most of this expression, the syntax of this expression, right? Those number related things, and true and false, and conditional expression and that's it. Interesting thing is that here we have multiple parameter function expression with no argument function expression, right? So the function call null takes no arguments or one or more arguments except that the language looks very familiar to us. This is the language for today. Yeah, quiz number 3, question number 4, is the following an expression? Let's see. It's a function call. The first part is a function expression with two parameters x and y. The function party is 1, the argument is an expression 7. So it looks like an expression, right? A function called expression, right? So the correct answer is it's an expression according to our grammar. So first, second, next question. What is the value of the following expression? It's a function expression., right, with two parameters. And now we are calling this function with this one single argument 7. What do you think? What is the value of this expression? A possible answer could be what? This one, meaning that we'd like to apply 7 to x. And the remaining thing could be another function expression expecting another argument and then returns 1 according to some interpreters. So according to some semantics, right? Yeah, but no reasonable language would accept this. Because the syntax says, I'm expecting two parameters and the argument is only a single argument was given. So we may not want to allow this kind of syntax. So let's agree to call this language, this expression function call where function expression takes one. I mean, two arguments but the function call gives only one argument meaning the number of parameters and the number of arguments do not match. In this case, let's call it ill-formed expression. It is not very formed, it's ill-formed because this function expression should be used only with two arguments not with one argument. This is just our promise, our policy now. We added one more policy saying that if a function expecting 2 or an n parameters, then the function call should give the exact number of arguments. That's going to be our new rule. Let's agree to never evaluate ill-formed expressions from now on. Okay, then next question, what is the value of the following expression? Yeah, we already saw that. It's a function expression expecting two parameters. And at the core site, we have only one argument. So the answer is, it is not a valid expression. It's ill-formed expression. Okay, then, so now you see we are asking more questions about good expressions, well-formed expressions versus ill-formed expressions. Then according to our current rule for well-formed expressions, is the following a well-formed expression? What's that? It's an addition of functional expression and a number. Is it away from the expression or not? What do you think? Right, it's well-formed because the grammar said so. We already saw the grammar for these questions, right? Yeah, but what is the value of the following expression? It is well, from the expression, but what is the value of the expression? What's that? Can you add a number 8 to a function expression? What's the result? 9? No, no, no. We are not adding the number 8 with the function body. So it produces an error because we don't know how to add a number to a function expression, right? Do you agree? Right, we don't want to do that. Then let's agree that this function expression cannot be inside a + form. Yeah, I know it's a weird restriction but we are trying to add some syntactic restrictions to expressions so that we can avoid any errors at runtime. Okay, one more time. We do have a syntax in grammar for our own language. And if we say that yeah, this expression is good. Then we want to run the expression to get a value. But as you can see here, even though the syntax is okay at runtime, it produces an error. It's not really good. When we said it's okay to run, we'd better have a value instead of one error at runtime. So these series of questions are trying to trim down, prune those error cases syntactically and we are trying to see whether that's possible or not. So because we don't want to add a function expression and a number, let's agree that function expressions cannot be inside an addition form. Are you with me? Okay, then let's move on. Next question then with that restriction, is the following a well-formed expression? It's an addition, right? It's an addition of something and another. This one is a number. We are good but this one is a function expression. In our recent restriction, we decided, we agreed that we are not going to put function expression inside the addition form. So no, it's not away from the expression. Very good, so that we can avoid adding a function expression to a number. How about this, is the following a well-formed expression? What is that? It's again an addition of one expression and another. This one is a number, we're good. This one is a function called expression, yeah. And this one is a function expression, do we want to allow this or not? Let's see if we apply this function call, it's just the identity function and the argument is 7. So the result is 7. So we can get the result 12 if we valued this. But we said that function expressions are not going to be inside this addition form. Is this inside the addition form or not? Because actually it's a functional applications self expression, maybe not the inside of plus form. I don't know because we didn't determine. We didn't define what we mean by inside an addition form intentionally, right? Then what what's the answer? Actually whether it's a well-formed expression or not depends on what we mean by inside in our most recent agreement. If we meant anywhere inside, then this expression is well-formed because this function expression is inside the function called expression which is inside the addition form, right? Yeah, but if we meant not immediately inside, then the addition with function call and number, so this is not technically immediately inside the addition form. So we can accept this expression. So it's a bit weird but because we can get the result 12 if we apply this function called and add five to that, let's agree to allow this expression. Meaning that we are not going to accept an expression of an addition form whose immediate self expression is a function expression. Okay, a bit complex rule but let's try that whether this complex rule can save our program from running wrong expressions. Then with that restriction, let's see this example is the following a well-formed expression? What is it? It's let's see. Yeah, this is the inner expression. This is the entire expression. The entire expression is again an audition of some expression and another expression. And this sum expression is actually function called expression which is not a function expression, right? The function expression is not immediately inside the addition format. It's not immediately. [LAUGH] But you know what, the result of this function call is yet another function expression. This is the identity function. This is identity function. If you apply this to that, we get another function expression. So evaluating this function called expression actually made yet another function expression immediately inside the addition expression, right? Yeah, so we don't want it to be away from the expression. Remember what we want to have is when we say it's away from the expression, then we don't want to have any runtime error, right? So this is not a good definition for that. Then what can you do about it? So is it actually possible to define well-formed as a decidable property so that we reject all expressions that produce errors? Because we do not want to have expression that produce errors at runtime and we'd like to reject them before running the expressions. But is it possible? Yeah, if we reject all expressions, don't hate me. Yeah, right, it's just kidding. So if we reject all expressions, then we can do that but that's not what we want. We want to accept some good expressions. Then is it possible to define well-formed as a decidable property so that we reject only the expressions that produce errors, not all of them, but only the expressions that produce errors? If that's possible, that'd be great. That's what we want. But unfortunately it is not possible. And actually it's well known. If we always know, so let's see this example to explain what I mean. This is an addition expression of 1 and if expression. This if expression says this condition expression ..., let's evaluate this first. And when that produces true, then we are going to return 1 meaning 1 +1 is 2. If this condition expression produces false, we return this function expression meaning 1 + function expression is an error. So depending on the condition expression whether it produces true or false, we could what? Actually solve the halting problem. If you do not know the halting problem, then search for that. It's a very well known problem that is not possible. [LAUGH] In other words, it's called an undecidal problem meaning that we cannot. Reject only expressions that produce errors. So, let's assume that there is what the entire universe of programs, syntactically correct programs. Or let's start with some programs you just write whatever you want to write, okay. So these are a set of programs but in there a self set is going to be syntactically correct program. Outside is like x + y + z, because in this language we have only audition of two sub expressions. If you have addition of three sub expressions it's going to be syntactically incorrect, right? So let's assume that this is the set of syntactically correct programs. Even in this set as we already saw, some expressions will produce an error at runtime. Just like identity, function expression plus one, syntactically correct, but at one time it's going to throw an exception. So, here we have small or yeah, set of good programs meaning they're syntactically correct and semantically correct. So we'd like to identify this set. We only want to run this set at runtime but the theory says it is not possible. So, either we just accept this and have runtime error, or we accept this and when we say it's okay at runtime there's no error. But some bad part is that we also reject this part which should be okay. But we have no choice either except wrong programs or reject some good programs. That's our dilemma, yeah. So, solution to our dilemma is that in the process of rejecting expressions that are certainly bad, also reject some expressions that are good, that's our choice. I don't want to have expressions that producing error after we checked the expression and it's okay to run. Whether I'd better reject some good expressions, I'm sorry to see rejecting them. But still when our checker says okay then I would get some guarantee that it's not going to produce an error at runtime. Okay, so that's types long story for introducing types. So our strategy is, assign a type to each expression without evaluating. So it's really important to remember that without evaluating, that's what we mean by static type. Compute the type of a complex expression based on the types of its subexpressions. So we are going to have some basic primitive types for simple expressions. And for some complex expressions, we are going to compute the type of those complex expressions by using types of their subexpressions. And we are going to discuss that from the next lecture. Here's Quiz, consider the following grammar that we just saw. What is the value of open identity function expression, plus one, plus eight, close, what is the value of this expression? Do you have an answer, right? It is not a valid expression because in this language, audition should be enclosed by parenthesis and it should have only two sub expressions. But in this expression, it has three sub expressions so it's not a valid expression. Thank you. [MUSIC]
