I wish to remind you that, because the function call and return implementation is rather hairy, we decided to describe it in three separate units. And we went through a preview of what has to be done, and I suppose that by now you understood maybe 50% of what I explained. And in the next unit, in this one, you will understand another half of the remaining 50%, and then in the third one you will understand everything. So what I'd like to do next is to simulate the function call and return protocol in progress. So let's see how it actually works. And to illustrate it, we'll take an example of a recursive function factorial. And this is how the function may be written in some high level language like C or Java. And I'm sure that you've seen this function before, so I'm not going to spend any time on it. And what I do want to show you is what the compiler will do with this function. And basically the compiler, if applied to this source code, will generate the following VM code. Assuming that it's a two-tier compiler, like that of Java or C# and some other languages. So let's see. We start by compiling the main function, and we want to compute factorial three. So we push 3, we call factorial, and return. That's what we were asked to do. Moving along, I now have to compile the factorial function. So we start with the function declaration, function factorial. And then we evaluate the condition n equals 1. And because we have to do things in the VM way, we push n, we push 1. We ask if they're equal, and if they're equal we go to a BASECASE, which is a label that the compiler is going to generate and insert into the generated code stream later on. Okay? So if we have to go to, we'll go to a BASECASE. And notice, by the way, that when we push n, push 1, and do eq, the eq is going to consume these two values, right? And return true or false, and based on this we're going to make the jump. And now we have to implement the else part of the if. So, in the f spot, we have to evaluate the expression. Actually, return the value of the expression n times factorial(n) minus 1. So we push n, and then we turn to compute factorial(n) minus 1. Well, how do we do it? We push n, we push 1, we sub. We get n minus 1, we call factorial on this value, and then we call the mult function that we wrote before in order to multiply the result of the factorial(n) and we return. So that's the end of the else. And finally, we need to implement the BASECASE, and so we put this label that you generated before. We label BASECASE, and in the BASECASE is very simple. We push 1 and return, because that's what the source code wants to do. And that's the end of the story. We also need to implement the mult function, because we decided to use mult instead of math multiply. It doesn't really matter. But I decided to omit the code of mult, which in the context of factorial, is kind of a service function. We use it just to multiply things, and it's not terribly interesting. All right, so that's the pseudo code of factorial, and here is the final code. And we now go to explore how it actually works. But actually, before we do this, I'd like to say something peripheral and to point out that, once again, I've shown you how the compiler plays its magic, but I didn't say how it actually does it. I showed you the result of the magic, and you may be wondering how is the compiler, how it knows how to generate these labels and so on and so forth? Don't worry about it. We'll spend a whole module, in fact two modules, explaining how the compiler operates. But we can stop for a minute in order to appreciate the beauty of this compiler. Because, look at it. The source code consists of something like, I don't know, ten commands? And the target code consists of something like 20 commands. And it's remarkable, right? We are compiling a high level program, and the target code is only twice as long as the source. See, that's the beauty of a two-tier compiler. We don't have to compile all the way to machine language. If we had to compile all the way to machine language, then there would be no way that I could possibly explain to you the target code. But here, we compile to a super elegant intermediate VM language, and therefore, the result is very elegant. And the compiler doesn't have to work hard. So the compilation task is not immense, moving from Java to Bytecode, moving from Jack code to our VM code, is not such a big deal. I mean, lots of work, but still very manageable. We'll get to it, once again, in modules four and five. So stay tuned, we'll get back to this later. So, what I described so far was the so-called compiled time, and now I'd like to turn to explain what happens in run-time. When in run-time, we are executing this program. So main starts running, and it informs that it has 0 local variables, which is very nice. And then, main pushes, so it starts with an empty stack. It pushes 3, so we get 3 on the stack. And then we have the call factorial 1 command, and notice that the 1 informs that 1 argument was pushed onto the stack. So we can refer to the topmost value now in the stack as argument 0, because we know that this value should serve as an argument, right? Well, now we have to service the call command. So here's what we do. The first thing that we do is we have to save the frame of main onto the stack. So we save it, okay? Now the blue dot is something that they added for cosmetic and pedagogic effects. And the blue dot shows the return address in the given code. And notice that this is exactly where we want to return to after factorial finished its operation, right? We want to compute factorial and go to the next command, the next command's return, and therefore the blue dot is correctly positioned in the code. And we save this return address, the blue, on the stack. And then, moving along, we jump to execute factorial. And so we have 0 local variables, so we don’t have to add anything to the stack. And then we do the following operations. Push argument 0, so argument 0 is 3. So we push 3, we push 1, we ask if they're equal. They are not equal because 3 does not equal 1, and therefore we don't go to BASECASE. The if-goto does not work, is not relevant. And also, notice that the eq has consumed these two values, argument 0 and constant 1, so the overall effect of these four commands on the stack is nil, no effect. So, moving along, we now have to look at the commands push argument 0. So we push 3, right? And then push argument 0 again and subtract 1 from it, so we're going to get 3 and 2 on the stack. And then we get to the command call factorial 1. So once again, we inform the implementation that one argument has been pushed onto the stack. We can refer to it as argument 0. And we want to issue a call command. So the implementation is going to save the frame of the current function, the current instance of the factorial function. And the return address is the green, right? Because that's where I want to return to after the factorial returns. So we save the green also, and we jump to the factorial function. Well, we do push argument 0, which is 2, now and then we push constant 1. And we ask, is it true that 2 equals 1? No, so we ignore the BASECALL. The net impact on the stack is nil, so we happily move to evaluate these commands, or implement these commands. So push argument 0, it is true, and then we push argument 0 again. We deduct 1, we get 1. And then we call factorial 1, informing that one argument has been pushed onto the stack. So we know that we can call this argument 0, and we have to save the state of factorials. So we save the state including the return address, which is the violet dot, right? Because after the call, we want to return to the next instruction. So the violet point is properly positioned in the code, and I save it on the stack. So now we go to function factorial 0. And let's see, we push argument 0 onto the stack, which is one. We push 1 onto the stack. And then we ask, are these two values equal? Is it true that 1 equals 1? The answer is yes, it's true. So we are going to do the jump. And we're going to jump to the BASECASE, right? So we jump to the BASECASE, and here I see that I have to push the constant 1. So we push it, okay? We push the constant 1, and now we have to do a return. Now, this is the first time that we have to do a return or that the return occurs in this simulation. And here's what the implementation does when it encounters this return command. First of all, it gets the return address off the stack. It can pop it, and we'll see later how we do it exactly. But we get the return address, which is the violet, and we know exactly where we have to return. You see this, I placed this arrow here, which is going to tell me exactly where I have to return when I finish my little business here. So the next thing that I'm going to do is copy the return value, which I know is the topmost value onto arg 0. So I copy 1 onto arg 0, and I get 1. It looks very uninteresting because 1 became 1, but in fact, it's not the same 1. It's this new 1 that was copied, right? And then I have to do, let's see, I have to multiply, right? I have to call mult 2. Now, I'm not going to show you what happens when I call multiply, but if I did show you, I'd have to show all the stack growing and so on. I will omit this, and I will just record the result of multiplying these two values. And the result is 2, right? So, 2 and 1 are going to replace with 2. And so I call mult 2. 2 and 1 are replaced with the result of mult, which is 2. And I omitted all the details. And then I have to do another return, right? And so, let's see. I have to do another return, so I get the return address, which is the green. And once again, I know exactly where I have to return to, right? I position this blue arrow next to my intended return value. And then I have to do the copy. I take the top most value, which is 2, and I copy it onto arg 0, and so I get 2. I can get rid of the frame, which is no more relevant. And I jump to the return address where I find the command call mult 2. So once again omitting the details, I call mult, I do 2 times 3, I get 6. That's the result, okay? And the next command that I hit in the code is return, right? Well, the return is implemented by, first of all, consulting the frame. And I see that the return address is blue. So I put my marker on the blue command. Then I copy the 6 on arg 0. I get the result 6. I get rid, I recycled what is got free, and I jump to the blue marker and I do the return. So at the end of the story, I pushed. I wanted to compute 3 factorial, so I pushed 3, I called factorial, and boom, I got 6, right? This is the view of the caller. And notice how the caller is completely oblivious of all the drama that took part behind the scene. It's unbelievable how much work we had to do in order to get this result. 6, right? Factorial of 3. And just imagine what would have happened if we did something like call factorial 50, right? We would have to do this 50 times, and the stack would grow [SOUND] 50 times. And then it will return because that's the nature of factorial, right? It grows, and then it sort of drills down and then it drills up. And so you can also imagine what happens if I do call factorial 200. I will probably get a stack overflow, right? I mean, the stack would become too large at some point. And so, this is what I wanted to show you in the run-time simulation of the protocol that I just described. And in the next unit, we are going to finally implement it using code. I mean, we'll actually write the code that implements this function call and return implementation. And you will be surprised by the simplicity of this code.
