▲

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

 (github.com/ArhanChaudhary)
2P by neo 7달전 | favorite | 댓글 1개

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 프로그램 참조

스택 프레임이나 내부 레지스터 수정

  • 스택 프레임이나 2562047, 115번 주소에 있는 내부 레지스터를 수정하면 미정의 동작이 발생할 수 있음
  • 보통 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개 메모리 주소 예약

  • 깊은 재귀를 하지 않는 한 이 제한은 문제 없을 것임

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