Show HN: NAND 게이트로 만든 프로그래밍 가능한 컴퓨터

 (github.com/ArhanChaudhary)
2P by GN⁺ | ★ favorite | 댓글 1개
  • NAND는 웹에서 에뮬레이션되는 튜링 동등 16-bit 컴퓨터로, clock과 NAND gate만으로 구성된다는 교육적 전제를 바탕으로 CPU부터 IDE와 UI까지 포함함
  • 자체 스택은 Jack-VM-Hack 플랫폼을 기반으로 하며, CPU, 기계어, 어셈블리, assembler, VM 언어, VM translator, Jack 언어, compiler를 함께 제공함
  • 예제 프로그램은 Average, Pong, 2048뿐 아니라 stack overflow와 stack smashing을 이용한 VM escape 데모, 단순 머신러닝을 쓰는 GeneticAlgorithm까지 포함함
  • Jack은 Java 문법과 비슷한 약타입 객체지향 언어지만 내부적으로는 signed 16-bit integer 하나에 의존하며, 연산자 우선순위 없음·수동 메모리 관리·정의되지 않은 동작 같은 제약이 큼
  • 프로젝트는 실제 모든 계산이 물리적 NAND gate에서 실행된다는 뜻은 아니며, TypeScript compiler와 VM translator, Rust 기반 NAND gate logic simulator, WebAssembly를 쓰는 교육·이론용 구현임

NAND가 제공하는 전체 컴퓨터 스택

  • NAND는 Not A Nand-powered Device의 약자로 소개되는 웹 기반 16-bit 컴퓨터임
  • clock과 NAND gate로 만들어진 튜링 동등 컴퓨터를 에뮬레이션하며, 다음 구성요소를 자체적으로 포함함
    • CPU
    • machine code language
    • assembly language
    • assembler
    • virtual machine language
    • virtual machine translator
    • programming language
    • compiler
    • IDE
    • user interface
  • 기반은 Nand to Tetris course와 관련 도서의 Jack-VM-Hack 플랫폼임
  • NAND 데모 영상이 제공됨

예제 프로그램과 데모

  • Average

    • 숫자 입력과 평균 계산을 수행하는 간단한 프로그램
    • control flow, 산술 연산, I/O, 동적 메모리 할당을 보여줌
    • Nand to Tetris software suite에서 제공된 프로그램임

  • Pong

    • 객체지향 모델을 보여주는 Pong 게임
    • 방향키로 paddle을 좌우 이동해 공을 튕김
    • 공이 튕길 때마다 paddle이 작아지고, 공이 화면 아래에 닿으면 게임이 끝남
    • Nand to Tetris software suite에서 제공된 프로그램임

  • 2048

    • recursion과 복잡한 application logic을 보여주는 2048 게임
    • 4x4 grid에서 방향키로 숫자를 이동하고, 같은 숫자는 합쳐짐
    • 2048 tile에 도달하면 승리하지만, 패배할 때까지 계속 플레이할 수 있음

  • Overflow

    • 무한 재귀로 stack overflow를 의도적으로 발생시켜 virtual machine escape를 수행함
    • runtime에 stack overflow 방지 검사가 없다는 점을 이용함
    • stack pointer 값이 2048을 넘으면 stack이 의도된 메모리 공간을 벗어나 heap memory space로 흘러 들어감
    • 비어 있는 RAM에서 실행하면 program counter가 0으로 설정되는 instruction 때문에 프로그램이 중간에 reset될 수 있음
    • GeneticAlgorithm 실행 직후 실행하면 덮어쓰이지 않은 이전 RAM memory를 읽을 수 있음

  • SecretPassword

    • runtime이 stack smashing을 막지 않는다는 점을 이용해 원래 접근할 수 없는 함수를 호출함
    • 사용자가 RAM의 한 memory address를 원하는 값으로 덮어쓸 수 있음
    • stack frame의 return address를 다른 함수 주소로 덮어쓰면 프로그램 안의 임의 코드 실행이 가능함
    • 예시 값은 memory location 267, overwrite value 1743임
    • 같은 종류의 취약점은 C의 buffer overflow에도 존재함

  • GeneticAlgorithm

    • 단순 머신러닝을 사용하는 creature simulation임
    • 각 dot은 acceleration vector로 구성된 자체 “brain”을 갖고, 자연선택을 통해 goal에 도달하도록 진화함
    • goal에 더 가까운 위치에서 죽은 dot이 다음 세대 parent로 선택될 가능성이 높음
    • reproduction 과정에서 brain 일부가 mutation되어 자연 진화를 시뮬레이션함
    • Genetic Algorithm 데모 영상이 제공됨

