In the second unit of this module, we'll begin exploring the VM Abstraction, and we'll start by talking about the most important element in the abstract. VM Architecture which is the Stack. Now I wish to start with the big picture, as usual, and remind you that we are developing 2 tier compilation process. And the centerpiece of this process is the Virtual Machine that operates the VM code, that you see here in the center of this slide. Now, let us assume that we had a complete freedom of designing this VM language. That sort of sits in the middle of this translation process. How would we go about designing it, which language would we come up with? Well, we have to strike a balance between two conflicting objectives. On the one hand, we want the VM language to be sufficiently high so that the distance, so to speak, between the high level and the VM level will be relatively low. And therefore, the translation challenge will be relatively manageable, and the resulting VM compiler will be a relatively simple and elegant programs. On the other hand, we want the VM code and the VM language to be sufficiently low, so that the distance that we have to cover between it and the final target language, the low level language. Will also be manageable and conveniently small, so that the VM translator or the VM implementation will also be a relatively simple and elegant program. So we have to find the right balance and years of research and practice in computer science have indicated that one architecture that hits a very good balance between these two objectives, is something called stack machine. And the stack machine is an abstraction that consists of an architecture, a stack, and a set of operations which we can apply to this architecture. And this is a good summary of what we're going to do from now on, we're going to describe this architecture and this set of commands. So let's begin with a stack. One way to think about stacks is to envision a stack of plates, that has the top of course and to come up with a some sort of a game in which we have only two allowable manipulations. One of them is called push for historical reasons and this operation allows us to put the plate on the top of the stack and pop allows us to remove the top plate from the stack. And as we do these operations the top pointer moves accordingly to reflect what we have just done. And the top pointer always points to sort of one position above the topmost plate in the stack. Now, with a regular stack of plates, you can sort of take a few plates, sort of pick them up and put another plate in the middle. But in this stack, you're not allowed to do it, you can only access the stack from the top. Now in computer science, stacks look somewhat different, but the idea is exactly the same. The stack contains some values instead of plates and these values, we can think about them as integers, but in general these integers can represent anything. They can be strings and Boolean values and so on, but let's think about integers to make life very simple. And we have something called the stack pointer that points to the location in which the next value is going to be pushed. This stack is available in a larger context called the Virtual Machine, which is also equipped with a regular sort of a memory segment. Which is very similar to the RAM that we built in part one of the course and you can basically think about it as an array. An array which offers direct access to every element in this, in this memory as opposed to the stack which only offers, through a stack pointer. Now, what can we do with this architecture? Well, suppose we do push x, and by the way, we assume that we can label different location in the RAM as we please. So, if we do push x, well, let's check x contains the number 7 and therefore, we see the number 7 being added to the top of the stack and nothing happens to the memory. Okay, another thing we can do is pop Y which will effect two separate sub operations. One sub operation will remove the top value from the stack. This three and the second operation will take this value three and store it in location y. So whatever used to be location y is going to be overrided. So these are the two fundamental operations that we're going to use in order to move data from the stack to the memory and vice versa. Now, in addition to this, we're going to have a whole set of arithmetic commands. For example, if we say add, the following thing is going to happen. We're going to pop the two top most values from the stack. We're going to add them up on the side, so to speak and then we're going to push the result onto the stack. So the result will be this. Notice that the operands of the addition, in this case three and seven, have been replaced by the result of the addition, in this case, ten. We can do something similar with another command called neg, which will negate the topmost value. Now it will not simply negate it will first of all, pop the top value. It will negate it on the side and then it will push the result back on to the stack. So in general, if you want to apply a certain function on the stack, you have to do three different things. First of all, you have to pop from the stack as many operands there as are necessary. Then you compute the function of these operands in a separate process and then you push the result back on to the stack. Now I said you but all these things happen quote unquote, automatically, it's part of the obstruction. So the obstruction supports all these operations inherently, you don't have to worry about them. All you have to say is add neg, and these things will take place. Now in a similar fashion, we can also apply all sorts of Boolean operations on the stack. So in this example, if we say eq, we're going to implicitly pop the two top values which happen to be equal. We're going to ask are they equal, is it true that 5 = 5? The answer is yes, so we're going to push, true to the stack. Then if we want, can say or we will pop the two topmost values, the stack will become empty. We will or them on the side, we'll get true, and then we'll push true back onto the stack. So I hope that you understand sort of the spirit of this very elegant virtual machine. Now at this point you may will ask yourself, where do these commands come from? Push, pump [INAUDIBLE] eq, who gives us these commands? What's the story here? Now, actually I'm not obliged to answer this question. And I can so called ask you to forget about the outside world and just focus on the VMware Infrastructure. Which is sufficiently attractive, elegant, and powerful architecture in its own right. It's a good abstraction in its own right and we may well dwell on it without worrying on what exists outside this obstruction. And you have to understand that there's a certain virtue to this bliss of ignorance because we can focus on what we're doing now instead of 100% level. And that's how, some great minds really think, they are able isolate themselves from anything else and just focus on what their currently working on. But in this course, people who take this course, people like you are intelligent students who take this course because they won't understand the big picture. So it's in the DNA of this calls to ask questions like where does this come from? Where we going from here? And so on and so forth, so I allow myself to actually venture outside the context of the virtual machine and say a few words about the big picture of stack arithmetic. Where do these commands come from? Well, they come from the compiler that we haven't seen yet, okay? So if you start with a high-level statement like x = 7 + 19, the compiler that we will build later on in the course is going to translate it into, in this case, push 17, push 19, add, and pop x. Okay, and the result of executing all these operations will put in x the value of 17+19. Now, there's an interesting abstraction, implementation interplay going on here. First of all, the high-level language, of course, is an abstraction, it doesn't exist for real. It can be implemented by translating it into stack machine, but the stack machine is also an obstruction and this obstruction is implemented by something else. Stay tuned because the whole list of this module is to understand this obstruction and implement it as will do later on in the module. All right, so here is the virtual machine in its whole glory, it's stack machine which is manipulated by four categories of commands. Arithmetic logical commands, Memory segment commands, Branching commands and Function commands. And what we do next is talk a little bit more about arithmetic and logical commands. So here's an example, we start with this high level code which the compiler is going to translate into this VM code. How this translation takes place is something that you shouldn't worry about at this stage of the course because we'll worry about it later on, in about two or three modules from here. Now, we do want to worry about how to execute this code, because this is squarely with the VM obstruction. So here's an empty stack to begin with and we assume that we have a memory segment with the x and y variables. And then we say push to, so the stack becomes two and then we push x, so the value of x is being pushed onto the stack. We subtract these two values, we get the result. We then push y, the stack grows, we then push 9, the stack continues to grow. We then add up the two top most values and we get, I think, 21. Then we do another addition and we get -4 plus 21, which gives us 16. And finally, we pop the result into d, and we get a new variable, d, which contains the value of this computation. So what we saw here is a typical sequence of stack machine commands executing, and achieving some useful value. Now, we could have done something very similar with the logical commands. And here's an example, what we see at the top of this code pane here is a logical expression or bullion expression that has a tooth value. And in order to evaluate this expression, the compiler will generate this code, the code that you see here. So starting again with an empty stack and some x and y assumptions, we can execute every one of these commands, one after the other. And what we'll end up getting is this simulation that you see here. And if you want, maybe you can stop the video here, go through the motions, and convince yourself that you understand what is going on here from one transformation to another. So please do this. So to recap, what we've done so far, here are our arithmetic logical commands. We have three arithmetic commands, add, subtract and negate, that always operate on the top most values in the stack. Then we have three logical comparisons command, equal greater than, less than which also operate on the two topmost values in the stack. And finally, we have the three classical logical connectors and/or a not that also operate on the two topmost values of the stack. Now, this doesn't look like much, right? It looks like a very spartan set of commands, but here's an interesting observation. Any arithmetic and logical operation that you can dream of, written in any programming language can always be reduced to a subset of operations that uses these commands and executes them on a stack machine. And the stack machine will end up computing the value that you wanted to compute in the high level. So, this goes on to show the underlying power of this very simple virtual machine that we are building here. All right, so with that here is once again a description of the overall VM language. We have said everything that we want to say about arithmetic and logical commands. And in the next module, we'll talk about memory segment commands.
