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

> Clean Markdown view of GeekNews topic #14518. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=14518](https://news.hada.io/topic?id=14518)
- GeekNews Markdown: [https://news.hada.io/topic/14518.md](https://news.hada.io/topic/14518.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-04-27T08:43:27+09:00
- Updated: 2024-04-27T08:43:27+09:00
- Original source: [github.com/ArhanChaudhary](https://github.com/ArhanChaudhary/NAND)
- Points: 2
- Comments: 1

## Topic Body

### NAND: 웹으로 구현된 완전한 Turing 등가의 16비트 컴퓨터

- NAND는 NAND 게이트와 클럭만으로 웹에서 에뮬레이션 된 Turing 등가의 16비트 컴퓨터
- NAND는 자체 CPU, 기계어, 어셈블리어, 어셈블러, VM 언어, VM 트랜슬레이터, 프로그래밍 언어, 컴파일러, IDE, UI를 가짐
- NAND는 Nand to Tetris 코스와 관련 책에서 명시된 Jack-VM-Hack 플랫폼을 기반으로 함

### 프로그램 예제

#### Average
- 숫자들을 입력 받고 평균을 계산하는 간단한 프로그램
- 제어 흐름, 산술 연산, I/O, 동적 메모리 할당을 보여줌

#### Pong
- Pong 게임으로 언어의 객체지향 모델을 보여줌
- 화살표 키로 패들을 좌우로 움직여 공을 튕김
- 매번 튕길때마다 패들이 작아지고, 공이 화면 아래로 떨어지면 게임 끝

#### 2048
- 2048 게임으로 재귀와 복잡한 애플리케이션 로직을 보여줌
- 화살표 키로 숫자들을 4x4 그리드에서 움직임
- 같은 숫자들이 합쳐질 때 서로 합쳐짐
- 2048 타일에 도달하면 이기는 것이지만 계속해서 더 모을 수 있음
- 보드가 가득차고 움직일 수 없을 때 게임 끝

#### Overflow 
- 무한 재귀로 스택 오버플로우를 의도적으로 발생시켜 가상 머신에서 탈출하는 프로그램
- 스택 오버플로우를 방지할 런타임 검사가 없다는 점을 활용
- 실행 시 스택 포인터 값을 계속 출력함
- 스택이 의도된 메모리 공간 끝까지 도달하여 힙 메모리로 넘어가면 프린트문이 폭발적으로 오작동함

#### SecretPassword
- 런타임이 스택 스매싱을 방지하지 않는다는 점을 활용하여 접근할 수 없는 함수를 호출하는 프로그램
- NAND의 스택프레임 레이아웃을 이해하고 있어야 함
- 사용자가 임의의 메모리 주소를 임의의 값으로 덮어쓸 수 있도록 허용
- 함수의 반환 주소를 다른 함수의 주소로 덮어쓰면 임의의 코드를 실행할 수 있음
- 스택 주소와 어셈블러를 수동으로 검사하여 얻은 특정 메모리 위치와 덮어쓸 값을 입력하면 이 아이디어가 동작하는 것을 볼 수 있음

#### GeneticAlgorithm
- NAND의 많은 컴포넌트들 중 개발에 가장 오래 걸린 부분
- 간단한 기계 학습을 사용하는 생물 시뮬레이션
- 각 점의 "뇌"는 가속 벡터들이며, 목표까지 자연 선택을 통해 진화함
- 매 세대에서, 목표에 더 가까이 "죽은" 점들이 다음 세대의 부모로 선택될 확률이 높음
- 재생산이 뇌를 돌연변이 시키고, 자연 진화를 효과적으로 시뮬레이션 함
- 성능상 제한으로 인해 많은 최적화 기법들을 활용하여 하드웨어 제한을 우회하고 이를 가능하게 함

### 잭으로 프로그래밍 하기

- 잭으로 프로그래밍할 때 가장 중요한 점은 연산자 우선순위가 없다는 것임. 이것이 프로그램이 제대로 동작하지 않는 이유일 수 있음.
- `4 * 2 + 3` → `(4 * 2) + 3`, `if (~x & y)` → `if ((~x) & y)` 처럼 괄호로 우선순위를 명시해야 함

#### 잭 소개
- NAND는 자체 기술 스택 전체를 자랑 
- Jack은 약한 타입의 객체지향 언어. 쉽게 말해 Java 문법을 가진 C언어 
- 한 예제를 통해 배워보자

#### 커스텀 데이터 타입
- 잭은 세가지 기본 타입 `int`, `char`, `boolean`을 지원 
- 필요에 따라 추상 데이터 타입으로 이를 확장할 수 있음
- 객체지향 프로그래밍 지식이 바로 적용 가능함
- 예제를 보면, `Point` 클래스로 추상적인 공간의 점을 정의
- `field` 변수로 데이터 타입의 인스턴스별 속성을 선언
- 점을 조작하는 공개 `method` 함수들을 제공하여 호출자가 점을 더하거나 두 점 사이 거리를 계산할 수 있게 함
- 모든 `field` 변수는 비공개로 범위가 지정됨. 이 변수들을 접근하려면 `method` 함수로 제공되어야 함
- 데이터 클래스는 `dispose` 메소드를 정의하는 것이 관례
- `function`, `method` 호출 문법 참조

#### 약한 타입 변환
- 잭은 자바에 크게 영감을 받았다고 했지만 단순한 파사드일 뿐 
- 자바는 강력한 타입 언어이고 다운 캐스팅, 다형성, 상속 등의 복잡한 타입 기능을 지원
- 반면 잭은 실제로는 signed 16-bit integer 하나만 지원함
- 이것이 잭이 약한 타입인 주된 이유임
- 그래서 잭 컴파일러는 할당 및 연산에서 다른 타입을 혼용해도 신경쓰지 않음
- 잭은 여전히 강력하고 기능적인 객체지향 모델을 제공함
- 타입 변환을 언제 어떻게 해야할지 이해하는데 도움이 될 것임

#### 수동 메모리 관리
- 잭은 수동으로 메모리를 관리하는 언어
- 더 이상 필요하지 않은 메모리를 적절히 해제하는데 주의해야함
- 그렇지 않으면 잭 OS가 메모리 누수가 있다고 생각할 것임
- 모범 사례는 각 클래스마다 할당 해제를 제대로 캡슐화 하는 `dispose` 메소드를 작성하는 것
- 객체가 더 이상 필요없을 때 이 메소드를 호출하면 힙 메모리가 부족해지는 것을 방지할 수 있음
- C 같은 다른 수동 메모리 관리 언어를 해봤다면 익숙할 것
- 차이점은 잭 OS가 배열과 문자열을 스택이 아닌 힙에 저장한다는 것
- `String.dispose`를 보면 어떻게 `dispose` 메서드를 작성할지 알 수 있을 것

#### 미정의 동작

##### 연산자 우선순위
- 너무 중요해서 앞으로 옮김

##### 작거나 큰 연산자
- 잭의 비교식 `a > b`, `a < b`는 단순해 보이지만 수학적으로 항상 옳지는 않음
- 가상 머신이 이를 `a - b > 0`로 바꿈. 그런데 `a - b`가 overflow될 수 있음
- `20000 > -20000`가 어떻게 평가될까? `20000 - (-20000) > 0` 즉 `-25336 > 0`가 되어 `false`가 됨
- 하지만 `20000 > -10000`는 `30000 > 0` 즉 `true`가 됨
- `a`와 `b`의 절대값 차이가 32767보다 크면 `a > b`와 `a < b`가 틀려짐. 아니라면 괜찮음
- 이는 버그가 아니라 Nand to Tetris과의 비호환성임. 호환성을 위해 이 동작은 고쳐지지 않을 것임

##### -32768
- -32768은 -(-32768) = -32768 라는 독특한 속성을 가진 유일한 숫자. 양의 짝꿍이 없는 싱글톤임
- 이로 인해 타당하지 않은 로직 오류가 발생할 수 있음   
- `-x`가 내부적으로 `~(x-1)`로 처리되기 때문  
- `x`에 `-32768`을 대입하면 `x-1 = ~x` 를 만족. `~(~x)`는 `x`와 같아짐
- 무슨 일이 있었나? NAND가 16비트 머신이어서 -32768에서 1을 빼면 비트들을 뒤집은 결과가 나옴
- 중요한 것은 음수 연산자 처리에서 로직 오류를 다루는 것임
- -32768 케이스를 확인하고 적절히 처리하는 것은 프로그래머의 책임임

##### 인자가 부족한 함수 호출
- 설명이 필요 없는 명백한 미정의 동작

##### 부적절한 타입 캐스팅
- `Array`로 변수를 아무 타입으로나 캐스팅할 수 있음
- 존재하지 않는 인스턴스 메소드를 호출하면 미정의 동작이 발생
- 컴파일러는 이를 감지할 만큼 똑똑하지 못함

##### 스택 오버플로우
- Overflow 프로그램 참조  

##### 스택 프레임이나 내부 레지스터 수정
- 스택 프레임이나 256~2047, 1~15번 주소에 있는 내부 레지스터를 수정하면 미정의 동작이 발생할 수 있음
- 보통 `Memory.poke`나 음수 배열 인덱스를 오용하지 않는 한 불가능함
- SecretPassword 프로그램 참조

#### 하드웨어 사양 
- 1970년대 이후 16비트 컴퓨팅이 도태된 이유가 있음
- 32비트나 64비트에 비해 처리 능력과 메모리 용량이 제한되어 현대 소프트웨어의 요구사항을 충족시키지 못함
- NAND도 예외는 아님
- 16GiB 맥북과 비교하면 NAND는 4KiB RAM밖에 없음. 0.00002%에 불과
- 그럼에도 우리를 달에 데려다 줄 만큼은 됨

- 잭 OS는 4KiB 중 14,336 메모리 주소를 힙에 예약. 비정상적으로 작은 수
- 그래서 잭 애플리케이션이 메모리를 효율적으로 할당 해제 하는게 매우 중요
- 너무 야심찬 계획이라면 힙 메모리가 부족해져서 데이터 타입과 로직을 완전히 다시 작성해야 할 수도 있음

- 4KiB 중 8,192 메모리 주소는 화면에 예약
- 각 주소의 각 비트는 512x256 화면의 픽셀에 선형으로 매핑. LSb 0 비트 넘버링 사용
- 24,576번 메모리 주소는 키보드에 예약
- 눌린 키의 ASCII 코드값이 반영됨
- 하지만 사용자 입력 처리를 위해 직접 접근하면 안됨. 잭 OS가 제공하는 Keyboard 클래스와 관련 함수 사용해야 함
- NAND 키보드는 ASCII와 특수키들을 인식함

- 정적 클래스 변수에는 240개, 전역 스택에는 1,792개 메모리 주소 예약
- 깊은 재귀를 하지 않는 한 이 제한은 문제 없을 것임

## Comments



### Comment 24726

- Author: neo
- Created: 2024-04-27T08:43:28+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40159278) 
- Nand to Tetris 프로젝트를 통해 컴퓨터의 추상화 레벨을 깊이 이해할 수 있음
- Ben Eater의 6502 컴퓨터 키트도 비슷한 교육적 가치가 있음
- 이 프로젝트는 여러 대학 수업으로 만들 수 있을 정도로 잘 정리된 자료임
- 1990년대 초 UC Berkeley의 컴퓨터 하드웨어 자격시험에서는 이와 유사하게 NAND 게이트만으로 마이크로코드화되고 파이프라인된 RISC 프로세서를 설계하는 문제가 출제되었음
  - 당시에는 실제 제작까지는 요구되지 않았고, 상세 설계만 종이에 작성하면 되었음
- 이 프로젝트는 [MarquisdeGeek/gates](https://github.com/MarquisdeGeek/gates) 와 유사해 보임
- Nand2Tetris 과정을 수강하면서 가상으로 이와 비슷한 것을 만들고 싶었는데, 실제로 구현한 것이 인상적임
  - 이를 통해 컴퓨터 동작 원리에 대한 이해도가 크게 향상되었을 것임
- NAND 게이트 외에 클럭도 사용했다는 지적이 있음 
- Nand2Tetris를 완주하진 못했지만 팬으로서 이 프로젝트를 깊이 살펴보고 싶음
- 총 몇 개의 NAND 게이트가 사용되었는지 궁금함
- 근본 원리에 충실한 접근에 감사를 표함