Assignment 05: Hack Virtual Machine

Due Friday, November 21st, before midnight

Milestone 1 Due: Nov 17th (Monday)

In this assignment, we build a translator from VM code to Hack assembler. Your translator will input .vm files and output .asm and .hack files.

The APIs in this assignment follow the design in your book The Elements of Computing Systems but with some differences that will allow us to reuse our work more easily across assignments.

There is a demo requirement for this assignment. You must check-in with the TA or Prof. Normoyle on Nov 20th or 21st during office hours.

Update your repository

We will use the same repository as Assignment 1. The changes have already been merged into your repository.

$ cd cs240-f25-classwork
$ git pull

Your repository should include new files under the folder named Hack-Compiler.

1. Preliminaries

In the files common/filereader.cpp and common/filereader.h, add an option to your FileReader to enable/disable removing all whitespace when reading a file. When stripWhitespace is false, be careful to handle the case where a line is empty or only includes whitespace.

  • bool open(const char* filename, bool stripWhitespace = true)

To test your function, run test_readvm.cpp

$ cat vm/SimpleConstant.vm
// Pushes constant 111

push constant 111

$ make test_readvm
$ ./test_readvm vm/SimpleConstant.vm
push constant 111

2. VM Parsing

In the file, common/vmtranslator.cpp, implement the following functions.

  • VMType vm_type(const char* line): Return the type of command, for example, VM_POP or VM_ARITHMETIC

  • void vm_parse(const char* line, VMCommand* cmd): Fill in the fields of cmd based on the input string.

VMCommand (defined common/vmcommand.h) is a struct that contains the VM type, command, and arguments. Run test_vmparser (implemented in test_vmparser.cpp) to check your work.

$ *make -j6*
$ *./test_vmparser*
push argument 1 -> cmd: 1 arg1: argument arg2: 1
label L2 -> cmd: 3 arg1: L2 arg2:
sub -> cmd: 0 arg1:  arg2:
if-goto end -> cmd: 5 arg1: end arg2:
function print1 3 -> cmd: 6 arg1: print1 arg2: 3
make -j6 runs using multiple jobs (e.g processes) for a faster build speed.

3. Milestone I

In the file, common/vmtranslator.cpp, we will implement the features of VMTranslator step by step, testing each as we go.

To check your work, run vm_compiler which compiles either a VM file or a directory of VM files to both an ASM and Hack file. Then, run your generated code in either

  • The nand2tetris CPUEmulator. Open the ASM file in the emulator, run, and check that the contents of memory are correct

  • Our simulated computer. You have been given executables for testing called test_vm_milestone1 and test_vm_milestone2. This program loads the programs in the /vm directory and checks the contents of RAM afterwards. The executable will only run on Ubuntu Linux. However, the source code has been checked into your repository, under the hack-hw, so you can also compile your own.

You can also run the VM examples in the VMEmulator. This is helpful for understanding the scripts before you translate them to assembly.

3.1. Bootstrap

In the file, common/vmtranslator.cpp, implement the following methods of VMTranslator.

  • translateFile(const char* filename): This method should use FileReader to open the given filename and process each line. For each line, we determine the VM command type and then call the associated writeXX method to generate assembly instructions for it. The instructions should be added to the vector of strings, mInstructions. The algorithm should look as follows:

setFileName // Save the current filename to use for symbol generation
for each line
  parse the line into a VMCommand cmd
  call `writeX(&cmd)` depending on the VM command type X

  • writeInit(): This function writes bootstrap code. To start, add instructions for setting SP = 256

  • setFileName(const char* filename): This function saves the current file being processed in mFilename. The saved filename should not have path and extension characters (e.g. / or .)

  • write(const char* filename): This function writes the contents of mInstructions to a file with the given filename.

$ make -j6
$ cat vm/Bootstrap.vm
// Bootstrap code is added automatically....
$ ./vm_compiler vm/Bootstrap.vm
Writing vm/Bootstrap.asm
Writing vm/Bootstrap.hack
$ ./test_vm_milestone1
Testing vm/Bootstrap.hack...
Program exited
Check: RAM[0] = 256? (Got 256): PASSED
Check: RAM[256] = 0? (Got 0): PASSED
....

3.2. push constant

In the file, common/vmtranslator.cpp, implement the "push constant X" command in writePushPop.

  • void writePushPop(VMCommand* cmd), Converts push and pop commands to assembly. Adds the assembly instructions to the member variable mInstructions