GeneticAlgorithm이 부딪힌 하드웨어 제약

  • GeneticAlgorithm은 NAND의 여러 구성요소 중 개발에 가장 오래 걸린 단일 프로그램임
  • 성능 때문에 dot이 진화에 사용하는 요소는 죽을 때 goal에 얼마나 가까운지뿐이며, 자연선택 알고리듬의 entropy가 낮음
  • 메모리 사용량 때문에 dot 개수와 brain 크기에 만족스럽지 않은 제한이 있음
  • 기술적 복잡성 때문에 simulation 중 obstacle을 다시 배치해도 dot의 brain이 goal에 도달할 만큼 충분히 크다고 보장되지 않음
    • brain size는 프로그램 시작 시점에만 결정됨
  • 구현은 여러 최적화로 NAND의 제약을 우회함
    • ROM instruction memory space가 제한되어 코드가 너무 많으면 compile되지 않음
    • 최종 GeneticAlgorithm은 instruction memory space의 99.2% 를 사용함
    • RAM memory space가 제한되어 heap memory usage를 최적화해야 함
    • 세대 사이에 화면이 static으로 채워지는 이유는 screen memory space를 다음 세대를 위한 temporary swap memory로 사용하기 때문임
    • NAND에는 floating point type이 없고, 표현 가능한 integer 범위는 -32768부터 32767까지임
    • fitness 계산 정밀도가 낮아지고 integer overflow도 고려해야 함
  • 관련 최적화와 추가 insight는 GeneticAlgorithm codebase에 문서화되어 있음

Jack으로 NAND 프로그램 작성하기

  • Jack에서 프로그램이 동작하지 않는 가장 중요한 원인으로 연산자 우선순위 없음이 강조됨
    • 4 * 2 + 3은 (4 * 2) + 3처럼 써야 함
    • if (~x & y)는 if ((~x) & y)처럼 써야 함
    • 괄호가 없는 모호한 expression의 evaluation value는 undefined임
  • Jack은 NAND의 weakly typed object-oriented programming language임
    • 설명상 “Java syntax를 가진 C”에 가까움
    • NAND는 자체 complete tech stack을 갖기 때문에 Jack으로만 프로그래밍할 수 있음
  • 기본 Jack OS는 compile 시 프로그램에 함께 bundle됨
    • strings, memory, hardware와의 interface를 제공함
    • Keyboard.readLine, Keyboard.readInt, Output.printString, Output.println 같은 함수가 포함됨
  • Jack은 int, char, boolean 세 primitive type을 지원함
    • class를 통해 abstract data type을 정의할 수 있음
    • field variable은 instance별 attribute를 선언함
    • field variable은 private scope이며, 외부 접근에는 method가 필요함
  • function과 method는 호출 방식이 다름
    • current object의 method는 같은 class 안에서 do g();처럼 호출할 수 있음
    • function call은 class name을 앞에 붙여야 함
    • object method는 do b.q();처럼 object를 통해 호출함

Jack의 약타입성과 메모리 관리

  • Jack은 Java와 달리 strong type, down casting, polymorphism, inheritance를 지원하지 않음
  • 내부적으로 실제 type은 signed 16-bit integer 하나뿐임
    • compiler는 assignment와 operation에서 type을 섞어도 신경 쓰지 않음
    • char에 65를 넣으면 'A'와 동등하게 다룰 수 있음
    • Array 변수에 5000을 넣고 a[100] = 77을 수행하면 RAM[5100] = 77이 됨
    • array entry는 서로 다른 data type을 담을 수 있음
    • memory layout이 맞으면 Array를 다른 class instance처럼 사용할 수 있음
  • Jack은 수동 메모리 관리 언어임
    • 더 이상 필요 없는 memory를 deallocate하지 않으면 memory leak이 발생함
    • heap overflow는 ERR6로 나타남
    • Jack OS는 array와 string을 stack이 아니라 heap에 저장함
  • object를 나타내는 class는 dispose method를 갖는 것이 best practice임
    • field variable의 dispose를 먼저 호출함
    • 마지막에 do Memory.deAlloc(this);로 object instance 자체를 deallocate함
  • string literal을 반복 생성해 출력하는 루프는 heap overflow를 만들 수 있음
    • 매 반복마다 string을 dispose하거나
    • string을 한 번만 allocate하고 재사용하면 계속 출력할 수 있음

