Lil' Fun Langs' Guts

taylor.townaboutspamrss Lil' Fun Langs' Guts

나는 여전히 그 lil' fun langs에 대해 생각하고 있다. 그건 어떻게 동작할까? 안에는 뭐가 들어 있을까? 내 췌장이 필요할까? 내 IR을 정규화하고 싶지 않다면? 게으름은 미덕일까?

Haskell-스러운 언어들은 비슷해 보일 수 있지만, 많은 차원에서 서로 다르다:

• 엄격 vs. 지연
• 커리드 vs. 밋밋
• 부트스트랩 vs. 호스티드
• 인터프리트 vs. 컴파일
• 이름 기반 vs. 구조적 타입
• 예쁜 vs. 못생긴 에러

대부분의 구현은 표준적인 컴파일 단계들을 사용한다:

1. 렉싱: 소스 → 토큰 스트림
2. 파싱: 토큰 → 표면 AST
3. 디슈가링: 표면 AST → 코어 AST
4. 타입 추론: 코어 AST → 타입이 붙은 AST
5. 패턴 매치 컴파일: 타입이 붙은 AST → 케이스 트리
6. 정규화(ANF/K): 타입이 붙은 AST → 정규화된 IR
7. 최적화: 정규화된 IR → 정규화된 IR
8. 클로저 변환: 정규화된 IR → 클로저-명시 IR
9. 코드 생성: 클로저 IR → 타깃(asm/bytecode/C/LLVM)
10. 레지스터 할당: 가상 레지스터 → 물리 레지스터(네이티브인 경우)
11. 런타임 시스템: GC, 프리미티브, 엔트리 포인트

---

Strict vs. Lazy

엄격 평가에서는 인자들이 함수에 전달되기 전에 평가된다. 지연 평가에서는 인자 값이 실제로 필요할 때만 평가되며; 결과는 캐시되므로, 작업은 최대 한 번만 발생한다.

-- lazy eval returns `3` without applying `foo`
length [ 1, foo 2, 4 ]

엄격 평가는 단순한 선택이다. 지연성을 원한다면, Peyton Jones의 STG 머신이 표준 접근이다. MicroHs는 STG 머신을 피하고, 그래프 축약을 동반한 조합 논리로 직접 컴파일함으로써 우회한다.

지연 평가는 또한 무한 컬렉션을 가능하게 한다 — 무한 리스트를 정의하고 필요한 만큼만 소비할 수 있다.

Curried vs. Bland

커리드 언어에서 f x y는 ((f) x) y이다: 함수 적용 두 번. 백엔드가 f가 항상 인자 두 개를 받는다는 것을 감지하지 못하면(arity 분석), 다인자 호출마다 힙 할당 비용을 치르게 된다.

Bootstrapped vs. Hosted

나는 기타를 치는 법을 독학하려 했다. 하지만 나는 끔찍한 선생님이다 — 왜냐하면 나는 기타 치는 법을 모르기 때문이다.

— Mitch Hedberg

대부분의 컴파일러는 기존 언어(예: C, Rust, Haskell, OCaml)로 작성되며, 파싱 라이브러리, 빌드 도구, 패키지 관리 같은 호스트의 생태계에 기대어 있다.

부트스트랩 컴파일러는 자기 자신을 컴파일한다. 컴파일러를 그 언어로 작성한 뒤, 이전 버전의 컴파일러(또는 최소 시드 런타임)를 사용해 다음 버전을 빌드한다. 언어가 자급자족하게 되고; 컴파일러는 스스로의 테스트 스위트가 된다.

공부할 만한 훌륭한 셀프-호스티드 언어들이 많다:

• MicroHs는 Haskell을 조합자로 컴파일하는 Haskell 컴파일러다. 조합자 리듀서는 C로 구현되어 있다. 컴파일러는 Haskell로 작성되었고 자기 자신을 컴파일할 수 있다. 부트스트랩에는 C 컴파일러만 필요하며 -- 기존 Haskell 설치가 필요 없다.
• Ben Lynn은 C로 된 최소 런타임(~350 LOC)에서 시작해, 점점 더 강력한 컴파일러들을 구성하는데, 각 컴파일러는 이전 컴파일러가 컴파일할 수 있는 부분집합으로 작성된다. 각 단계는 정의되는 언어 코드로 ~100–300 LOC 정도다. 전체 체인은 ~2000 LOC + 350 LOC C 정도다.

