---
title: "Quadratic Micropass Type Inference — 타입 추론 에러 메시지를 인간 사고방식에 맞추는 새로운 알고리즘"
published: 2026-03-27T20:37:22.000Z
canonical: https://jeff.news/article/1325
---
# Quadratic Micropass Type Inference — 타입 추론 에러 메시지를 인간 사고방식에 맞추는 새로운 알고리즘

코드 순서가 아니라 사용자가 중요시하는 순서로 타입 추론을 수행하는 새 알고리즘 제안. 여러 마이크로패스를 우선순위 순으로 실행해서 에러 메시지가 개발자 직관에 부합하도록 함.

## 문제: 타입 추론이 만드는 혼란스러운 에러 메시지

- 타입 추론이 풍부한 언어들은 에러 메시지가 혼란스러운 경우가 많음. 컴파일러가 타입을 추론하는 과정에서 **잘못된 가정을 먼저 하고**, 그 가정에 기반한 에러를 보여주기 때문임
- 예를 들어 `fn example(x) -> Point[int]`에서 `x`를 `log(["origin: ", x])`에 넣고 `Point(x, x)`를 리턴하면, 기존 방식은 코드 순서대로 추론해서 `x`를 `string`으로 먼저 잡음. 그래서 "expected int, got string" 에러가 뜨는데 — 개발자 입장에서는 `x`가 `int`인 게 훨씬 자연스러움. 리턴 타입이 `Point[int]`니까

## 해법: 사용자가 중요하게 여기는 순서로 타입을 추론

- **코드 순서(top-to-bottom)**가 아니라, 사용자가 가장 중요하게 여길 법한 순서로 타입 통합(unification)을 수행하는 알고리즘을 제안함
- 하나의 큰 추론 패스 대신 **여러 개의 마이크로패스**로 분리:
  1. `known_applications` — 함수 파라미터 타입 추론
  2. `known_assignments` — 할당 대상 타입 추론
  3. `known_return_types` — 리턴 타입 기반 추론
  4. `known_same_as_unifications` — 같은 리스트/분기 내 타입 통합
  5. `known_record_fields` — 레코드 필드 타입 추론
  6. `resolve_records` — 필드명으로 레코드 타입 결정
  7. `less_known_functions` — 호출 패턴으로 함수 타입 추론
  8. `default_numbers` — 숫자 리터럴 기본 타입 결정
  9. `default_unknown_to_unit_or_lift` — 미추론 타입 처리
- 리스트 위쪽일수록 사용자 사고방식에 가까운 패스임. 각 패스 실행 후 **이전 패스를 다시 돌려서** 새로 알게 된 타입 정보가 전파되게 함

## 왜 "Quadratic"인가

- 각 패스 후 이전 패스를 전부 다시 돌리니까 이론상 O(n²)임. 하지만 OCaml처럼 작은 함수가 많은 언어에서는 quadratic 특성의 심각도가 줄어듦
- 벤치마크 (Intel i7 13700k @ 5.3GHz): **100 이터레이션에 7.79ms**, 50,000 이터레이션에 2.78초. 캐시된 번역 단위 사용 시 실용적으로 충분한 성능

> [!NOTE]
> 에러 생성은 추론 중이 아니라 추론 완료 후 타입 체킹 단계에서 수행됨. 각 패스는 에러를 무시하고 자기가 처리할 수 있는 타입만 건드림. 최종적으로 타입 변수 → 정적 타입 매핑을 만들어서 단순 동등 비교로 타입 체킹

- 결과: 아까 문제의 예제에서 `known_applications` 패스가 먼저 돌아가면서 리턴 타입 `Point[int]`에서 `x = int`를 추론함. 그래서 에러가 **"expected string, got int"**로 바뀜 — 개발자 직관에 훨씬 부합하는 메시지

## 핵심 포인트

- 기존 inside-out 추론 방식의 혼란스러운 에러 메시지 문제 해결
- 9개 마이크로패스를 사용자 사고방식 우선순위로 정렬하여 순차 실행
- i7 13700k에서 100 이터레이션 7.79ms 성능, 실용적으로 충분

## 인사이트

에러 메시지 품질은 컴파일러 UX의 핵심인데, 타입 추론 순서를 '인간이 생각하는 순서'로 바꾸는 접근이 참신함. Rust나 TypeScript처럼 추론이 복잡한 언어에 적용되면 DX가 크게 개선될 수 있음.