Welcome to unit four of this module in which we are going to talk about the challenge of handling the translation of the Flow of Control into the VM language. Well, let's start with an example as usual. And what we have here is an example of some Jack code which presumably computes the square root of some given number X using some binary search algorithm. All right. This is the source code and the challenge of course is translating or reexpressing the semantics which is captured in this source code into the VM language. Now, I would like to point out at the outset that I could have named this module also, not necessarily handling flow of control, but rather handling statements. Because in the Jack language we have five possible statements of which we see I think four in this example. We have let statements and we see quite a few of them here, we have while statements, if statements, return statements, and do statements. We don't have a do statement example here but all the others are present. The challenge that we face is reexpressing everyone of these statements using the VM language, not necessarily just the three commands that you see here. And yet, I would like to argue that of these five statements, the only two interesting ones are the while and the if. Because let, do and return are trivial statements to translate, and we have already done some of it before. We'll do some of it in the next unit. And translating while and if are far more challenging and that's why I want to focus on these two branching commands or flow of control commands only. The challenge once again is to translate while and if statements into code that involves the three branching command of the VM language, which are goto, if-goto and label. How do we do it? Well the first thing that I'd like to observe is that we have some very structured or well structured patterns here and once we focus on the patterns everything becomes much easier to comprehend and handle. In particular, a while statement always has some expression that has to be evaluated. If this expression is true then we go into the while and we evaluate the statements. If not we skip the while and we go to whatever is after the end of the while. And with the if we have a similar situation. If the expression is true, we execute the statements of the if clause. If not, we execute the statements of the else clause, if there is an else clause. And once again, the structure here is very well defined and therefore we can systematically handle it quite nicely using a compiler or the cogenerator that we develop in this module. What I would like to do next is focus on each one of these statements while and if in isolation. So let me begin with the if, here is the generic structure of an if statement in the Jack language. Before I generate code for this statement, I would like to rewrite it using what is sometimes called a flow chart, I believe. As you notice, the first thing that I do is I take the expression of the if and I negate it. And then I look at the result. If the result is true, I go on to execute statements two, the block of statements which is denoted here in statements two. If not expression is false, I execute statements one. Now, why do I do this negation? Because once you negate the expression in such a way, cogeneration becomes far simpler and tighter and in particular here is how we generate code for an if statement. We compile or I should say we generate code that compiles the, let me take it back. We generate code that computes the value of the expression and puts it on the stack, then we negate whatever we computed. If the result is true, we go to label L1. If the result is false, we go to label L2. And that's it, this is resulting execution of the if statement. Now where do these labels come from? Well, the answer is that the compiler generates these labels, quote, unquote, automatically. It's the job of the person who develops the compiler to write code that generates these labels cleverly and when I say cleverly, I mean that these labels have to be unique, something that I will discuss later on in the module. You simply generate the labels, you go to it, and later on you plug the label into the code exactly where it belongs. Once again, you just have to convince yourself that everything that I show here is completely deterministic. Given any if statement, we can generate the code that will compile and compute exactly the same if statement, using the VM language only. That's how we handle if. What about while? While in a way, is even simpler than if. This is the generic while statement in its source code manifestation, and the first thing that I do, conceptually speaking, is I generate this flow chart, which begins once again with negating the expression. If the result is true, I get out of the while. If the result is false, It means that the expression is true and therefore I go into the while and I execute the statements and then I go back to reevaluate the expression and so on and so forth. That's how I implement this loop here. How will the generated code look like? Well, it will look like this. Conceptually speaking, I use this flow chart and I follow it, so I start by inserting a label into the code stream. I call this label L1, then I generate code that computes the value of the expression. I then immediately negate this value, if what I got is true I go to L2 I step out of the loop. If it's false I go on to generate code for the statements and executes them, and then I go back to L1 in order to reenter potentially reenter the while loop as we did before. Once again, I don't really need this flow chart explicitly it just sort of a mental exercise that helps me to think about code generation. But given any while statement I can systematically generate the VM code that will implement the same while semantics in the virtual machine. Once again the labels here are created automatically by the code writer. That's it, that's how I compile if and while statements and as I said before, compiling the other three statement types let, do, and return is fairly straightforward. All right now there's some mild complications which are very easy to resolve. And in order to talk about these complications, I want to go back to the generic code that I showed you before and I'd like to observe that a program typically contains multiple if and while statements. We can have many of them, not just two as we have in this example. How do we handle it? Well, all we have to do is make sure that the compiler generates unique labels. Once we used L1, for example, we should not use L1 in other control structures that we find or compile downstream. We should always create new labels like L2, L3, L4, and so on. Very easy to handle but it's the detail that you have to remember. That's one thing that we have to worry about, creating unique labels. The other detail or the other observation is that the if and the while statements may well be nested. In fact here we have an if which is nested within the while and as you know within this if I can have another while and within this while I can have another while and so on and so forth and I can get what is sometime called telescopic code and the level of nesting is infinite theoretically. Practically you don't have too many levels of nesting, but you should be able, or your compiler should be able to support this phenomena of nested if and while command. How do we handle it? The answer is that we already took care of it, because the compiler that we developed all along, beginning with a parser, and throughout what we do in this module, this compiler employs a highly recursive compilation, sorry, this compiler employs a highly recursive compilation strategy. And therefore there's no problem at all compiling a while within an if within a while and so on. It will happen naturally because that's how the software engineering works in the way we designed our compiler. Having taken care of these complications, I'd like to recap and point out once again that beginning with this source code, we already know how to handle variables. We did it in the first unit of this module, then we talked how to handle expressions, we also know how to handle expressions, using this code writer algorithm, if you recall. And now, we also discussed how to handle flow of control. Things look pretty promising. And if you add up all these capabilities here, you can conclude that we already have all the tools and techniques that we need in order to develop a compiler for a simple procedure language, some sub set of the C language without a raise. We can do it, we can write the compiler for that language which is quite remarkable I think. And I can see some of you are probably telling yourself, gee Shulman showed me seven and a half slides and I could write the compiler. That's impressive. Well the answer is, first of all I didn't show you seven and a half slides. I showed you about 30 slides. But still it's impressive that with so little material we can already write a compiler. We have every reason to be proud in this accomplishment but at the same time we have to remember a few things. First of all the compiler that we develop does not translate all the way down to machine language. It translates only to the intermediate VM language layer. And therefore, the distance so to speak, that the compiler has to cover between the source and the VM is much shorter than the distance that we should have covered or would have covered if we translated all the way from lets say C to machine language. The reason why writing a compiler is such a manageable and elegant process, one reason Is because we already took care of the VM obstruction. Now the compiler writer, you, in the next project, all we have to do is generate VM code. And you treat the VM code as an obstruction. You don't care how pop and push commands are being implemented. Why don't you care about it? Because we already took care of it in the previous projects and in the previous modules. This, once again, is an example of the great virtue of working in a modular fashion. Because we already took care of this obstruction, we can now use it without worrying about the details of how these VM commands are actually being executed. You see that if you design your software engineering in a modular and kind of unit tested fashion, everything becomes much more manageable, elegant and useful. All right, so this is what I wanted to say about handling flow of control and about handling statements in the Jack language in general. And in the next unit we'll venture into the very interesting issues involved in handling code that creates and manipulates objects.