C runtime (350 LOC)
    → compiler₁: lambda calculus + integers
    → compiler₂: + let, letrec, ADTs
    → compiler₃: + type inference
    → compiler₄: + pattern matching
    → compiler₅: + type classes
    → ...
    → compilerₙ: near-Haskell-98

• Newt는 JavaScript를 타깃으로 하는, Newt로 작성된 의존 타입 언어다. 생성된 JS를 리포지토리에 체크인해 두는 방식으로 부트스트랩한다. 이는 네이티브 코드보다는 (JS, JVM 같은) 고수준 런타임을 타깃으로 할 때 가장 잘 작동한다.

Interpreted vs. Compiled

인터프리터는 AST를 순회하거나 바이트코드를 단계적으로 실행하면서 프로그램을 직접 실행한다. 컴파일러는 프로그램을 다른 언어(예: x86, C, JS)로 번역하고, 실행은 그 타깃이 처리하게 한다.

여기서 경계는 흐릿하다. 바이트코드 VM은 중간 형태로 컴파일한다. “트랜스파일러”는 기계어가 아니라 소스 코드로 컴파일한다.

lil' fun langs는 보통 인터프리터다. 컴파일이 없다면 클로저 변환, 레지스터 할당, 런타임 시스템을 건너뛸 수 있다. 인터프리터에서 컴파일러로의 도약은 ~500–2000 LOC 정도의 비용이 든다.

Nominal vs. Structural Types

type Meters  = Int
type Seconds = Int

-- Nominal:     Meters ≠ Seconds  (different names)
-- Structural:  Meters = Seconds  (same shape)

대부분의 ML 계열 언어는 대수적 데이터 타입에는 이름 기반이지만, (구현되어 있다면) 레코드에는 구조적인 경우가 많다. 행 다형성(EYG, Grace, Koka)은 본질적으로 구조적이다 -- “적어도 이 필드를 가진 어떤 레코드든”에 대해 동작한다. Simple-sub는 더 나아가 합집합/교집합 타입을 제공하면서도 주(Principal) 추론을 유지한다.

Pretty vs. Ugly Errors

-- Ugly:
Error: type mismatch: int vs string

-- Pretty:
 3 │ let x = 1 + "hello"
   │             ^^^^^^^^
Error: I expected an `int` here, but got a `string`.
  The left side of `+` is `int`, so the right side must be too.

예쁜 에러는 겉에 페인트칠만 한다고 얻어지지 않는다. 코드의 특정 줄/영역을 가리키려면, 모든 컴파일 단계에 걸쳐 소스 위치를 스레딩해야 한다. 최소로 쓸 만한 에러 시스템은 다음을 포함한다:

1. 모든 AST 노드에 소스 스팬. 모든 표현식, 패턴, 타입이 { file, start_line, start_col, end_line, end_col }를 가진다. 이는 노드당 필드 하나가 추가되는 비용이다.
2. 디슈가링을 거쳐도 스팬을 보존. where를 let으로 내릴 때, 새 let 노드는 where의 스팬을 상속한다.
3. 타입 추론을 거쳐도 스팬을 보존. 유니피케이션이 실패하면 충돌하는 두 타입의 스팬이 필요하다.
4. 문맥과 함께 에러를 포매팅. 소스 줄을 보여주고, 관련 스팬에 밑줄을 긋고, 불일치를 설명한다.

---

Lexing

선택적 향상:

• 레이아웃/들여쓰기 민감(Haskell 스타일 오프사이드 규칙): Ben Lynn은 이후 부트스트랩 단계에서 이를 구현한다. MicroHs는 완전한 레이아웃 파싱을 포함한다. 100–300 LOC 추가. 알고리즘은 Haskell Report의 Section 2.7에 잘 설명되어 있다.
• 유니코드 식별자: 대부분의 작은 컴파일러는 이를 아예 건너뛴다. Koka는 지원한다.
• 보간 문자열: "hello ${name}" 같은 문법은 ML 계열의 표준은 아니지만, 일부 새 언어가 추가한다.

Parsing

