In this unit, we will begin to discuss functions. And we'll start with the abstract view of functions. Which is to say that, if you were a VM programmer, how would you use functions in your code? So as you well know, high-level functions can be extended using subroutines, functions, procedures, methods and so on. And you may ask yourself where all these names come from. Well, different languages use different terminology to describe what we will call functions. And we don't have to dwell on this, everyone understands what is a function, it's kind of a black box artifact. You give it some arguments, push a button, the function does something and returns the value, that's a function. And once again, different languages, for historical reasons, call these functions with different names. All right, so moving to our VM language, we already took care of all the commands that you see here. And now we are finally beginning to talk about how to use, and how to implement, the notion of functions. All right, so here's an example of where functions come to play. The high-level code may say something like, square root of a certain value, which is the result of evaluating this algebraic expression. And when the compiler is asked to translate this code, it will produce the following Pseudo VM code. Well first of all, we have to evaluate the expression within the parentheses, so how do we do it? Well, we start with push x, push 17, sub, this will give us the result of x- 17. Then we do push x, push 5, and then we do something that you haven't seen before, we call the function Math.multiply. And Math.multiply is a function which resides in a class called Math, which is part of the operating system that surrounds our virtual machine. So our virtual machine is allowed to interact with this operating system. And because multiply is not part of the VM language, we are lucky to have a multiplier method that knows how to compute the product of two numbers. So we use the services of this function. Now multiply will operate on x and 5, it will replace x and 5 with the result of x*5, that's the rules of the game. And then I can carry out the addition of the result of the multiplication and the value of x. Then I can call the square root function, which also part of the math library of the host operating system, and so on and so forth. So we see that the VM language features two types of operators, if you will. First of all there are the fixed operations, which are the part of the language, add, subtract, and so on. But there only so many such operations. If you want to use other operations, well, you either use functions that someone else has already written, like Math.multiply and Math.sqrt. Or you can write functions of your own. And once again, you have this wonderful freedom to create and use as many functions as you fancy. In that respect, the VM language is unlimited. You can extend it as you please, which is incredible. And here's another interesting observation. Applying a primitive operator like sub, as we see in this example, has exactly the same look and feel as applying an abstract function like Math.multiply or Math.sqrt. In both cases, the rules of the game are as follows, and it's very important to listen and understand what I say. The rules of the game are such that, if you want to call a function that expects to get, let's say three arguments, then here's what you do. You push the three arguments onto the stack, and you call the function. And then some magic happens, and the result of the function is going to replace these three values that you pushed earlier onto the stack. So the values or the arguments that you pushed disappear, and instead, what appears on the stack is the return value of this function. If you will follow this logic through the example, you will see that it makes perfect sense. And I recommend that you will now pause the video, take a blank sheet of paper, draw an empty stack on it, and just go through the motions here. Go through every command and see how the stack grows and shrinks until it comes back with the right value, which is the result of this computation. You can make some assumptions about the value of x if you want to make your life easier. But that's not important. What's important is to understand that once again, calling the function and calling a built-in command has exactly the same look and feel. And this is some very elegant feature of the language, which I hope you appreciate just as much as I do. All right, so how do we define a function in the VM language? Well, here's the function in its source view, in some high-level program. So what we have chosen to do here is to revisit the multiplication function that we used in the previous module. So this is our own multiplication. So we are going to shortcut the multiplication method of the operating system. [COUGH] Excuse me, and we'll use this one instead, because I want you to see the code. And repeating a comment that I said before, which is completely peripheral to this discussion, this implementation of multiply is very naive and inefficient. The Math.multiply however, is a very sophisticated and efficient operation, and we'll discuss it when we develop the operating system in the last module of this course. All right, so the compiler goes to work. Translates this high-level mount into Pseudo VM code. And what you see on the right hand side is the final real VM code that will actually be generated. The Pseudo VM code I show you just so that we can easily discuss The example but as you know, we don't have any symbolic variables in VM programs, so the real thing is shown on the right hand side. Now one interesting observation here, well, it's not interesting, it's technical, is that the function definition syntax begins with the word function. Then comes the name of the function, mult. And then comes an integer, which is either zero, one, two, or some other positive or non-negative numbers. And this integer informs the implementation how many local variables this function is going to use. So function mult 2 implies, here starts the function. The name of this function is mult, and it's going to use two local variables. Now why we have to mention how many local variables we need is something that we'll understand in the next unit, not in this one. All right, so what I do here is repeat the same mult function that you saw before in it's VM version. And I also added line numbers just for reference, so we can have some common language. I also want to introduce some code that shows how we use this mult function. So here's a function called main, that at some point includes the command call mult 2. And notice the syntax, call mult 2. This syntax implies the following, Call, I'm going to call a function. The name of the function that I want to call is mult, and the following number informs how many arguments were pushed onto the stack before staging this call. So notice what the VM programmer did here. The VM programmer pushed the constant eight, then she pushed the constant five, and then she called mult. So the VM implementation knows that not only we have to invoke the mult function, we have to pass to it the arguments eight and five. We know that we pushed, because the programmer informed me that she pushed two arguments onto the stack. Now in the function calling terminology, the calling function is sometimes called Caller and the called function is sometimes called Callee. So I'm going to use these terms interchangeably throughout the following examples. Now what I'd like to do next is to go through some runtime simulation that will sort of flesh out how this program actually, how these code actually gets executed. So, let us begin with the main view of the world. So I'm going to stop this simulation, imagine it with the simulation in certain points of interest. So what happens after line three was executed. So let's look at the code. In lines one, two and three, I pushed three, eight and five. So the stack is going to contain three, eight and five. And then we commence the call, we commence the command, call mult 2. Well, this is a rather dramatic turn of events. Because the main function says, I now have to call some other function. And therefore, we have to put the main function on hold and go to execute this other function, which we call the mult. So, here is the view of the mult function and let's see what happens after line zero. After line zero gets executed, I get several things. First of all I get an empty stack. Now when I say I, I mean I'm now the mult function. The second thing that I get is an argument segment. And notice that this argument segment contains the exact two values that were pushed by the caller. So, I get to see these values and not only to see them, I know how to call them. They are called argument zero and argument one, for me, in my world. And then another thing that I get is two local variables which are initialized to zero. Now, why do I get two local variables? Because look at the function declaration command, it was function mult 2. So the VM implementation prepared for me a segment called local, with two local variables, which are initialized to zero. So moving along, what happens after line seven is executed? Well, let's go through all the commands from zero to seven. We do a push constant zero. So we push zero to the stack. And we pop this zero onto local zero. So that's not terribly interesting because local zero was zero before, so it will remain zero, fine. Then we push one onto the stack and we pop it onto local one. So the local segment is going to look like this, right? Zero and one. Then there's a label loop, great. And the following thing is pushed local one onto the stack, but actually before that, the argument segment remains the same because we didn't touch it. So let me sort of put it on the screen. And now going back to command six, we push local one onto the stack, and then we push argument one onto the stack. So what we'll get, local one is one, argument one, is five. We get these two numbers one and five. And then, we go through this whole loop in which we compute the product of the two given numbers, and the two given numbers are the arguments eight and five. So we compute their product, we get 40, believe me, I checked this code. And according to the code that was shown in the previous slide, the product is accumulated into local zero. So what happens after line 20? Now we are at the end of this computation, so local zero contains the product 40. Local one contains the value of what we called n in the high level code. You have to go to the previous slide to see it. And we stop when n exceeds the second argument. The second argument is five, so local one will be six. That's how we know to stop the code, and the stack now contains 40. Why? Because we did push local zero. Look at instruction number 20. This instruction takes the value of local zero and puts it onto the stack. Now we do it because we want to return this value to the caller. And indeed the next command is return and the VM implementation knows how to handle return. And in particular, when we say return the VM implementation, takes the top most value in the stack of the callee and it does the following trick. It takes this value and it puts it on the stack of the caller instead of the arguments that were pushed previously. So now we go back to the main function. The mult function is gone and forgone. And all its memory resources have been recycled in a process that we haven't seen yet. And now going back to the view of main I get this, right, because I pushed 8 and 5, I called mult, I got 40. That's what I expected to get. And then at line 5 of main, I add up these two numbers and I get 43, very nice indeed. So notice the difference between the abstract view of main and what actually transpired, right? Main pushed to argument said multiply, boom, it got the result. It went onto compute add as if nothing happened, but in real, a lot happened behind the scene. So how should we make this abstraction actually work? What we see here is exactly the same code that we had before. And I'd like to now take the view of the implementation. I mean, what do we have to do in order to make this magic here work? And let us begin with a call, right? That's where the story began. We called the function, a new momentous event that we are now dealing with. Well, here is what I have to do. For each function call during run-time, the implementation has to do the following things. First of all, it has to somehow pass the parameters, we also call them arguments, from the caller to the callee. Somehow, we have to make this handshake. Then we have to determine the return address within the caller's code. Because think about it, we are going now to venture into a new adventure and when this adventure is going to be completed, we have to return exactly to the next command in the caller's code. So we have to remember this address, somehow we have to remember where to return, so we determine the return address. Then we save the return address somewhere. I mean, what is, when you say remember it has no meaning, right? We have to save it somewhere in memory. And we also have to save the current state of the caller. And the state consists of the working stack of the caller, the memory segments. Everything has to be saved so that when we return to the caller's code, we will be able to sort of recreate the private world of main and continue executing as if nothing happen, right? So we have to save the state of the caller, which includes the return address, and only then we can allow ourself to jump to execute the call function. So all this somehow has to happen in order to implement and service a call command. Now what about return? Return is also quite involved, right? Because here is what I have to do whenever is an implementation, whenever I have to deliver a return command. So let's see. I have to return to the caller the value that was computed by the called function, okay? And here you see that there is an underlying assumption, an implicit assumption, which I had to make it explicit, but I'll do it now. It is required that the callee, the called function always pushes a value before it returns. This is part of the rules of our game. Before you make a return, you must push a value onto the stack. And this is the return value. So the implementation knows that the topmost value on the stack must be the return value. So it knows that it has to return this value, somehow transport this value back to the caller. After doing this, by the way, instead of just saying transporting back to the caller what it actually has to do, it has to take this return value and put it at the topmost value. It has to push it onto the stack of the caller, that's what it has to do. But before it makes its push, it has to remove the arguments, right, as I explained before. So it's even more involved than that. And then, after doing the return value, because the implementation is a good citizen, it has to recycle the memory segments and the memory resources, and the stack and all the stuff that was used by the called function because the called function is irrelevant now. Then we have to reinstate or recreate the world of the caller, which is consisting of its saved working stack of memory segments. And only then we can jump to the return address in the caller's code and continue executing it as if nothing happened, right? So this is the view of the implementation. And what we'll do in the next three units is we'll actually make this implementation work.
