访问官网
Github
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.
Table of Contents
- Example programs
- Writing programs for NAND
- How does NAND work?
- Jack Reference
- Jack OS Reference
- FAQ
Example programs
Average
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 210
This program was supplied by the Nand to Tetris software suite.
Pong
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.
2048
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.
Overflow
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.
SecretPassword
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!
GeneticAlgorithm
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!
Video demo of the Genetic Algorithm program
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:
- NAND has a limited ROM memory space, meaning the program won't compile if there's too much code. In fact, the final version of this program uses 99.2% of the instruction memory space.
- NAND has a limited RAM memory space, meaning the program has to be careful to optimize heap memory usage. In fact, the reason why the screen fills with static between generations is to use the screen memory space as temporary swap memory for the next generation — the RAM is already completely full!
- NAND has no floating point type (decimal numbers) and can only represent the integers between -32768 and 32767, making calculating fitness less precise and more challenging to implement. Integer overflows must also be accounted for.
To avoid beating around the bush, I've stuck to documenting these techniques and additional insights in this program's codebase for those interested.
Writing programs for NAND
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.
Jack Introduction
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.
Custom Data Types
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 3
taken 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.
Weak Type Coercions
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