정의되지 않은 동작과 주의점

  • 비교 연산자

    • a > b와 a < b는 항상 수학적으로 정확하지 않음
    • VM 구현은 a > b를 a - b > 0으로 변환함
    • a - b가 overflow될 수 있어 20000 > -20000은 false가 됨
    • a와 b의 absolute distance가 32767보다 크면 >와 <는 틀릴 수 있음
    • 이 동작은 Nand to Tetris와의 compatibility 때문에 수정되지 않음

  • -32768

    • -32768은 -(-32768) = -32768이 되는 유일한 값임
    • positive counterpart가 없어 unsoundness와 logic error를 만들 수 있음
    • Output.printInt는 내부적으로 Math.abs가 positive number를 반환한다고 기대하지만, -32768에서는 그렇지 않아 Jack OS가 오동작함

  • 인자가 너무 적은 함수 호출

    • parameter가 있는 function을 인자 없이 호출해도 undefined behavior가 발생할 수 있음
    • 반대로 인자가 너무 많은 function call은 유효하며, extra argument는 arguments keyword로 index할 수 있음
    • argument count indicator는 없음

  • 부적절한 type casting

    • Array를 이용해 변수를 다른 type으로 cast할 수 있음
    • cast된 variable에서 존재하지 않는 instance method를 호출하면 undefined behavior임
    • compiler는 이를 알아차릴 만큼 smart하지 않음

  • stack frame과 internal register 수정

    • memory address 256~2047의 stack frame 또는 1~15의 internal register를 수정하면 undefined behavior가 발생할 수 있음
    • 일반적으로 Memory.poke 오용이나 negative array indexing 없이는 어렵다고 되어 있음

  • 사용자 VM 파일 로딩

    • NAND는 .jack file에 대해서는 program validation을 제공하지만 .vm file에는 제공하지 않음
    • .vm file에서는 nonexistent function 호출, unassigned variable 참조, 논리적으로 invalid한 memory operation을 수행할 수 있음
    • 대부분의 경우 virtual machine escape가 발생하고 screen에 아무것도 표시되지 않을 수 있음

하드웨어 사양과 메모리 배치

  • NAND의 RAM은 32,768 words로 구성되며 각 word는 16-bit binary number를 담음
  • 하드웨어는 screen을 위해 8,192 memory address를 예약함
    • 각 address의 각 bit는 512x256 screen의 대응 pixel에 linearly map됨
    • bit numbering은 LSb 0 방식임
  • keyboard는 memory address 24576에 매핑됨
    • 현재 눌린 key가 이 위치에 반영됨
    • user input을 직접 이 주소로 처리하기보다 Jack OS의 Keyboard class를 쓰는 것이 권장됨
  • keyboard는 ASCII character와 특수 key를 인식함
    • new line = 128
    • backspace = 129
    • left/up/right/down arrow = 130~133
    • home/end/page up/page down/insert/delete/ESC = 134~140
    • F1~F12 = 141~152
  • hardware는 static class variable을 위해 240 memory address, global stack을 위해 1,792 memory address를 예약함
    • deep recursion을 수행하지 않는 한 이 제한은 대체로 문제가 되지 않는다고 되어 있음