$ make -j6
$ ./vm_compiler vm/SimpleConstant.vm
Writing vm/SimpleConstant.asm
Writing vm/SimpleConstant.hack
$ ./test_vm_milestone1
Testing vm/SimpleConstant.hack...
Program exited
Check: RAM[0] = 257? (Got 257): PASSED
Check: RAM[256] = 111? (Got 111): PASSED

3.3. Arithmetic and logic

In the file, common/vmtranslator.cpp, implement the arithmetic and logic commands in writeArithmetic.

  • void writeArithmetic(VMCommand* cmd), Converts the following commands to assembly. Adds the assembly instructions to the member variable mInstructions

    • add, sub, neg

    • and, or, not

    • eq, lt, gt

You are given a script, compile_tests_milestone1.sh to automatically compile all test scripts. 
$ make -j6
$ ./compile_tests_milestone1.sh
Writing vm/Bootstrap.asm
Writing vm/Bootstrap.hack
Writing vm/SimpleConstant.asm
Writing vm/SimpleConstant.hack
$ ./test_vm_milestone1
Testing vm/SimpleAdd.hack...
Program exited
Check: RAM[0] = 257? (Got 257): PASSED
Check: RAM[256] = 15? (Got 15): PASSED
Testing vm/SimpleSub.hack...
Program exited
Check: RAM[0] = 257? (Got 257): PASSED
Check: RAM[256] = -1? (Got -1): PASSED
Testing vm/SimpleNeg.hack...
Program exited
Check: RAM[0] = 258? (Got 258): PASSED
Check: RAM[257] = -8? (Got -8): PASSED
... etc
False is represented using 0 and True is represented using -1
Auto-generated labels should be unique. A simple way to guarantee unique names is to add a numeric suffix that increments each time a new label is created.

3.4. Memory

In the file, common/vmtranslator.cpp, implement the arithmetic and logic commands in writePushPop.

  • void writePushPop(VMCommand* cmd), Converts the following commands to assembly. Adds the assembly instructions to the member variable mInstructions

    • local, argument, this, that

    • pointer

    • static

    • temp

$ make -j6
$ ./compile_tests_milestone1.sh
Writing vm/Bootstrap.asm
Writing vm/Bootstrap.hack
Writing vm/SimpleConstant.asm
Writing vm/SimpleConstant.hack
$ ./test_vm_milestone1
Testing vm/SimpleLocal.hack...
Program exited
Check: RAM[0] = 256? (Got 256): PASSED
Check: RAM[1] = 300? (Got 300): PASSED
Check: RAM[256] = 111? (Got 111): PASSED
Check: RAM[303] = 111? (Got 111): PASSED
Check: RAM[306] = 111? (Got 111): PASSED
... etc

4. Milestone II

Now, we will implement branching and functions. We will use the same methods for testing as before.

4.1. Branching

In the file, common/vmtranslator.cpp, implement the goto, if-goto and label commands.

  • void writeLabel(VMCommand* cmd), Converts label commands to assembly. Adds the assembly instructions to the member variable mInstructions

  • void writeGoto(VMCommand* cmd), Converts goto commands to assembly. Adds the assembly instructions to the member variable mInstructions

  • void writeIf(VMCommand* cmd), Converts if-goto commands to assembly. Adds the assembly instructions to the member variable mInstructions

$ make -j6
$ ./compile_tests_milestone2.sh
Writing vm/IfElse.asm
Writing vm/IfElse.hack
Writing vm/While.asm
Writing vm/While.hack
...etc
$ ./test_vm_milestone2

4.2. Functions

In the file, common/vmtranslator.cpp, implement the call, function, and return methods inside VMTranslator. Additionally, extend the bootstrap code to goto Sys.init when the member variable mSysInit is true.

  • writeInit();: writes bootstrap code into mInstructions

  • writeCall(VMCommand* cmd);: generates assembly code corresponding to a function call.

  • writeFunction(VMCommand* cmd);: generates assembly code corresponding to a function definition.

  • writeReturn();: generates assembly code corresponding to a function return.

$ make -j6
$ ./compile_tests_milestone2.sh
Writing vm/AddFn.asm
Writing vm/AddFn.hack
$ ./test_vm_milestone2

Submit your Work

Push you work to Github to submit your work.

$ cd Hack-Compiler
$ git add .
$ git commit -m "Hack-Compiler complete"
$ git push