Project 28 (ecs08)

March 29, 2010

This project has intermediate milestones that are relevant to your grade.

Objective

Extend the basic VM translator built in Project 7 into a full-scale VM translator. In particular, add the ability to handle the program flow and function calling commands of the VM language.

Resources (same as Project ecs07)

You will need two tools: the programming language in which you will implement your VM translator, and the CPU Emulator supplied with the book. This emulator will allow you to execute the machine code generated by your VM translator -- an indirect way to test the correctness of the latter. Another tool that may come handy in this project is the visual VM Emulator supplied with the book. This program allows experimenting with a working VM implementation before you set out to build one yourself. For more information about this tool, refer to the VM Emulator Tutorial.

Contract

Write a full-scale VM-to-Hack translator, extending the translator developed in Project 7, and conforming to the VM Specification, Part II (Section 8.2) and the to the Standard VM-on-Hack Mapping, Part II (Section 8.3.1). Use it to translate the .vm programs supplied below, yielding corresponding .asm programs written in the Hack assembly language. When executed on the supplied CPU emulator, these assembly programs should deliver the results mandated by the supplied test scripts and compare files.

Building Plan

You should complete the implementation of the translator in two stages. First implement the program flow commands, and then the function calling commands. This will allow you to unit-test your implementation incrementally, using the test programs supplied below.

For each program Xxx, the XxxVME.tst script allows running the program on the supplied VM Emulator, so that you can gain familiarity with the program's intended operation. After translating the program using your VM Translator, the supplied Xxx.tst and Xxx.cmp scripts allow testing the translated assembly code on the CPU Emulator.

An estimated timeline with project milestones is provided at the bottom of this project document.

Test Programs

Five VM programs are supplied, designed to unit-test the proposed implementation stages described above. For each program Xxx are supplied four files, beginning with the program's code in Xxx.vm. The XxxVME.tst script allows running the program on the supplied VM Emulator, so that you can gain familiarity with the program's intended operation. After translating the program using your VM Translator, the supplied Xxx.tst and Xxx.cmp scripts allow testing the translated assembly code on the CPU Emulator.

Testing the program flow commands implementation:

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 goto and if-goto commmands.

BasicLoopVME.tst

BasicLoop.tst

BasicLoop.cmp 

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 the function calling commands implementation:

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 function and return commands.

SimpleFunctionVME.tst

SimpleFunction.tst

SimpleFunction.cmp

FibonacciElement:

Main.vm

Sys.vm

A full test of the implementation of the VM's function calling commands, the bootstrap section and most of the other VM commands. The program directory consists of two .vm files:
  • Main.vm contains one function called fibonacci. This recursive function returns the nth element of the Fibonacci series.
  • Sys.vm contains one function called init. This function calls the Main.fibonacci function with n=4, and then loops infinitely.

(The bootstrap code of the VM implementation includes a call to Sys.init)

Since the overall program consists of two .vm files, the entire directory must be compiled in order to produce a single FibonacciElement.asm file. (compiling each .vm file separately would yield two separate .asm files, which is not desired here).

FibonacciElementVME.tst

FibonacciElement.tst

FibonacciElement.cmp

StaticsTest:

Class1.vm

Class2.vm

Sys.vm 

A full test of the implementation's handling of static variables. Consists of two .vm files, each representing the compilation of a stand-alone class file, plus a Sys.vm file. The entire directory should be compiled in order to produce a single StaticsTest.asm file.

StaticsTestVME.tst

StaticsTest.tst

StaticsTest.cmp

 

Tools (same as Project ecs07)

The VM Emulator: This Java-based VM implementation illustrates how the VM works, using visual GUI and animation effects. Specifically, it allows executing VM programs directly, without having to translate them first into machine language. This practice enables experimentation with the VM environment before you set out to implement one yourself. Here is a typical screen shot of the VM Emulator in action:

Recommended Steps

First, read ECS chapter 8.

Within your src directory, create a subdir named project08. Extract the contents of project08.zip into it.

Add, commit and push the new files.

cd src/project08
git add *
git commit -m "Adding project08 files. Fibonacci yourself!"
git push

Next, copy your VM source files from your project07 directory to your new project08 directory.

Write and test your VM code in the stages described above, adhering to the contract specified in chapter 8. For each one of the above test programs, follow these steps:

  1. Run the program on the supplied VM Emulator, using the XxxVME.tst test script, to get acquainted with the intended program's behavior.
  2. Use your VM Translator to translate the .vm file(s). The result should be a single text file containing a translated .asm program, written in the Hack assembly language.
  3. Inspect the translated .asm program. If there are visible syntax (or any other) errors, debug and fix your translator.
  4. Use the supplied .tst and .cmp files to run your translated .asm program on the CPU Emulator. If there are run-time errors, debug and fix your translator.

The supplied test programs were carefully planned to test the specific features of each stage in your VM implementation. Therefore, it is important to implement your translator in the proposed order, and to test it using the appropriate 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, it must include a preamble startup code that forces the VM implementation to start executing it on the host platform. In addition, in order for any VM code to operate properly, the VM implementation must store the base addresses of the virtual segments in the correct locations in 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 effects the necessary initializations "manually". The last two programs assume that the startup code is already part of the VM implementation.

Hints

Collaborate! We have a lot of code to write for the remainder of this semester.

Dive in! This project will take some hacking *bzzzt*.

Plan your time and stick to the milestones below.

Grading Criteria (850 pts)

Due Date Points Description Grading Criteria
March 31 @ 5:00PM 300 Pass BasicLoop, FibonacciSeries tests You must commit & push a version of your VM Translator that successfully translates BasicLoop.vm and FibonacciSeries.vm
April 2 @ 5:00PM 150 Pass SimpleFunction tests You must commit & push a version of your VM Translator that successfully translates SimpleFunction.vm.
April 5 @ 5:00PM 400 Pass FibonacciElement, StaticsTest tests You must commit & push a version of your VM Translator that successfully generates FibonacciElement.asm and StaticsTest.asm.
n/a extra credit Share snippets Share your gists containing regular expressions, code snippets (eg, opening & writing to files), helpful libraries, etc by posting links to your gists on the forum.

Your repository must show a history of work. You should be committing at least every time you complete a milestone (per the ones above or your own intermediate milestones). A repository log showing one commit with a message like "project done" is not acceptable.

The final due date is 5PM on Monday, April 5.