Show HN: I made a programmable computer from NAND gates

ArchAndStarch · 2024-04-25T16:08:05.000Z

I am proud to present my solo hobby project NAND. This year-long undertaking follows the completed Nand to Tetris course, but ported to the web with its own runtime, user interface, and IDE. Using the "Load example program" selector, you can try out some programs I wrote on NAND's emulated hardware such as 2048, a genetic algorithm, and a manual stack overflow to corrupt the screen.Check out NAND at https://nand.arhan.shAdditionally, I've authored an extensive writeup about the project. Read about it on the GitHub repository's readme.

rpmw 2 years ago |

Wow that is a great side-project, and a great README to boot. I've been meaning on working through Nand to Tetris after playing around some with Ben Eater's 6502 Computer (https://eater.net/)

laweijfmvo 2 years ago | |

Would it be at all feasible to build a physical NAND-to-tetris computer? Or is it purely a virtual exercise?

ArchAndStarch 2 years ago | | |

A few nand2tetris fanatics have actually done this! And by a few, I mean quite a lot of people. Here's one such hardware project of nand2tetris: https://gitlab.com/x653/nand2tetris-fpga/

But you can Google "nand2tetris fpga" for more.

moefh 2 years ago | | |

There's this one that goes one step beyond that, it's built out of 40,000 discrete transistors: https://www.youtube.com/watch?v=z71h9XZbAWY

EDIT: there's more information here: https://www.megaprocessor.com/

dhosek 2 years ago | | |

I kind of want something midway between the FPGA version and the all-transistor version, something that just uses 7400 series chips (or, presumably there’s a 26-pin equivalent with 6 gates instead of three). Heck, I think even something that goes ahead and uses the full panoply of basic logic chips available could be kind of cool to see.

moefh 2 years ago | | |

I think Ben Eater's 8-bit computer is closer to what you want: https://eater.net/8bit/

It's been a few years since I studied it (I even built the clock module, registers and the ALU), but from what I remember the biggest departing point from what you want is that the control logic (from instruction decoding to deciding which sub-units to activate for each instruction) is done with an EEPROM instead of individual logic gates, as described here: https://eater.net/8bit/control

cellularmitosis 2 years ago | | |

Slu4 has a great series of videos about exactly what you are looking for, with his Minimal 64 computer https://youtu.be/FJsnKu20ch8

61 TTL chips mentioned in this 8 minute overview https://youtu.be/3zGTsi4AYLw

dailykoder 2 years ago | | |

Probably doable, but takes a lot of dedication. Especially debugging such physical endeavors is crazy

djmips 2 years ago | | |

A friend and myself made a working one in FPGA for a game jam. He did the hardware and I wrote a game in the Jack language.

It displayed on a VGA monitor.

kristopolous 2 years ago |

I could make a few college classes out of this. Well done material.

djmips 2 years ago | |

Isn't this just Nand2Tetris? I've done that course and at a glance this looks the same including the Jack language.

kristopolous 2 years ago | | |

Yes

farhanhubble 2 years ago |

Great work! You have seen the levels of abstraction that most programmers won't throughout their careers.

2OEH8eoCRo0 2 years ago |

Fantastic work. NAND to Tetris helped me land my first job out of college.

SilasX 2 years ago | |

How did it help?

2OEH8eoCRo0 2 years ago | | |

Resume padding and conversation starter during interviews. It also filled in some gaps in knowledge.

not2b 2 years ago |

Doing a design for this (specifically, design a microcoded, pipelined RISC processor, from the bottom up, with nothing but NAND gates) was the main problem on the Computer Hardware quals exam at UC Berkeley in the early 1990s. We didn't have to physically build it, though, just produce the detailed design on paper.

ryeguy_24 2 years ago |

This is amazing work. I wanted to build something similar (virtual) while I was taking the Nand2Tetris course. I'm so impressed that you actually did it. You must have a really good understanding of how computers work now.

marai2 2 years ago | |

And I was just thinking about the same thing this morning, using SVG to model the basic components. And lo and behold somebody has done a magnitude more amazing job then what I was imagining!

c0wb0yc0d3r 2 years ago | | |

You still can! :)

