1장: 소개
동기
제가 2014년에 이 글을 쓰기 시작한 것은 제게 필요한 입문서가 존재하지 않았기 때문입니다. 함수형 컴파일러에 관해 제가 찾은 자료는 대개 난해하고 다가가기 어려웠으며, 업계에서 소프트웨어를 만드는 사람들보다는 학계 독자를 위해 쓰인 것이었습니다. 저는 누군가가 동작하는 컴파일러를 함께 짚어 가며 필요한 시점마다 그 아이디어를 설명해 주기를 바랐습니다.
저는 제 지식의 빈틈을 천천히 채워 나갔지만, 다른 사람들까지 같은 느린 길을 걸어야 할 이유는 없었습니다. “보고 싶은 변화가 직접 되어라”라는 정신으로, 저는 제가 찾아 헤매던 입문서를 직접 쓰기로 했습니다. 이 책은 다음 사람을 위해 사다리를 내려 주는 제 나름의 방법입니다.
우리는 타입 추론, 대수적 데이터, 명목적 레코드, 타입 클래스를 갖춘 엄격한 함수형 언어인 Fun을 만들 것입니다. 그리고 Fun을 만드는 일은 분명 재미(fun)있을 것입니다! 우리는 이를 Rust로 작성하고 LLVM을 거쳐 네이티브 코드까지 끝까지 가져갈 것입니다. 그 과정에서 코드 생성기를 갖추기 전에도 프로그램을 실행할 수 있게 해 주는 인터프리터를 만들고, 진행하면서 우리의 변환을 검증할 것입니다. Haskell Report는 구문과 타입 체계에 대한 출발점을 제공합니다 (Simon Marlow 2010).
각 변환이 작은 입력 언어와 작은 출력 언어를 가지면 컴파일러를 이해하기가 더 쉬워집니다. 앞쪽 장들에서는 파싱, 평가, 추론을 각각 따로 살펴봅니다. 7장부터는 각 크레이트가 같은 컴파일러의 완전한 스냅숏입니다. 각 장은 해당 diff와 함께 읽으십시오. 더 단순한 구현을 다시 살펴보고 싶을 때는 언제든 이전 스냅숏을 실행하십시오.
도구 설정
Apple Silicon macOS나 x86-64 또는 AArch64 기반 Linux를 사용하십시오. 각 장을 빌드하려면 Rust와 Cargo가, 저장소 레시피를 실행하려면 just가, 런타임에는 C 컴파일러와 Boehm GC가, 네이티브 컴파일과 JIT에는 LLVM 22가 필요합니다. 책에는 just bootstrap으로 설치하는 별도의 툴체인이 있습니다.
macOS
Apple의 커맨드라인 개발 도구를 설치하고, brew를 아직 사용할 수 없다면 Homebrew 설치 안내를 따르십시오. 그런 다음 시스템 의존성을 설치하십시오:
xcode-select --install
brew install git python just llvm@22 bdw-gc pkg-config
export LLVM_SYS_221_PREFIX="$(brew --prefix llvm@22)"
export GC_LIB_DIR="$(brew --prefix bdw-gc)/lib"
빌드를 실행하기 전에 커맨드라인 도구 설치 프로그램이 끝날 때까지 기다리십시오. 이후의 터미널 세션에서도 두 export를 사용하려면 셸 설정에 넣어 두십시오. llvm@22는 의도적으로 지정한 것입니다. 버전을 지정하지 않은 LLVM 패키지는 우리의 Rust 바인딩이 사용하는 것과 다른 ABI를 선택할 수 있습니다.
Ubuntu
이 명령은 이 판을 쓸 당시의 최신 LTS인 Ubuntu 26.04 LTS를 대상으로 합니다. 지원 대상인 Ubuntu 24.04 CI 환경에서도 동작합니다. 공통 도구를 설치한 다음, 공식 LLVM 패키지 설치 프로그램을 사용해 버전 22를 명시적으로 선택하십시오:
sudo apt update
sudo apt install -y build-essential git curl wget ca-certificates \
gnupg lsb-release software-properties-common python3 pkg-config \
libgc-dev libssl-dev just
curl -fsSLo /tmp/wyah-llvm.sh https://apt.llvm.org/llvm.sh
sudo bash /tmp/wyah-llvm.sh 22
sudo apt install -y llvm-22-dev libpolly-22-dev
export LLVM_SYS_221_PREFIX=/usr/lib/llvm-22
버전이 붙은 LLVM 접두 경로는 이후 빌드를 위해 셸 설정에 넣어 두십시오. 배포판의 기본 Rust 패키지는 이 책이 고정한 컴파일러 버전과 다를 수 있으므로, 다음으로 rustup을 통해 Rust를 설치하십시오.
Rust와 저장소
공식 Rust 설치 안내서를 따르십시오. 두 플랫폼 모두에서 rustup 설치 명령은 다음과 같습니다:
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
. "$HOME/.cargo/env"
git clone https://github.com/sdiehl/write-you-a-haskell.git
cd write-you-a-haskell
rustup show
rustc --version
cargo --version
이 체크아웃 안에서는 rust-toolchain.toml이 Clippy와 rustfmt를 포함한 Rust 1.99.0을 선택합니다. Rustup은 필요할 때 선택된 툴체인을 설치합니다. rustup 책에서 디렉터리 툴체인이 어떻게 동작하는지 설명합니다. just는 명령 실행기이며, 또 다른 빌드 시스템이 아닙니다. just 설치 안내서에는 위의 시스템 패키지 대신 쓸 수 있는 방법들이 나와 있습니다.
이제 작은 장 하나와 전체 워크스페이스를 빌드해 봅시다:
cargo run -p ch02_calc -- repl
just build
cargo fmt --all -- --check
cargo clippy --workspace --all-targets -- -D warnings
HTML과 PDF를 만들려면 버전이 고정된 책 도구들을 로컬에 설치하십시오:
just bootstrap
just book
just pdf
부트스트랩은 mdBook과 그 전처리기들, Pandoc, Typst를 .tools 아래에 설치합니다. just 레시피는 .tools/bin을 PATH에 추가합니다. 글꼴은 이미 저장소에 포함되어 있습니다. book/build/html/index.html 또는 build/write-you-a-haskell.pdf를 여십시오. 공개된 사본은 https://sdiehl.github.io/write-you-a-haskell/의 HTML과 그 옆의 https://sdiehl.github.io/write-you-a-haskell/write-you-a-haskell.pdf에 있는 PDF이며, 이 PDF는 저장소의 최신 GitHub 릴리스에 첨부된 파일이기도 합니다. 전체 컴파일러 테스트는 cargo test --workspace로 실행하며, 깊은 재귀와 메모리 할당에 대한 회귀 테스트를 포함합니다.
Nix를 이용하는 방법
Nix를 설치했다면, flake가 Apple Silicon macOS와 두 Linux 아키텍처에서 쓸 수 있도록 고정된 Rust 툴체인, LLVM 22, Boehm, C 컴파일러, 개발 도구를 제공합니다:
nix --extra-experimental-features 'nix-command flakes' develop
just build
just bootstrap
just pdf
잠금 파일이 패키지 입력을 고정합니다. 이 셸은 LLVM과 GC 경로를 설정하므로, 위의 플랫폼별 패키지 설치 단계를 대신합니다. 그래도 부트스트랩은 여전히 책에 필요한 정확한 버전의 도구들을 .tools에 설치합니다.
왜 Rust인가
제가 2010년대 중반에 이 책을 처음 썼을 때, Haskell은 컴파일러를 설명하기에 매력적인 언어였습니다. 대수적 데이터 타입, 패턴 매칭, 간결한 구문 덕분에 변환 과정이 마치 그 수학적 정의처럼 읽혔습니다. 하지만 그런 정의에서 완전한 네이티브 컴파일러까지 나아가려면 당시에도 이미 지원이 빈약한 라이브러리에 기대야 했습니다. 제 경험상 그 유지보수 문제는 시간이 지날수록 더 나빠졌습니다.
저는 여전히 Haskell의 표면 언어를 좋아합니다. 하지만 이제는 이 책의 컴파일러를 만드는 데 Haskell이 실용적으로 좋은 선택이라고 생각하지 않습니다. 컴파일러에는 우아한 트리 변환뿐 아니라 꾸준히 유지보수되는 바인딩, 진단 기능, 테스트 도구, 패키징, 예측 가능한 런타임도 필요합니다. 암묵적인 지연 평가는 제가 작성하는 프로그램과 그 프로그램의 할당 및 평가 동작 사이에 거리를 더 벌려 놓기도 합니다. 컴파일러가 큰 입력을 안정적으로 처리해야 할 때 이러한 비용은 중요해집니다.
제가 이번 판에서 Rust를 선택한 이유는 훨씬 넓은 생태계와 프로덕션 도구에 대한 꾸준한 투자 때문입니다. Rust는 중간 언어를 위한 열거형과 패턴 매칭, 그 저장 공간을 위한 명시적 소유권, 그리고 LLVM과 네이티브 런타임에 대한 직접적인 접근을 제공합니다. Cargo 덕분에 각 장의 스냅숏을 함께 빌드하고 테스트하기가 쉽습니다. 저는 독자 여러분이 마지막 장을 마친 뒤에도 계속 쓸 수 있는 툴체인으로 컴파일을 배우는 데 시간을 쓰기를 바랍니다.
이 프로젝트에서 Rust는 표현력 있는 구현 코드와 실용적인 엔지니어링 사이에서 가장 좋은 균형을 이룹니다. 언젠가는 OCaml 판이 나올지도 모릅니다. 지금으로서는 Haskell은 여전히 공부할 가치가 있는 언어이고, Rust는 제가 무언가를 만들 때 쓰고 싶은 언어입니다. 원래의 Haskell 판은 저장소에 haskell-edition 태그로 보존되어 있습니다.
왜 지연 평가가 아닌가?
Haskell의 가장 강력한 교훈들은 모든 평범한 계산을 잠재적으로 지연되게 만들지 않아도 살아남습니다. 대수적 데이터, 패턴 매칭, 주요 타입(principal type), 순수성, 타입 클래스는 모두 유지할 가치가 있습니다. Fun은 이것들을 값에 의한 호출(call-by-value)과 함께 묶습니다. 인자는 호출 전에, 생성자 필드는 생성 전에, 평범한 바인딩은 그 본문 전에 계산됩니다. 이로써 독자는 작업이 언제 일어나고 저장 공간이 어디에 필요한지를 직접적으로 파악할 수 있습니다.
저는 암묵적 지연 평가가 새로운 언어에 생산적인 기본값이라고 보지 않습니다. 보류된 식은 그 원천 바인딩이 끝난 것처럼 보인 뒤에도 오랫동안 자신의 환경을 붙잡고 있을 수 있습니다. 그것을 강제하면 작업과 실패가 모두 그 원인에서 멀리 떨어진 곳으로 옮겨질 수 있습니다. 공유는 반복되는 작업을 피할 수 있지만, 그 자체의 할당 및 갱신 프로토콜을 도입합니다. 엄격성 분석은 많은 경우에 효율적인 실행을 되찾아 줄 수 있지만, 이는 처음부터 명시적으로 만들 수 있었던 비용 모델을 재구성하기 위한 상당한 장치입니다. 5장에서는 이 트레이드오프를 실행 가능한 형태로 살펴봅니다.
그래도 지연된 계산은 여전히 유용합니다. 이를 선택적으로 사용하게 만드는 데 제가 선호하는 기반은 call-by-push-value(CBPV)입니다. 이 방식은 값과 계산을 분리합니다. 계산은 값을 만들어 낼 수 있고, 값은 보류된 계산을 담을 수 있습니다. 명시적인 썽크(thunk) 연산과 강제(force) 연산이 그 경계를 표시합니다. 값에 의한 호출과 이름에 의한 호출(call-by-name)은 모두 이 더 작은 연산들을 통해 표현할 수 있습니다(Levy 2001). 따라서 프로그래머나 컴파일러는 지연을 모든 곳에서 물려받는 대신 지연이 들어가야 할 곳을 지정할 수 있습니다.
CBPV 자체는 중단된 계산을 메모이즈하지 않습니다. 필요에 의한 호출(call-by-need)에는 공유와 함께 결과를 기억하는 갱신이 추가로 필요합니다. 평범한 썽크를 두 번 강제하면 그 계산이 두 번 실행될 수 있습니다. 바로 그 차이 때문에 저는 지연 평가를 탐구할 때 이 토대를 선호합니다. Fun 자체는 여전히 엄격한 값에 의한 호출(call-by-value) 언어입니다. Fun은 CBPV도, 지연 값도 구현하지 않습니다. 지연을 명시적으로 다루는 일은 이 책의 컴파일러를 넘어서는, 이후 언어를 위한 방향입니다.
장별 로드맵
아래 표는 책 전체를 설명합니다. 링크된 제목을 누르면 각 장이 열립니다. 2–6장은 각각 독립된 언어입니다. 7–24장은 Fun의 연속된 스냅숏입니다. 각 행에는 선행 지식 목록 대신 여러분이 만들 부분이 적혀 있습니다.
1부: 기초
| 번호 | 주제 | 만들게 될 것 |
|---|---|---|
| 1 | 소개 | 워크스페이스, 테스트 러너, 장별 도구, HTML/PDF 책 파이프라인. |
| 2 | 파싱 | logos, LALRPOP, 비교용 Pratt 파서, 진단, REPL을 갖춘 산술 언어. |
| 3 | 람다 대수 | 치환, 드 브루인 인덱스, 정규 순서 축약, 그리고 엄격한 클로저. |
| 4 | 단순 타입 람다 대수 | 타입이 명시된 함수와 평가 전에 실행되는 타입 검사기. |
| 5 | 평가 | 재귀 함수, 상수 스택 CEK 기계, 이름에 의한 호출(call-by-name) 비교. |
| 6 | 힌들리–밀너 추론 | 알고리즘 W와 레벨 기반 유니온-파인드를 모두 사용한 다형적 let 추론입니다. |
2부: 프런트엔드
| 번호 | 주제 | 만들게 될 것 |
|---|---|---|
| 7 | Fun의 설계 | 소스 스팬, 진단, 패스 세션, Core, CLI를 갖춘 첫 번째 Fun 컴파일러입니다. |
| 8 | 레이아웃과 확장된 파서 | 오프사이드 레이아웃, 주석을 보존하는 포매팅, 시그니처, 결합성 선언(fixity), 섹션입니다. |
| 9 | 리네이머 | 고유 이름, 렉시컬 스코프, 의존성 컴포넌트, 상호 재귀입니다. |
| 10 | 타입이 있는 Core와 Core 린트 | System F 정교화(elaboration)와 컴파일러의 실수를 잡아내는 독립적인 Core 린트입니다. |
| 11 | 데이터 타입과 패턴 매칭 | 대수적 데이터, 리스트와 튜플, 중첩 패턴, 등식, 가드입니다. |
| 12 | 레코드 | 생성, 갱신, 패턴, 해석된 점 프로젝션을 갖춘 명목적 레코드입니다. |
| 13 | 카인드와 타입 생성자 | 고차 카인드 생성자, 추론된 카인드, 검사되는 타입 동의어입니다. |
| 14 | 타입 클래스 | 제약, 인스턴스, 슈퍼클래스, 기본값, 사전 전달, Double입니다. |
| 15 | 모나드, do 표기법, IO | 고차 카인드 제어 클래스, do 표기법, 불투명한 IO, 효과가 있는 프로그램. |
| 16 | 패턴 매칭 컴파일 | 결정 트리와 조인 포인트, 그리고 완전성 및 중복 경고. |
| 17 | Prelude와 파생 | 소스로 작성한 전체 Prelude와 자동 생성되는 Eq, Ord, Show 인스턴스. |
3부: 백엔드
| 번호 | 주제 | 만들게 될 것 |
|---|---|---|
| 18 | A-정규형과 조인 포인트 | 타입 소거, ANF, 작은 단순화기, 반복적으로 실행하는 오라클. |
| 19 | 클로저 변환 | 명시적 환경, 끌어올려진 함수, 부분 적용, 그리고 Flat IR 오라클. |
| 20 | 데이터 표현과 런타임 | 태그가 붙은 워드, 힙 레이아웃, eval/apply, 공유 프리미티브, 그리고 Boehm 기반 런타임. |
| 21 | LLVM 코드 생성 | 네이티브 오브젝트 생성, 링킹, 꼬리 호출, 인터프리터와 대조하는 테스트. |
| 22 | JIT와 REPL | LLVM 실행과, 타입·카인드·컴파일러 패스를 살펴볼 수 있는 상태 유지형 REPL. |
| 23 | 최적화 | 작업 보존, 도달 가능한 전역, 네이티브 수치 중간값. |
| 24 | 정밀 GC(선택) | 활성 루트 추적, 섀도 스택, 그리고 스트레스 테스트를 거친 복사 컬렉터를 다룹니다. |
| 25 | 향후 과제 | 지연 평가, 모듈, 더 풍부한 타입, 최적화, 디버깅 확장을 위한 안내서입니다. |
부록에는 문법, 타입 규칙, 중간 표현, 런타임 ABI, 진단 색인을 모았습니다. 책의 마지막은 참고 문헌으로 마무리합니다.
우리가 만들어 갈 방식
우리는 계산기로 시작합니다. 계산기는 충분히 작아서, 우리가 입력한 텍스트에서부터 그 식이 만들어 내는 답에 이르기까지 식 하나를 끝까지 따라가 볼 수 있습니다. 그다음에는 함수, 평가, 타입을 각각 따로 탐구하기 위해 작은 언어 몇 개를 만듭니다. 각 언어에는 직접 실행하고 수정해 볼 수 있는 완전한 Rust 구현이 있습니다. 컴파일러의 한 부분을 실험해 보기 위해 컴파일러 전체를 먼저 이해할 필요는 없습니다.
7장에서 이 아이디어들이 Fun으로 합쳐집니다. 그 뒤로 각 장은 이전 장의 컴파일러에서 출발해 한 조각씩 더해 갑니다. 레코드는 언어를 확장하고, 타입 클래스는 여러 타입에 걸쳐 연산을 공유하는 방법을 도입하며, 이후의 장들에서는 컴파일러가 네이티브 코드를 생성하도록 가르칩니다. 모든 장에는 저마다의 크레이트가 있으므로, 지금 공부하는 버전 옆에 이전 버전을 열어 두고 함께 볼 수 있습니다.
완성된 코드뿐 아니라 변경 사항도 읽어 보십시오. 각 장은 새로 추가되거나 변경된 소스 파일을 중요한 것부터 나열합니다. 두 스냅숏을 비교해 보면 어떤 기능이 실제로 컴파일러에 무엇을 요구하는지 알 수 있습니다. 새로운 구문 노드, 타입 규칙, 그리고 더 단순한 연산으로의 변환이 필요할 수도 있습니다. 이 책은 그 소스 파일들에서 코드를 가져와 싣기 때문에, 여러분이 읽는 구현이 곧 여러분이 실행하는 구현입니다. 테스트도 다음 장으로 이어지므로, 기능을 추가해도 이미 동작하던 부분이 망가지지 않았는지 확인하는 데 도움이 됩니다.
이론은 그것이 해결을 돕는 문제와 함께 등장합니다. 우리는 작은 예제를 시도해 보고, 그 예제가 제기하는 질문을 찾은 다음, 답을 정확하게 표현할 수 있을 만큼의 표기법을 도입할 것입니다. 코드와 예제를 먼저 따라가 본 뒤, 규칙이 실제로 작동하는 모습을 보고 나서 다시 그 규칙으로 돌아와도 됩니다. 타입 이론 강의를 미리 들었다고 가정하지 않습니다. Rust의 열거형, 패턴 매칭, 빌림, Cargo에 익숙하다면 구현을 따라가는 데 도움이 될 것입니다.
이론
컴파일러는 컴퓨터가 프로그램을 실행할 수 있게 되기까지 프로그램을 여러 번 다시 씁니다. 핵심 과제는 프로그램이 하는 일은 그대로 유지하면서 프로그램이 쓰인 방식을 바꾸는 것입니다. 여러분의 프로그램이 42를 출력한다면, 우리가 생성하는 기계어 코드도 42를 출력해야 합니다. 프로그램이 인사하기 전에 이름을 묻는다면, 컴파일은 그 동작들의 순서를 그대로 지켜야 합니다.
우리는 이 단계들을 하나씩 쌓아 올릴 것입니다. 먼저 소스 텍스트가 어떻게 짜여 있는지 알아냅니다. 1 + 2 * 3에서 곱셈은 덧셈 안에 속합니다. 그다음에는 연산들이 말이 되는지 검사하므로, 숫자를 함수에 더하는 일은 프로그램이 실행되기 전에 잡힙니다. 이후의 장에서는 프로그램을 기계어 코드로 바꾸기 더 쉬운 단순한 형태로 변환합니다.
변환을 제대로 했는지 어떻게 알 수 있을까요? 한 가지 유용한 요령은 각 형태마다 작은 인터프리터를 작성하고 같은 예제들을 그 인터프리터들에 돌려 보는 것입니다. 서로 다른 답이 나온다면 컴파일러 버그를 찾은 것입니다. 답이 일치한다고 해서 가능한 모든 프로그램이 동작한다는 것이 입증되지는 않지만, 진행하면서 작업을 확인할 수 있는 실용적인 방법이 됩니다. 그 과정에서 우리는 타입과 평가 규칙이 테스트할 수 있는 예제를 넘어 프로그램에 대해 추론하는 데 어떻게 도움이 되는지도 배울 것입니다 (Pierce 2002).
구현
저장소는 이 책의 일부입니다. 각 장에는 실행하고, 뜯어 보고, 고쳐 볼 수 있는 크레이트가 있습니다. 어떤 변환이 실제로 무엇을 했는지 궁금하다면, 컴파일러에게 출력을 덤프하게 한 뒤 입력과 비교해 보십시오. 그런 습관이 구현을 뚫어지게 바라보며 깨달음이 오기를 바라는 것보다 더 많은 것을 알려 줄 것입니다.
우리는 또한 컴파일러가 커지는 동안에도 예제들이 계속 동작하기를 원합니다. testkit은 작은 프로그램들을 실행하고 그 출력, 오류, 종료 상태를 검사합니다. 나중에는 같은 프로그램을 여러 실행 엔진으로 실행합니다. 두 엔진의 결과가 서로 다르다면 조사할 구체적인 대상이 생긴 것입니다.
#![allow(unused)]
fn main() {
/// The chapter supplies its binary and available engines; the runner owns policy.
pub struct Config<'a> {
pub binary: &'a Path,
pub programs: &'a Path,
pub engines: &'a [Engine],
pub timeout: Duration,
}
}xtask는 장을 복사하고 물려받은 예제들을 검사하는 반복 작업을 처리합니다. 책 자체는 각 장의 소스에서 Rust 코드를 직접 포함합니다. 포함된 함수를 따라 크레이트 안으로 들어가 지금 읽고 있는 코드로 실험해 볼 수 있습니다. HTML과 PDF는 같은 장들로부터 빌드됩니다.
실행해 보기
just bootstrap으로 버전이 고정된 책 도구들을 설치한 다음, 다음을 실행하십시오:
$ cargo test --workspace
$ just book
$ just pdf
HTML은 book/build/html/에 있습니다. PDF는 build/write-you-a-haskell.pdf입니다. 컴파일러의 --dump 명령은 2장부터 시작합니다. 1장에는 덤프할 컴파일러 패스가 없습니다.
더 읽을거리
Haskell Report는 이 언어의 레퍼런스입니다 (Simon Marlow 2010). Pierce는 우리가 사용할 연산적 판단과 타입 판단을 소개합니다 (Pierce 2002). Kiselyov는 타입 일반화를 의존성 추적과 연결하며, 이는 6장을 위한 준비가 됩니다 (Kiselyov 2013). 우리의 선택을 실제 구현과 비교해 보고 싶다면, Takenobu Tani의 GHC Reading Guide(pdf / github)가 GHC 소스 트리와 그 파이프라인을 안내하는 지도 역할을 합니다.