Unit 1.9: Project 7: Building the VM Translator, Part I

Loading...

From the course by Hebrew University of Jerusalem

Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)

212 ratings

Hebrew University of Jerusalem

Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)

212 ratings

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.

From the lesson

Virtual Machine I: Stack Arithmetic

Unit 1.0: The Road Ahead21:37

Unit 1.1: Program Compilation Preview12:36

Unit 1.2: VM Abstraction: the Stack15:32

Unit 1.3: VM Abstraction: Memory Segments9:57

Unit 1.4: VM Implementation: the Stack17:13

Unit 1.5: VM Implementation: Memory Segments26:36

Unit 1.6: The VM Emulator23:08

Unit 1.7: VM Implementation on the Hack Platform8:57

Unit 1.8: VM Translator: Proposed Implementation12:27

Unit 1.9: Project 7: Building the VM Translator, Part I23:05

Unit 1.10: Perspective17:20

Meet the Instructors

Shimon Schocken
Professor
Computer Science

In this unit we'll discuss project seven in which we'll build

the first part of our VM translator.

Now, since this is the first project in the course,

I'd like to say a few words about the big picture.

And what you see here is the overall Nand to Tetris journey which starts,

if we think about it top to down.

It starts with some human thought or some fantasies about developing,

let's say a Tetris game or a Pong game or something like this.

And then you go through several stages of construction

until you end up with a program that actually runs on a real computer.

Now to remind you we decided to divide this overall journey into

two different parts, two different courses.

And in Nand to Tetris part one we've built the hardware platform which

is the host computer on which we can actually execute programs.

This course in part two, we build the elaborate soft

hierarchy that sits on top of the host hardware platform and

enables us to write programs in high level language like Jack or Java or Python.

And then translate them all the way down into machine language,

generating code that can actually execute on the platform that we built in part one.

Now, we decided to split this overall journey into six standalone projects,

which are numbered project seven all the way up to project 12.

And we also have project zero, which is kind of optional, and

was the focus of the first module of the course.

In this particular module, we're going to focus on project seven,

in which we build the first stage of a full blown

VM translator that can translate programs from VM code to machine language.

And I also listed project zero because we're going to use some tools

that come into play in project zero and they will serve us in Project 7 as well.

Now, to remind you, the VM code is written in the VM language and

the VM language consists of four categories of commands

of which in Project 7 we're going to focus only on the first two.

So we're going to develop a basic VM translator that is

capable of translating VM programs that include arithmetic,

logical, and memory access commands into machine language.

And in the next project, in project eight, we're going to deal with the rest of

the VM language and complete the picture of building the full blown VM translator.

So here's an example of a VM program, which is stored in some VM file,

it is actually a set or a sequence of VM commands.

And the goal of Project 7 is to write a program in a language like Java or Python,

a program which is called a VM translator that goes through this input file and

translates it into assembly code.

So here's the translation of the first VM command, and

then we continue to go through the input file.

And for each VM command we provide or

rewrite the translation of this command into the output asm file.

And notice that there's just a little detail that I recommend that your

VM translator will always emit a comment

that specifies which command it is now translating.

If you do this, then debugging will be much easier because when you read

the produced assembly file, you can sort of see and

then relate the assembly code to the commands that generated it.

So that's the overall goal.

Now the question is how do you test the translation?

How can you tell or ascertain

that the VM translator actually generates legible machine level code?

Well, you can take this code,

the code that we generated, and load it into the target platform.

In our case, the head computer, run it, and

convince itself that the code is doing what the source code intended to do.

So going back to the overall picture, we can once again take the code,

load it into the machine level, and run it.

Now, if you didn't take Nand to Tetris part one, and

also if you did take it, there's an alternative way of doing it.

Instead of using the actual hack computer, we can use a supplied

CPU emulator that can run hack programs as is and

do exactly what the host platform would do for real.

And if you use the CPU emulator, you can run it on any computer,

including your own PC.

And indeed if you downloaded the Nand to Tetris software suite,

you have this program available to you.

And we use it actually in project zero.

And that's why I listed project zero as an element of Project 7 as well.

So we can use a CPU emulator to test the resulting code does

what it's supposed to do.

All right, now I'd like to go through our development plan, which is a little

bit elaborate, and explain what we have to do in every step of the way.

So first of all, we supply five VM programs and

each one of them is designed to test some specific features

of the VM translator that you're building in Project 7.

Every one of these programs is stored in a separate directory, so

there are five directories, that have the same name as the name of the program.

And here's an example of one of these directories, called BasicTest.

Now, the most important file in this BasicTest directory is

the VM program itself, that's the program that we have to translate, and

