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 5.7: Handling Objects: Manipulation
Loading...
Из курса от партнера Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
150 оценок
Hebrew University of Jerusalem
150 оценок
Из урока
Compiler II: Code Generation
Познакомьтесь с преподавателями
Shimon SchockenProfessor
Computer Science
Now that we understand how objects are constructed,
we can move on to object manipulation.
And when I say object manipulation I mean two different things.
First of all, we have to know how to handle code that calls
methods that are supposed to operated on selected objects.
And then, we have to discuss on compiling the method themselves.
So as usual we have a caller code kind of relationship.
Here we have an example of some clan class that creates some objects,
similar objects to those that we discussed in the previous unit.
And then, we see some examples of method cause and
because this code is almost self-explanatory.
I can guess what is going on here.
It seems like, in the first method call,
I am calling the get x accessor on p1.
And this will presumably get the value of the x coordinate
of the p1 point, and put it In the x variable.
In the second statement it seems like I am doing a vector addition of p1 and
p2, and I am putting the result in p3,
which is yet another point variable.
And in the last statement it seems like I'm measuring the distance between
the Cartesian distance between p1 and p2 and
putting the result in the integer variable d.
Now, obviously all of this is completely irrelevant for the compiler, but as usual.
I want to provide some background information.
So let us focus on the last statement here,
in which we call the distance method for its effect.
This is the caller.
And here is the callee.
The callee is the distance method which is located in the point class.
And when we call it now this is the code which will end up executing.
And as a compiler writer I'm faced
with the challenge of compiling these two classes separately.
Because both of them are or
each class is a separate and standalone compilation unit.
So to get started, let us look at the calling code.
Now, before we actually deal with the code generations, I would like to make
a general comment about the challenge of compiling object orientated code.
And here's the challenge.
When you write programs using the object oriented style then
according to the object oriented philosophy, if you will,
if you want to apply, some if you want to use some subroutine like distance.
Then first you specify the name of the object on which you want to operate,
then you write the name of the subroutine, and then you may or
may not supply some additional arguments to this sub routine.
That's the rule of the game in object orientated languages.
That's how you apply a method or call a method on a particular object.
However, when you write a compiler,
you are going to translate all these calls into some procedure language
like the VM language or ultimately machine language and
these languages don't understand what objects are all about.
And so, you're faced with the challenge of transforming the object
oriented lingo so to speak into procedural lingo.
And here's how you can do it.
What you do is you take the object on which you want to operate,
and you pass it as the first implicit argument To be desired method.
That's how you always do it.
You take this obj, that you see at the end, at the bottom of these examples here.
I just selected it as one typical example.
And you kind of push it, literally, you push it onto the stack because you want it
to become the first argument on which this method is going to operate.
So when we write code the tender such method called,
such method calls that's exactly what we do.
So here's the general technique.
Here is the high level method call.
And in order to generate code that effects the semantics,
we first of all push the object onto the stack.
Then we push as many arguments as we had within within the argument list.
We push them all onto the stack, and then finally, we call fool for it's effect.
And here's an example if you want to compile this particular method call
we do it by pushing the p1 and p2 objects and
then calling distance for it's effect.
Now, what do I mean when I say push an object onto the stack?
After all, the object can be huge.
It can be, I don't know, it can be the image of some JPEG picture
that occupies many thousands of words on the ram.
How do you push it on the stack?
Well, I don't really care What the object contains.
All I'm interested in is the base address of this object.
And the base address is stored exactly in p1 and p2.
So these are the things that I push onto the stack.
And then, if the calling method will have to do something to these objects,
I assume that it will have the code.
That will know how to go into the object and actually manipulate it.
As we will actually see in the remaining of this unit.
So in particular, we now know how to handle the caller side of
the method calling or the object manipulation operation and
now let's move our attention to the method itself.
In this particular case to distance.
Well, let's think about it.
Methods are designed to operate on the current object.
Always, that's why you write methods.
You want to do something to the current object.
And the current object is something that we refer to as a this in all,
or most object oriented managements.
And because we know that the method we
want to operate on the methods on the objects of fields,
we have to somehow facilitate Xs to these fields.
How can we do it?
Well, we discussed it in the first unit of the three unit series
about handling objects.
We can access the objects i-th field by accessing this i.
For example, the first field is stored or represented by this zero,
the second field by this one, the third field by this two, and so on.
However, before we use this segment,
we first have to anchor it on the proper address on the RAM.
And we do this as we learned two units earlier using the pointer segment.
So this technique and this reminder that I just gave you will come to play
in the next slides in which we discuss the actual code that we generate.
So, first of all, just for context,
here's the client code that calls the method for the effect.
We don't really need it, it's a separate compilation unit,
we dealt with it already but it provides context.
And here is the method itself, distance.
How do we compile this method?
Well the method is compiled within some class, right?
So the first thing that we do is when we compile the point class is we'll compile
the three lines, class point, the field declarations, the static declaration.
As we discussed in the previous unit, this will end up with generating no code
whatsoever at the same time the compiler will create the class level symbol table.
And then at some point the compiler will come to generate code for
distance and the first thing that I want to describe is what
the compiler does with these two statements.
Well, both the method declaration and
the variable declaration once again generate no code.
Instead, the compiler creates the symbol table of the subroutine and
populates it with the this object, the current object,
as well as the explicit variables that it
found in the parameter list and in the variable declarations.
All right, moving along.
The next thing that we have to do is rewrite the compiler.
We know that we are now compiling a method.
We can anticipate that the method will want to operate on the current object.
So we know that we have to generate code that will anchor
this on the correct address in memory.
Now, what is the correct address?
It's the address of the current object.
Now what is the current object?
It is the object that the caller passed in order to operate upon.
And this object is always stored in argument zero.
If you're not sure take a look at the subroutine's symbol table and
you will see that this is argument zero, right?
So here's what we do.
We push argument zero onto the stack, and
then we unload it or pop it onto pointer zero.
By doing this, we effectively set that this pointer
to contain the address of the current object,
the object on which you were called to operate.
Well, now that I did it, I can safely access this,
as needed by the high level code.
In particular, here's a command that seeks to manipulate
the x property or the x field of the current object.
How do we do it?
Well, we can easily do it now because this has been taken care of.
So we push this 0, what is this 0,
when we look at the symbol table that's what represents x.
Right?
X is mapped on this 0.
So we push this 0 on the stack and
then we have to do to call get x on other so we push other.
Other happens to be argument one according to the symbol table and
then we call Point.getx for its effect, notifying that we push the one argument.
And then once we get the result of getx we can do the subtraction and
store the result in local 0 which is
the entry that represents dx according to the symbol table.
How do we handle the DY statement in a very similar fashion and
therefore am not going to repeat it.
And finally, we have to handle the method square root computation
which computes the Cartesian distance between the two points.
This has nothing to do with handling
fields and so on, so I just give you the code.
And however, what is super important, is to remember
that after the method has run it's course and
did everything that it was supposed to do it must return something to the caller.
This is a requirement in VM programing.
And indeed we see that we have a return command at the end so
the the compiler generates a return command.
And in this particular example what we'll get returned is the value
that was computed by square root.
Now where will this value go to?
Well, remember that we had a caller right?
So that when the distance method completes it's execution and
terminates, control will return to the caller.
And it will be more clear if we look at the compiled code of the caller.
And we see that control we return
to the point which is exactly specified here just after the method called.
So with that in mind it makes perfect sense to now
push the top most value into d because we know that the top most value
is something very useful that was return to us by the method.
By contract we know that the method returned something so
we remove it form the stack and put it into d.
That's what the high level code wanted us to do so
we generate code that does just that as we saw previously.
Alright so we know how to handle methods
and with that in mind, here's a very important footnote.
How do we handle void methods?
Well, void methods are very similar to regular methods.
However, they return no value.
At least in the high level view of the code.
It looks like they return no value.
For example, if I want to print p1, if p1 stands for
the intersection of, let's say, four and five, then when I print p1 I
would like to see left paren, four, comma, five, right paren.
I have a method that does exactly that.
This method resides in the point class and I don't want to repeat it's call because
we can find it in previous units somewhere and it's not important anyway.
So the question is of course how do we compile
this void method and so let us review that.
So, most of what you'll see now will repeat what we did below or before, and
therefore I'm going to do it briefly.
First we compile the class declaration,
the field declarations, the static declarations and we generate no code.
We just generate or create the class level symbol table.
Then, when we have to generate code for compiling method void print,
the only thing that the compiler will do,
is it will create the symbol table of this subroutine,
which so far contains one entry only, which is this, right?
Because every method, irrespective of what it has to do,
always contains this object as the first entry of its symbol table.
All right, now what should we do next?
Well, we have to generate code that associates this with
the current object as we did before.
So we push argument 0 and pop pointer 0, nothing is new here.
Then we compile the code that was omitted,
so you find it here as well.
And finally, and
that's why I went through the trouble of discussing this whole thing, and
finally I have to remember that methods must return a value.
Now, the print method has a side effect, it prints four comma five,
but it returns no value to the caller, and you see it from the calling code, right?
The calling code doesn't use any assignment or
any variable, it simply says do.
So it does not expect to get a return value, and yet,
according to the rules of the game, I must return a value.
So, first of all, I return a value because I am a good citizen and
I was told that I always have to return a value, so I, as a compiler writer
I generate code at the end of each method that returns a value.
And if I have nothing to return, I push constant 0,
which is a dummy value and then I return, okay?
So once again, as a convention, if you compile or
when you compile void methods at the end of the compiled code,
you push something, we don't care what, and you return, okay?
Now, where do we return?
We return right here, and
if we look at the compiled code right there, and
so, now the compiled code faces the slight problem.
That the stack contains some unnecessary value and we have to get rid of it.
So that's exactly what we do in the last command that you see here, pop temp 0.
We pop the top value off the stack and
we dump it somewhere in temp 0, for example.
And by doing this we remove this unnecessary value from the stack and
we can go on to execute the remaining code.
So, to recap, each compiled method, whether its void or
not must return a value.
By convention, void methods return something,
some dummy value, and by convention it's the responsibility of the caller
to rid the stack from this unnecessary value.
And therefore it's a responsibility of the compiler writer to generate this
statement, pop temp 0, which always completes the call to a void method.
All right, so with that we said everything that we need to say about compiling,
both the caller side and the callee.
As you see, the high level programmer is completely oblivious to
all the incredible drama that takes place behind the scene.
And now you are fully connected to this drama as well, so you've gained
what I hope is a very deep understanding of how our computers handle objects.
And with that in mind we're now ready to move on and talk about the last
unit in this sequence in which we'll discuss how compilers handle arrays.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
