컴파일러 구현에도 의외로 괜찮은 TypeScript

 (matklad.github.io)
8P by GN⁺ | ★ favorite | 댓글 1개
  • 컴파일러형 도구의 구현 언어는 전통적으로 OCaml과 C++ 로 갈렸지만, 작은 언어 실험에서는 TypeScript가 ML 계열 언어처럼 가볍게 쓸 수 있는 선택지가 됨
  • Rust는 ML과 C++의 장점을 결합하고 안전한 멀티스레딩까지 제공하지만, 데이터의 물리적 배치를 모델링해야 해 작은 프로토타입에는 부담이 커질 수 있음
  • Deno는 단일 바이너리, 내장 린팅·포매팅, 컴파일 단계 없음, 태스크 러너와 watch 모드 덕분에 TypeScript 언어 실험을 빠르게 시작하게 해줌
  • 예제 타입체커는 제네릭 AST, 태그드 유니언, visitor, bottom-up transform을 조합해 Expr<void>를 Expr<Type>으로 바꾸고, TypeError를 타입 값으로 넣어 연쇄 오류를 줄임
  • TypeScript는 자동완성, 유연한 타입 시스템, 필요할 때 동적 방식으로 빠질 수 있는 런타임 특성 덕분에 작은 언어 해킹용 도구로 생산적일 수 있음

구현 언어 선택의 기존 구도

  • 컴파일러 형태의 도구를 만들 때 구현 언어 선택에는 크게 두 흐름이 있음
  • 구현 중심이고 프로덕션 준비가 필요한 작업에는 C++가 자주 선택됨
    • LLVM, clang, v8, HotSpot이 모두 C++ 기반임
  • Rust는 ML과 C++의 영향을 직접적으로 받았고, 두 언어의 장점을 결합하며 안전한 멀티스레딩 같은 자체 강점도 제공함
    • 다만 스펙트럼상 프로덕션 준비성 쪽에 더 기울어 있음
    • “그냥 동작하는” 빌드 시스템은 프로토타이핑에도 도움이 되지만, 데이터의 물리적 배치를 모델링해야 하는 추가 복잡도가 따라옴

Rust 인덱스 방식의 장점과 작은 코드의 부담

  • Rust로 컴파일러를 만들 때 흔한 조언은 포인터를 피하고 인덱스를 쓰는 것임
  • 인덱스는 큰 코드베이스에서 여러 장점을 가짐
    • 사이드 테이블을 관련 모듈 안에 둘 수 있어 결합도를 낮춤
    • 인덱스가 u32이고 struct-of-arrays 배치를 유도해 성능에 유리함
    • 직렬화하거나 증분 컴파일 프레임워크에 연결하기 쉬워 계산 전략이 유연해짐
  • 하지만 작은 단위의 프로그래밍에서는 인덱스 방식 자체가 번거로워지고, 취미성 실험에서는 이 부담이 치명적일 수 있음
  • OCaml은 오래된 느낌이 남아 있으며, 이 맥락에서 TypeScript가 ML에 해당하는 대안처럼 쓸 수 있는지 검토됨

Deno와 TypeScript가 주는 빠른 실험 환경

  • 시작 환경으로 deno가 사용됨
    • TypeScript를 바로 쓸 수 있는 즉시 사용 경험을 제공함
    • OCaml에서는 이 부분이 고통 지점이고, Rust는 OCaml이나 C++보다 낫지만 Deno는 Rust보다 더 간단한 경험을 줌
  • Deno의 개발 경험은 작은 PLT 해킹에 잘 맞음
    • 단일 바이너리임
    • 린팅과 포매팅이 내장됨
    • 별도 컴파일 단계가 없음
    • 내장 태스크 러너와 watch 모드가 있음
  • TypeScript 자체는 충분히 유연하면서도 문법 부담이 가벼운 타입 시스템을 제공함