파싱은 평평한 토큰 스트림을 트리로 변환한다. 표면 문법은 구체 구문 트리(CST)로 파싱되거나, 곧바로 추상 구문 트리(AST)로 변환된다. ML 계열 언어는 문법이 잘 정리되어 있고 거의 LL(1)이다.

그 다음 단계들은 모두 이 타입을 변환한다. ML 계열 언어에서 AST는 보통 이렇게 생겼다:

type expr =
  | Lit of literal                    (* 42, 3.14, "hello", true *)
  | Var of name                       (* x *)
  | App of expr * expr                (* f x *)
  | Lam of name * expr                (* fun x -> e *)  (or \x -> e)
  | Let of name * expr * expr         (* let x = e1 in e2 *)
  | LetRec of name * expr * expr      (* let rec f = e1 in e2 *)
  | If of expr * expr * expr          (* if c then t else f *)
  | Tuple of expr list                (* (a, b, c) *)
  | Match of expr * branch list       (* match e with p1 -> e1 | ... *)
  | Ann of expr * type                (* (e : t) *)

Name Resolution & Desugaring

타입 추론 전에, 표면 AST는 단순화된다:

1. 알파-리네이밍: 섀도잉을 제거하기 위해 모든 바인더에 유일한 식별자를 부여한다. MinCaml의 Rust 포트는 타입 체크 중에 이를 수행한다. 대부분은 파싱 중 또는 별도 패스로 수행한다.
2. 결합성/우선순위(fixity) 해석: 중위 연산자들을 선언된 우선순위와 결합성에 맞게 재결합한다. HaMLet은 이를 별도 패스로 수행한다. 많은 작은 컴파일러는 연산자 우선순위를 파서에 하드코딩한다.
3. 디슈가링: 표면 구문을 코어 구문으로 내린다: * where 절 → let * 패턴 매칭의 가드 → 중첩 if * do 표기(모나딕) → >>= 체인 * 리스트 컴프리헨션 → concatMap * 연산자 섹션 → 람다: (+ 1)는 fun x -> x + 1 * 레코드 문법 → 위치 기반 생성자 + 접근자 함수 * 타입 클래스 인스턴스 → 딕셔너리 전달(엘라보레이션)

Type Inference

이는 ML 계열 언어의 심장이다. “표준” 알고리즘은 Hindley-Milner(HM) 타입 추론이며, 특히 Algorithm W 또는 Algorithm J다.

핵심 구성요소:

1. 타입 표현: 타입은 타입 변수, 타입 생성자, 함수 화살표로 구성된 항(term)이다: type ty = TVar of tvar | TCon of string | TArr of ty * ty | TTuple of ty list
2. 유니피케이션: 두 타입이 주어졌을 때, 둘을 같게 만드는 가장 일반적인 치환을 찾는다. occurs-check를 포함한, 타입 변수에 대한 유니온-파인드 구조로 구현된다.
3. 일반화: let 경계에서, 타입 안의 자유 타입 변수를 전칭 양화하여 다형적 타입 스킴을 만든다: ∀α. α → α.
4. 인스턴스화: 다형적 이름이 사용될 때, 그 스킴을 새로운 타입 변수들로 인스턴스화한다.

-- Given:
let id = fun x -> x in (id 1, id true)

-- Type inference trace:
-- 1. id : α → α                (infer: x has fresh type α, body is x)
-- 2. generalize: id : ∀α. α → α    (α is free at let boundary)
-- 3. id 1:  instantiate α=β, unify β→β with int→γ, get int
-- 4. id true: instantiate α=δ, unify δ→δ with bool→ε, get bool
-- 5. result: (int, bool)

하지만 화려한 타입 시스템 기능은 공짜가 아니다:

다른 전략들:

