Hi, everyone. Today, we are going to learn First-Order Functions. What are first-order functions? You will see in a minute. The textbook that explain the first-order functions is Chapter 8. Please read Chapter 8, you'll understand this material better. Before starting the real content of first-order functions, let's review one of the most important concepts in the previous lecture which is shadowing. Do you remember shadowing? The shadowing or hiding. Let's see these two good examples. On the left we have this val x, whose value is the value of this expression. On the right, we have this val x whose value is right here, 3. Then you can see that there are two occurrences of binding of x, x1 and x2 here, x1 and x2 here. The question is, which one is shadowing and which one is not? What do you think? What is shadowing? Shadowing meaning that the value of x is right here, but x is shadowed or hidden by inner declaration of the same name. Here, x is introduced here and its scope is from here to there. This x is hidden by this inner x. But in this example on the left, this x is not yet declared. It is not yet given any value because the value of x is the value of this expression, and while evaluating this expression, we have x. X is already here, and x is not shadowing this x on the left. This is not shadowing, but this is shadowing. Then let's see functions. These are mathematical functions that you see in mathematics or in other programming languages. What are they? You can guess. There are two functions named identity and twice. The first identity function takes a parameter x, returns the argument as it is. That's identity. The second function definition twice, it takes another parameter x with one parameter x and it is x to x. It's twice. They are usually called functions. Then what do we do with functions? Why do we need functions? The very first tiny language that we started with is AE, arithmetic expressions. If the language had numbers, addition, and subtraction, and then we introduced arithmetic expressions with names, identifiers, so that we can give names to some numbers or some work that we'd like to do repeatedly so that we can just use the name multiple times. What about giving names to computation? That we'd like to give some computation, some work to do with some name, and instead of doing the same thing over and over again, we'd like to call the function. Isn't it cool? That's why we want to have functions. Now, the third language that we are going to learn today is called F1VAE. F1VAE allows us to define functions. Wow, now we can define functions that we'd like to call. Here, just like the first and second line, the mathematical function, we'd like to define functions in our language, F1VAE. How? DEF is the keyword Defined Functions, DEF. I'm defining a new function. What's that? The name is identity or twice. Open, parameter name, close, equals function body. Then we can use the function by calling their name. What I just said is when you say D, E, F, you're telling the computer that I'm defining a new function whose name is identity or twice or whatever name you'd like to give. Open, close, open, close, showing that there is a parameter. Here, only one parameter. After equals, this is the function body. When we want to use the function, we just name it with open-close argument value. Nothing surprising. So far so good. Then this is the language. This is our new language called F_1VAE. This is the concrete syntax. Now, when we define a function, again, we use D, E, F. The first ID is for the function name. Open, close. Second ID is for the parameter name, equals function body expression. This is what I just said in the previous slide. When we have this function definition, we'd like to use it. How did we use it? Either twice, open, 42, close. What's that function name? Open, close argument expression. That's it. Black things are as usual with VAE and these two red language constructs are added to define functions and use functions. So far so good? Do you see that? This is for defining functions, this is for calling functions. Isn't this something different from before? Can you see that? Remember AE and VAE, we had only one non-terminal expr and now we have two non-terminals, F def and expr, meaning that function definitions are not expressions. Function definitions are different thing. They are not expressions. We are not evaluating them, we are not getting values from them. Functions are different things. In this language, functions are not producing values, so we call them first-order functions. You don't get it yet? Don't worry, I am going to explain that later. As we saw before, this is a concrete example of using this language to define a function named twice and using the function. Later, we're going to learn non-first-order functions, which are first-class functions, where functions are values. In that language FVAE, we do not have this F with def. We don't have that. There, we make functions as expressions. Functions are going to produce values in FVAE. That's really cool. You may not see what's cool about but I'll explain that later after learning these first-order functions. Stay tuned. I really like first-class functions and I think you're going to like that too. But in this lecture and in the following two more lectures, we are going to learn first-order functions with this concrete syntax with these examples. Then, how are we going to implement the concrete texts in the previous slide? As I said before, in this F_1VAE, we have two kinds of non-terminals. Two: F def for defining functions, expr for defining expressions in concrete syntax. Then you can see, you can guess that abstract syntax will do the same thing. Yes, you are right. In abstract syntax, as usual with AEMVAE, we have trait expr and those black things, number, addition, subtraction, name introduction, and name use, they're all expressions. This new thing function called? That's also expression. It has function name and argument expression. Because function definition is not an expression, we have a special case class f with F to denote the function named f with parameter name x and the body expression b, which does not extend expr. For a second. Then what about a parser? Remember, a parser takes an expression in concrete syntax, parses that, and creates an abstract syntax. A program in concrete syntax is going to be parsed and be translated to an abstract syntax, that's a parser. The concrete syntax has two entities, function, definition, and expression. Then parser will take them as well. Now in this parser for expression, we have the usual expression, and for this function call, and what? For our function definition, we are going to have, say pre parser for function definition. As usual, you do not need to read every single line of this. But the thing that you need to remember is, these things. That in function definition, the keyword to define a function needs def. Remember, we wrote like def twice, open x close, x plus x, def is the concrete syntax keyword to signal that I'm defining a function. But when the parser identifies def, it's going to construct an abstract syntax of Fdef. There's an abstract syntax, remember Fdef, which has three fields, function named f, parameter name x, and by the expression e. That's it. Isn't it simple? Then let's interpret this new language. Interpreting this new language called F1VAE is a bit different from before. In the beginning when we interpreted the function AE if you remember, the interp function, took an expression and then produced its result. When we introduced identifiers there, to define VAE. If you remember, we added one more parameter argument to the interp function to handle names. Do you remember what it was? Yes, environment. Environment to keep mapping from names their values, and now we have F1 first-order functions. On top of VAE, we added first-order functions. Then this interp function will need one more argument FDs. What is FDs? FDs, it's a list of function definitions. You can imagine. In C programs or Python programs or Java programs, whatever languages that you are familiar with, you may have predefined list of functions. Library functions, or whatever function they are. They are usually kept in function table. This FDs is like a function table, and you can check the functions from there. Then, how are we going to interpret this code? Wow, don't worry, it's not that complicated. This function interpreter again takes an expression, on environment, and function definition list. Let's call that F for s. All the usual things that are going to be as usual, except that these interp function calls are going to have extra argument function definitions, and you just pass extra arguments for them because they do not use fs and they are going to use this expressions and environments as usual, when you have an identifier lookup the environment, when you have this name introduction, you're going to add the name to this existing environment. As usual, helper function call, what can we do about it? This is the new thing. What can you do about it? We're going see some examples and tests first. Instead of telling you how to do that, here is the way to do. You'd better think first. [Korean] If I give you an answer on how to do it, [Korean] you may feel better,
[Korean] but it doesn't help you learn.
[Korean] Before that, take a quiz,
[Korean] think through your head, and think yourself.
[Korean] Then, my explanation will give you a better understanding. Instead of giving you how to do that, this is the way to go. I will ask you some questions and I will step through the examples with you to find a solution together. We're going to do that in the next lecture, and here's a quiz for today. Which of the following results in an error? These four examples are F1 VAE examples that we just learned. What are they? Let's see. Everything defines a function named f. That's good. So far, so good. Every function definition has one parameter. Did you notice that in the concrete syntax of F1 VAE, when we define a function, we write d, e, f function name, open, name, close, meaning that in this F1 VAE, every function takes only one parameter. Oh, that's too primitive. It's not very powerful. That's right. We're more than happy to ask you to extend the language. You can extend the language to take multiple parameters. [Korean] I explain only important concepts for simplicity [Korean] in this lecture,
[Korean] so every function has only one parameter.
Every function has only one parameter, single parameter. But in real programming languages, you know that functions have multiple parameters or no parameters. [Korean] In real programming languages, [Korean] functions have multiple parameters
[Korean] or no parameters.
You can do that by yourself extending the x linkage to have zero or more parameters. I think you're going to have that as an exercise in the textbook. Let's see. Until then, until you have that extended generalized language, we have this language F1 VAE which requires to have only one parameter. Using only one parameter, what are we supposed to do? The last one, let's see. Oh, the function body is the parameter as it is. We know this function, identity. This function is an identity function, but we named it f. This identity function is defined and we call the function with number 3. So it's going to be what? Three. How about this? Oh, this is another identity function. Same here. How about this? Another their identity function even though we named parameters differently, the bodies are just giving you the parameter value as they are and their identity functions. This one is interesting. Why? We define the function named x, but in this expression we defined an identifier x. But what about this one? Isn't it cool? What is this x? Is it going to be this identity or it's going to be the function? What do you think? This one should be this function because the semantics of this function call was what? I said this is going to be function name, open, argument expression close. We're going to see the semantics more closely in the next lecture. In this example this is a function name. Here it's going to be what? Function name and ID. This function name is defined here, but this f is not defined. Oh, remember, what did we call that? Free identifier error. Thank you.