I have just embarked on this journey myself, recently. It is motivating to see others' work. Especially when they're not quite the same as what I'm doing.

bhasi 2 years ago |

This is excellent work! I recently started Nand2Tetris myself, and hope to finish part 1 (the HW part of the course) sometime in the next few months. I blogged about my progress here: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

IncreasePosts 2 years ago |

Liar. You used NAND gates and a clock.

userbinator 2 years ago | |

...a clock which can be made from a ring oscillator, consisting of an odd number of NAND gates wired as NOT gates.

ArchAndStarch 2 years ago | | |

Oh wow, I didn't actually know that. Thanks for the interesting trivia

schoen 2 years ago | | |

How do we know that that will converge to a single constant period of oscillation? Could you have a few different-sized square waves continue to cycle through the circuit?

(I've never built or simulated that, I'm just trying to imagine what could happen!)

rational_indian 2 years ago | | |

>Could you have a few different-sized square waves continue to cycle through the circuit?

No.

schoen 2 years ago | | |

Could you help improve my intuition about that, or give me a reference where I could learn more?

rational_indian 2 years ago | | |

Okay, so I was wrong. You can get multiple harmonics if you use a long enough chain of inverters. I will simplify the paper mentioned in a sibling comment. In a long chain at any given point of time certain (variable number of) pairs of inverters drop in and out of the circuit changing the total propagation delay, giving rise to multiple harmonics. You'll have to read the paper for details.

rational_indian 2 years ago | | |

First look up Barkhausen criteria, then read the following. For ring oscillators gain will be greater than unity for only those waves whose period matches the gate delay. Only one such wave exists since the gate delay is a fixed number.

mikestew 2 years ago |

Awesome work! Bookmarked for in-depth perusal later. As a fan of NAND-to-Tetris, but never made it all the way through, I look forward to poking around in your project.

gmiller123456 2 years ago |

Curious, how many NAND gates are there in total?

ArchAndStarch 2 years ago | |

I've inspected my code closely. Every clock cycle, the NAND gate is used 3,234 times :)

apienx 2 years ago |

Thank you. First principles FTW!

Animats 2 years ago |

Seymour Cray would have loved this. Some of his computers were all NAND gates.

dhosek 2 years ago | |

The supercomputers (all?) used wirewrap rather than PCBs. I heard a story once about someone coming in for a demo of a supercomputer and Cray realized there was a bug in the hardware during the demo and while the potential customers were at lunch, he rewired the machine to fix the bug.

Animats 2 years ago | | |

Right. Seymour Cray said that the two big problems in supercomputing were "the thickness of the mat" (of wires on the backplane) and getting rid of the heat.

This is a Cray-I backplane.[1]

[1] https://www.flickr.com/photos/geekmuseum/2926520634/

syockit 2 years ago | | |

I wonder if any of his machines ever caught fire, causing an localized out-of-season aurora borealis. On the other hand, Cray machines are never mentioned in the "Halt and Catch Fire" machine code instruction humor.

greenavocado 2 years ago |

Can anybody recommend challenges similar to this one?

wayoverthecloud 2 years ago | |

Try emulating Message Passing Interface. Could be lot more challenging though.

BooleanMaestro 2 years ago |

The readme is so detailed. God job.

alanjay 2 years ago |

Isn't this just https://github.com/MarquisdeGeek/gates ?

greenavocado 2 years ago |

Incredible achievement! Good job.

SomeoneFromCA 2 years ago |

On one hand cool project, on the other - e-waste, unless made of recycled ics.

theanonymousone 2 years ago |

Nice job. Now we should program it in subleq2[0] :D

[0] https://en.wikipedia.org/wiki/One-instruction_set_computer

fire_ball 2 years ago |

this is fantastic! great work...

