With Unit 4 we start a sequence of three units in which we are going to explain how the function call and return protocol, if you will, is implemented. Now this implementation is non trivial and actually is quite fascinating and somewhat technical. And therefore we decided to devote three units to explaining how we have to do it. So we'll begin with a preview in this unit, then we'll do a simulation to see how it actually works behind the scene. And then finally, we'll discuss how to actually make it happen. So I'd like to begin by saying a few words about the notion of function execution. As you well know, a computer program typically consists of several functions, or a JAVA program consists of several methods typically. And if the program is doing something not trivial, it may well consist of dozens of methods which are spread over multiple classes and so on. And yet, at any given point of time, only a very small subset of these methods are actually doing something. For example, foo calls bar and bar calls square root. And square root may call something else. And all these functions that participate in this example of execution are, we call all these functions taken together the calling chain. So the calling chain is a completely abstract notion that describes the chain of command, so to speak. So, foo called bar, bar called square root, and that's where we are presently at. Now think about it, from an implementation standpoint, every one of these functions has some state, it has some private world. And this private world must be maintained as long as this function exists on the calling chain. So what is this state that I refer to? Well, the function state is also an imaginary concept that we use in order to refer to the function's working stack and memory segments. And so, taken together, we call these things a state. And here is what we have to do with a state. When the function enters its execution, when the function starts running, we have to create a state for this function. We have to give it an empty working stack, we have to give its local segment, argument segment and so on. And then the function starts doing its things. And as long as the function works, we have to maintain this state. In particular, if this function will call another function, we have to save this state somewhere and know how to return to it when this function ends its execution. Now when the function returns, well, then at this point we don't need the state anymore. So we can recycle it in order to be good citizens and in order to make sure that the memory would not be completely consumed. So that's what we have to do with the function's state. So in general, when a caller calls a callee, we will have now two states, right? We'll have the state of caller we'll have the state of the callee. Once the callee starts running, the state of the caller has to be saved somewhere. And when the callee terminates, we can reinstate the caller state and continue its execution. So how should we do all this? How should we maintain the states of all the functions up the calling chain? Because remember, the calling chain is not just two functions. It can be this function calling this one, calling this one, calling that one. It may be several functions deep and we have to repeat what you see on the slide here for every one of these couples of calling and caller and callee. [COUGH] So what should we do, what do you think? What should we do to save all these states? Well, think about it and then we make one observation. And the observation is that the calling pattern is LIFO, which stands for last in, first out, right? The only function that can return is the function which is currently running, right? Which is the function at the end of the calling chain. And all the other functions are waiting for it to return. So once this one returns, the calling chain shortens. And then this function does something. And then it returns and the calling chain shortens and so on. So it grows like this. Let me sort of go this way. It grows like this, and then this one returns, and this one returns. And then this one returns. So it grows this way and returns this way. And I do this, does this remind you of something? Hey, that's a stack, right? I mean, what I describe here looks like the stack that we dealt with all along. So maybe we can use the stack in order to save and retrieve all these function states. What I'd like to do next is to illustrate how this ingenious usage of the stack is going to help me save and reinstate the states of the according function. So let us start, as usual, with the big picture. And the big picture is that we want to compute the product of 17 and 212. How do we do it? Well, the function is doing something. It sets up for the call. And then it says call mult 2, informing the implementation that two arguments were pushed onto the stack. And then, boom, something happens and I'm going to get the product of these two numbers. That's the view of the caller, right? So the net effect of this operation is that the function arguments have been replaced with the functions value, which is exactly what I want. And now, to the gory details. And the details are as follows, the function is running, doing something, right? So at some point it prepares to call another function. So, it pushes some values, right? Now, if I'm the implementation which is doing all this, I don't know really that the function is preparing to do anything. But at some point the function says, call foo nArgs, okay? And nArgs is the number of arguments that we pushed on to the stack. Well, once I see this command, I know how many arguments were pushed onto the stack And it may be so many arguments, and I call it by the variable nArg. And at this point, I know where I can set the arg pointer. Remember the segment pointer, arg? Well it should be right here, right? The arg pointer should refer to the base address of the argument's segments in memory. So from now on, I know that what is above the arg is the working stack of the caller, and what is below the arg are the arguments of the callee. I mean, the arguments that the callee is going to use. Now what else do I have to do as the VM implementation? Well recall that previously was said that before we jump to execute the called function, we have to save the state of the caller. Now, what is the state of the caller? It consist of the working stack of the caller and the current segments that it uses. Well, the working stack is safe, right? I mean, look at the stack, it's right there. The working stack of the caller is already on the stack, so it's safe where it is. And now I have to save the segments, and I also have to save the return address, within the caller's code. Now taken together, we call these things the function's frame. Okay, so the frame is just a fancy word that we use in order to refer to the return address and the saved memory segments of the caller. Now, put yourself in the shoes of the VM implementation, it can access all these pointers. I mean, all these pointers are variable, right? The arg, the LCL, THIS, and THAT, they are available, so I simply push them onto the stack. And this way I save the base addresses of these segments, and therefore I will be able to return to them later on. Okay, the next thing that I can do is finally, after I took care to do all these very responsible things, I can happily jump to execute foo's code. So that's what I do when I have to field or service a call command. So we came here because there was a jump to execute the foo function. Now think about it, if I jump to execute foo, well I'm going to hit the command function foo nVars, the beginning of the foo function. nVars informing how many local variables I expect to have, I now is foo. So the VM implementation looks at this, and it has to service this command. And it does it as follows. Well first of all it, creates a local variable segment for the called function. Now, I know exactly how many variables I need, I need nVars variables. And I also have to initialize them to 0, so let's do that. I push nVars 0s on to the stack, and once I do it, I also know that from now on, I can refer to these values on the stack as local 0, local 1, and so on. If I want, I can use this syntax to refer to these words in the memory. And once we do it, the called function is ready to take off and start running. So let's assume that the called function is running and doing its things. And in the process, it grows its working stack, and it now has a working stack of its own. And then at some point, it is going to return, because, all functions return at some point. So at some point the called function is going to prepare to return. Now the preparation, from the called function's standpoint, requires that I push a return value onto the stack. So we do this, notice we push a return value at the bottom of the stack, and then I say return. So now VM implementation has to service the return command, has to implement this command. How do we do it? Well, here's what we have to do. First of all, we have to take the topmost value from the stack, which we know is the return value, because these are the rules of the game. And we have to copy it onto argument 0, why? Because in the net effect of this operation, I want to replace the values of the arguments that the caller pushed with the return value. So we do this, right, we take the return value, and we copy it on to the word which can be referred to using argument 0. The next thing that we do is, we want to restore the segment pointers of the callers, right? We want to take the saved LCL, the saved ARG, the saved THIS, the saved THAT, and turn them into the current LCL, ARG, THIS and THAT. By doing this, I'm going to reconnect, so to speak, with these memory segments. Then I want to clear the stack of the called function, which is no longer relevant, because the called function is going to die in just a few milliseconds. Then I have to set the sack point for the caller. And the stack pointer for the caller should be located just after the return value, right, just after argument 0. And after I do this, I have to finally jump to the return address in the caller's code, and continue executing the caller's code. So after I do all this, here's what happens, okay? I get the return value, and the stack pointer is positioned just after this return value. And as far as the caller is concerned, he's back in business, and he can continue to do what he did before. Now before we go on, I'd like to make some peripheral comments. First of all, this may sound very complex, and indeed it is complex. And it shouldn't be surprising that it's complex, because if you think about it, we're actually building here a little brain. A very primitive brain, but a brain nonetheless. Because it reminds me of, let's say you have a robot which is designed to clean your rugs. Well that's very nice, so the robot is roaming around, cleaning its rugs, cleaning your rugs. And it does it because it runs a program that tells it how to clean the rugs. Now I assume that at some point in a future version of these robots, you will be able to sort of sit back at your home and watch the robot does its cleaning. And then at some point you will be able to say, hey robot, make me a cup of tea. Then the robot will have to stop and start running another function that turns it around and leads it to make a cup of tea. And then it will take the cup of tea, give it back to the master. And then it will say okay, so this thing is finished, now I have to go back to work. Yeah, there was another function of cleaning the rugs, so I'm jumping to this function. My world is restored, I have all my memory segments and then I can continue cleaning the rugs. So that's what we're implementing here. We're implementing a little brain that can do several things and not necessarily the same time. But it has this wonderful capacity to stop what it's doing now, start doing something else. And by the way, while he was doing the cup of tea, I could have stopped in and say, and you know what? Before you do the cup of tea, go answer the doorbell. And so he will put this thing on hold. He will go to answer the doorbell, and then will say, okay, where was I? I was making a cup of tea, we'll go back to make a cup of tea. Give the cup of tea, where am I now? Yeah, I'm supposed to go back to do the rugs. So we have to implement here something which is very sophisticated. So there is no wonder the implementation is not trivial. So that's one thing that I wanted to say, and the other thing is, is that we are now in a position to introduce this notion of what we call the global stack. And think about it, above this stack which we are growing here there are more states of functions that are up the climbing chain, right? Because in this example, we talked only about the caller and the callee. But there are many other pairs of callers and callee up the counting chain, and we have to maintain all these states also. So we get a very large stack which we call the global stack that contains everything. And contains all the information which we need in order to implement and service the runtime of this program not only the current function but the entire program. Now I can refer to some segment or some subset of this global stack here using the term block, which I just made up. And notice what the block contains. The block is we can call it, it's the world of the currently running function, okay? Now what does it include? I am now the currently running function, so my block contains, first of all, my argument segment. You see the top we see argument 0 argument, these are my arguments. Then the block contains some gray material that I don't deal with at all because this is some saved information that belongs to my caller. So none of my business, then I have my local segments and then I have my working stack. This is my world, I can operate within this world and do whatever is necessary. So this is the block of the currently running function, and the global stack contains many more such blocks. One block for every function up the calling chain, so that's the global stack. And before we go on actually, two more comments. First of all, notice that the saved frame of the caller contains only four memory segments, right? Local argument this and that, and if you remember from the previous model actually eight memory segments, right? So we also have constant, temp, pointer and what did I forget? Constant, temp, pointer and static, okay? So I argue that these four segments, constant, temp, pointers, static don't have to be saved, okay? And you can think bout it yourself, why we don't have to say them. They don't belong to the world of the function, they belong to some other parts of the machine that we're building. If you don't complete the seat, you will see that in the future units. So we save only the segments which are relevant to the current function. This is one observation that I want to make, and the other one, which is kind of more general, is that what we really see here is the stack in all its glory, right? Because the stack is such a remarkable data structure, it not only allows me to around all my algebraic operations and logical operations on the stack. But I use the very same stack not only to execute everything in the program. But also to execute all the behind the scene apparatus that is needed in order to service this program, which is currently running, which is really remarkable. Think about it, we have here, both sort of the operational memory of the currently running function and program. And we also have everything else, the return address, and the memory segments. And everything else is saved on the same stack, and everything works perfectly. So this is really a brilliant apparatus. I mean this whole idea of using the stack to support the runtime of the computer program. We really see why the stack is so effective. Okay, so that's the global stack and I want to recap what we did in this unit. Basically, we described how to compute a function in the world of the VM. Very simple, from an abstract standpoint, all you have to do is push as many arguments as the function requires. And then all you have to do is say call foo. And then boom, you're going to get the result, right? And the result is going to be the value of this function, value in these arguments. And it's going to replace the arguments that you pushed, and that's it. So from the abstract standpoint, life is very, very simple. From the implementation standpoint, boy, we just went through what has to be done and we haven't even gotten to the details yet which we'll get to in the next unit. So it's incredible to think about the difference between the abstract view of the world, which is sort of an armchair view of calling a function. Call this function, boom, it happens, I get the result. And all the work that has to be done, behind the scene and the color doesn't care I mean it just does the call and gets the result. And this reminds me of this is saying by Arthur C Clarke that any sufficiently advanced technology is indistinguishable from magic. Because from the abstract standing point, we had magic. And you know how much work we had to put to make it happen. So we can also say that any sufficiently advanced magic is also indistinguishable from a lot of work behind the scenes. And in the next two units, we'll continue to talk about this lot of work which still has to be done in order to implement the function call and return protocol.
