If you recall, we decided to present the function call and return implementation using three different units. And we already went through the preview of what we want to do. We gave sort of an informal runtime experience of the function call and return in action. And in this unit, we are going to actually describe how we're going to make it happen, how we're going to implement it. So let's get started. Well, we begin with some VM code, which is quite arbitrary and uninteresting. And yet we're going to use it to illustrate a few things. So we have a function called Foo.main and another function called Bar.mult, and we assume that these functions emanate or they come from presumably two different classes. Right, I mean VM code is expensive at times. It's something which is typically written by compilers. And therefore, it is safe to assume that if this is compiled Jack code, then the compiler was applied to a directory that included two different class files named Foo and Bar. And Foo and Bar had at least one function written in them. And we see these functions here, Foo.main and Bar.mult. And we see that at some point in main's code, it computes this expression that we see in the comment. So it pushes 19, 3, it calls Bar.mult and then Bar.mult does some work and that pushes a return value and returns. So there is nothing really new here. Except that I emphasized the fact that a function may well call another function which historically belongs to a different class. But once everything is compiled into VM code we lose this notion of classes and what we get is just a long list of functions that have a full name. Which is the class name dot the function name. All right, so we have a caller and callee, and that is under a typical situation that we discussed. And we have a typical function call and return a command that we are dealing with all the time. And here is the contract by which these two parties must play. So let's begin with a caller's view of what is going on here. Before I call another function, I must push as many arguments as the function expects to get. So if I call square root, I know that they have to push one argument, if I call them out they have to push two arguments and so on. So the assumption is whoever wrote this VM code, whether its a human being or a compiler, well you know he knows what he's doing so he knows how many arguments to push. Next I invoke the function by saying call function name. N args whereas n args is the number of arguments that I pushed before. After the called function returns, the argument values that I pushed before the call are going to be replaced with the return value that always exists. So I know that when the function returns something new is going to be at the top of my stack, and this something new is the return value. After the called function returns, all my memory segments, magically, are exactly the same as they were before the call. Except that Temp is undefined and some values of my static segment may have changed, because the static segment is visible by all other functions in the application. So if maybe that some function that I called or function that were called by the functions that I called changed some statics, and that's just fine. All right, what is the contract from the callee's perspective? Let's see, before I start running my argument segment has been initialized with the argument values that were passed by the caller. I don't care how, I just know that it's there and it's available to me. My local variable segment has been initialized and all my locals begin with zeros. Once again I don't care how but it's there, my static segment has been set to the static segment of the class to which I belong. And since it's a compiled class, it's the VM file to which I belong. Memory segments are this, that, pointer and temp are undefined upon entry. My code may well use them, but it's responsible to store some sensible values in them in case I intend to use them. And finally my working stack is empty. One more thing that is very important in the contract is that before issuing a return command, I hereby agree that I'm going to push a value onto the stack. So, once again we see something that we've said several times. The function must return something before it returns. Must push something onto the stack before it returns. Now think about the situation in which this function began its life as a void method. Suppose it was a void method or void function at the Jack level. And void functions are not supposed to return a value, and we just said that you must return a value. Well, indeed this is the case. Even if you are a void function, you must return a value. So you push something, you can push zero. And it's the caller's responsibility to do something with returned values. So if the caller knows that he called a function which is supposed to be void it can simply post away the value that was returned by the callee. If you didn't completely understand what I said here about this observation about void functions, then don't worry about it. We'll get to it again when we talk about the compiler. So we described the function, call and return protocol from the perspectives of the caller and the callee. And now, we tend to describe the perspective of the implementation, which is the third party in this dance here. Now, one way to realize the VM implementation is to write a VM translator. And a VM translator is a program that reads the VM code and translates it into Assembly, and in our case, it's Heck Assembly And so, the VM translator will go through the code, and focusing on the function commands, it will, for example, when it reaches the call Bar.mult two, it will generate code that realizes this call. When it gets to the function command it will generate code that realizes the function, same with the return. And what we'll do from now until the end of the unit is that we'll zero in on any one of these things that I just described and we'll explain what exactly the VM translator does. Now, the big picture is that the VM translator is going to generate code that, reading what is written here, it's going to save the caller's state, the state of the Foo.main function. Then it's going to do a few more things to set up for the function call, and finally, it's going to say, go to the name of the function. So, presumably, the VM translator at some point will generate a label which is the name of this function, and, indeed, if you look, if you take a few more lines down the target code, you will see the label, Bar.mult, so this is how we represent the entry point to a function in assembly, in the translated assembly code. All right, so now we're going to explain exactly what we have to do with this psuedo code here on the right. So let's see, handling a call, we'll begin with some global stack that includes all sorts of stuff, and it also, obviously, at the tip of the stack, we see the working stack of the current function. So the caller, the current function, is doing all sorts of things, and then all of a sudden, we encounter a call, some other function command, and we have to implement this command using assembly, what do we do? Well, since the call command includes the nArgs parameter, we know exactly how many arguments have been pushed before, right? nArgs, so we know how many of the values on the stack should be treated as arguments, and here is what I do. Okay, the first thing is I push a label onto the stack and later on I'm going to use the same label as the label to which I'm going to return after the called function terminates. So let's keep this in the back of our mind, I pushed some label that I generated, we see it on the stack now. Then I push LCL to save the state of the local segment, my local segment. I push my ARG, saving the state of my argument segment. I push THIS, I push THAT, and then I reposition ARG, now, let's think about it, ARG should be repositioned for the called function, now, where should we reposition ARG? Well, obviously, we should reposition it at the beginning of the ARG segment, which is right here, right? Now, where is this address? Well, I can calculate it because, I know how many things I pushed, I pushed five values, so I do SP minus five. And then, previously, the caller pushed nArg's arguments, so I know exactly where to position ARG for the called function. Then, I do LCL equals SP, and that's where I'm going to start to push the local variables of the called function, so that's just fine. And finally, I go to execute the called function, okay, so I go to execute the called function by simply writing the command in assembly, goto, and the name of the called function. And now I do something very tricky, I insert into the generated code stream the label that I pushed before, right? Remember I generated the label, I gave it some agreed upon name that, I have to agree exactly on all these things at some point, and then I push it. So first I generate it, I'm sorry, first, I generate it, I push it to the stack, and then later on, I output it, or I emit it, into the generated code stream, so that's exactly what I have to do in order to implement a call command. Now, just to explain what is going on here, this is pseudo assembly code, and you have to take this pseudo code and translate it on a piece of paper into actual Hack code, should you decide to implement this thing on the Hack platform. All right, moving along, we know how to handle call, so now I want to treat the function command, the command that signifies that the function begins in the code. So let's read the big picture, the big picture is such that whenever we hit a function command, the first thing that the translator does is it takes the function name and generates a label, and this label will serve as the entry point to the translated assembly code of this function. And then we simply have to write some assembly code that handles the setting up of the function's execution, so let's see how we do that. Here's my stack, and the stack is exactly as it was after the call happened, because remember, when do we hit the function command? We hit the function command always just after a call command, right? Call, and then I hit the function, so, this is the same state as we had at the end of the handling of the call, and now we encounter the function, function name nVars, which inform how many variables, how many local variables, the call function expects to have. All right, so what can I do? I can generate the following assembly code, first of all I take the function name and generate this label, as I said before and I write it into the generated code stream, and then I repeat nVars times push zero, right? I know how many local variables I have to create, and so I create them, and I simply push as many zeros as necessary, and I basically build the local segment of the called function. And that's it, right, that's all I have to do, and now the function can start doing its thing. So it will do its thing and at some point, it will want to return. Right? And this will happen in our example here. And now, I have to handle the return commit. So, reading the big picture, I have to generate assembly code that moves the return value to the caller, reinstates the caller's state, and then does a go to Foo's return address, which is the return value in the caller's code. If you look at the middle of the code pane, of the generated assembly code, you will see this address there. Foo- $ret.1, so presumably this is the returned value that the VM translator created when it handled the call. If you recall the call command involved generating a return address and so I see that I go to exactly. That's return address, and the question, of course, is how do I know how to do it? And that's what you'll see in the next slide. All right, so, the called function did some work, right, and it grow its working stack and our working stack includes all sort of stuff that the called function created. And then, I have a return command. Now, because everyone is assumed to play by the rules I know. That once I hit the return command, I know for sure that the value at the top of the stack must be a return value. Because everyone plays by the rules and a function must push a return value before it returns. So, the next thing that I have to do is as follows, and this is a little bit involved but it's really not terribly complicated. First of all, I'm going to create some temporary variable, which I call endFrame, and I'm going to assign the value of LCL to it. So if you look at the Stack diagram you will see that end frame indeed points at the end of the frame in the host RAM. The stack is obviously stored in the host RAM somewhere. All right, now the return address must be the contents of the word end frame minus five, right? So, end frame which is like LCL, if you go minus five you hit exactly the address of the return address, right? The address of the return address. Now, I need the asterisk because I want to look inside. This word and this is how I get the return address. And I put it in yet another temporary variable which I call RETADDR return address and I sort of put it aside for now. And I have to do all these things in assembly, right? All right, so the next thing that I do is I reposition. The return value for the caller. Now where should the return value should be. The return value should be copied on to zero right, and I already have a pointer that is located right on our zero and this is the pointer ARG. So, I have to perform the command, ARG equals pop. Because the pop is going to retrieve the return value off the stack. And then, I take this value, and I put it in ARG. So, the result? Look at the stack diagram. The result is going to be. This I popped the return value and I copied it onto ARG okay, or to the address that arg refers to. All right, moving along, I know where the stack pointer should be. The stack pointer should be just after ARG because this is the view That the caller expects to get. The caller expects to see a return value. And then continue to do his work. So, SB becomes R plus 1. And now, I can begin to recover the various segments that I saved on the stack before. So that should be N frame minus one. The contents of N frame minus one. This should be N frame minus two R should be N frame minus three and LCL should be N frame minus four. So I recovered all my memory segments and finally I can jump to the return address. Where do I jump? I jump to the address that I retrieved before, that I popped from the step before, and put it in the variable retAddr. Okay, so this is the logical that I have to now implement in assembly, you have to implement in assembly when you write the VM. Now another thing that I want you to notice is that once I set SB below ARG, I basically communicate implicitly that everything below SB is it's just game right. It's recycled, it's dead, it's irrelevant. Because the next push is going to override the memory location where SB shows. Then SB/s is going to be down and the next push will do this. So, all the, the entire block which is marked as recycle is no longer relevant. So effectively, that's the situation that now the caller is going to see. The caller is going to see the return value at the top of its working stack. And the stack pointer is going to show to point at the next word in the memory. And that's exactly what we wanted. So we did it, we showed how to implement return and basically we show how to implement that everyone of the function calling commands. So to recap, this is our global stack and we showed how to generate the assembly code that, when executed, will end up building and maintaining this global stack during run-time. And we didn't give you the actual assembly code, but we did give you cell door assembly. And this code, when you write it in Hack would actually do everything which is necessary in order to build this complicated world that we describe in the last three units. And the last command they want to make which I think is interesting, is that the code that I showed you is completely language and platform independent. So, you don't even have to commit yourself to the hack platform. The specification that I gave you here is actually a specification on how to implement our VM language on any given target platform. We didn't say anything about where this thing is going to be stored in memory or which assembly language I want you to use. Use whatever you want and this is important because we just gave a universal recipe for implementing our VM language on any hardware platform, any computer out there. But of course in this course, we will do it in heck because it's simply this is the computer that we are playing with in this particular course. All right, so basically up until this point, we implemented the three-quarters of the language and with this unit we are now putting a check mark also on the function commands and we are done implementing the VM language. In the unit we will add a few more technical details on how to do it on the Hack Platform and I'll see you there.