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 1.5: VM Implementation: Memory Segments
Loading...
From the course by Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
150 ratings
Hebrew University of Jerusalem
150 ratings
From the lesson
Virtual Machine I: Stack Arithmetic
Meet the Instructors
Shimon SchockenProfessor
Computer Science
In the previous unit, we started to talk about the VM implementation.
And we went through the implementation of the stack architecture.
And in this unit, we'll continue with implementation of the memory segments.
Now to remind you, we started this journey of
virtual machine with a stack that interacts with some abstract memory space.
And then we replaced this abstract space with eight memory segments,
whose names are local, argument, this, that, constant, static, pointer, and temp.
And the question,
of course, is how to implement these memory segments on the host's computer?
Well, before we get started, let us note that the abstraction
of these memory segments is quite uniform.
We address any location in any segment using exactly the same syntax, push, pop,
segment name, followed by a non-negative integer.
So examples include push constant 17, pop local 2, and so on and so forth.
So how should we go about implementing these memory segments?
Well, we will do it one step at a time, beginning with local.
Now, the local segment is accessed using the uniform syntax
that we had all along push, pop, segment name, index.
So here's the local segment in the context of this simple example of a stack machine.
And how do we realize these two data structures on the host RAM?
Well, the stack is going to be implemented as we did in previous units.
We'll start the stack at 256, which is an agreed-upon convention.
And we use a pointer that we call SP, to record the address of
the next available location in the stack.
And we decided that SP will be mapped on RAM 0 in the host memory.
Now, what about the local segment?
Well, the local segment can be placed,
in principle, anywhere we want on the host RAM.
We don't care where the local segment is going to be stored,
as long as we remember the base address of this block.
And as you see here, we've decided to place
the base address of the local segment in a pointer called LCL.
And we also decided that LCL will refer to RAM 1.
So as you see in the example, the local segment happens
to begin in this arbitrary address that I made up, 1015.
And LCL contains the same address.
So notice that indeed we are using two pointers, but
we use them in a very different way.
The stack pointer points to the next available location in the stack.
And LCL points to the base address of the local segment.
All right, so here is how we use this implementation
when we set out to implement commands like pop and push.
So here is the same RAM segment that we had before.
And SP and LCL are mapped as we had before.
And following the pop local 2 command, here is what is going to happen.
SP has changed to reflect the pop operation.
And we see that the number 5, which used to be the topmost value in the stack,
is now located in local 2, which happens to be 1017.
Now, how do I know that local 2 is 1017?
Well, that's simple.
I take the base address, which is 1015.
I know this information, right, it's always stored in LCL.
And I add the offset, or the index 2, to it.
And by adding up these two values, I get the value of the target
address on which I have to store the popped value.
Okay, so that's how I can generalize this translation process.
I can take the base address and add the offset to it.
Another thing which is interesting to note here is that, look at address 257.
Right, it contains the value 5.
But notice that this value is out of play, it's kaput, it's dead.
It doesn't know it, but it's dead, because the stack pointer now points at 257.
So the next push, which will happen probably at some point,
is going to kill this number 5.
And that's perfectly okay.
So it's quite typical when you manage a stack that you have all sorts of
garbage along this stack.
And yet the pointers indicate exactly which part of the stack are in play,
and which are kind of game and can be recycled at will.
All right, so how can we translate the pop operation?
Well, we can do it using the pseudo assembly code that you see here.
First of all, we compute the target address,
which is LCL plus 2 in this example.
We store it in some temporary variable, if we need such a variable.
Then we decrement the stack pointer.
And we take the value which is stored now under the stack pointer,
or the value that the stack pointer points at, and we put it into
the address that addr points it.
So this is the semantics that we want to implement.
And how do we implement it in assembly?
Well, that's your job to do it.
Now, you have everything that is necessary in order to
translate such pseudo instructions.
Obviously, you will need the Hack language.
You will need the A command, the C command, and so on.
So that's a little sort of riddle that you have to solve.
And once you do it, you will know how to always implement pop local i commands.
So in general,
indeed you have to observe that there's nothing special about this number 2.
I can replace 2 with i,
and then everything will work just as well as it did before.
Instead of doing LCL plus 2, I will do LCL plus i.
So I manage to indeed generalize this translation completely, and
I know how to handle pop local i.
So here is the generalized translation of pop local i command.
What we see on the right-hand side is exactly what we had in the previous slide.
And the push local i command is implemented in a very similar way,
somewhat symmetric, okay.
So we compute the target address, as we did before.
And then we carry out a push operation using sort of two pseudo instructions.
And once again, in order to actually make it happen,
your VM translator has to generate the assembly instructions
that will realize this pseudo code using the Hack language.
Now, I would like to extend the picture.
And talk now about these four segments together.
The local argument, this and that segments.
And it always helps to sort of extend, also, our perspective.
And remember or think about where these segments come from.
Or what purpose do they serve?
In the sort of larger enterprise of what we're doing.
Well, think about a typical method in let's say in Java which is
operating in run time.
Well, this method typically has local variables,
it has argument variables, typically it processes some current
object which is also a bundle of so-called member variables, I think.
And also the method may well process some array that also has entries,
which are data values.
So when we translate this logic into the world of the virtual machine,
we have to preserve all this semantics.
Well, we do this with the local and argument memory segments,
as well as with two other segments that we call this and that.
This segment stores the member variables or
the values of the fields of the current object, and the that segment
stores the values of the array that the current method may be processing.
So basically, we are using these four segments in order to
capture these semantics also at the VM level.
So how do we implement these four memory segments?
Well, first of all let us remember that abstractly
we use them exactly the same way.
We do push and pop, segment name, index and that's it,
we don't need anything beyond that.
So they are accessed in a uniform fashion.
Well, I'm very glad to report that we also implement them in a precisely
the same way.
In addition to the stack pointer which is always available we are now
also going to use four pointers which are called LCL, arg, this and that.
And every one of these pointers is going to do exactly what the LCL pointer did
in the previous slides.
They're all implemented precisely the same way.
And every one of them holds the base address
of the respective memory segment that it relates to.
And therefore, the implementation of the commands push and
pop is also going to be exactly the same.
We're going to use the same semantics that we use for
the local segment, but instead of saying local, we'll say segmentPointer name where
the segment pointer being the right, the corresponding pointer
to the memory segment that we are dealing with in the source code, in the VM code.
Now, you may well ask yourself a good question here which is, wait a minute,
where exactly on the RAM these segments are going to be located?
Well, the answer is we don't care.
We don't care because they're going to be located somewhere, and
all we have to do is remember the base address of these dynamic allocations.
Well, later in the course we will see that deciding where to put
these segments in memory.
Is a very interesting question, and
we solve this question using all sorts of clever algorithms,
which are going to be part of the operating system, and the compiler,
that together, will decide where to map these segments on the host RAM.
The next segment that I want to discuss is called a constant.
And the context of these constants is that when
the compiler encounters constants in your program,
in your high level source program.
It handles these consents by generating VM that include,
or that use the constant memory segment.
So it is going to be re-expressed using operations like push constant something or
pop constant.
Something on the stack.
So how do we implement these operations?
Well, here's the generic push constant i command and
there's no pop constant because,
you know it doesn't make any sense to store something in this constant.
And the implementation of this constant is trivial
because this is a truly virtual segment.
It doesn't really exist.
So whenever we see a push constant i command, we simply generate
low level code that supplies the specified constant.
So we do *sp equals
the specified constant and then we advance the stack pointer.
So this is has been the treatment of the constant segment.
Moving along, the next segment that we are going to deal with is the static segment.
Now, what's the story of this segment?
Where does it come from?
Well, the compiler that handles your high-level code
may well encounter some static variables.
Now, these are the so-called class level variables that every method in your
class sees.
So obviously we have to treat these variables
differently than the way we treat local variables or argument variables and so on.
And therefore, we've decided that in the virtual machine
extraction we'll use a dedicated segment called static to
represent static variables in the source code.
So every operation on the static variable in the source is going to
be re-expressed as a push static i or pop static i operation at the VM level.
So here is how I'm going to implement static variables.
Well, we start with some example of a VM code in which
using static variables come to play in the context of pop instructions.
Now, let us remember what static variable are all about.
Unlike local variables and
argument variables which are unique for each VM function.
Static variables are at a higher level of scoping.
And therefore,
all the VM functions in your program should see the same static variables.
And therefore since we have this functional requirement
it makes sense to store, or actually it's required to store the static
variable in some global space that all the code
which is generate from these VM functions will see the same static variables.
And so, the decision that we decided to undertake
is to have the VM translator, translate each reference to static
i in some vm File Foo.vm,
into the assembly reference Foo.i, so
Foo, the prefix of this label, Is the name of the file.
And i is the index which is taken from the VM command.
Static five, i equals five, static two I equals 2.
And so, if we follow this convention, which will become
understood in just a few seconds, then the VM translator is going
to translate pop static 5 into well, first there will be some code.
Which I omitted that carries out a pop from the stack and
the topmost value from the stack is going to go into,
I suppose, the d register, the data register, and
then we have to put it into our assembly level incarnation of static 5.
How do we do it?
Well, we generate a label called Foo.5, and then we say M=D.
What about the other command?
Well, we handle it in exactly the same fashion, only instead of 5,
we're going to generate 2.
Now, why is this going to actually work out?
Well, remember, following assembly,
the hack assembler by convention is going to map these
references onto RAM[16], RAM[17],
all the way down to RAM 255, in case you have so
many static variables in your program.
Which is unlikely,
typically we just have a few static variables in a typical computer program.
So, what will happen is that this references will end up being mapped
to the blue area that you see here on the RAM and that's exactly what we want.
Because you see this blue area is outside the stack, and
all the functions which are running in you program can.
Take a look at this RAM area and
see exactly the same thing, the static variables.
And so, in using this trick here, we basically took advantage of
this unique convention in the hack assembler of mapping.
Symbolic variables onto the RAM from position 16 onward.
And therefore, the entires of your static segment
are going to be mapped on RAM 16, RAM 17, and
so on, in the order in which they appear in your VM code.
And therefore, you will have this slightly peculiar situation
in which static 5 in this example will go to RAM 16, static 2 will go to RAM 17.
There's so many to static 2 that there are no more static
variables declared and used in between.
So, there is a one to one mapping,
but the order of the index values is not
the same as the order of the RAM entries.
It's the order of appearance in the code which determines where each
one of these variables will be mapped on the RAM.
So, that's how we implement the static segment,
it's a little bit hairy, but it works, and it works quite well.
And, I'd like to sort of say,
makes general observation about this implementation here.
And that is that up until this point, up until we discussed static variables,
everything that I said in this module was completely platform agnostic.
After all, every computer has a RAM.
And everything that I said about implementing argument and so
on did not make any assumptions about the underlying platform,
aside of the assumption that there's a stack somewhere, which is a very safe
assumption, because once again, every computer has a stack somewhere.
And it is only here in the implementation of static variables that we take
an exception to this platform independence elegance and
we actually take advantage of something which is unique to the Hack assembler.
So once again, up until now everything they said can be implemented
on any computer out there, not necessarily on the Hack platform.
And yet, if you want to implement the static segments,
you have to find some other tricks to do it if you decide to implement our virtual
machine on a computer which is not a Hack machine.
All right, moving along, the next segment that we want to discuss is temp.
Now, why we need the temp segment?
Well, it so happens that when the compiler generates
code when it translates your Jack program into VM code,
it sometimes has to use some temporary variables.
So, we decided that we're going to allocate an 8th
place segment called temp that will contain and
serve these variables when needed.
So, here's how we do it.
The push and the pop are uniform, exactly as we had before,
and yet temp is going to be a fixed 8-place memory segment,
and we decided to allocate or to map this segment on RAM locations 5 to 12.
So, altogether we have eight values there, and therefore the translation of push and
pop are going to take this base address 5 obviously into account.
So, it's almost the same as the translations that we had previously,
except that the base address is now 5 instead of one of the segment pointers.
So, that's how we implement the temp segment.
The last segment that we have to worry about is called pointer.
And the pointer segment is a little bit obscure.
And it's obscure because you can't understand really why we need it until
you begin to write the compiler which is something that we'll do
down the road in the course.
So for now, I'm just going to explain the point of segment as some sort of
almost an arbitrary rule of the game, and given my explanations you will have
all of the information in order to actually realize it on the target machine.
So first of all, where does this segment come from?
Well, it turns out that when the compiler translates a method,
it has to remember the base addresses of the this and that segments.
These are the segments that represent the current object and
the current array that the method may be processing.
So, we decided to keep the base addresses of this and that in this pointer,
in this, I'm sorry, segment, which we decided to call pointer.
So, here are the rules of the game.
Pointer is a fixed memory segment.
It has only two entries, 0, and 1.
And therefore, the only push and pop commands which are applicable here,
are push and pop pointer 0 and 1, and
any other integer is simply invalid in the context of pointer.
Now, what we do with these commands?
This was just the syntax of the commands.
Well, whenever the VM code tries to access pointer 0,
it should result in accessing this.
And whenever it wants to access pointer 1, it should result in accessing that.
So, the implementation should service these push and
pop commands by supplying this and that.
So, with this in mind or with that in mind as you please,
let me say a few words about how we actually do this implementation.
So, the push pointer 0 command should be implemented as follows.
You want to create assembly code that realizes the obstruction,
*SP equals THIS followed by SP++.
If the VM command is push pointer 1, you do exactly the same but
you use THAT instead of THIS.
And the handling of pop pointer is symmetrically similar.
Now, I wish to remind you that the assembly code that you see here is pseudo
code, and you have to realize this pseudo code using Hack assembly.
So, that's how we handle the pointer segment.
Now, I must admit that this segment and the way we use it and
realize it may sound somewhat peculiar and strange.
But you shouldn't worry about it because it will make perfect sense once we talk
about code generation when we set out to write eject compiler.
For now, let us just strive to create this functionality that I described here.
Now, before we end this unit, I'd like to do a recap and observe what we are doing.
So, basically,
we are implementing the VM language which consists of Arithmetic/Logical commands,
Memory access commands, Branching commands and Function commands.
By now, we've implemented the first two categories of commands, and the remaining
two categories are going to be handled in the next module of the course.
So, before we get to this module, we still have some work to do here.
So, I'll meet you in the next unit, when we talk about The VM Emulator.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