Jack OS를 넘어 자체 OS 구현하기

  • 기본적으로 Jack OS는 compile 시 프로그램과 함께 bundle되어 string, memory, hardware interface를 제공함
  • 전용 hardware interface를 가진 자체 OS implementation을 제공할 수 있음
    • IDE는 Jack OS file을 일반 program file과 동일하게 취급함
    • OS file도 delete 또는 overwrite할 수 있음
  • 자체 OS를 쓰더라도 compile을 위해 반드시 구현해야 하는 core function들이 있음
    • Sys.init: Main.main이 아니라 VM implementation에 hardcoded된 실제 entry point임
    • Memory.alloc: class constructor가 object를 만들 때 내부적으로 사용하는 heap memory allocator임
    • String.newWithStr: string literal을 위한 internal constructor임
    • Math.multiply: Jack expression x * y 대신 내부 호출됨
    • Math.divide: Jack expression x / y 대신 내부 호출됨
  • 제공 Jack OS의 Sys.init은 memory, math, screen, output을 초기화한 뒤 Main.main()을 호출하고 Sys.halt()를 호출함

NAND 내부 동작

  • NAND computer는 Harvard architecture를 따름
    • instruction memory인 ROM과 data memory인 RAM이 분리되어 있음
    • CPU가 둘을 함께 동작하게 함
  • CPU는 accumulator machine임
    • control flow에서 built-in register에 크게 의존함
    • 여기서 accumulator는 D register임
  • CPU instruction set은 opcode가 두 개뿐임
    • instruction set은 비교적 단순하지만 풍부한 기능을 제공함
    • ALU는 한 instruction에서 계산할 수 있는 expression들로 지정됨
  • compiler와 virtual machine은 NAND만의 고유한 개념은 아니어서 짧게 다뤄짐
    • 일부 이상한 syntax feature는 compiler 구현을 쉽게 하기 위한 결과임
    • compiler는 LL(1) grammar 위의 recursive descent parser임
    • compiler는 VM code를 생성하고, VM은 simple stack machine으로 사용됨
    • 각 VM instruction은 assembly와 machine code로 mapping됨
  • 구현 코드는 core와 compiler implementation에서 확인할 수 있음

Jack 언어와 OS Reference의 핵심

  • Jack program은 class collection으로 구성됨
    • class는 별도 file에 정의됨
    • 하나 이상의 class가 필요하며, 그중 하나는 Main이어야 함
    • Jack OS 기준 entry point는 Main class의 main function임
  • class는 field, static, constructor, method, function 선언을 포함할 수 있음
    • field와 static declaration의 순서는 arbitrary임
    • subroutine declaration의 순서도 arbitrary임
    • type은 void, int, boolean, char, class name 중 하나임
  • syntax 특징
    • whitespace와 comment는 ignored됨
    • &와 |는 bitwise operator이며 short-circuit하지 않음
    • true, false, null은 각각 -1, 0, 0임
    • string constant는 newline이나 quotation mark를 직접 포함할 수 없고 escape도 불가함
    • quotation mark와 newline은 OS의 String.doubleQuote()와 String.newLine()로 제공됨
    • identifier는 case-sensitive임
  • Jack OS 주요 class
    • Array: array 생성과 dispose
    • Keyboard: key press, character, line, integer input
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: text screen 출력과 cursor 이동
    • Screen: pixel, line, rectangle, circle drawing
    • String: string 생성, dispose, character access, append, integer conversion
    • Sys: halt, error, wait
  • invalid state는 "ERR[N]" 형식의 error code를 표시하고 program execution을 종료함
    • ERR3: division by zero
    • ERR6: heap overflow
    • ERR15, ERR16: string index out of bounds
    • ERR17: string is full
    • ERR20: illegal cursor location

실제 NAND gate만으로 된 프로젝트는 아님

  • FAQ는 “everything made from NAND gates”라는 설명과 title이 misleading하지만 good faith라고 인정함
  • compiler와 virtual machine translator는 TypeScript로 작성됨
  • emulated kernel과 emulated hardware는 real computer가 작동하는 방식을 그대로 대표하지 않음
  • 실제 NAND gate logic simulator는 Rust로 작성되었고 전체 codebase의 작은 부분만 차지함
    • Rust code는 browser에서 실행되도록 WebAssembly로 compile됨
    • 이 점 때문에 모든 computation이 NAND gate에서 실행된다는 전제가 사실상 제거된다고 되어 있음
  • NAND는 educational and theoretical project의 역할을 함
    • 이론적으로 같은 CPU logic은 emulated hardware의 real-world manifestation에서도 동작할 수 있음
    • nand2tetris 기반 FPGA hardware project 예시로 https://gitlab.com/x653/nand2tetris-fpga/가 제시됨