the other files provide some other purposes that I'll explain later on.

So here's the contract.

Your job is to write a VM-to-Hack translator which conforms

to the Standard VM-to-Hack Mapping that we described in unit 1.7.

Now we have to use the VM translator in order to translate every one

of the five VM files that we supplied in this project.

And for every one of these translations, you have to generate an assembly program.

And then, when you execute the resulting assembly program on the VM emulator,

the output file that our script is going to produce

from your code has to be the same as the supplied compare file.

If this is the case, you pass the test and

you can go on to translate the next VM program and go through the same routine.

So let me go through the exact steps that I recommend that you go through

when you test every one of these five programs.

Well, first of all, there's an optional stage that I recommend that you go

through, in which you take this VM program and you play with it in the VM emulator.

And I recommend that you do it in order to get acquainted with the VM program and

understand what it is designed to do.

Now it's not really directly relevant to this project because this project

translates the program into assembly and

the VM translator doesn't care what the program is doing.

It is simply, it views it as a translation task from one file to another.

However, if you spend a few minutes playing with this program,

it will give you a lot of good context for the subsequent translation task.

All right, so the next thing that you have to do, once you understand what the VM

program is doing, you invoke your VM translator, the program that you wrote and

you translate it into an assembly program which is stored in a separate asm file.

Now the next thing that I recommend you do is take this resulting asm file,

load it into some text editor and convince yourself that the file looks good.

After all, this file was generated by your VM translator and

you want to make sure that it generates some legible VM commands.

If there's any problem, you have to go back to VM translator and fix it and

repeat this process.

Once you've completed this visual inspection, you can load the ASM file into

the CPU emulator and proceed to execute it and inspect the results.

Unfortunately, the last stage, stage 4 will not work out.

And it will not work because the source VM code,

as well as the assembly code that your VM translator generated from it,

expects to use the stack and the virtual memory segments.

And there's nothing in the source code that actually initializes

these virtual segments and the stack on the host platform.

So instead you have to load the supplied test script

into the CP emulator, execute it, inspect the results.

And if there's a problem you can go back to stage one and fix your VM translator.

If you use the test script instead of the assembly file.

The test script will take care of all the required initializations and

then the translated code will actually execute on the CPU emulator correctly.

All right, now we have to use all sorts of tools and resources in this project,

and the first thing that you need are the test programs and the compare files.

They are available in the project directory in your computer.

You have to experiment with the supplied VM programs.

You can do it using the supplied VM emulator.

You have to translate these VM programs into assembly.

You do it by using your VM translator, the VM translator that you are developing.

And then in order to test resulting code, we use the supplied CPU emulator,

as we just explained.

And in order to develop the VM translator,

you need some resources like a high level language, java, python and so on.

We recommend that you take a look at some tutorials that we provide in

the nand2tetris website.

The VM emulator tutorial, the CPU emulator tutorial and you can also consult

chapter seven in the nand2tetris book, the elements of computing systems.

So this is an elaborate project, and

you have all these tools that will help you complete it successfully.

All right, now there are some testing challenges that you have to,

we have to address, and actually described them already.

So I would like to summarize them again.

The code that we provide in the VM files is missing

what I call the function return envelope.

And therefore this code does not initialize the stack and

the VM segments on the holes platform.

So these missing items would be supplied in or completed in project eight.

And for now, we use a test script that plugs these holes manually.

So the test kit starts with the usual preamble commands that we don't have to

fully understand, it's not, once again, part of the course.

Then we have a set of commands that anchor the virtual memory segments and the stack.

On the whole strand.

And then we have a loop that actually executes the resulting machine label code.

So we see that we use these commands in order to manually what project

eight will do automatically when we get to work on eight in the next module.

All right, what I'd like to do next is to recap and

go through everything that I said so far,

in the context of actually using the tools that you have to use in project seven.

So this will be done in the next video clip.

The purpose of this demo is to walk through the steps

that you have to go through when you work on Project 7.

So I have here my nand2tetris folder.

Let's go into Project 7.

And within Project 7 we'll go into memory access, and into basic test.

And let me resize the window for better focus.

And we see that what we have here are four files, a compare file.

A test script design for the CPU emulator

then we have the vehicle that you have to translate into assembly.

And finally we have yet another test script design for the VM emulator.

The star of the process here is basictest.vm,

this is the program that we have to translate so let's take a look at it.

Well, we see that we have here a set of VM commands, which are designed

to carry out various operations on the stack and

the virtual segments, constant, local, argument, this, that and so on.

So the challenge that we are facing is to translate this VM into assembly code.

And then use the CPU emulator to run the assembly code and ascertain

