Assignment 13


This assignment is mostly a free-form assignment. You are free to do additional work on any of the projects that you wish. You may also work with exactly one partner on this assignment if you choose. You only need to turn in one copy per team.

You are expected to try something that your team will find sufficiently challenging. You have the option of working in a group so that you will try something ambitious. Regardless of the project you pick, be sure to document what you did, what you tried, and how to demonstrate your project in the README.txt.

The non-free form part is to implement the Memory module of the OS, as you did for the other Jack standard libraries in assignments 8 and 9.

Due Dates

By April 22, 2015, 11:59 PM CST, you need to email the class account with your chosen project and partner. The main project Due April 26, 2015, 11:59 PM CST.

Project Ideas

Hardware Assignments

  • Nand Gate Reduction - The total number of nand gates people used for the Hack computer is usually somewhere between 4 and 5 million. Write a tool the calculates how many gates you use, and then reduce that number as much as you can.
  • Efficient Addition - Addition is a very frequent operation in the Hack machine. However, as discussed at the end of lecture 2, the ripple carry adder is inefficient. Implement the more efficient carry look ahead adder instead.
  • Hardware Math - The ALU we implemented does not support hardware multiplication or division...yet. Extend the ALU to support these two operations.
  • Floating Point - The Hack computer only supports integer operations. Extend the ALU to support floating point addition and/or multiplication.
  • New Computer Architecture - Given the chips made in assignments 1-3, we could have created any number of computers, but we chose one that would implement the Hack language easily. Perhaps you don't like having separate memory for instructions and data. Maybe you don't like only having two real registers, or how the ALU is implemented. Design a new assembly language and make the hardware changes to implement your new language.
  • Apocalypse Training - Using some sort of physical system, build the Hack computer (or at least some parts of it).

Software Assignments

  • Better Faster Stronger - Compile a program like Pong, alongside your OS implementation, and figure out how much VM code it generates, and how many Hack instructions it translates to. Then reduce that number by improving the compiler and/or VM translator.
  • Tetris - Fulfill the subtitle of the course (From Nand to Tetris) by writing a full implementation of the classic game.
  • Alternate VM Implementation - Instead of translating the VM language into Hack, translate it into some other language (assembly, java byte code, etc.)
  • Jack++ - Add features to the Jack language by changing your parser and code generator (and maybe your tokenizer). Possible ideas: for loops, case statements, do while loops, else if statements, using another class's fields, add order of operations, greater than or equal to comparisons, ++ operator, += operator.
  • Jack-- - Remove some of the annoying language constructs of Jack (by changing the parser/code generator). Possible ideas: remove "let" and "do", remove "var" and "field", don't require a return statement at the end of a function, allow variable declarations and subroutines/statements to be mixed.
  • Advanced Memory Management - The Memory class in the OS is ultimately very simple, and can run out of space, even if there is sufficient space has been freed. Augment your memory module to keep a linked list of available sections of memory. If you want to take it one step further, augment the class again to recombine adjacent sections of free memory.
  • String Things - Take a look at the following program.
    class Main {    
      function void main() {
            do Output.printString("Hello World ");
    If you run it, it will run out of memory. Figure out why and fix the problem.
  • Bootstrapping - Rewrite one of the previous programming assignments (Assembler, VMTranslator, Tokenizer/Parser, Compiler) in the Jack language. You can take input using the keyboard, and output to the screen.

Other Ideas

  • Make some sweeping changes to make your code more efficient. Wouldn't it be a lot easier if there was a Hack instruction that changed the color of one pixel? Find some common operation, and make changes through your entire pipeline that implements it as a new Hack instruction and/or VM command.
  • Rewrite the hardware simulator, CPU Emulator or VM Emulator, complete with GUI, in a non-Java language.
  • Something else, as long as you clear it with me before Wednesday.