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 in at least those of you who took programming courses before before NAND to Tetris. So in this code segment, I manipulate an array called arr. I assume that, you know, this array has been declared and initialized at some point. And now I write the, a piece of code that sets the first n entries of this array to the value minus 1. If you write with a regular high level language, it's very easy to write such such a statement, such a full 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 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 obstruction. And as far as the machine language is concerned, the array is just a segment in memory of which we know the base address of this segment and, and the length of the array that the programmer has decided to declare. So if we assume that the array starts in entries 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 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 minus 1. This the goal, that's, that's what we want to do. And the question is of course how do, how do we actually do it? All right, so let's start working on this on, on writing this particular program. The beginning of program is going to set up 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 we n, with n. We assign the number 10 to n. We initialize i to 0. You know, once again, don't forget, we are, we, 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, we can start actually doing going through the loop, so to speak. So once we do these three variable declarations and assignments, we have this as setting arr, n and i allocated to memory registers 16, 17, 18. And we are ready to begin the actual processing. All right, so here is the actual processing. The first segment of of the loop, and by the way, we we realize the for loop using a machine language oriented the loop, which begins with a label decla, declaration called loop. And the first thing that we do is we translate the termination condition into a machine language. So, what used to be, if i equals n, goto END, which is, you know, the end of the processing. Because once i, you know, what is i? i begins with 0 and go through 1, 2, 3. When it, when it gets to 10, in our example, we want to jump to n, so we have six hack instructions that actually perform this semantics. And then we come to the heart of this loop, in which we actually assign the number minus 1, which is meaningless, by the way, we just used it as an example. We assign minus 1 to the current entry of the array. How do we do it? Well, let us begin with the, with a comment. And well as you see, what we are doing is, we, 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 0, then the first entry that we're going to operate on is RAM 100, because arr is 100. And then i will become 1. So we'll operate on RAM 101, and then i becomes 2, we'll operate at 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 say, at arr. No 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 is new to 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 minus 1, the register that will be affected is the register that A addresses. Now if we do this within loop, the trans ten times or 10,000 times in each iteration, the A register will acquire, you know, 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 as advertised. So. Variables that store memory addresses like arr and i are called pointers, in, in any language not, not only in in Hack. And in Hecht the typical logic is as follows. Whenever we have to access a memory using a pointer, we need some instructions like A equals something, something that comes from some memory register. So the typical semantics 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. Okay, so this in a nutshell, is how we do pointer processing in in the Hack machine language. In the next part of this unit, in the next and final part of this unit, we will see how pointer manipulation comes to play in the when we write code that interacts with the screen and and with other similar peripheral devices. All right, so 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 on it and a 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 yet another area on the memory called which we call keyboard. All right, 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. All right, so here's an example of using the screen, and in particular, using the screen to draw a rectangle. You know, 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 ROM, the instruction memory on the left, data memory next to it. And then we see some simulation of a physical screen. We see it at 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 some number like 50 in RAM[0] and, and clicks the the play icon, what will happen is that the co, the program will start running and at the end of its execution, which 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 the CPU emulator and actually demonstrate this program working, and then once we'll do it, we'll then talk about the code proper. The purpose of this demo is to illustrate how we can load and execute a 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 the 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 to want to draw a rectangle at the screen's top left corner. And hopefully that's 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 co, 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 look for this program, Rectangle.asm. Here it is. Found it. Loading it. And it's interesting to contrast the source code with what was actually loaded into, into the CPU emulator. So let's take this window and put it right next to the loaded 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 CPU 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 of Hack symbolic programs into machine language. This is something that we are going to learn in Unit 6. So please don't worry about it for now. If you want to understand how a program works in the CPU emulator, 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. All right, so let's put this window roughly back where it was before. And go back to the CPU emulator, and once again the program is loaded. We are told that we have to determine the depth or, 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 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 a 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 executed. This is fairly slow, so I can make it faster by using this slider here, and I see now that the rows until the counter of, 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 goto command. It 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 just 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 more 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 have 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 what, 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, if you get your pseudo code right, it's like 90% of the job done because the rest of it is translating the pseudo code into machine language. Which is a relatively, technical, thing to do. All right. So, let us focus on some subset of our CPU emulator, screenshot. On the right hand side, we, we 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, you know, for i goes from 0 to N, where N is the value of RAM0. That's the 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 pixels in the beginning of row i. So the rows go from, let's say, 0 to 49, and then we 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, that I'm going to use. So at the beginning, addr equals SCREEN, n equals RAM[0]. You know, I don't want to destroy RAM[0], so I save it in a nicely and, variable that I declare to be N. And then I set i to 0 to, 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 minus one. 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, where I am in the loop, and then I'm going to repeat this thing n times. Okay. Why minus one? Well we discussed it when we looked at the simulation, minus one in binary is 16 ones, which will represent, 16 black, pixels. Now, why do I have to, to jump in this, 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 gives you one row in the physical display, you alternate, and because we're interested only in the first 16 pixels in each row, we can safely jump from the current word to the current word plus 32 or the index of the current word plus 32. So, this pseudo code should deliver the, the, rectangle drawing, and what remains to be done is to simply translate these pseudo code into machine language. This is, by now, by this stage of the course or by this stage of, of the lectures in this week, this is a relatively straightforward, task. I have split the programming to two different fields on the screen. And you can stop the video, look at the, look at the code. Convince yourself that it does what pseudo code in the previous slide advertised to be doing and one you know area of the code which is kind of interesting is this area in which. I finally, computed the, the address in which I'm going to operate. I set this address into the A register and then, I operate on this particular memory register, register and set it to minus 1. This is very similar to what we did previously with the, 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 are 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 will be interesting as it, 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 the course in which we part in this unit in which we talk about working with the screen. And, I'd like to say a few words about working with the keyboard, and as you recall, they keyboard is the standard unit with which we interact with the user, with the user, with which we acquire inputs from the user. So, how do we, how can we write code that manipulates the keyboard. In previous units, we discussed how the keyboard is connected 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 setting is such, that if the user presses any key on the physical keyboard, the scan code of this key appears in the keyboard memory map in this designated register. So, 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. We have to write code that accesses this, particular register and inspects it. So, 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, if 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 0, it means that the keyboard is idle and the user is not really using it. Otherwise, it, it contains the scan code of the presently pressed key. Now, this is very, very low-level programming. You know, all we know is which key the user is pressing. Normally, when you write computer programs, you want to let the user enter, you know, complete strings, like a log in or a password or something like that. So, you have to accumulate several keys, until the user presses enter or 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, you know, 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 do about, what we wanted to say about low-level programing. 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, to the notion of compilation in some of the examples that we saw in this and in previous units. And, in particular, you know, we, 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 abstraction 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 re-write the code using the within, within the, the constraints of of the low-level language. Now, in the second part of the course, in 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 our, a host operating system. And if you want to learn all these very interesting layers of obstruction well, you have to take or you're invited to take the second part of this course. All right, so, finally, I think that by now you're convinced that low-level programming is, first of all it's, it's very low-level. You have to work directly with the machine. But, it's also because it is so minimal and so Spartan, 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, is subtle and it's intellectually challenging. And it kind of reminds me of, of a saying that I heard somewhere which I think is very is very correct. And the, 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 Spartan, capability, I can execute any program that comes to our 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, 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're going to write some programs on your own. And, we'll give you some tips on, on how to do it easily.
