From Nand to Orbit Game: Part 2

In Part 1, we covered Modules 1-6 of the course From Nand to Tetris. In Part 2, we’ll cover Modules 7-12.

Module 7: VM I: Stack Arithmetic

This module continues moving up the levels to VM code, an intermediate layer between assembly code beneath it and the high-level code above it. The compiler translates the high-level language into VM commands which are generic commands doing arithmetic and manipulating values between different memory segments. These VM commands can be translated into any computer architecture available: our Jack computer architecture or an industry standard like x64 or ARM.

The VM uses a main stack and 8 virtual memory segments, which also behave like stacks. These stacks are just sections of the RAM set aside for this purpose. Values are pushed and pulled to transfer them from one stack to the other. For example, adding 2 numbers is done by pushing them onto the stack, popping them to the addition function, then pushing the result back onto the stack.

When the VM pushes a value onto a stack it undertakes a set of assembly commands:

  1. Find the address of the top of the stack
  2. Put the value to be pushed into the data register
  3. Set the memory location at the top of stack = value
  4. Set the top of stack to be 1 position further for the next operation

The sequence varies with the 8 types of stacks. 7-13 assembly commands are used to implement a push or pop.

Arithmetic operations in the VM are translated almost directly to assembly. Compare operations like “<” etc. involve around 10 lines of assembly.

The translator parses the VM code to determine if the command is a push/pull stack command or an arithmetic command. The stack commands are parsed further to the stack and the location within it.

Project

Write the basic version of a VM translator that creates a set of assembly commands to implement a VM command. The VM translator should work with 5 test VM programs.

A portion of the VM translator for popping values from a stack:

The IDE includes a VM emulator which shows how executing VM code effects locations in RAM and the stacks. The goal is for the VM translator to generate assembly code that behaves the same on the CPU emulator as the VM emulator running the provided VM code.

VM emulator after running BasicTest.vm:

CPU emulator after running BasicTest.asm:

 

Module 8: VM II: Program Control

VM code includes the ability to jump to a labeled part of the code based on an if statement value. Functions can also be defined as sequential lines of code and then called from a different part of the code.

The labeling and jumping in VM code corresponds pretty directly to the functionality in assembly so this part is fairly straightforward. Labeling a section is only 1 line of assembly. Jumping to a labelled location based on a condition is only 6 lines of assembly.

The complicated part is implementing function returns and calls. Calling a function requires that all the values going into the function are pushed onto the argument stack for the function to access. Then the execution jumps to the first line where the function is defined. A new set of stacks is initiated that the function will need for that run. A single function calls end up being about 52 lines of assembly when all the pieces are put together.

Returning from a function requires pushing the returned value to the main stack for the calling code to access and then jumping to the correct line in the code right after the function call. A unique label is generated when the function is called so the function knows where to jump back to (the same function could be called from multiple places over the course of the program so it has to know which one to return to). The set of stacks for the function are wiped out and original stacks from the calling code are restored. A single return statement ends up being 55 lines of assembly.

This works if functions call other functions or even themselves. The stacks are just added on to the next spot in memory and then wiped out when that function returns until everything is back to the way it was when the final function returns.

Project

Extend the VM translator to handle branching and function commands. The VM translator should work with 6 test VM programs.

A portion of the VM translator for function and return:

 

Module 9: High Level Language

Jack is a high-level language, similar to Java, that can be translated into VM code, then compiled into assembly that can run on the Hack computer architecture. It’s not as user friendly as Python as it trades some programmer facing complexity for compiler simplicity. However, it’s still easy to learn and the conventions make sense.

Jack features if statements, while loops, classes, and several data types. These are all things the compiler and components of the chain further down know how to handle.

Project

Write a program in Jack that involves graphics and uses the classes, methods, etc.

I chose to implement a very pared down version of Orbit Game for this project. Orbit Game is a JavaScript orbit simulator I developed back in college for an orbital dynamics class. It sums up the gravitational forces acting on each object, then computes their acceleration, velocity, and position using Euler integration. The user can rotate the spacecraft and add thrust which is also integrated into the force simulations. This results in realistic orbital maneuvering and some fun challenges to do an orbital transfer between Earth and Mars or to reach an orbit with certain orbital parameters.

The goal of the implementation in Jack was just to do the core force simulation part with 2 planets without any user interactivity. This was still quite a challenge due to the fairly limited set of graphics and mathematics capabilities from the Jack OS.

Much of the user facing JavaScript/HTML code and code that sets up specific scenarios did not need to be included. I hardcoded just one scenario with 2 planets. Orbit Game in JavaScript was about 1,200 lines. The Orbit Game in Jack was only about 250 lines.

The object-oriented nature of the program made it fairly easy to port over. There is a Planet class that has attract(), move(), and draw() methods that run on each planet on each iteration.

