From NAND to Tetris Building a Modern Computer From First Principles
HomeCourseBookSoftwareLicensePapersTalksCool StuffAboutTeamStay in TouchQ&A

project 8: Virtual Machine II - Program Control


We continue building the VM translator - a program that translates programs written in the VM language into programs written in the Hack machine language. This is a respectable chunk of engineering, so we are doing it in two stages. Welcome to stage II.


Extend the basic VM translator built in project 7 into a full-scale VM translator. In particular, in project 7 we focused on handling the stack arithmetic and memory access commands of the VM language. We now turn to handle the VM language's branching and function calling commands.


Write a full-scale VM-to-Hack translator, extending the basic translator developed in project 7, and conforming to the VM Specification, Part II (book section 8.2) and to the Standard VM-on-Hack Mapping, Part II (book section 8.3.1). Use your VM translator to translate he VM programs supplied below, yielding corresponding programs written in the Hack assembly language. When executed on the supplied CPU emulator, the translated code generated by your VM translator should deliver the results mandated by the test scripts and compare files supplied below.


The relevant reading for this project is chapter 8. You will need two tools: the programming language with which you will implement your VM translator, and the supplied CPU emulator. This emulator allows executing, and testing, on your PC, the machine code generated by your VM translator. Another tool that comes handy in this project is the supplied VM emulator. The VM emulator (described at the bottom of this page) allows experimenting with the supplied VM programs before setting out to write your VM translator.


We recommend completing the implementation of the VM translator in two stages. First, implement and test the translation of the VM language's branching commands. Next, implement and test the translation of the function call and return commands. This will allow you to unit-test your implementation incrementally, using the test programs supplied below.

Testing how the VM translator handles branching commands:

Program Description Test Script
BasicLoop.vm Computes the sum 1+2+...+ n and pushes the result onto the stack. This program tests the implementation of the VM language's branching commands goto and if-goto. BasicLoopVME.tst
FibonacciSeries.vm Computes and stores in memory the first n elements of the Fibonacci series. This typical array manipulation program provides a more challenging test of the VM's branching commands. FibonacciSeriesVME.tst
FibonacciSeries.tst FibonacciSeries.cmp

Testing how the VM translator handles function call and return commands:

Program Description Test Script
SimpleFunction.vm Performs a simple calculation and returns the result. This program provides a basic test of the implementation of the VM commands function and return. SimpleFunctionVME.tst
SimpleFunction.tst SimpleFunction.cmp

An optional and intermediate test, which may be useful when SimpleFunction (the previous test) passes but FibonacciElement (the next test) fails.
Tests several requirements of the function calling protocol.

For more information about this optional test, see this guide and this stack diagram.

Can be used with or without the VM bootstrap code.

Since the program consists of more than one .vm file, the entire directory must be translated.

The translation should yield a single assembly file named FibonacciElement.asm.

See the note below for more information on handling multiple .vm files.
Tests the handling of the VM's function calling commands, the bootstrap section, and most of the other VM commands. The program directory consists of two files, as follows.

Main.vm contains one function named Main.fibonacci. This recursive function returns the n'th element of the Fibonacci series, and is unrelated to the Fibonacci series program described previously in this project.

Sys.vm contains a single function named Sys.init. This function calls the Main.fibonacci function with n=4, and then loops indefinitely (the Sys.init function, in turn, will be called by the VM implementation's bootstrap code).
FibonacciElementVME.tst FibonacciElement.tst FibonacciElement.cmp

Unlike the previous tests, this test assumes that the VM translator initializes the VM implementation.

If the generated assembly file will not begin with bootstrap code, the test will fail.
Class1.vm and Class2.vm contain VM functions designed to set and get various static values; this is done in order to test the handling of the static memory segment.

Sys.vm contains a single Sys.init function that calls the get/set functions of Class1 and Class2

This test assumes that the VM translator initializes the VM implementation; if the generated assembly file will not begin with bootstrap code, the test will fail.
Proposed Implementation

For each one of the five test programs, follow these steps:

  1. To get acquainted with the intended behavior of the supplied test program Xxx.vm, run it on the supplied VM emulator using the supplied XxxVME.tst script (if the program consists of one ore more files residing in a directory, load the entire directory into the VM emulator and proceed to execute the code).)
  2. Use your VM translator to translate the supplied Xxx.vm file, or directory, as needed. The result should be a new text file containing Hack assembly code. The name of this file should be Xxx.asm.
  3. Inspect the translated Xxx.asm program. If there are visible syntax (or any other) errors, debug and fix your VM translator.
  4. To check if the translated code performs properly, use the supplied Xxx.tst and Xxx.cmp files to run the translated Xxx.asm program on the supplied CPU emulator. If there are any problems, debug and fix your VM translator.

API: Chapter 8 includes a proposed, language-independent VM translator API. This API can serve as your implementation's blueprint.

Implementation order: The supplied test programs were carefully planned to test the incremental features introduced by each stage in your VM implementation. Therefore, it's important to implement your VM translator in the proposed order, and to test it using the supplied test programs at each stage. Implementing a later stage before an early one may cause the test programs to fail.

Initialization: In order for any translated VM program to start running, the translated program (written in Hack assembly code) must include a preamble startup code that forces the VM implementation to start executing it on the host platform. In addition, in order for the translated code to operate properly, the base addresses of the virtual segments must be stored somewhere on the host RAM. The first three test programs in this project assume that the startup code was not yet implemented, and include test scripts that effect the necessary initializations (as was done in project 7). The last two programs assume that the startup code is already part of the VM implementation.


Before setting out to extend your basic VM translator, we recommend playing with the supplied .vm test programs. This will allow you to experiment with branching and function call-and-return commands, using the supplied VM emulator.

The VM emulator: This Java program, which should be in your nand2tetris/tools directory, is designed to execute VM programs in a direct and visual way, without having to first translate them into machine language. For example, you can use the supplied VM emulator to see - literally speaking - how one function calls another, and how the called function does its act and returns a value to the caller. For more information, see the VM emulator tutorial (PowerPoint Format Portable Document Format ).

Here is a typical screen shot of the VM emulator in action:

Best viewed with
Designed and built by Tali Gutman ©