TypeScript 타입으로 실행되는 DOOM [비디오]

 (youtube.com)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 1993년 게임 DOOM을 런타임 코드가 아닌 TypeScript 타입 시스템만으로 부팅해 첫 프레임을 출력한 실험임
  • 첫 프레임까지 TypeScript 타입 체커가 3.5조 줄, 총 177TB를 12일 동안 처리했으며, 초기 추정치는 1.25PB와 3개월 이상이었음
  • 핵심 구현은 타입으로 만든 WebAssembly 가상 머신으로, DOOM에 필요한 116개 명령을 타입 수준 논리로 구현하고 1,800만 개 명령을 평가함
  • 개발 중에는 컴파일러의 재귀·유니언·튜플·깊은 타입 인스턴스화 제한을 제거했지만, 최종 결과물은 사용자가 실행 가능한 순정 TypeScript 형태로 남음
  • 일반 앱의 타입 체크 규모를 훨씬 넘는 작업이라 기존 개발 도구가 거의 무력화됐고, 12,364개 테스트와 커스텀 도구를 직접 만들어야 했음

TypeScript 타입 시스템 안에 만든 컴퓨터

  • DOOM은 일반 JavaScript 실행이 아니라 TypeScript 타입 시스템 안에서만 동작함
  • 목표는 속임수나 다른 실행 언어 없이, 타입만으로 다른 프로그램도 실행할 수 있는 WebAssembly 가상 머신을 만드는 것이었음
  • 타입 수준 컴퓨터는 실행에 필요한 기본 구성요소를 타입으로 갖춤
    • RAM
    • 디스크 공간
    • 호출 스택
    • 서브루틴
    • 메모리 포인터
    • 실행 컨텍스트
    • 커스텀 개발 도구
  • DOOM 실행에 필요한 116개 WebAssembly 명령을 TypeScript 타입으로 논리 구현함
  • 이 논리만으로도 타입 체커가 하나씩 평가해야 하는 1,800만 개 명령이 만들어졌고, 각 명령은 시스템의 고유한 머신 상태를 나타냄

첫 프레임까지의 규모

  • 첫 DOOM 프레임을 얻는 데 3.5조 줄의 타입이 필요했고, 전체 타입 크기는 177TB였음
  • TypeScript 컴파일러 TSC를 12일 동안 계속 실행해 게임을 부팅하고 첫 프레임을 얻음
  • 초기 계산으로는 컴퓨터가 1.25PB의 TypeScript 타입을 처리해야 했고, 실행 시간은 3개월 이상으로 예상됨
  • 극단적인 최적화 끝에 처리량을 177TB와 12일까지 줄임
  • 일반 앱의 TSC 타입 체크는 보통 20만~50만 타입 인스턴스화 수준이지만, 이 작업은 12일 내내 초당 2,000만 인스턴스화를 지속함
  • 최종 출력은 TypeScript 객체이며, 각 값이 픽셀 한 줄을 나타냄
    • 출력 프레임은 320×200
    • 총 128,000픽셀의 ASCII 프레임임
  • 키보드 입력으로 게임을 제어하는 방법도 있음

개발 중 제거한 TypeScript 보호장치

  • 최종 결과물은 사용자가 직접 실행할 수 있는 순정 TypeScript임
  • 실험을 가능하게 하려고 TypeScript 컴파일러를 수정해 여러 제한을 제거함
    • 타입 비교 시 과도한 스택 깊이 제한 제거
    • 지나치게 깊거나 무한할 수 있는 타입 인스턴스화 제한 제거
    • 유니언과 튜플의 최대 크기를 Infinity로 설정
    • 출력 잘림 제한 제거
    • 유명한 TypeScript 재귀 제한 제거
  • 컴퓨터 자체의 스택 제한도 올림
  • 이런 보호장치를 없애자 타입 체커가 100GB 메모리를 쉽게 사용할 수 있게 됨
  • 제한 제거의 대가는 컸음
    • import 오타처럼 사소한 문제도 무한 루프를 만들 수 있었음
    • 힙 할당이 메모리를 모두 사용해 전체가 크래시될 수 있었음
    • 스택 트레이스는 매우 거대했고, 대부분은 그냥 멈추는 식으로 실패함