The hardest part was getting the values scaled right to get realistic movement of the planets. In the JavaScript version, everything is scaled with physical values (sunMass=1.989e30 kg, EarthOrbitRadius=149e6 km, etc.). I used a time scaling factor to speed up movement and a distance scaling factor to convert from km to pixels on the webpage. This worked really well and allowed realistic calculations to be done like computing an orbital period in days or ΔV in km/s. The problem is that Jack only supports numbers of int, not float. Int doesn’t support decimal values and only goes up to 32,767. Astronomical numbers like the mass of planets are way off scale. I had to come up with new values for planet masses, initial positions, initial velocities, and even the gravitational constant via trial and error. The program no longer models our physical solar system, but it does a decent job with this imaginary one.

Division with integers is imprecise because only the quotient is returned. The remainder is not considered. For example, 9/10 would result in 0, not 0.9 or even 1. To avoid this as much as possible, when numbers were being multiplied and divided in the same equation, I tried doing all the multiplications first so the number would be as large as possible before it was divided. This minimized the impact of a discarded remainder.

The Jack OS does not include sin() or cos(). This required a rework of the section that determines how to break the gravitational force into X and Y directions. It turns out there was actually a more direct way that just uses the components of the position vector with some multiplication and division, no trigonometric functions required.

A portion of Planet.jack:

Rendering of the planet movement in the VM Emulator:

The planets in the JavaScript version follow a consistent orbital path because it has floating point precision, the math to handle it, and more pixels to display that precision. This Jack version can’t match that, but overall, this proves the concept and it’s pretty cool to see the gravitational force producing orbital behavior in a relatively simple computer architecture.

 

Module 10: Compiler I: Parsing

Modules 7 and 8 cover the VM translator which is the back half of the compiler. Modules 10 and 11 cover the front half, the part that takes the high-level language and generates VM code. This module specifically covers the compiler’s ability to parse the code: identifying each relevant character, grouping into tokens, and organizing those tokens.

The parser knows all of the keywords that mean special things, the symbols that denote operations or blocks of code, and how numbers and strings are defined. The Jack grammar defines the components of element in the language. Each child element is defined until you can define any element as a nested set of terminal tokens.

The key trick in a parser is to define a parsing function for each element and then call those functions as you encounter a new element. Each function parses the section it’s responsible for, moves the position in the parser ahead, and returns. This is known as recursive descent and is an elegant way of handling the complex paths the parser must take as it explores the code and outputs the parsed results as it goes along.

Project

Write a compilation engine that performs syntax analysis (parsing) on Jack code. It should output XML reflecting the syntactic structure of the source code. The engine should handle the code of three provided programs.

