In the previous two units we talked about working with registers and memory, branching, variables, iteration. And what remains to be done in order to complete our survey of Hack programming is talk about how we handle something called pointers. And how we write programs that manipulate our input and output devices. So, that's what we'll do in the current unit. Let us begin with pointers. And as usual I would like to start with an example, in which pointers come to play. In particular, I want you to consider this very simple piece of code, that many of you have written, at least those of you who took programming courses before Nand to Tetris. So in this code segment I manipulate an array called arr. I assume that this array has been declared and initialized at some point. And now I write a piece of code that sets the first n entries of this array to the value -1. If you write with a regular high level language, it's very easy to write such a statement, such a for statement. And as you know by now, when you have to bring it down to the level of machine language, you have to work much harder to deliver the required functionality. So how do we do it? Well one thing that you have to realize, and in fact, you realize it only when you set out to write the compiler, is that the notion of arrays gets lost in the translation, so to speak. So when the assembler has completed to translate this piece of code from, let's say java or python, into machine language, the machine language no longer recognizes the array abstraction. And as far as the machine language is concerned, the array is just as segment in memory, of which we know the base address of this segment and the length of the array that the programmer has decided to declare. So if we assume that the array starts in address 100, and that we want to do something to the first ten entries of this array, this is how it's going to look like in the data memory on which this program will end up executing. We start with two variables. One of them holds the base address of the array. And the other one is the number of entries that we want to manipulate. And what we would like to see is that at the end of the execution of this program, we would like to see the first ten entries of this array set to -1. This is the goal. That's what we want to do. And the question is, of course, how do we actually do it? All right, so let's start working on writing this particular program. The beginning of the program is going to setup these variables that we just discussed. So we assign the number 100 to arr to signify that the array, arr begins in the memory register number 100. And we do something similar with n. We assign the number 10 to n. We initialize i to 0. Once again, don't forget we are trying to deliver the functionality of a for loop that begins with i equals 0. So we set i to 0. And then we can start actually going through the loop so to speak. So once we do these three variable declarations and assignments, we have this setting arr, n and i allocated to memory registers 16, 17 and 18. And we are ready to begin the actual processing. All right, so here is the actual processing. The first segment of the loop, and by the way, we realize the for loop using a machine language-oriented loop which begins with a label declaration called loop. And the first thing that we do is translate the termination condition into machine language. So what used to be if i equals n go to end which is the end of the processing because once i. What is i? I begins with 0 and goes through 1, 2, 3. When it gets to 10 in our example we want to jump to n. So we have six Hack instructions that actually perform the semantics. And then we come to the heart of this loop in which we actually assign the number -1, which is meaningless by the way, we just used as an example. We assign -1 to the current entry of the array. How do we do it? Well, let us begin with a comment. As you see what we are doing is we are computing the value of arr plus i which is the value of the base address of this array plus the current value of the index. Now if the index begins with zero then the first entry that we're going to operate on is RAM 100. Because arr is 100. And then i would become 1 so we'll operate on RAM 101. And then, i becomes 2 we'll operate on RAM 102 and so on, and so forth. How do we do it? Well, we have to add up arr and i. And that's exactly what we do in the first four instructions. We set et arr, we address the variable called arr, we put the value of this variable in d, then we say @i, we address the variable i. We add up d plus m and we put the result in the a register. Now, this is something which should be new to you. Because it's the first time that we actually use this capability of the language to assign something directly to a, using an arithmetic operation, okay? Now, what will happen when we do it? Well, d plus m now store an address. So this address is assigned to a and by the time we say m equals -1 the register that will be effected is the register that a addresses. Now if we do this within loop that runs 10 times or 10,000 times in each iteration the a register will acquire one more address. And we're going to operate on a different register in the memory. And that's exactly what we want to do. So, after we run so many iterations, we'll get the desired effect. And as usual we recommend that you stop the video and convince yourself that this is actually Working as advertised. So variables that store memory addresses like arr and i are called pointers, in any language, not only in hack. And, in hack, the typical logic is as follows. Whenever we have to access memory using a pointer we need some instructions like A equals something, something that come from some memory register. So the typical semantic is set the address register to the value of some memory register in which I do some pointer arithmetic to compute the address on which I want to operate. So this, in a nutshell, is how we do pointer processing in the heck machine language. In the next part of this unit, in the next and final part in this unit, we will see how pointer manipulation comes to play when we write code that interacts with the screen and with other similar peripheral devices. So let's talk about input, output. First of all, if you recall, we have two standard input and output devices, we have a display unit and the keyboard and these I/O devices are connected so to speak to two designated area In the RAM. One of them is called the screen memory map and these are 8K of bits that represent about 13,000 pixels on the physical display unit. And we have a keyboard which is connected to it, another area on the memory which we call keyboard. So we also have these labels that record the base addresses. So we don't really have to remember any actual number when we set out to process the screen and the keyboard. So here's an example of using the screen, and in particular, using the screen to draw a rectangle. This is like the hello world of computer graphics. Drawing a rectangle. How do we do it? Well, this is a screenshot of a CPU emulator I want to remind you that what we see here is the RAM, the instruction memory on the left, the data memory next to it. And then, we see some simulation of a physical screen. We see it on the top right-hand side, and the task in front of us is to draw a filled rectangle at the upper left corner of the screen. And the dimensions of the rectangles are such that it has to be 16 pixels wide, and RAM[0] pixels long. So RAM[0] is a parameter of this program. And if you look carefully at the top of the RAM in this slide, you will see that RAM[0] has been set by the user to 50. So once the user puts a number like 50 in RAM zero and clicks the play icon what will happen is that the program will start running. And at the end of its execution, she is going to be very quick. You're going to see a rectangle drawn at the top left of the screen. The rectangle is 16 pixels wide. This is a fixed width and the length is a variable according to the input of the user. So this is the mission. That's what we have to do. Before we look at the actual code let us go into CPU emulator actually demonstrate this program working and then once we do it we will talk about the code proper. The purpose of this demo is to illustrate how we can load and execute the program that draws a rectangle at the top left corner of the screen. So what we have here is two windows in the foreground I have CPU emulator and in the background I have a plain text editor with the program in question loaded already into it the program has been written If we read the documentation. We see that the program claims to want to draw a rectangle at the screen's top left corner and hopefully that is also what the commands of the program are actually doing. We can scroll through this program and see all sorts of familiar Hack commands written in the symbolic Hack machine language, along with documentation and white space to make the code more readable and manageable. So let's go to the CPU emulator, and click the Load Program button, which is right here. And I look for this program rectangle ASM here it is found it loading it and it's interesting to contrast we are so spoiled with what was actually loaded into intercept you and me later. So let's take this window and put it right next to the bloated code, we see that the source contains all sorts of symbolic addresses like @r0, @n, and so on. Now all these symbolic addresses are being translated on the fly into their concrete numeric semantics, so if we look at the code that was actually loaded into the CP emulator instead of @r0, we see @0. Instead of @n, we see @16, and so on and so forth according to the rules of translation symbolic programs into machine language. This is something that we are going to learn in unit six, so please don't worry about it for now. If you want to understand how a program works in the simulator it's better to look at the source code and not at the code that was actually loaded into the emulator. So you run the program in the emulator, but you inspect and debug it in the text editor. And then, you reload the corrected version in order to continue to test it. So let's put this window roughly back where it was before. And go back to the CP emulator and once again the program is loaded. We are told that we have to determine the depth or the length of the rectangle by filling in some number in RAM[0]. So let's do that and I'm going to put here the number 50, so we are going to draw a rectangle which is 16 bits or 16 pixels wide and 50 rows long. Hopefully, that's what the program is going to do. So I can start executing the program by clicking. This Play button, and each time I click a Play button I execute the next command in the program. And so far nothing seems to happen, but perhaps you have to be slightly more patient. And indeed we see that we drew one line of 16 pixels at the top left corner of the screen, very nice, so let's continue to execute and Looks like there was loop in the program, and I'm doing it slightly more quicker, and I see that I drew another line and keep on drawing another line, another line, and so on and so forth. If I get tired of this step-wise simulation, I can click the fast forward, and then I can just sit back and watch the program get execute. This is fairly slow, so I can make it faster by using this slider here. And I see now that the program runs much quicker than before, and it keeps on drawing rows until the counter of these rows will reach RAM 0, which now happens to be 50. And that's it. We got this limit, and at that stage, the program executed some go to command that sent it to the end of the program where it runs an infinite loop. And that's exactly what I want to do at the end of every hack program. So once I get tired of seeing this infinite loop, I can stop the program, look at the screen, and convince myself that the program has actually done what it was supposed to do. Now, let's scroll back to the top of the program. And we can try some other input. Let's say, 70, or let's even make it a larger number. So, we're going to draw a rectangle which is 120 rows long. And if I'm tired to see all this animation, I can click this control here and cancel the animation, at least temporarily. And then I, reset the program. And, once I've canceled the animation, I can simply click fast forward, sit back, and watch the program execute in an instance, so let's do that. And as you see, a rectangle of 120 rows by 60 pixels has been drawn so called instantaneously. Of course, as a low level programmer, you know that this program required 120 iterations and in each duration we had to execute several machine level commands. So, this has been a demo in which we illustrated how to use the CPU emulator in order to execute a graphics oriented program. All right, so now that we saw that the rectangle drawing program actually works, let's take a look at how we actually do it. And we'll start with pseudo code because, once again, if you get the pseudo code right, it's like 90% of the job done. Because the rest of it is translating the pseudo code in to machine language which is a relatively technical thing to do. All right, let us focus on some subset of our CPU emulator screenshot. On the right-hand side, you see the physical screen, with a rectangle already drawn, and on the left-hand side we see the ram. And, in particular, we focus on the area of the ram which is the top of the screen memory map. And, as a programmer, we are not terribly interested about the physical screen. We cannot manipulate the physical screen directly, but what we can do is manipulate the screen memory map. And because we have this contract that whatever we write into the memory map is going to be reflected on the screen, we know that we can indirectly manipulate the screen and do whatever it is that we are asked to do. All right, so here's the pseudo code of writing this rectangle. Basically, we have to implement a for loop. We have to say that for i goes from 0 to n, where n is the value over m0. That's what the user, the number of rows that the user wanted to fill with 16 pixels, well, for every one of these i values, we want to draw 16 black pixels at the beginning of row i. So the rows go from let's say 0 to 49. And then we'll get the desired rectangle. How do we do it? Well, we translate this semantics into pseudo code. And we get something like the following. We begin with some base address, which I call it addr. Actually, this is going to be a running address that I'm going to use. So the beginning addr = SCREEN, n = RAM[0]. I don't want to destroy RAM[0], so I save it in a nicely variable that I declare to be n, and then I set i to 0 to count how many iterations I did so far. I can actually do it without this variable, but I decided to do it with this variable as well. And here's the loop that we're going to use. As long as i, has not reached n, I want to set RAM[addr] to -1. And then, I want to set up for the next iteration. In the next iteration, I'm going to move within the memory map to the word that represents the beginning of the next line. And I'm going to increment i to remember where I am in the loop, and then I'm going to repeat this thing n times, okay? y-1, well, we discussed it when we looked at the simulation -1 in binary is 16 1s which will represent 16 black pixels. Now why do I have to jump in these offsets of 32? Because that is the way that the screen memory map is mapped on the physical screen. We use the first 32 words in the map to represent an entire row of 512 pixels. And then we use the next 32 words to represent the next row, and so on and so forth. 32 times 16 gives you 512 pixels, which is one row in the physical display unit. And because we're interested only in the first 16 pixels in each row, we can safely jump from the current word to the count word plus 32, or the index of the count word plus 32. So this pseudo code should deliver the rectangle drawing and what remains to be done is to simply translate this pseudo code into machine language. This is by now by this stage of the course or by this stage of the lectures in this week, this is a relatively straight forward task. I have split the program into two different fields on the screen. And you can stop the video, look at the code, convince itself that it does what the pseudo code on the previous slide advertised to be doing. And one area of the code which is kind of interesting is this area in which I finally computed the address in which I want to operate. I set this address into the A register and then I operate on this particular memory register and set it to minus 1. This is very similar to what we did previously with the pointers. And it is yet another example that shows you the power of pointer manipulation. So we basically do something very similar to what we did before, we manipulate an array, but we now have all the nice side effects of what happens when you manipulate not just a regular array but an array which happens to be a subset of the screen memory map. You get the side effect that whatever you do in the memory map is reflected on the physical screen. And if you know what you're doing, you're going to end up drawing a rectangle. If you don't know what you're doing, you're going to end up drawing something crazy, which would be interesting as an experiment. But then, you have to debug it, until you get the desired rectangle or whatever other figure you were asked to draw. So, this has been the end of the part in this unit in which we talk about working with the screen. And I'd like to say few words about working with the keyboard. As you recall, the keyboard is the standard unit with which we interact with the user, with which we acquire inputs from the user. So how can we write code that manipulates the keyboard? In previous units, we discussed how the keyboard is connect to the computer. And in particular, the keyboard is connected to a certain register, which in the overall address space of the memory happens to be register number 24576 in the Hack Computer architecture. So this register is the keyboard memory map. And the second you search that if the user presses any key on the physical keyboard this can code of this key appears in the keyboard memory map in this designated register. With that in mind, it's quite obvious what we have to do as a programmer in order to figure out what the user is doing with the keyboard. You have to write code that accesses this particular register and inspects it. To check which key is currently processed, you read the contents of the RAM in address 24576. You don't really have to use this difficult to remember number because this number also happens to be the value of the predefined label keyboard. So all you have to do really is say something like at keyboard, D equals M and then the D register will contain the scan code that the user is currently pressing. Now, I wish to remind you that if the register contains zero it means that the keyboard is idle and the user is not really using it. Otherwise, it contains the scan code of the presently pressed key. Now this is very, very low level programming. All we know is which key the user is pressing. Normally, when you write computer programs, you want to let the user enter complete strings like a login, a password or something like that. So you have to accumulate several keys until the other person to enter for something like this. Writing code like this in low level language is very tedious and that's why we normally do it in a high level language, and then after we compile it into machine language, we get the desired effect. But at the level of programming that we do now, all we want to know is, once again, which key the user is presently pressing. So that's it. We completed discussing our survey of hack programming. We talked about the classical things that we do with every programming language, working with registers, branching, variables, iterations, pointers, inputs and outputs. And this basically wraps up what we wanted to say about low level programming. In closing, before we end this unit, I'd like to say a few words about compilation in general. Because we got very close to the notation of compilation in some of the examples that we saw in this and in previous units and in particular we explained how we write a piece of code like this one in the low level of machine language. And moving from one to the other is exactly what a compiler is designed to do. So the compiler allows you to live, so to speak, within the obstruction of a high level language without worrying about all the details of how this thing gets translated into machine language. But by now, you know that in order to do it in low level, you have to work really hard to rewrite the code within the constraints of the low level language. Now in the second part of the course, in NAND to Tetris part two, we will actually write such a compiler. We will write a compiler that can take any program that is written in a high level language, object-based language similar to the languages that you use in your regular programming courses, and we'll write a compiler that translates from this high level into the low level. In the process, we will use a virtual machine, and we will use the services of a host operating system. And if you want to learn all these A very interesting layers of obstruction, well you have to take, you're invited to take the second part of this course. All right, so finally, I think that by now you are convinced that low level programming is, first of all it's very low level. You have to work directly with the machine. But it's also because it is so minimal and so spot on and because it is so fantastically expressive, it is also a very profound and subtle thing to do. Writing programs in machine language is profound, it's subtle and it's intellectually challenging. And it kind of reminds me of a saying that I heard somewhere which I think is very correct. And the saying is that simple minded people are impressed by sophisticated things and sophisticated people are impressed by simple things. And in particular, when the simple things are fantastically expressive they are very impressive. And if you think about it, the Hack language has two commands only. It has the ability to represent symbols, and that's it. And the act with this very spot-on capability, I can execute any program that comes to mind. Any program written in any high level language can be translated into a Hack program that does exactly the same thing. And this, I think, is rather satisfying. So this has been the end of our survey of Hack Programming. And in the next unit, you are going to come to play. You are going to write some programs on your own. And we'll give you some tips on how to do it easily.