DOOM 실행을 위해 추가로 만든 것들

  • 6개월 작업 후에는 작은 C 프로그램을 실행할 수 있었지만, DOOM 실행에는 훨씬 더 많은 구현이 필요했음
  • DOOM의 구성요소를 모두 타입으로 인코딩해야 했음
    • 게임 맵
    • 텍스처
    • 스프라이트
    • 사운드
    • 적 AI
    • 무기
    • 아이템
    • 물리 엔진
    • 오디오 서브시스템
    • 게임 내 텍스트
  • 타입 수준에서 런타임에 가까운 기능까지 구현함
    • 가비지 컬렉터
    • L1 CPU 캐시
    • 런타임 dead code elimination
    • 실시간 메모리 컴팩터
    • 스택 언더플로 보호를 위한 깊이 카운팅 포함 전역 값 스택
    • 동적 디스패치 테이블
    • 모듈 수준 전역 변수
    • labeled goto
    • 타입 수준 예외 처리
    • 런타임 스택 트레이싱
    • 전체 코어 덤프
  • 선형 RAM은 32비트 주소 키와 바이트 값을 가진 거대한 정렬 불가능 객체로 표현됨
  • 타입 사용자 공간에서 타입 평가를 일시 중지하는 방법을 찾아 코어 덤프, 예외 처리, 스택 트레이싱이 가능해짐

