N ot
A
N and-powered
D evice
is a Turing equivalent 16-bit computer made entirely from a clock and NAND gates emulated on the web. NAND features its own CPU, machine code language, assembly language, assembler, virtual machine language, virtual machine translator, programming language, compiler, IDE, and user interface. NAND is based on the Jack-VM-Hack platform specified in the Nand to Tetris course and its associated book.
A simple program that inputs some numbers and computes their average, showing off control flow, arithmetic operations, I/O, and dynamic memory allocation.
Program output:
How many numbers? 4
Enter a number: 100
Enter a number: 42
Enter a number: 400
Enter a number: 300
The average is 210This program was supplied by the Nand to Tetris software suite.
The game of Pong, showing off the language's object-oriented model. Use the arrow keys to move the paddle left and right to bounce a ball. Every bounce, the paddle becomes smaller, and the game ends when the ball hits the bottom of the screen.
This program was supplied by the Nand to Tetris software suite.
The game of 2048, showing off recursion and complex application logic. Use the arrow keys to move the numbers around the 4x4 grid. The same numbers combine into their sum when moved into each other. Once the 2048 tile is reached, you win the game, though you can keep playing on until you lose. You lose the game when the board is full and you can't make any more moves.
A program that deliberately causes a stack overflow via infinite recursion to perform a virtual machine escape. It leverages the fact that there are no runtime checks to prevent a stack overflow. No other modern platform will let you do this :-)
Upon running, the program will constantly print the stack pointer to the screen. Once this displayed value exceeds 2048, the stack will have reached the end of its intended memory space and spill onto the heap memory space, causing the print statement to malfunction in explosive fashion:
Two things of noteworthy interest are worth pointing out.
If you run this program on an empty RAM full of zeroes (you can clear the RAM through the user interface), you will notice that the program resets itself halfway through its execution despite not pressing the "Reset" button. Why this happens is simple: the jailbroken runtime executes an instruction that sets the program counter's value to 0, effectively telling the program to jump to the first instruction and start over.
If you run the GeneticAlgorithm example program and then run this immediately afterwards, the program in its rampage reads old RAM memory that was simply never overwritten.
A program that exploits the fact that the runtime doesn't prevent stack smashing to call a function that would otherwise be inaccessible. In order to understand how this works, let's examine this illustration of NAND's stack frame layout.
taken from the Nand to Tetris book.
If you're unfamiliar with stack layouts, here's the main idea behind the exploit. Whenever a function returns, it needs to know where (which machine code instruction memory address) it should go to proceed with execution flow. So, when the function is first called, this memory address, along with some other unimportant data, is temporarily stored on the stack in a memory region referred to as the stack frame as a reference for where to return. The illustration describes the exact position of this return address relative to the function call, a position that can be reverse engineered.
The program enables the user to overwrite a single memory address in the RAM to any value. Putting two and two together, if the user were to overwrite the return address of a stack frame with the address of another function, they essentially gain the ability to execute arbitrary code included in the program.
Indeed, if you enter 267 as the memory location and 1715 as the value to overwrite, two numbers reverse engineered by manually inspecting the stack memory space and the assembler, you'll see this idea in working action.
This isn't a vulnerability unique to NAND. It exists in C as well! How cool!
Believe it or not, out of the many, many different components of NAND, this single-handedly took the longest to develop!
This program is a creature simulation that utilizes simple machine learning. It follows the artificial intelligence coded series (parts one and two) from Code Bullet. Make sure to check out his channel, he makes some really cool stuff!
Simply explained:
Every dot has its own "brain" of acceleration vectors, and they evolve to reach a goal through natural selection. Every generation, dots that "die" closer to the goal are more likely to be selected as the parents for the next generation. Reproduction inherently causes some of the brain to mutate, wholly effectively simulating natural evolution.
Nevertheless, there is much to be desired. Due to performance, the only factor dots use to evolve is their closeness to the goal upon death, endowing the natural selection algorithm with low entropy. Due to memory usage, there are smaller than satisfactory limits on the number of dots and the sizes of their brains. Lastly, due to technical complexity, re-placing obstacles during the simulation does not guarantee that the dots will have large enough brains to reach the goal. Brain sizes are only determined at the beginning of the program.
I've utilized a myriad of optimization techniques to snake around the following hardware restrictions and make this possible:
To avoid beating around the bush, I've stuck to documenting these techniques and additional insights in this program's codebase for those interested.
Before we start, the most important detail to remember about writing programs in Jack is that there is no operator priority; this is probably why your program isn't working.
For example, you should change: 4 * 2 + 3 to (4 * 2) + 3 if (~x & y) to if ((~x) & y)
but you can keep if (y & ~x) the same as there is no operator ambiguity.
Without parenthesis, the evaluation value of an ambiguous expression is undefined.
NAND boasts its own complete tech stack. As a consequence, NAND can only be programmed in Jack, its weakly typed object-oriented programming language. In layman's terms, Jack is C with Java's syntax.
Let's take the approach of example-based learning and dive right in.
/**
* This program prompts the user to enter a phrase
* and an energy level. Program output:
*
* Whats on your mind? Superman
* Whats your energy level? 3
* Superman!
* Superman!
* Superman!
*/
class Main {
function void main() {
var String s;
var int energy, i;
let s = Keyboard.readLine("Whats on your mind? ");
let energy = Keyboard.readInt("Whats your energy level? ");
let i = 0;
let s = s.appendChar(33); // Appends the character '!'
while (i < energy) {
do Output.printString(s);
do Output.println();
let i = i + 1;
}
}
}taken from the Nand to Tetris lecture slides.
If you've already had some experience with programming, this should look very familiar; it is clear that Jack was heavily inspired by Java. Main.main, the entry point to the program, demonstrates basic usage of variables as well as the while loop for control flow.
Additionally, it uses Keyboard.readLine and Keyboard.readInt to read input from the user, and Output.printString and Output.println to print output to the screen — all of which are defined in detail in the Jack OS Reference. By default, the Jack OS is bundled with your program during compilation to enable interfacing with strings, memory, hardware, and more.
Every programming language has a fixed set of primitive data types. Jack supports three: int, char, and boolean. You can extend this basic repertoire with your own abstract data types as needed. Prior knowledge about object-oriented programming directly carries over to this section.
/** Represents a point in 2D plane. */
class Point {
// The coordinates of the current point instance:
field int x, y;
// The number of point objects constructed so far:
static int pointCount;
/** Constructs a point and initializes
it with the given coordinates */
constructor Point new(int ax, int ay) {
let x = ax;
let y = ay;
let pointCount = pointCount + 1;
return this;
}
/** Returns the x coordinate of the current point instance */
method int getx() { return x; }
/** Returns the y coordinate of the current point instance */
method int gety() { return y; }
/** Returns the number of Points constructed so far */
function int getPointCount() {
return pointCount;
}
/** Returns a point which is this
point plus the other point */
method Point plus(Point other) {
return Point.new(x + other.getx(),
y + other.gety());
}
/** Returns the Euclidean distance between the
current point instance and the other point */
method int distance(Point other) {
var int dx, dy;
let dx = x - other.getx();
let dy = y - other.gety();
return Math.sqrt((dx * dx) + (dy * dy));
}
/** Prints the current point instance, as "(x, y)" */
method void print() {
var String tmp;
let tmp = "(";
do Output.printString(tmp);
do tmp.dispose();
do Output.printInt(x);
let tmp = ", ";
do Output.printString(tmp);
do tmp.dispose();
do Output.printInt(y);
let tmp = ")";
do Output.printString(tmp);
do tmp.dispose();
}
}var Point p1, p2, p3;
let p1 = Point.new(1, 2);
let p2 = Point.new(3, 4);
let p3 = p1.plus(p2);
do p3.print(); // prints (4, 6)
do Output.println();
do Output.printInt(p1.distance(p2)); // prints 5
do Output.println();
do Output.printInt(getPointCount()); // prints 3taken from the Nand to Tetris lecture slides.
We define a Point class to represent an abstract point in space. It uses field variables to declare per-instance attributes of the data type. It exposes public method functions we can use to interface with the point, giving the caller the functionality to add two points together and calculate the distance between two points.
All field variables are privately scoped. If you wish to get or set these variables from outside the class declaration, these variables must have corresponding method functions to provide this functionality.
Omitted from the code sample to stay on-topic, it is customary for data classes to define dispose methods for deallocation once objects are no longer needed. See Manual Memory Management.
If needed, here's a reference for function and method calling syntax.
class Foo {
...
method void f() {
var Bar b; // Declares a local variable of class type Bar
var int i; // Declares a local variable of primitive type int
do g(); // Calls method g of the current class on the current object instance
// Note: Cannot be called from within a function (static method)
do Foo.p(3); // Calls function p of the current class;
// Note: A function call must be preceded by the class name
do Bar.h(); // Calls function h of class Bar
let b = Bar.r(); // Calls function or constructor r of class Bar
do b.q(); // Calls method q of class Bar on the b object
}
}taken from the Nand to Tetris lecture slides.
Remember how we said Jack was similar to Java? That was a facade, or at best misleading. While Java is strongly-typed and as such supports complex type features such as down casting, polymorphism, and inheritance, Jack supports none of these and only has one type under the hood: the signed 16-bit integer. This is the primary reason why Jack is so weakly-typed. In effect, the compiler won't care if you mix and match different types in assignments and operations.
var char c;
var String s;
let c = 65; // 'A'
// Equivalently
let s = "A";
let c = s.charAt(0);var Array a;
let a = 5000;
let a[100] = 77; // RAM[5100] = 77var Array arr;
var String helloWorld;
let helloWorld = "Hello World!"
let arr = Array.new(4); // Arrays are not strictly typed
let arr[0] = 12;
let arr[1] = false;
let arr[2] = Point.new(5, 6);
let arr[3] = helloWorld;class Complex {
field int real;
field int imaginary;
...
}
...
var Complex c;
var Array a;
let a = Array.new(2);
let a[0] = 7;
let a[1] = 8;
let c = a; // c == Complex(7, 8)
// Works because it matches the memory layout
// of the Complex typeall code segments taken from the Nand to Tetris lecture slides.
Don't take this the wrong way — Jack still provides a powerful and functional object-oriented model. This insight intends to help you understand when and how you should perform type conversions as needed.
Let's say you're a crazy cat lover, just like me! And you wanted to write this program to show off just how much you absolutely adore cats.
class Main {
function void main() {
while (true) {
do Output.printString("Kittens are so adorable! ");
}
}
}You may be startled to notice that after a few seconds, the program will crash with "ERR6", or a heap overflow!
Jack is a manually memory managed programming language. This means you must be vigilant to properly deallocate memory that is no longer needed, or else the Jack OS will think otherwise and facilitate a memory leak. The best practice advice is to feature a dispose method for each class that represents an object that properly encapsulates this deallocation. Thus, when objects are no longer needed, you can call their dispose methods to ensure you won't eventually run out of heap memory.
If you've programmed in other manually memory managed languages, like C, this should look very familiar. One key difference is the Jack OS stores arrays and strings on the heap rather than on the stack, hinting to why the program crashes with a heap overflow.
Let's fix this program for our fellow feline fanatics.
class Main {
function void main() {
var String s;
while (true) {
let s = "Kittens are so adorable! ";
do Output.printString(s);
do s.dispose();
}
}
}Alternatively, you could allocate memory for the string only once.
class Main {
function void main() {
var String s;
let s = "Kittens are so adorable! ";
while (true) {
do Output.printString(s);
}
}
}You'll notice that not only do these alternative versions print the string much faster, but this time they'll actually print forever! Hooray!
Let's quickly peek into String.dispose so you can better understand how to write your own dispose methods.
method void dispose() {
do stringArray.dispose();
do Memory.deAlloc(this);
}Array.dispose called by stringArray
method void dispose() {
do Memory.deAlloc(this);
}Proper dispose methods must first appropriately call dispose on their field variables and then finish with do Memory.deAlloc(this); to deallocate the object instance itself.
With how primitive Jack and NAND are, footguns within the language are inevitable. I've compiled the following instances of undefined behavior you should be aware of, ordered from (in my opinion) most important to least important.
I found this caveat to be so important that I've moved it towards the beginning of this section.
The Jack expressions
a > b
a < bare deceptively simple. They aren't always mathematically correct, and are respectively equivalent to the Java expressions
((a - b) & (1 << 15)) == 0 && a != b
((a - b) & (1 << 15)) != 0What's up with the nuance? The virtual machine implementation converts a > b to a - b > 0. Here's the problem: a - b can overflow :(
What does 20000 > -20000 evaluate to? The virtual machine transpiles this to 20000 - (-20000) > 0 which evaluates to -25336 > 0. Unfortunately, the answer is false.
However, 20000 > -10000 evaluates to 30000 > 0, or true.
As you may have figured, if the absolute distance between a and b is more than 32767, a > b and a < b are wrong. Otherwise, you're fine.
This isn't an implementation bug, but rather an inconsistency with Nand to Tetris itself. More about it here. For compatibility reasons, this behavior won't be fixed.
-32768 is one of its kind. It is the only number that holds the property such that -(-32768) = -32768, a singleton without a positive counterpart*. This can lead to unsoundness and logic errors.
/**
* Program output:
* --.)*(
*/
class Main {
function void main() {
// Note that -32768 must instead be written as ~32767
// because the CPU can't load a number that large
do Output.printInt(~32767);
}
}Output.printInt internally expects Math.abs to return a positive number. This isn't the case with -32768, so the Jack OS malfunctions.
Your main concern should be handling logic errors with the negative operator. As the programmer, if you want to guarantee the negative of a negative number is positive, it is your responsibility to check for the case of -32768 and take appropriate action.
* This holds true because NAND's ALU internally processes the Jack expression -x as ~(x - 1). Let's set x to -32768 and evaluate it step by step. Here are the corresponding 16-bit two's complement binary representations of the computation:
x = 1000 0000 0000 0000 x - 1 = 0111 1111 1111 1111 ~(x - 1) = 1000 0000 0000 0000 = x
It's the same thing! What happened here? Because NAND is a 16-bit machine, -32768 is the only number such that if you subtract one from it, you get its flipped bits. In other words, -32768 satisfies x - 1 = ~x, simplifying the expression to ~(~x) or just x.
This one is self-explanatory, so here's a brief demonstration.
/**
* Program output:
* I have 818 cookies.
*/
class Main {
function void main() {
do Main.cookies();
}
function void cookies(int a) {
do Output.printString("I have ");
do Output.printInt(a);
do Output.printString(" cookies.");
}
}On the other hand, calling a function with too many arguments is perfectly valid. You can use the arguments keyword to index extra function arguments. Note that there is no indicator for the argument count.
You can utilize Array to cast a variable into any other type. Calling instance methods that don't exist on type casted variables is undefined behavior; the compiler isn't smart enough to realize when you're doing this.
/**
* Program output:
* 4
*/
class Main {
constructor Main new() {
return this;
}
function void main() {
var Array a;
var Main b;
var String c;
let a = Array.new(1);
let b = Main.new();
let a[0] = b;
let c = a[0];
// Invalidly calling `String.length` on an instance of `Main`.
do Output.printInt(c.length());
}
}See the Overflow program for an in-depth example.
Modifying stack frames or the internal registers that respectively reside at memory addresses 256 to 2047 and 1 to 15 may lead to undefined behavior. This typically isn't possible without misusing Memory.poke or negative array indexing. See the SecretPassword program for an in-depth example.
NAND offers program validation for .jack files but not for .vm files. This means NAND's virtual machine compiler gives you free reign to call nonexistent functions, reference unassigned variables, or perform any other logically invalid memory operation. In most cases of such undefined behavior, the virtual machine will escape and the screen simply won't display anything. It will be your responsibility to debug the program yourself.
Since its rise in the 1970s, there's a good reason why 16-bit computing has fallen from grace in the modern era. Compared to 32-bit or 64-bit computing, 16-bit computing offered limited processing power and memory capacity that simply weren't meeting the demands of contemporary software and applications.
NAND is no exception to this reality.
taken from the Nand to Tetris lecture slides.
Compared to your 16 GiB MacBook, NAND enjoys a meager 4 KiB of RAM, a ratio of 0.00002%! In spite of this, it was enough to take us to the moon, so who's to say NAND can't either.
The Jack OS reserves 14,336 memory addres