구현 범위와 IDE 한계

  • NAND는 Nand to Tetris course와 관련 book의 specification을 따름
  • 구현자는 CPU, assembler, virtual machine translator, compiler specification을 직접 구현했고, platform을 web으로 porting하면서 자체 IDE와 UI를 붙였음
  • Jack이 type을 명시해야 하는 이유는 compiler가 instance method가 어느 class에 속하는지 판단하기 위해서임
    • String type으로 선언한 s의 s.appendChar(33)은 compile 중 String.appendChar(s, 33)으로 변환됨
  • IDE는 구현 단순성을 위해 user experience를 희생함
    • syntax highlighting을 위해 contenteditable과 cursor positioning logic을 사용함
    • 결과적으로 느리고 눈에 띄게 buggy하며 common keybind가 동작하지 않음
  • code를 compile하고 실행하려면 “Start”를 누르면 됨
    • OS는 일반적으로 memory initialize와 service setup에 1초보다 조금 덜 걸림

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 훌륭한 사이드 프로젝트이고 README도 정말 좋음. Ben Eater의 6502 Computer(https://eater.net/)를 좀 만져본 뒤 Nand to Tetris를 따라 해보려고 생각 중이었음

    • 물리적인 NAND-to-Tetris 컴퓨터를 만드는 것도 가능할까? 아니면 순수하게 가상 환경에서 하는 연습일 뿐일까?

  • 이 자료만으로 대학 수업 몇 개는 만들 수 있겠음. 잘 만든 자료임

    • 이거 그냥 Nand2Tetris 아닌가? 그 과정을 해봤는데, 얼핏 보기에는 Jack 언어까지 포함해서 같아 보임

  • 정말 잘 만들었음. 대부분의 프로그래머가 커리어 내내 보지 못할 추상화 계층을 직접 밟아본 셈임

  • 멋진 작업임. NAND to Tetris 덕분에 대학 졸업 후 첫 직장을 얻는 데 도움이 됐음

    • 어떻게 도움이 됐는지 궁금함

  • 1990년대 초 UC Berkeley의 컴퓨터 하드웨어 자격시험에서 이와 비슷한 설계가 핵심 문제였음
    구체적으로는 NAND 게이트만으로 밑바닥부터 마이크로코드 기반 파이프라인 RISC 프로세서를 설계하는 문제였고, 실제로 만들 필요는 없었지만 종이에 상세 설계를 제출해야 했음

  • 정말 대단한 작업임. Nand2Tetris 과정을 들을 때 나도 비슷한 가상 구현을 만들어보고 싶었음
    실제로 해냈다는 게 인상적이고, 이제 컴퓨터가 어떻게 동작하는지 정말 잘 이해하고 있을 것 같음

    • 나도 오늘 아침에 SVG로 기본 부품을 모델링하는 비슷한 생각을 하고 있었음
      그런데 내가 상상한 것보다 한 자릿수는 더 대단한 작업을 이미 누군가 해놨다니 놀라움

  • 훌륭한 작업임. 최근에 나도 Nand2Tetris를 시작했고, 앞으로 몇 달 안에 과정의 하드웨어 파트인 1부를 끝내고 싶음
    진행 상황은 여기 블로그에 적어뒀음: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • 거짓말임. NAND 게이트와 클록을 썼잖아

    • 그 클록도 링 발진기로 만들 수 있고, 링 발진기는 NAND 게이트를 NOT 게이트처럼 연결해 홀수 개로 구성하면 됨

  • 멋진 작업임. 나중에 깊게 살펴보려고 북마크해둠
    NAND-to-Tetris를 좋아하지만 끝까지 해보진 못해서, 이 프로젝트를 둘러보는 게 기대됨

  • 궁금한데, 전체 NAND 게이트 수는 몇 개임?

    • 코드를 자세히 살펴봤는데, 클록 주기마다 NAND 게이트가 3,234번 사용됨 :)
답변달기
GeekNews BeeBS 게시판 오픈! 자유로운 이야기와 소소한 일상을 함께 나눠보세요.