<a href="https://news.ycombinator.com/item?id=40159278">
  <img
    alt="Featured on Hacker News"
    src="https://hackerbadge.now.sh/api?id=40159278"
  />
</a>






<img src="https://github.com/ArhanChaudhary/NAND/raw/main/media/logo.png" width="200" alt="The NAND logo">






<b>https://nand.arhan.sh/</b>

---

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.

Video demo of NAND

Table of Contents

• Example programs
  • Average
  • Pong
  • 2048
  • Overflow
  • SecretPassword
  • GeneticAlgorithm
• Writing programs for NAND
  • Jack Introduction
  • Custom Data Types
  • Weak Type Coercions
  • Manual Memory Management
  • Undefined Behavior
  • Operator Priority
  • Lesser and Greater than Operators
  • -32768
  • Calling a Function with Too Few Arguments
  • Improper Type Casting
  • Stack Overflows
  • Modifying Stack Frames or Internal Registers
  • Loading your Own Program
  • Hardware Specification
  • Beyond the Jack OS
• How does NAND work?
• Jack Reference
  • Program Structure
  • Syntax
  • Variables
  • Statements
• Jack OS Reference
  • Array
  • Keyboard
  • Math
  • Memory
  • Output
  • Screen
  • String
  • Sys
  • Error Codes
• FAQ
  • Whoa, is everything made from NAND gates?
  • Did you design NAND by yourself?
  • If there's only one type, what is the point of specifying types at all?
  • Why does the IDE feel finnicky?

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 1743 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.

```js / 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