In this project-centered course you will build a modern software hierarchy, designed to enable the translation and execution of object-based, high-level languages on a bare-bone computer hardware platform. In particular, you will implement a virtual machine and a compiler for a simple, Java-like programming language, and you will develop a basic operating system that closes gaps between the high-level language and the underlying hardware platform. In the process, you will gain a deep, hands-on understanding of numerous topics in applied computer science, e.g. stack processing, parsing, code generation, and classical algorithms and data structures for memory management, vector graphics, input-output handling, and various other topics that lie at the very core of every modern computer system. This is a self-contained course: all the knowledge necessary to succeed in the course and build the various systems will be given as part of the learning experience. The only prerequisite is knowledge of programming at the level acquired in introduction to computer science courses. All the software tools and materials that are necessary to complete the course will be supplied freely after you enrol in the course. This course is accompanied by the textbook "The Elements of Computing Systems" (Nisan and Schocken, MIT Press). While not required for taking the course, the book provides a convenient coverage of all the course topics. The book is available in either hardcopy or ebook form, and MIT Press is offering a 30% discount off the cover price by using the discount code MNTT30 at https://mitpress.mit.edu/books/elements-computing-systems. The course consists of six modules, each comprising a series of video lectures, and a project. You will need about 2-3 hours to watch each module's lectures, and about 15 hours to complete each one of the six projects. The course can be completed in six weeks, but you are welcome to take it at your own pace. You can watch a TED talk about this course by Googling "nand2tetris TED talk". *About Project-Centered Courses: Project-centered courses are designed to help you complete a personally meaningful real-world project, with your instructor and a community of learners with similar goals providing guidance and suggestions along the way. By actively applying new concepts as you learn, you’ll master the course content more efficiently; you’ll also get a head start on using the skills you gain to make positive changes in your life and career. When you complete the course, you’ll have a finished project that you’ll be proud to use and share.
Unit 0.8: Low-Level Programming, Part III
Loading...
En provenance du cours de Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
167 notes
Hebrew University of Jerusalem
167 notes
À partir de la leçon
Machine Language
Rencontrer les enseignants
Shimon SchockenProfessor
Computer Science
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.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
