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초. 캐시된 번역 단위 사용 시 실용적으로 충분한 성능

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