작은 타입체커 예제로 본 TypeScript 패턴

  • AST는 파일 위치 정보를 가진 표현식으로 시작함
    • Location은 file, line, column을 가짐
    • TypeScript에서는 문자열은 그냥 string, 숫자는 그냥 number라서 usize와 u32 같은 구분을 고민하지 않아도 됨
  • 표현식은 위치와 kind를 나누고, 나중에는 Expr<T> 형태로 연관 데이터를 제네릭화함
    • 파싱 직후 표현식은 void 데이터를 가짐
    • 타입체커가 처리한 표현식은 Type 데이터를 가짐
    • 타입 추론 함수는 ast.Expr<void>를 받아 ast.Expr<Type>을 반환함
  • TypeScript는 런타임 동작을 자동으로 추가하지 않으므로 유니언 타입을 매칭하려면 직접 런타임 타입 정보를 넣어야 함
    • tag: "binary", tag: "if" 같은 필드가 이 역할을 함
    • tag: "binary"는 런타임에서 해당 값이 문자열 "binary"만 가능하다는 뜻임
  • boolean 리터럴과 int 리터럴은 거의 같은 형태라서 ExprLiteral<T, V, Tag>로 추상화됨
    • ExprBool<T>는 ExprLiteral<T, boolean, "bool">
    • ExprInt<T>는 ExprLiteral<T, number, "int">
  • 타입 값은 TypeBool, TypeInt로 나뉘고 싱글턴 값도 같은 이름으로 제공됨
    • TypeScript는 타입을 완전히 지우므로 타입 관련 이름과 값 관련 이름이 별도 네임스페이스에 존재함
    • 이 특성을 이용해 타입과 값을 같은 이름으로 정의할 수 있음

