In the previous unit, we started to talk about the VM implementation. And we went through the implementation of the stack architecture. And in this unit, we'll continue with implementation of the memory segments. Now to remind you, we started this journey of virtual machine with a stack that interacts with some abstract memory space. And then we replaced this abstract space with eight memory segments, whose names are local, argument, this, that, constant, static, pointer, and temp. And the question, of course, is how to implement these memory segments on the host's computer? Well, before we get started, let us note that the abstraction of these memory segments is quite uniform. We address any location in any segment using exactly the same syntax, push, pop, segment name, followed by a non-negative integer. So examples include push constant 17, pop local 2, and so on and so forth. So how should we go about implementing these memory segments? Well, we will do it one step at a time, beginning with local. Now, the local segment is accessed using the uniform syntax that we had all along push, pop, segment name, index. So here's the local segment in the context of this simple example of a stack machine. And how do we realize these two data structures on the host RAM? Well, the stack is going to be implemented as we did in previous units. We'll start the stack at 256, which is an agreed-upon convention. And we use a pointer that we call SP, to record the address of the next available location in the stack. And we decided that SP will be mapped on RAM 0 in the host memory. Now, what about the local segment? Well, the local segment can be placed, in principle, anywhere we want on the host RAM. We don't care where the local segment is going to be stored, as long as we remember the base address of this block. And as you see here, we've decided to place the base address of the local segment in a pointer called LCL. And we also decided that LCL will refer to RAM 1. So as you see in the example, the local segment happens to begin in this arbitrary address that I made up, 1015. And LCL contains the same address. So notice that indeed we are using two pointers, but we use them in a very different way. The stack pointer points to the next available location in the stack. And LCL points to the base address of the local segment. All right, so here is how we use this implementation when we set out to implement commands like pop and push. So here is the same RAM segment that we had before. And SP and LCL are mapped as we had before. And following the pop local 2 command, here is what is going to happen. SP has changed to reflect the pop operation. And we see that the number 5, which used to be the topmost value in the stack, is now located in local 2, which happens to be 1017. Now, how do I know that local 2 is 1017? Well, that's simple. I take the base address, which is 1015. I know this information, right, it's always stored in LCL. And I add the offset, or the index 2, to it. And by adding up these two values, I get the value of the target address on which I have to store the popped value. Okay, so that's how I can generalize this translation process. I can take the base address and add the offset to it. Another thing which is interesting to note here is that, look at address 257. Right, it contains the value 5. But notice that this value is out of play, it's kaput, it's dead. It doesn't know it, but it's dead, because the stack pointer now points at 257. So the next push, which will happen probably at some point, is going to kill this number 5. And that's perfectly okay. So it's quite typical when you manage a stack that you have all sorts of garbage along this stack. And yet the pointers indicate exactly which part of the stack are in play, and which are kind of game and can be recycled at will. All right, so how can we translate the pop operation? Well, we can do it using the pseudo assembly code that you see here. First of all, we compute the target address, which is LCL plus 2 in this example. We store it in some temporary variable, if we need such a variable. Then we decrement the stack pointer. And we take the value which is stored now under the stack pointer, or the value that the stack pointer points at, and we put it into the address that addr points it. So this is the semantics that we want to implement. And how do we implement it in assembly? Well, that's your job to do it. Now, you have everything that is necessary in order to translate such pseudo instructions. Obviously, you will need the Hack language. You will need the A command, the C command, and so on. So that's a little sort of riddle that you have to solve. And once you do it, you will know how to always implement pop local i commands. So in general, indeed you have to observe that there's nothing special about this number 2. I can replace 2 with i, and then everything will work just as well as it did before. Instead of doing LCL plus 2, I will do LCL plus i. So I manage to indeed generalize this translation completely, and I know how to handle pop local i. So here is the generalized translation of pop local i command. What we see on the right-hand side is exactly what we had in the previous slide. And the push local i command is implemented in a very similar way, somewhat symmetric, okay. So we compute the target address, as we did before. And then we carry out a push operation using sort of two pseudo instructions. And once again, in order to actually make it happen, your VM translator has to generate the assembly instructions that will realize this pseudo code using the Hack language. Now, I would like to extend the picture. And talk now about these four segments together. The local argument, this and that segments. And it always helps to sort of extend, also, our perspective. And remember or think about where these segments come from. Or what purpose do they serve? In the sort of larger enterprise of what we're doing. Well, think about a typical method in let's say in Java which is operating in run time. Well, this method typically has local variables, it has argument variables, typically it processes some current object which is also a bundle of so-called member variables, I think. And also the method may well process some array that also has entries, which are data values. So when we translate this logic into the world of the virtual machine, we have to preserve all this semantics. Well, we do this with the local and argument memory segments, as well as with two other segments that we call this and that. This segment stores the member variables or the values of the fields of the current object, and the that segment stores the values of the array that the current method may be processing. So basically, we are using these four segments in order to capture these semantics also at the VM level. So how do we implement these four memory segments? Well, first of all let us remember that abstractly we use them exactly the same way. We do push and pop, segment name, index and that's it, we don't need anything beyond that. So they are accessed in a uniform fashion. Well, I'm very glad to report that we also implement them in a precisely the same way. In addition to the stack pointer which is always available we are now also going to use four pointers which are called LCL, arg, this and that. And every one of these pointers is going to do exactly what the LCL pointer did in the previous slides. They're all implemented precisely the same way. And every one of them holds the base address of the respective memory segment that it relates to. And therefore, the implementation of the commands push and pop is also going to be exactly the same. We're going to use the same semantics that we use for the local segment, but instead of saying local, we'll say segmentPointer name where the segment pointer being the right, the corresponding pointer to the memory segment that we are dealing with in the source code, in the VM code. Now, you may well ask yourself a good question here which is, wait a minute, where exactly on the RAM these segments are going to be located? Well, the answer is we don't care. We don't care because they're going to be located somewhere, and all we have to do is remember the base address of these dynamic allocations. Well, later in the course we will see that deciding where to put these segments in memory. Is a very interesting question, and we solve this question using all sorts of clever algorithms, which are going to be part of the operating system, and the compiler, that together, will decide where to map these segments on the host RAM. The next segment that I want to discuss is called a constant. And the context of these constants is that when the compiler encounters constants in your program, in your high level source program. It handles these consents by generating VM that include, or that use the constant memory segment. So it is going to be re-expressed using operations like push constant something or pop constant. Something on the stack. So how do we implement these operations? Well, here's the generic push constant i command and there's no pop constant because, you know it doesn't make any sense to store something in this constant. And the implementation of this constant is trivial because this is a truly virtual segment. It doesn't really exist. So whenever we see a push constant i command, we simply generate low level code that supplies the specified constant. So we do *sp equals the specified constant and then we advance the stack pointer. So this is has been the treatment of the constant segment. Moving along, the next segment that we are going to deal with is the static segment. Now, what's the story of this segment? Where does it come from? Well, the compiler that handles your high-level code may well encounter some static variables. Now, these are the so-called class level variables that every method in your class sees. So obviously we have to treat these variables differently than the way we treat local variables or argument variables and so on. And therefore, we've decided that in the virtual machine extraction we'll use a dedicated segment called static to represent static variables in the source code. So every operation on the static variable in the source is going to be re-expressed as a push static i or pop static i operation at the VM level. So here is how I'm going to implement static variables. Well, we start with some example of a VM code in which using static variables come to play in the context of pop instructions. Now, let us remember what static variable are all about. Unlike local variables and argument variables which are unique for each VM function. Static variables are at a higher level of scoping. And therefore, all the VM functions in your program should see the same static variables. And therefore since we have this functional requirement it makes sense to store, or actually it's required to store the static variable in some global space that all the code which is generate from these VM functions will see the same static variables. And so, the decision that we decided to undertake is to have the VM translator, translate each reference to static i in some vm File Foo.vm, into the assembly reference Foo.i, so Foo, the prefix of this label, Is the name of the file. And i is the index which is taken from the VM command. Static five, i equals five, static two I equals 2. And so, if we follow this convention, which will become understood in just a few seconds, then the VM translator is going to translate pop static 5 into well, first there will be some code. Which I omitted that carries out a pop from the stack and the topmost value from the stack is going to go into, I suppose, the d register, the data register, and then we have to put it into our assembly level incarnation of static 5. How do we do it? Well, we generate a label called Foo.5, and then we say M=D. What about the other command? Well, we handle it in exactly the same fashion, only instead of 5, we're going to generate 2. Now, why is this going to actually work out? Well, remember, following assembly, the hack assembler by convention is going to map these references onto RAM[16], RAM[17], all the way down to RAM 255, in case you have so many static variables in your program. Which is unlikely, typically we just have a few static variables in a typical computer program. So, what will happen is that this references will end up being mapped to the blue area that you see here on the RAM and that's exactly what we want. Because you see this blue area is outside the stack, and all the functions which are running in you program can. Take a look at this RAM area and see exactly the same thing, the static variables. And so, in using this trick here, we basically took advantage of this unique convention in the hack assembler of mapping. Symbolic variables onto the RAM from position 16 onward. And therefore, the entires of your static segment are going to be mapped on RAM 16, RAM 17, and so on, in the order in which they appear in your VM code. And therefore, you will have this slightly peculiar situation in which static 5 in this example will go to RAM 16, static 2 will go to RAM 17. There's so many to static 2 that there are no more static variables declared and used in between. So, there is a one to one mapping, but the order of the index values is not the same as the order of the RAM entries. It's the order of appearance in the code which determines where each one of these variables will be mapped on the RAM. So, that's how we implement the static segment, it's a little bit hairy, but it works, and it works quite well. And, I'd like to sort of say, makes general observation about this implementation here. And that is that up until this point, up until we discussed static variables, everything that I said in this module was completely platform agnostic. After all, every computer has a RAM. And everything that I said about implementing argument and so on did not make any assumptions about the underlying platform, aside of the assumption that there's a stack somewhere, which is a very safe assumption, because once again, every computer has a stack somewhere. And it is only here in the implementation of static variables that we take an exception to this platform independence elegance and we actually take advantage of something which is unique to the Hack assembler. So once again, up until now everything they said can be implemented on any computer out there, not necessarily on the Hack platform. And yet, if you want to implement the static segments, you have to find some other tricks to do it if you decide to implement our virtual machine on a computer which is not a Hack machine. All right, moving along, the next segment that we want to discuss is temp. Now, why we need the temp segment? Well, it so happens that when the compiler generates code when it translates your Jack program into VM code, it sometimes has to use some temporary variables. So, we decided that we're going to allocate an 8th place segment called temp that will contain and serve these variables when needed. So, here's how we do it. The push and the pop are uniform, exactly as we had before, and yet temp is going to be a fixed 8-place memory segment, and we decided to allocate or to map this segment on RAM locations 5 to 12. So, altogether we have eight values there, and therefore the translation of push and pop are going to take this base address 5 obviously into account. So, it's almost the same as the translations that we had previously, except that the base address is now 5 instead of one of the segment pointers. So, that's how we implement the temp segment. The last segment that we have to worry about is called pointer. And the pointer segment is a little bit obscure. And it's obscure because you can't understand really why we need it until you begin to write the compiler which is something that we'll do down the road in the course. So for now, I'm just going to explain the point of segment as some sort of almost an arbitrary rule of the game, and given my explanations you will have all of the information in order to actually realize it on the target machine. So first of all, where does this segment come from? Well, it turns out that when the compiler translates a method, it has to remember the base addresses of the this and that segments. These are the segments that represent the current object and the current array that the method may be processing. So, we decided to keep the base addresses of this and that in this pointer, in this, I'm sorry, segment, which we decided to call pointer. So, here are the rules of the game. Pointer is a fixed memory segment. It has only two entries, 0, and 1. And therefore, the only push and pop commands which are applicable here, are push and pop pointer 0 and 1, and any other integer is simply invalid in the context of pointer. Now, what we do with these commands? This was just the syntax of the commands. Well, whenever the VM code tries to access pointer 0, it should result in accessing this. And whenever it wants to access pointer 1, it should result in accessing that. So, the implementation should service these push and pop commands by supplying this and that. So, with this in mind or with that in mind as you please, let me say a few words about how we actually do this implementation. So, the push pointer 0 command should be implemented as follows. You want to create assembly code that realizes the obstruction, *SP equals THIS followed by SP++. If the VM command is push pointer 1, you do exactly the same but you use THAT instead of THIS. And the handling of pop pointer is symmetrically similar. Now, I wish to remind you that the assembly code that you see here is pseudo code, and you have to realize this pseudo code using Hack assembly. So, that's how we handle the pointer segment. Now, I must admit that this segment and the way we use it and realize it may sound somewhat peculiar and strange. But you shouldn't worry about it because it will make perfect sense once we talk about code generation when we set out to write eject compiler. For now, let us just strive to create this functionality that I described here. Now, before we end this unit, I'd like to do a recap and observe what we are doing. So, basically, we are implementing the VM language which consists of Arithmetic/Logical commands, Memory access commands, Branching commands and Function commands. By now, we've implemented the first two categories of commands, and the remaining two categories are going to be handled in the next module of the course. So, before we get to this module, we still have some work to do here. So, I'll meet you in the next unit, when we talk about The VM Emulator.