• 다형성: 단형 타입 추론만(전칭 ∀ 양화 없음). 모든 타입이 완전히 결정된다. 이는 일반화와 인스턴스화를 완전히 제거해 타입 체커를 ~100 LOC로 줄인다. id x = x 같은 함수는 각 사용 지점에서 구체 타입을 갖게 된다.
• 엘라보레이션: 현대 타입 체커는 점점 더 엘라보레이션(표면 구문을 완전히 명시적인 코어로 번역)과 유니피케이션(타입 제약 해결)을 분리한다. Elaboration Zoo는 이를 깔끔하게 보여준다: 각 단계가 200–800 LOC의 단일 Haskell 파일이며, 기능을 점진적으로 추가한다.
• 딕셔너리 전달을 통한 타입 클래스 디슈가링: Haskell 스타일 타입 클래스는 클래스 제약을 명시적인 딕셔너리 인자로 번역해 구현한다. sort :: Ord a => [a] -> [a]는 sort :: OrdDict a -> [a] -> [a]가 된다. Ben Lynn의 컴파일러와 MicroHs는 둘 다 이 접근을 사용한다.

Pattern Match Compilation

타입이 추론되면, 패턴 매칭을 효율적인 결정 트리 또는 케이스 트리로 컴파일할 수 있다.

핵심 단계:

1. 완전성 검사: 매치가 모든 경우를 커버하지 않으면 경고/에러.
2. 중복성 검사: 도달 불가능한 패턴이면 경고.
3. 가드 컴파일: 가드는 “백트래킹” 의무를 추가한다.
4. 중첩 패턴 평탄화: (Cons (x, Cons (y, Nil))) → 테스트들의 시퀀스.

정전(定典) 같은 참고문헌은 Compiling Pattern Matching to Good Decision Trees다. Luc Maranget의 알고리즘은 테스트 수 관점에서 증명 가능한 최적의 결정 트리를 만든다. OCaml과 Rust가 이 접근을 사용한다.

Normalization

-- Before (nested expression):
f (g x) (h y)

-- After (A-normal form):
let a = g x in
let b = h y in
f a b

모든 중간 값이 이름을 갖는다. 모든 함수 인자는 사소한(trivial) 형태가 된다. 평가 순서는 이제 let 체인에서 명시적이다.

정규화 전략:

Optimization

프로그램이 정규형에 있으면, 최적화 패스가 이를 단순화할 수 있다. 작은 컴파일러에서는 최적화를 최소로 유지한다 -- 목표는 GCC와 경쟁하는 것이 아니라, 민망하지 않을 정도로만 느리지 않게 하는 것이다.

MinCaml의 최적화 패스(총 ~300 LOC):

이 여섯 패스는 작은 컴파일러에서 최적화 가치의 80%+를 커버한다. 고정점에 도달할 때까지 반복 적용된다(보통 2–3회 반복).

기본을 넘어:

Closure Conversion

-- Before:
let f = \ x -> x + y

-- After:
let f = 
  { fun = \ env x -> x + env.y
  , env = { y = y } 
  }

최적화된 IR에는 여전히 자유 변수를 가진 함수들이 있다. 클로저 변환은 모든 함수를 “닫힌(closed)” 형태로 만든다 -- 하드웨어는 어휘적 스코프를 이해하지 못하기 때문이다. 모든 함수는 (코드 포인터, 환경 레코드) 쌍이 된다. 환경은 정의 지점에서 함수의 자유 변수를 캡처한다.

Code Generation

코드 생성은 타깃 선택에 의해 완전히 결정된다:

Register Allocation

프로그램은 변수들을 임의로 많이 사용하지만, CPU 레지스터 수는 고정되어 있다. 레지스터 할당은 어떤 변수가 레지스터에 살고, 어떤 것이 메모리로 스필되는지 결정한다.

네이티브 어셈블리를 타깃으로 한다면 이를 직접 구현한다. C/LLVM/Cranelift 등을 타깃으로 하면 백엔드가 이를 처리한다.

Runtime System

최소 구성은 다음을 포함한다:

Lil' fun langs는 자주 할당한다 -- 모든 클로저, 모든 cons 셀, 모든 부분 적용. 회수가 없으면 금방 메모리가 바닥난다. 가비지가 쌓이지 않게 해야 한다:

언어에 대수적 이펙트(Eff, Frank, Koka, Ante)가 있다면, 런타임은 제한된 연속(delimited continuations) 또는 CPS로 변환된 호출 규약을 지원해야 한다. 이펙트 핸들러는 본질적으로 연속을 캡처하기 위해 두 번째 스택 또는 세그먼트 스택이 필요하다. Koka는 이를 evidence-passing으로 처리하고; Eff와 Frank는 인터프리팅을 사용한다.