userbinator 2 years ago |

NAND is popular probably because of nand2tetris, but it's worth mentioning that NOR is also a universal gate; and many early computers like the https://en.wikipedia.org/wiki/Apollo_Guidance_Computer#Logic... were entirely made of NOR gates.

ajross 2 years ago | |

That's because in NMOS logic (maybe there's a symmetric reason in TTL, but I don't know for sure) you can implement a NOR with two parallel transistors between a pullup and ground, producing a zero output if either input is high. The symmetric NAND circuit requires two transistors in series, and therefore switches more slowly.

a1369209993 2 years ago | | |

Conversely, PMOS logic has the exact opposite problem - NAND gates are parallel, while NOR gate are series.

Meanwhile, CMOS logic inherits both of these problems (in return for better performance in general), but due to semiconductor chemistry, PMOS transistors are weaker than NMOS ones (which was why NMOS was more widely used than PMOS in the first place), so NAND gates have two strong transistors in series and two weak transistors in parallel, which gives a better worst-case switching speed than a NOR gate (where the weak transistors are in series, and so switch noticably slower). This is where "NANDs are used for everything" comes from.

andai 2 years ago | |

I thought it's the other way around, nand2tetris used NAND because it was already popular? At least I remember hearing in university that NANDs are used for everything? Can't remember why they're used for everything though (and why not NOR, for example).

bramhaag 2 years ago |

Turing Complete[0] is a fun game similar to this where you create your own computer from NAND gates, including your own assembly language.

[0] https://store.steampowered.com/app/1444480/Turing_Complete/

elevatedastalt 2 years ago |

Wow, seriously impressive. And the fact that this is the work of basically a high-schooler.

I fear for the kind of competition my kids will have just to make it to college.

naikrovek 2 years ago | |

This is a natural extension/expansion of the “NAND to Tetris” course on coursera, and is free if you don’t want to be graded.

The course walks you through it all, and there is an accompanying book that you do not need to buy to finish the course.

Anyone who wants to do this and can focus on it for enough time can complete it and extend it into whatever shape they like, like this person.

It really is a good course.

ArchAndStarch 2 years ago | | |

I primarily used the physical book to learn about the nand2tetris platform. I highly recommend it, it's an enthralling read

brailsafe 2 years ago | | |

Absolutely true, I'm working my way through it now; it's challenging and time consuming, totally worthwhile imo.

pyuser583 2 years ago |

Ground up projects like this are fascinating!

It’s also neat how “ground” has been deepening. It used to mean building mainframe from source. Then building a compiler. Now building from logic gates.

How much deeper can you get? Building a mainframe out of Gödel numbers?

ArchAndStarch 2 years ago | |

One curious idea my friends have entertained is to go one level even deeper and emulate the very transistors that make up the NAND gates on the web, too. It would certainly spell disaster for performance, but it's without-a-doubt interesting.

vitiral 2 years ago | | |

Like... the physics?

If not, I think a NAND gate is made of just two transistors, so if you mean emulating how transistors should behave then I don't think it will affect performance more than ~50%

pyuser583 2 years ago | | |

That would be fascinating!

Do you know any resources that document the transistor to logic gate translation?

schoen 2 years ago | | |

In https://nandgame.com/ (mentioned elsewhere, a game version of NAND to Tetris) you start by making a NAND gate out of relays. The relays are electromechanical components, but you can choose to think of a transistor (within certain "regimes") as being directly electrically equivalent to one. (This simplification isn't appropriate for all engineering tradeoff purposes, although I don't know the details of how it fails or how we can benefit from knowing more about transistors' actual behavior.)

The electromechanical relay is a very simple device to understand, if you're willing to just believe that electromagnets produce magnetism (without understanding why the universe works according to Gauss's laws on the relationship between electric current and magnetism). It's a coil of wire where an electric current produces magnetism that physically pulls a switch open or closed.

cyanfrog 2 years ago |

https://www.nand2tetris.org/

cweagans 2 years ago | |