Visitor, transform, 오류 타입, desugaring

  • TypeScript의 switch는 표현식이 아니라 문이므로, 표현식 kind를 편하게 처리하기 위해 visitor가 정의됨
    • bool, int, binary, if 메서드가 각각 해당 kind를 처리함
    • 에디터 자동완성이 switch case와 visitor 구현을 도와줌
  • transform<U, V>는 Expr<U>를 Expr<V>로 바꾸는 일반화된 순회 함수임
    • 변환은 bottom-up으로 실행됨
    • 내부 노드를 방문할 때는 하위 표현식이 이미 변환되어 있으므로 visitor 타입이 Visitor<U, V>가 아니라 Visitor<V, V>가 됨
  • TypeScript가 동적 타입 언어라는 점을 이용하면 Object.keys로 더 일반적인 순회를 만들 수도 있음
    • 이 경우에도 정적 함수 시그니처는 유지할 수 있음
    • 예제에서는 꼭 필요하지 않지만, 필요하면 동적 방식으로 빠질 여지가 있음
  • 타입 오류는 부수효과로 배열에 누적하지 않고 TypeError 타입으로 표현됨
    • Type은 TypeBool | TypeInt | TypeError가 됨
    • TypeError는 tag: "Error", location, message를 가짐
    • type_equal은 어느 한쪽이 Error이면 true를 반환해 연쇄 실패를 막음
  • 최종 타입체커는 binary와 if를 검사함
    • binary 표현식은 좌우 피연산자 타입이 다르면 "binary expression operands have different types" 오류를 반환함
    • if 표현식은 조건이 boolean이 아니면 "if condition is not a boolean" 오류를 반환함
    • then과 else branch 타입이 다르면 "if branches have different types" 오류를 반환함
  • 결과물은 타이핑이 어느 정도 필요하지만 자동완성이 많이 보완하고, 언어와 싸우는 느낌이 적으며 문제의 형태에 자연스럽게 맞음
  • TypeScript가 작은 언어 해킹용 도구로 생산적인 이유는 세 가지로 정리됨
    • Deno는 작고, 밀폐적이며, 강력하고, 효과적인 개발 워크플로에 최적화된 스크립팅 런타임임
    • TypeScript 도구는 IDE가 유용하고 생산적이며, Deno 덕분에 설정이 필요 없음
    • 언어는 런타임과 컴파일 타임 양쪽에서 강력하고, 타입으로 꽤 정교한 표현을 하면서도 필요하면 동적 방식으로 빠질 수 있음
  • 추가 아이디어로 많은 문법 설탕을 타입 안전하게 desugar하는 방식도 가능함
    • Expr와 ExprKind를 연관 데이터가 아니라 전체 ExprKind에 대해 순환적으로 매개변수화함
    • ExprKindCore는 기본 표현식 집합을 나타냄
    • ExprKindSugar는 기본 표현식이거나 기본 표현식으로 desugar 가능한 표현식을 포함함
    • desugar(expr: ExprSugar): ExprCore는 문법 설탕 표현식을 핵심 표현식으로 줄임
    • desugar_one(expr: ExprKindSugar<ExprCore>): ExprKindCore<ExprCore>는 하위 표현식이 이미 desugar된 상태에서 한 단계 변환을 수행함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • TypeScript는 전반적으로 훌륭한 언어이고, 함수가 프로퍼티/메서드를 가질 수 있는 객체라는 점이 과소평가되어 있음
    함수 배열을 명령처럼 실행하다가 나중에 help 같은 설명을 붙이거나, 클로저/부분 적용으로 상태를 추가할 수 있어 Command 같은 클래스를 성급히 정의하지 않아도 됨
    객체지향에서 이름을 너무 일찍 붙이는 일이 많은 갈등을 만들고, VideoCompressor#compress() 같은 구조보다 필요한 값을 함수에 넘기는 편이 자연스럽다고 봄

    • 정확히는 TypeScript라기보다 JavaScript 기능에 가깝다
      함수처럼 동작하는 객체를 지원하는 다른 언어들은 https://en.wikipedia.org/wiki/Function_object에 정리되어 있음
    • Go에서는 함수에도 메서드를 붙일 수 있고, 사실상 어떤 타입에도 가능함
      net/http의 핸들러처럼 구조체가 serve 메서드를 구현할 수도 있고, 핸들러 함수가 자기 자신을 호출해 인터페이스를 만족할 수도 있음
      Clojure에서는 함수 var에 메타데이터를 붙여 비슷하게 처리할 수 있고, Lisp라 매크로로 거의 무엇이든 가능함
      또 core/async의 CSP 채널은 실행과 통신을 분리해 콜백/프로미스/async/await 같은 함수 색깔 문제를 피하게 해 주며, 명령들이 결과를 채널로 보내는 생산자처럼 동작할 수 있음
    • Java의 단일 메서드 인터페이스로도 비슷한 효과를 낼 수 있음
      메서드 이름이 무엇이든 함수 문맥에서 사용할 수 있고, 구체적인 메서드명을 참조하지 않아도 됨
      다만 함수가 프로퍼티를 가져 상태를 품고, 같은 인자로 호출해도 동작이 바뀔 수 있는 건 선호하지 않음. 함수형 프로그래밍의 큰 장점은 객체지향식 상태에서 벗어나는 데 있다고 봄
    • Python은 모든 것이 객체라서 이런 방향을 잘 지원함
    • C# 에도 반환값이 있는 함수는 Func, 반환값이 없는 함수는 Action으로 비슷하게 표현할 수 있음
      JavaScript의 람다 표현식은 C#과 상당히 닮았고, TypeScript와 C#의 함수 시그니처도 꽤 유사함
      JavaScript, TypeScript, C#의 유사성을 보여 주는 작은 저장소도 있음: https://github.com/CharlieDigital/js-ts-csharp
      같은 로직을 JS/TS/C#로 나란히 보여 주는 스크린샷: https://github.com/CharlieDigital/js-ts-csharp/blob/main/js-...

  • 그리 놀랍지는 않음. TypeScript도 결국 ML 계열 기능 상당수를 어렵게 받아들인 또 하나의 언어라고 봄
    진짜 패턴 매칭이 없어서 OCaml보다는 불편하지만, C#, Swift, Dart, Kotlin 같은 부류와 비교하면 무난한 수준임

    • 너무 높은 수준에서만 본 비교임. 실제 사용감은 꽤 다름
      TypeScript는 타입 시스템은 강력하지만 기반 표준 라이브러리와 언어 자체가 아쉽고, 패턴 매칭/스위치 표현식이 없음
      Dart는 객체 모델이 닫혀 있어 동적 자유도가 낮고, 타입 시스템과 표현식도 더 약하며, 메타프로그래밍 시설이 거의 없어 Java식 보일러플레이트와 코드 생성기에 기대게 됨
      C# 은 언급된 언어 중 ML 기능에 가장 가깝지만, TypeScript와 달리 합 타입이 없어 많은 일이 더 번거로워짐
    • 예전에 Haskell로 만든 Pascal-C풍 학습용 컴파일러에서, 파서 조합자는 문법을 BNF 비슷하게 코드로 직접 표현할 수 있게 해 줬음
      예를 들어 { ... }를 인식하는 파서를 다른 파서와 조합하고, 문장은 제어 흐름/선언/대입 중 하나로 정의할 수 있음
      ML식 리스트 처리와 패턴 매칭은 중간 표현을 다룰 때 매우 표현력이 좋았음
    • TypeScript에서 패턴 매칭이 필요할 때는 이 라이브러리를 즐겨 씀: https://github.com/gvergnaud/ts-pattern
    • TypeScript가 ML 기능 대부분을 가져왔다고 보기는 어려움
      본문에서도 switch가 표현식이 아니라서 방문자 패턴으로 우회해야 했고, JavaScript의 반복자 지원도 이상하게 부족함
      .map()은 있지만 배열에만 동작하고, 일반 반복자에는 바로 적용할 수 없음
    • TypeScript와 kotlin-js를 써 보면 두 언어가 꽤 가깝게 느껴짐
      차이는 많지만 전환은 어렵지 않고, 개인적으로는 Kotlin을 더 선호해도 둘 다 사용할 수 있음
      TypeScript가 JavaScript 호환성에서 벗어나 WASM으로 컴파일하면 어떨까 싶음. Kotlin은 WASM 컴파일러를 추가 중이고 이미 JS 트랜스파일러도 있는데, 같은 코드가 WASM에서는 더 작고 빠르게 로드됨
      브라우저 JavaScript는 좋은 컴파일 대상이 아니며, 새 프로젝트가 처음부터 TypeScript로 시작하는 일이 늘어난 만큼 기존 JavaScript에서 쉽게 전환해야 한다는 이유도 점점 약해지고 있음

  • Rust와 TypeScript를 오가면 태그 달린 열거형 같은 기능이 얼마나 빠져 있는지 매우 선명하게 보임
    ADT 열거형 제안은 멈춘 것 같은데, 다른 노력이 있는지 궁금함: https://github.com/Jack-Works/proposal-enum/discussions/19

    • 비슷한 용도에는 판별 유니언이 꽤 괜찮게 동작한다고 봄

  • TypeScript의 타입 시스템은 재미있지만, 컴파일러가 컴파일 언어로 작성됐다면 얼마나 더 빨랐을지 궁금해짐
    물론 “좋은 구현”이라는 큰 전제가 필요함

    • swc와 esbuild는 좋은 비교 대상이 아님. 속도 향상 상당 부분은 TypeScript 전용 문법을 제거해 JavaScript를 생성하기 때문임
      tsc는 첫 실행만 느린 편이고, incremental 플래그나 --transpile-only 감시 모드를 쓰면 보통 컴파일 시간이 100ms 아래로 내려가 SWC나 ESBuild와 체감 차이가 거의 없어짐
    • TypeScript 팀의 답변이 있음: https://twitter.com/drosenwasser/status/1260723846534979584
      중간 규모 프로그램 타입 검사에 20초가 걸린다면 보통 JS라서가 아니라, 타입이 조합 폭발을 일으키기 때문인 경우가 많다는 얘기임
      다른 런타임은 병렬성이나 시작 시간에서 이득을 줄 수 있지만, 전체 20배 속도 향상을 뒷받침하는 CPU 중심 벤치마크는 보지 못했다고 함
    • 타입 시스템은 제네릭에서 최대한 활용하기 전까지는 재미있음
      그러다 타입 로직 5줄을 하루 종일 디버깅하고 나면 내가 어쩌다 여기까지 왔는지 묻게 됨
    • 더 이상 상상만 할 필요는 없음: https://github.com/dudykr/stc
      SWC의 주요 개발자가 Rust로 작성한 프로젝트로, SWC는 TS를 JS로 컴파일하고 STC는 TS 타입을 검사함
    • 최근 TypeScript 컴파일러 성능은 크게 좋아졌음
      앞으로의 isolated declaration mode는 컴파일 시간을 최대 75%까지 줄일 수 있다고 함: https://github.com/microsoft/TypeScript/pull/53463#issuecomm...

  • 컴파일러를 막 배우기 시작하는 사람에게는 이 책을 추천함: https://keleshev.com/compiling-to-assembly-from-scratch/
    저자는 TypeScript 부분집합으로 32비트 ARM 어셈블리 컴파일러를 만들며, 거의 의사코드처럼 보여 접근성이 좋다고 설명함

    • Crafting Interpreters도 강력히 추천함: https://craftinginterpreters.com/
      책은 두 부분으로 나뉘며, 첫 번째는 Java로 언어 인터프리터를 만들고, 두 번째는 같은 언어를 바이트코드로 컴파일한 뒤 C로 바이트코드 가상 머신을 구현함
      구현의 모든 코드 줄이 책에서 참조됨

  • 방문자 패턴을 피하려면 run 유틸리티 함수로 IIFE 스타일 switch를 사용할 수 있음
    즉시 실행 함수 안에서 switch를 쓰고 반환 타입을 추론하게 만들면 됨

    • 이 패턴에 대해 글을 쓴 적이 있음: https://maxgreenwald.me/blog/do-more-with-run
    • 사실 그 정도도 필요 없고, 그냥 함수를 즉시 호출하면 반환 타입이 추론됨
      끝의 ()가 싫어서 IIFE를 피하고 싶다면 함수를 따로 정의한 뒤 호출하면 됨

  • TypeScript로 컴파일러를 작성 중인데, 생각보다 나쁘지 않다는 데 동의함
    처음에는 저자처럼 Deno로 시작했지만 결국 Bun으로 옮겼고, 거친 부분은 있어도 Deno보다 더 만족스럽고 매우 빠름
    표준 파서 생성기 프런트엔드로는 Ohm-js가 꽤 쾌적함: https://ohmjs.org/
    공식 tsc 컴파일러는 너무 거대해서 읽기를 권하지 않고, tsc가 어떻게 동작하는지 보기에는 mini-typescript가 더 좋음: https://github.com/sandersn/mini-typescript/
    특히 centi-typescript 브랜치가 도움이 됨: https://github.com/sandersn/mini-typescript/tree/centi-types...
    WASM에서 GC와 DOM 접근이 가능해지길 기대함

    • Bun으로 옮기게 된 이유가 궁금함

  • TypeScript는 인터페이스 때문에 추가 부담이 더 있을 줄 알았는데 의외임
    다른 분야에도 적용할 수 있을지, 예를 들면 언어 파싱에도 괜찮을지 궁금해짐

    • 런타임에서는 인터페이스의 부담이 0임
      컴파일 과정에서 완전히 사라짐

  • 결과가 아주 놀랍지는 않음. TypeScript 컴파일러 자체가 TypeScript로 작성되어 있기 때문임
    ML로서의 TypeScript는 이미 매일 무거운 프로덕션 환경에서 검증되고 있음

  • C#으로 컴파일러를 작성해 봤는데, 여기서 특별해 보이는 건 유니언 타입 정도임
    개인적으로는 방문자 패턴의 장황함을 피하기로 했고, 컴파일 시점의 완전성 검사를 위해 닫힌 열거형 기능을 기다리는 중임

    • 유니언 타입이나 Rust식 열거형이 없는 언어를 쓰면 그 기능이 많이 그리워짐
      보통 대안은 어색함. 합 타입 하나를 표현하는 클래스에 nullable 프로퍼티 N개를 두고 “항상 하나만 non-null”이라는 문서상의 조건에 기대거나, 여러 클래스를 공통 클래스로 상속시키는 방식인데 둘 다 무겁게 느껴짐
      겹치는 여러 유니언 타입을 만들려면 두 방식 모두 중복이나 영리한 조합이 필요해짐
답변달기