도구 한계와 구현상의 제약

  • 파일 크기가 최대 1GB까지 필요해 Prettier가 처리할 수 있는 범위를 넘어섬
  • 언어 서버 통합이나 린터는 즉시 크래시됐고, 사실상 문법 강조만 간신히 작동함
  • 엔진 내부는 문자열 리터럴에 저장한 2의 보수 이진수로 구현됨
  • TypeScript는 문자열을 왼쪽부터만 순회할 수 있어, 이진 알고리듬을 모두 역방향으로 구현해야 했음
  • 엔진 내부에는 배열, 객체, 문자열, 불리언이 없고 이진수만 사용됨
  • DOOM은 64비트와 32비트 정수만 사용하며, 그 정수들은 signed도 unsigned도 아니어서 이를 파악하는 데 하루가 걸림
  • 제작자는 시작 당시 필요한 지식의 10%도 알지 못했고, 자체 도구를 만들고 12,364개 테스트를 손으로 작성하며 여러 프로그래밍 언어를 새로 배움

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 처음엔 완전히 장난 같거나 쓸모없어 보일 수 있는 일을 위해 1년 동안 하루 18시간을 쏟았다니, 정말 엄청난 집념임
    하지만 DOOM 증명은 어떤 학술적 수학 증명만큼 칭찬받을 만하고, 비전문가도 검증할 수 있다는 장점까지 있음

    • 이런 표현을 미국식 영어에서 문자 그대로 읽으면 안 된다고 봄
      미국 영어 화자들은 하루에 몇 시간 일했다거나 며칠을 안 잤다는 식으로 늘 말하는데, 나도 처음엔 감탄하다가 “그냥 일상적으로 과장하는 건가?” 하고 깨달았음
      모든 구매가 “업그레이드”가 되고, 도시 통근용 자전거가 “urban assault vehicle”이 되는 문화라서, 실제로 1년 내내 하루 18시간 일했다고는 진심으로 믿기 어렵고, 열심히 했다는 뜻에 가까움
    • “1년 동안 하루 18시간”이라니, 재능이 있어도 난 못 했을 듯함
      돈을 벌려면 일도 해야 하니까
    • TypeScript 타입이 이미 튜링 완전하다는 건 알고 있었으니, 증명이라기보다는 시연에 더 가까움
    • 진지하게 한 말은 아니었을 것 같음

  • “나는 멋진 10x 개발자는 아니다. 장인정신의 달인이라기보다 ‘이 정도면 됐지’ 정신의 달인에 가깝다”라는 말에 크게 공감함
    또 “1년 동안 하루 18시간의 혹독한 여정이었다”고도 했는데, 사람들은 코드판 Good Will Hunting 같은 유니콘 10x 개발자를 찾지만, 바로 이해하지 못해도 끝까지 파고들어 결국 알아내는 개발자들이 있다는 걸 잊는 듯함
    그런 사람들은 유니콘보다 훨씬 많이 찾을 수 있을 것 같음

    • 예전엔 누군가가 어떻게 그런 트릭을 떠올렸는지 이해가 안 되는 것들이 사실은 트릭이 아니라 엄청난 노동량의 결과였다는 걸 깨닫는 순간이 있었음
      나는 몇 시간 안에 해낼 마법을 몇 주씩 찾았지만, 다른 사람들은 실제로 필요한 며칠이나 몇 주를 그냥 들였던 것임
      지금은 훨씬 더 잘 만들게 됐고, 사람들이 어떻게 그렇게 하냐고 묻기도 함
    • 어린 개발자들이 내가 허공에서 뽑아낸 것처럼 보이는 해법을 볼 때 자주 말하는 게 있음
      나는 그들보다 훨씬 더 많이 실패했고, 다만 실수 고치는 법을 잘 기억하고 있을 뿐임
    • 그런 사람들이 유니콘임
    • 나도 공감함. 테크 리드이기도 하고, 프로그래밍을 즐거운 퍼즐처럼 느끼는 편임
      아내가 TV를 틀어두면, 보통 눈에 띈 문제나 개선점을 건드려 봄
      Docker 빌드 시간 개선 대부분도 여러 방법을 시도해서 통하는 걸 찾은 결과고, 작은 삶의 질 개선 기능들도 비슷함
      이 프로젝트 개발자에게도 존경을 보냄. 어떤 면에서는 이런 프로젝트가 필생의 대표작 같은 것임
      많은 사람이 알거나 신경 쓰지 않을 수도 있지만, 실제로는 성취했다는 걸 자랑스러워할 만함
    • 균형이 필요하겠지만, 끈질긴 추진력과 집중력이 순수 지적 능력보다 조금 더 중요할 수도 있다고 느낌

  • TypeScript 타입만으로 만든 WASM 런타임 자체도 인상적이고, 많은 노력을 들이면 어떻게 동작할지 희미하게는 보임: https://github.com/MichiganTypeScript/typescript-types-only-...
    이해가 안 되는 건 키보드 입력을 어떻게 처리하느냐임
    영상 3:42에서는 “네, 키보드 입력을 하는 방법도 있습니다”라고만 하고 설명이 없음
    타입 시스템 바깥에서 키보드 입력을 TypeScript 타입으로 변환하는 뭔가가 있어야 하는 것 아닌가?

    • 작성자임. 그 화면에서 멈추고 오른쪽에 표시된 코드와 아래쪽 메모를 보면 됨
      키보드 입력 방식은 기본적으로 도구 보조 스피드런에서 하는 것과 거의 같음
      이 대목에서 어떤 사람은 “오 멋지네!” 했고, 어떤 사람은 “거짓말쟁이야! 그건 같은 게 아니잖아!” 했음
      7분짜리 짧은 영상에 담을 말이 너무 많았지만, 다음 영상들에서 이 부분을 깊게 다룰 예정임
      보이는 Pong 부분은 실제이고, 애니메이션 연출만 창작적 자유였으며 오픈소스 코드베이스에 들어 있음

    • DOOM 쪽은 확인하지 않았지만, Pong 예제에서는 키보드 입력이 미리 기록되어 있음
      키 누름 순서가 TypeScript 배열에 들어가는 식임0

    • 추측하자면, 특정 시간 간격마다 눌린 키나 눌리지 않은 키의 배열이 들어 있는 파일일 것 같음
      그러면 VS Code 확장이 0.1초마다 그 시점의 키 상태를 배열에 추가하고, 컴파일러가 이 배열이 갱신될 때마다 게임 상태를 업데이트하는 식임
      다만 그래서 DOOM이 아니라 Pong 데모를 보여준 것일 수도 있음. DOOM은 아마 이 속도를 따라가지 못할 테니까
      내가 방향이라도 맞게 짚은 건지는 전혀 모르겠음

  • 정신이 번쩍 들었음. Dimitri가 영상에서도 말하지만, 이 프로젝트가 어떻게 시작됐는지 보여주는 문구가 특히 좋음0
    “이 엔진은 TypeScript 타입에서 Doom이 실행될 수 없는 이유를 보여주려는 프로젝트를 위해 만들어졌다. 그런데 웃기게도… 실행된다”

    • 실행될 수 없다는 쪽의 논거는 뭐였을까?

  • Dimitri가 이 작업의 진행 상황을 내부에 올리는 걸 봤는데, 정말 말도 안 되게 놀라웠음
    코드로 해낸 것 중 내가 본 가장 놀라운 일 중 하나이고, 완전히 전설적인 업적임
    끈기도 엄청났음

    • 그 업데이트들은 어디서 볼 수 있음?

  • TypeScript의 타입 시스템이 튜링 완전하다는 얘기가 많았던 걸 생각하면, 이게 가능하다는 사실이 동시에 놀랍기도 하고 전혀 놀랍지 않기도 함
    그래도 실제로 끝까지 밀어붙인 근성은 박수받을 만함

    • Java와 Python 타입 시스템도 튜링 완전하다는 논문들을 본 적이 있음
      모든 타입 시스템이 튜링 완전하다고 해도 놀라지 않을 듯함

  • 오늘 HN에 올라갈 만한 최상위 글이 하나라면 이거여야 함
    완전히 미쳤고, 엄청나게 영감을 줌

    • 이번 달에 진짜로 소리 내서 웃은 글임
      타입 스케일 그래픽과 애니메이션이 너무 좋았음

  • 이제 어떤 시스템이 튜링 완전한지 아는 가장 쉬운 방법은 누군가가 DOOM을 이식했는지 확인하는 것 같음
    정말 인상적임

  • DOOM이 TypeScript 타입만으로 컴파일되자 177TB가 됐다니, 여러 층위에서 대단함

    • 이건 튜링 타르핏의 전형적인 예시일 듯함
      TypeScript 타입 안에서는 모든 게 가능하지만, 흥미로운 건 아무것도 쉽지 않음
    • 놀라울 정도로 비효율적임
      그래도 나는 이걸 재현할 수 없을 테니 존경함
    • 첫 프레임 기준으로는

  • Dimitri는 놀라운 엔지니어일 뿐 아니라, 커뮤니티 구축과 행사·영상 제작도 잘함
    Michigan TypeScript 밋업과 영상은 기대 이상으로 마감 품질이 높음

    • YouTube 댓글에서 본인은 그래도 빅테크 면접, 특히 기술 면접을 망쳤다고 했음
      아마 미리 외워두지 않은 우스꽝스러운 LeetCode 문제 때문이었을 것임
      이런 절차가 실제로 좋은 엔지니어나 프로그래머를 가려내지 못한다는 걸 보여줌
      이런 걸 해낸 사람이 취업을 못 한다면, 면접 프로세스 어딘가가 꽤 잘못된 것임
답변달기
GeekNews BeeBS 게시판 오픈! 자유로운 이야기와 소소한 일상을 함께 나눠보세요.