One of the tricky parts of the parser was keeping track of where the parser was at. Some of the parsing functions would expect the position coming in to be right before a “(“ and so would get lost looking for a “(“ if the position was already at that spot. The same parsing function could be called from several other functions based on the element it was contained by and so it needed to be compatible no matter how many levels deep the recursion had gone. Looking ahead by 1 or 2 characters is needed to determine what parsing function to call next.

The parser has to keep track of when it has entered a string definition or a comment because all other parsing does not apply to a string. Comments can also be the single line type or a multi-line type so the parser watches for when that end point is reached, then resumes normal parsing.

It was really satisfying to build this up from scratch, starting with a tokenizer, that breaks the source code up into tokens. Then I added on capabilities from there and tested them out until I had a solid parser that could handle any level of nested statements and any type of Jack code.

A portion of the input Jack code:

A portion of that code in parsed XML:

 

Module 11: Compiler II: Code Generation

The compiler maintains a symbol table with all the identifiers defined in the current scope. If an identifier is encountered for the first time, it is added to the symbol table. Identifiers can be a class, subroutine, or variable name. If it’s for a variable, an index is assigned within the appropriate scope. There are 2 active scopes at any time and therefore 2 active symbol tables: one within the class, and one within the subroutine. When an identifier is encountered later on, it’s looked up in the symbol table and its properties are retrieved. The kind of variable and the index are ultimately what is used in the VM to look up the corresponding location in the stack.

A few of the implementation details to give a sense of how the compiler works:

Operators like “+” are translated into the equivalent VM command although it’s done in a certain order to make sure the values are pushed to the stack before the operator is run.

Array indexing requires a multistep push/pop between the temp, pointer, and that stacks.

If and while statements are quite similar to each other and require careful use of the “if-goto” and label VM commands.

When a method is called, the address to its object is pushed first so that the object’s variables can be referenced from within the method.

Project

Extend the syntax analyzer from Module 10 to output the name, category, index, and usage of each identifier element. Extend the syntax analyzer to create a compiler that outputs corresponding VM commands instead of XML for each element. The compiler should handle 6 programs that have arithmetic, expressions, functions, and all the elements of the Jack language.

A portion of the same code from Module 10 in parsed XML:

A method from the SquareGame program:

That method translated to VM code by the compiler:

A portion of a method from the PongGame program:

A portion of that method translated to VM code by the compiler:

 

Module 12: Operating System

The final piece to implement is the OS, which is essentially the utility functions that are called by programs to handle IO, memory, math, etc. Modern OSs are very complex and provide a wide array of features to users directly and to the programs that run on the OS. The Jack OS is comprised of just 8 libraries, but they provide efficient implementation of functions so the software running on the OS doesn’t need to handle them:

  • Math
  • Memory
  • Screen
  • Output
  • Keyboard
  • String
  • Array
  • Sys

Multiplication can intuitively be done by just adding up numbers in a loop. However, there is a more efficient way that involves adding up bit-shifted variants of one of the numbers. The total number of operations is lower and it can be implemented directly in hardware. It’s pretty amazing that someone came up with this method because it’s not intuitive, but it is a smart way of making the calculation more efficient.

Computing the square root uses binary search where you define the target based on what satisfies the equation, then add up all the numbers that are less than that. The sum of those approaches the target as close as possible without going over. Pretty cool.

Whenever a new object is created, the OS finds a good spot in memory to store it. All of the free blocks in memory contain 2 pieces of metadata: the size of the block, and the address of the next free block. This allows the memory allocator to hop from one block to the next until a free block is found that is large enough. Then the metadata is updated to remove that block from the linked list. Similarly, to deallocate an object, that block in memory is added back to the linked list.

The graphics library was interesting because it is essentially visualizing some math. It reminded me a lot of some graphics code I wrote for PowerShell back in the day. Drawing a line involves drawing pixels one by one, deciding between going in a vertical or horizontal direction based on the target slope of the line. There are some counterintuitive adaptations to the math to reduce the total number of operations, so the line is drawn faster. That time savings adds up if you’re drawing many lines per screen cycle. Circles and rectangles are based on drawing a set of horizontal lines with varying lengths. Setting an individual pixel involves writing a binary number to a specific memory address where each bit of the number corresponds to one pixel.

Outputting text to the screen was more complicated than I realized. Each character is saved as a bitmap, which is an array holding the pixel values of an 8×11 pixel area. To display a character, the library finds the character and draws it row by row. Each row is drawn pixel by pixel using a bitmask that filters by one bit at a time. Moving and drawing the cursor requires translating between a screen that contains 512×256 pixels and 64×23 characters.

Getting input from the keyboard involves reading a number from one memory location, corresponding to each key on the keyboard. The function waits in a loop until a key is pressed and works in conjunction with the Output library to display the characters the user types.

Strings are implemented as an array of characters. Most of the utility methods were straightforward operations on arrays. Converting from a string to an integer involves converting each character and adding them together into a number. Going the opposite direction involves dividing by 10, getting the remainder, and recursively assembling the string from there.

Arrays are actually simple to implement because all the hard work of memory allocation and deallocation has already been done by the Memory library.

The Sys library is the core library of the OS. It initializes the other libraries and provides a few utility functions.

Project

Build the Jack OS by writing all the functions contained in the 8 libraries.

Test programs are provided that call the OS functions for each library separately. The OS is written in Jack itself and so everything can be tested like in Module 9 by compiling to VM code and running in the VM emulator. Once all libraries are validated separately, they are tested together by running the large Pong game which makes use of many OS functions.

The square root function in the Math library:

Test drawing using the Screen library:

Test character writing using the Output library:

My final goal was to integrate it all. Run the Orbit Game high-level Jack code through my compiler, then though my VM translator, then through my assembler. Then run that binary assembly code in the CPU emulator.

I ended up with a bug where the circles for the planets would not draw correctly and then the RAM would overflow into the segment that displays to the screen so weird repetitive patterns would show up.

I spent hours and hours doing the most hardcore debugging I’ve ever done. Multiple runs, line by line through the assembly code, and following individual locations in the RAM to figure out where values were being written and why. It is a major challenge to relate what the CPU is executing on assembly code to what is happening higher up at the VM or Jack level, but I eventually got good at it and could hop around to any part of the code and know where the RAM would be updated next or what function would execute. Even boiling down the Jack code to the simplest version that would reproduce the bug yielded 9,000 lines of assembly because of all the OS code that is essential.

Ultimately, the smoking gun was a simple bug in my VM translator. There is a variant of a push command that is only supposed to run once at the very start to bootstrap the program. However, it was running every time. This led to the stack pointer not being incremented. It was essentially 2 lines of assembly that was missing out of 9,000 lines, but it made a big difference downstream.

With that bug fixed, the planets were drawn, the gravitational force math was correct, and the planets moved according to the laws of nature! Super satisfying to have something that I wrote from top to bottom, all the way to the electrical signals going into a CPU.

 

For anybody wanting to learn one of the most important technologies in the world from the ground up and run your own code on a computer you essentially built yourself, I highly recommend From Nand to Tetris.

Leave a Reply

Your email address will not be published. Required fields are marked *