Welcome to unit four in the first module of the course. This is an important unit because up until now, we've treated the virtual machine as an abstraction. And from now on, we are going to actually build it. So to begin with, let's take a look at the VM abstraction. And basically, I am repeating the quiz that I gave you in the last unit. In this quiz, we started with some arbitrary stack machine state. And the question was, which VM commands will implement the abstract operation static 2 equals argument 1, leading to this final stack machine state. So you saw the answer, and the point that I'd like to make now is that everything that you see here, is completely imaginary. It does not exist for real. And if we want to actually execute this scenario in some concrete way, we have to realize it on some for Neumann machine. So what do we have to do? Let's think about it, if you had to do it, how would you go about it? Well first of all, you have to take these four memory segments, well actually we have eight of them. And we have to somehow map these memory segments on the single RAM that is available for us, and to do it in some sensible way, right? We have to remember where each segment starts on the RAM and manage these locations and so on. Once we come up with this mapping, we have to do something with the commands, with the push and pop commands. We have to translate them into a sequence machine labeling instructions that will operate on this world that we just built on the RAM. So we have a lot of work ahead of us, but as usual, we'll do things one step at a time and each step will be relatively simple and well defined. All right, so in order to carry out the implementation of the abstraction, I'm going to use a technique known as pointer manipulation. Which some of you may be aware of and for some, it maybe a numa trail. So I would like to give crash course in pointer manipulation and this crash course is going to last exactly one slide, so bear with me. Let us assume that we have a typical RAM and we decided to use the symbols p and q to refer symbolically to the first two RAM locations RAM 0 and RAM 1. Now consider the following pseudo assembly statement D equals asterisk p. Now what do we do here? Well, here's the rule of the game. Asterisk p refers to the memory location that p points at. So the asterisk location tells us that we want to treat p as a pointer. Know if we didn't put the asterisk, if we just dis D equals p, then presumably will get the value 257, because that's what p point at. P is equivalent to 0, so D equals p will give us the contents of RAM 0 and yet we said, the asterisk p. So when we say the asterisk p, we imply an indirect addressing operation. So we look at the value of RAM 0, which happens to be 257 and we treat it as an address. Next, we look at the value of RAM at this address, which happens to be 23 and we store it into the D container. So D becomes 23, so this is the gist of indirect addressing. Now, if we have to implement this thing in let's say, Hack, then here are the three statements that will make it happen. We start with @p, and by doing this, it's essentially the same as @0, because p and 0 are the same thing in our assumption here. And then we say A=M, this will cause A to become the contents of the selected memory register which is register number 0. And therefore, A will now contain 257. Now remember that A is an adverse register. So once we put a certain value into A, like 257. Automatically, we're going to select register 257 from the RAM. So this will become the selected register which in the Hack Assembly Language is represented by the letter M. And therefore, when we next say, D=M, we're going to get the value of this register. The currently selected register number 257 and the value happens to be 23. Now everything that we learned here is quite similar to what we did in project 0 of this course. And if you did project 0, you shouldn't be surprised by what I just described. If you didn't do project 0, then I strongly suggest that you stop the video, take about an hour or two of time and do project 0. Submit it, and only after you understand how to use the Hack Assembly Language will you be able to follow the next modules and really do them effectively. So assuming that you've done that and you understand the Hack Assembly Language, let's move on to the next example. Now what is the meaning of p-- and then D equals asterisk p? Well, x-- is shorthand for x = x-1 or so the decrement operation in x++ is the same with the increment operation. So if we do p--, well we now treat p as a regular variable. And therefore, RAM 0 will become 256. And now p points at address 256. So if we say D equals asterisk p will get the value 19, which happens to be the contents of the RAM in 256. Here's another sort of final example, which is kind of symmetric. Here, we do something that looks strange, we do asterisk q equals 9. Well asterisk q stands for the memory location which is addressed by q and q happens to be 1024. So asterisk q stands for RAM 1024, and we want to put in it number 9. So instead of seeing 5 as we see here on the righthand side, 1024 will contain the value 9. And if we then do q++, RAM 1 will become 1025. Now you may ask yourself, why am I showing you these two particular pairs of commands? Well it so happens that these two pairs of commands will be used extensively in what follows. So I wish to once again emphasize that what we saw in this example so far is sort of high level or I call it pseudo assembly code. And in order to actually implement it, you have to take every one of these instructions, seal the instructions, and re-write them in your assembly language. If use the Hack computer, you have to write the code in the Hack instruction set. If use some other computer, you have to write the same code which is seen here, using the target language of your computer. All right, so moving along, here is how we implement the stack abstraction on a real computer. This is the abstraction, we saw it all along. And we see here an example, an arbitrary example in which we take a stack. We push 17, we get a different stack state. And what I want to show you next is how these two states are going to mapped on physical memory. So here's the whole strand that we're going to use and we're going to make two important assumptions. First of all, the stack pointer is going to be stored in RAM 0. And the second assumption is that the stack is going to begin in address 256. Which looks like an arbitrary choice, but later on you will see that this choice actually makes sense. So with these two assumptions in mind, let us focus on the left hand side of the slide. And the stack that we saw above, the abstract stack, which is 12 and 5 will be met on the RAM beginning in address 256 as we assume. And therefore, the stack point there which always points to the next available locations now contains the number 258. Now, following the push constant 17, if we look at the top, we end up with the abstarct stack state on the top right of the slide. And if you look at the bottom now, you will see that within the RAM the number 17 ended up located in RAM 258 which happen to be the previously available space. And stack pointer has moved one position forward so now SP contains 259. So that's how we are going to modulate on the RAM. And of course, we now have to write the assembly commands that will actually make this transformation work for us. So the logic or the implementation of push constant 17 is going to be as follows at SP=17. And the meaning of this is, go to the address that SP points at and put there the number 17. And then increment the address that SP points at so that the stack pointer will move one position forward. Because we want it to always point to the next available location in the stack. So the next challenge that we have is to take these two commands and re-express them or translate them into assembly and we're going to do it using the Hack Assembly Language. So in Hack, it's going to be as follows, first of all we want to store the number 17 somewhere. And one way to do it is to say x7, using the A register as a data register. And then D=A, so we'll end up having the number 17 stored in the D register. Next, we want to do asterisk SP = 17, and we do it as I showed you in the point manipulation demonstration, we do @SP, A = M, M =D. If you don't understand this logic, go back to the pointer manipulation crash course a few slides back and check it again. So this will accomplish the assignment of the value of D into the topmost stack location. And finally, we have to remember to increment the stack pointer. So for this we do @SP, M=M+1. Once again I want to remind you that if you don't understand this code, you have to stop and convince yourself that you understand it. You have to practice it, you have to look back on the program that you wrote in project 0. And make sure that you understand this intricate business of indirect addressing using the A register. Note, if you look at this piece of code, we're using the A register here in two remarkably different ways. In the first instructions, we use the A register as a data register. We simply put the number 17 into it and then we move it into D. Now the A register has this automatic side effect that it always selects a certain location in the RAM. So when we say @17, memory location 17 is going to be selected but we don't care about it. We don't give it any attention. Because all we want is to take the number 17 and move it into D. So who cares if it also selected something in the RAM. We don't care about it. In the next three commands. Boy, do we care? In the next three commands we use the A register as a classical addressing register. We set it up carefully using the pointer and then we 0 in on m, on the RAM location that the A register addresses and we put the value of D exactly where we want it to be. So this piece of code has more to it than meets the eye. And once again, you have to make sure that you understand it before you continue with this module. Now, I'd like to observe that there's nothing special about the number 17 in this particular example. And therefore, what we saw here is a general implementation of the generic command pushed constant i, where i can be any non negative integer. All you have to do is replace 17 with i and everything will work perfectly well. And that's actually what we do in the next slide. In the next slide, we'll look at the generic command push constant i. And we see that in order to re-express it in machine language, we have to use the two syllable commands asterisk SP = i followed by SP++. Now, who is going to do this? The VM translator, is going to do it. You have to write a program called VM translator, which you probably write using Java or Python. This program will receive as input a stream of VM command of which push constant i represent one of them. And given this input command, your VM translator is going to re-express it using several assembly commands that basically carry out the semantics which is described on the right-hand side. So on the right-hand side we have the semantics asterisk SP=i followed by SP++ and you have to express this semantics in assembly. And once you know how to express it in assembly, you can write a program that actually does it in a very general sense, for any given push constant i command. All right, so the VM translator is a program that grows from the left to the right, that translates VM code into machine language. And each command like this one naturally is going to generate several assembly commands. All right, so this is the module in which we begin to talk about VM implementation. So far we talked about implementing one command only, push constant i. And in the next unit of this module, we'll talk about implementing all the other commands that we discussed before from an obstruct perspective. Now we'll talk about how we actually make them work.