that resulting code actually carries out what the VM code was supposed to do.

And so before we actually go through this translation process and

testing process, it make sense to try to play a little bit with the source code and

understand what the source code is designed to do.

So let me bring up my VM emulator and

load into it the BasicTestVME.tst script.

And as I said before, I think in one of my demos,

there's a little glitch in the output GUI.

So sometimes you have to click the output pane in order to see

or reveal its contents.

And so here is the test script and we can begin executing it.

So let's do a single step through the test script.

And we see that several things happened.

First of all the basictest.vm file was loaded into the simulator.

And we also see that the test script has created a new output file

called basictest.out.

I suspect that at this stage that the output file is empty

because nothing really happened yet in the execution of the code and

indeed they can take a look at it.

So let's do that.

And we see that the output file contains some labels of RAM locations,

but null values associated with them.

And they're null values because the code did not run yet.

So let us now select a fast execution pace, and

then fast forward through the script, and

at this stage I can kind of sit back and watch what is going on.

Which is rather difficult because the script runs rather quickly.

But now I can go into the virtual segments, and

the host RAM, and explore what happened with this program.

And I don't really want to get into this because we already gave

quite a detailed demo of the VM emulator.

I believe we did it in unit 1.6.

And in fact,

we illustrated the VM emulator in the context of this very same program.

So there's no need to repeat this material here.

Instead, I will minimize now the VM emulator and

turn to the next step in the process.

Which is translating the VM test file into assembly.

Now I wish to remind you that the essence of project seven is writing

a VM translator, and my VM translator has been written in Java.

So in order to use it, I'm going to bring up my

Terminal window and type java VMTranslator,

that's the name of my translator program.

And then I'm going to supply a parameter, which is the name of the file that I want

to translate, which happens to be basictest.vm.

All right, let's enter this command, and as you see, a new file has been created.

And this file is BasicTest.asm written in the Hack assembly language.

Now it may be interesting to take a look at the contents of this file, so

let's do that.

So this is the assembly file that was created and generated by my VM translator.

Let me scroll downward within this file.

And I see that altogether, it contains about 200 lines of hack assembly commands.

Now I remind myself that the original source

VM test file contained about what, I think 25 lines of code?

And so the translation ratio is about one to eight.

In other words, every VM command, upon translation,

generates about on average about eight Hack assembly commands.

Now it may well happen that your VM translator is better written than mine,

and therefore it may generate tighter assembly code and

achieve a better translation ratio.

Now the next thing I'd like to do is test that

the generated assembly code is actually correct.

In other words, I want to ascertain that this code

carries out what the source code sought to do, and

in order to do this, I'm going to invoke my CPU emulator.

So here is my CPU emulator into which I'm going to load

the supplied BasicTest.sts script file, this one.

And as usual, I will click my output pane in order to reveal its contents.

And let's see.

I will single step the first batch of scripting commands, and

in response, the CPU emulator has loaded the assembly program that

was generated by my VM translator into the emulator environment.

It's right here.

So now I can execute this program and see what happens.

So let's click fast forward, and now I can kind of sit back and

watch the code that was generated by my program execute.

And I see that execution continues because there's nothing that tells it to

stop in the code.

And at some point, right here, execution has stopped.

And the execution stopped because the supplied test script

is programmed to execute 600 clock cycles.

And therefore at some point it kind of forces the program to stop.

Now, how do I know that the program has run successfully?

Well, first of all,

I got this very nice message that tells me that I have fulfilled the contract.

The translated assembly code has passed the test

that was mandated by the supplied test scripts.

Now if you're not sure how to use the CPU emulator, you can go back to module zero

and look for a unit called, I believe, low level programming part one.

And somewhere within this unit, you will find a CPU emulator

demo that you're welcome to look at, and if you wish, you can go to the nand2tetris

website and there you will find a CPU emulator tutorial.

So this has been the demo in which we showed you the various steps that you have

to go through when you work on project seven.

So to recap, in this project and

in this module as well, we began developing a VM translator.

In Project 7, we are focusing

only on the arithmetic logical commands and the memory access commands.

So we developed a program which is capable of translating these commands into machine

level instructions that carry out the same thing on the holes platform.

And in the next module and in project eight, we are going to complete

the VM translator by extending the VM translator to handle also

the branching commands and the function and return commands.

And by doing this, we'll have a full scale VM translator,

which will serve as the back end of our Jack compiler,

the program that enables us to write high level programs,

and translate them all the way down to machine language.

So this is basically the end of the operational part of module 1.

And in the last and final unit, we'll discuss some perspectives and

observations about the general notion of virtual machines.

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.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play