쿼리 기반(증분) 컴파일러가 왜 매력적이면서도 언어의 의존성 구조에 의해 근본적으로 한계를 갖는지, 그리고 때로는 더 직접적인 설계가 더 단순하고 빠를 수 있는 이유를 살펴본다.
Feb 25, 2026
요즘 쿼리 기반 컴파일러가 대세인 만큼, 그 물살 속에 숨어 있는 위험한 여울을 몇 군데 표시해 두는 것도 적절해 보인다.
쿼리 기반 컴파일러는, 맞다, 컴파일에 증분 계산(incremental computations)이라는 아이디어를 적용한 꽤 직관적인 방식이다. 컴파일러는 그저 단순한 텍스트 변환 프로그램이고, 많은 함수들로 구현되어 있다. 특정 입력 소스 코드에 대해 컴파일러가 한 번 실행 되는 모습을 함수 호출 그래프로 시각화할 수도 있다:
여기서 개략적으로, 네모는 파일 텍스트나 컴파일러의 커맨드라인 인자 같은 입력을 나타낸다. g는 중간 단계 함수(예: 타입 체크)로, 서로 다른 인자를 받아 두 번 호출된다. f와 h는 최상위 함수들(실행 파일을 컴파일하거나, LSP를 위한 자동완성 목록을 계산하는 것)이다.
이 그림을 보면 컴파일러를 “증분화”하는 방법은 명백하다. 입력이 바뀌면, 바뀐 입력에서 루트 “쿼리”로 향하는 경로 위의 결과들만 다시 계산하면 된다:
조금 더 생각해 보면 “early cutoff(조기 차단)” 최적화도 도출할 수 있다:
함수의 입력은 바뀌었지만 결과는 바뀌지 않았다면(예: 공백 변경은 함수 타입에 영향을 주지 않는 경우) 변경 전파를 더 일찍 멈출 수 있다.
그리고… 기본적으로 이게 전부다. 이 방식의 아름다움은, 은빛 탄환(silver bullet) 같은 기운이 있다는 점이다. 어떤 계산에도 거의 생각 없이 적용할 수 있고, 메타프로그래밍을 살짝 곁들이면 컴파일러 코드 자체도 크게 바꾸지 않아도 된다.
여기서 읽을 만한 정전(canonical) 논문은 Build Systems à la Carte다. 빌드 시스템에서 쿼리는 입력과 출력이 파일인 불투명한 프로세스다. 쿼리 기반 컴파일러에서 쿼리는 그냥 함수다.
우리가 애초에 이걸 원하는 이유는 증분 컴파일(incremental compilation)이다. 특히 IDE 맥락에서 컴파일러는 아주 작은 편집들의 스트림에 반응해야 하고, 시간 예산은 대략 100ms 정도다. 여기서 빅오(Big-O) 사고가 유용하다. 변경에 반응하는 시간은 코드베이스 전체 크기가 아니라 변경의 크기에 비례해야 한다. O(1) 변경이 O(N) 코드베이스에서 O(1) 업데이트로 이어져야 한다.
비슷한 빅오 관점은 이 방식의 본질적 한계도 보여 준다. 업데이트 작업량은 결과의 변경량보다 더 작을 수 없다.
예를 하나 들어 보자. “컴파일러”가 문자열을 대문자로 바꾸는 작업을 한다고 하자:
compile("hello world") == "HELLO WORLD"
이는 증분화하기 쉽다. 입력에서 몇 글자만 바꾸면 출력에서도 몇 글자만 바뀌기 때문이다:
compile("hallo world") == "HALLO WORLD"
하지만 이제 “컴파일러”가 해시나 암호화 함수라면 어떨까?
compile("hello world") == "a948904f2f0"
compile("hallo world") == "a7336983eca"
이 경우 유의미하게 증분화하는 것은 증명 가능할 정도로 불가능하다. 암호화도 함수 호출 그래프로 구현할 수는 있고, 일반적인 증분 레시피를 적용할 수도 있다. 다만 그렇게 해 봐야 별로 빠르지 않을 것이다.
그 이유는 눈사태(avalanche) 성질 때문이다. 좋은 암호화에서는 입력의 어떤 비트가 바뀌어도 출력 비트의 대략 절반이 뒤집혀야 한다. 그러면 출력 자체를 바꾸는 작업만으로도(무엇을 바꿔야 하는지 계산하는 비용은 완전히 무시하더라도) O(1)이 아니라 O(N)이 된다.
쿼리 기반 컴파일러의 효과는 소스 언어의 의존성 구조에 의해 제한된다.
여기서 특히 골치 아픈 효과는, 비록 “잠재적” 눈사태만 있어도 문제가 된다는 점이다. 즉 어떤 종류의 변경이 가능성으로는 출력의 큰 부분에 영향을 줄 수 있지만, 실제로는 대개 그렇지 않더라도, 증분 엔진은 의존성이 없음을 확인하기 위해 CPU 시간이나 메모리를 써야 할 가능성이 크다.
내 글
Three Architectures For Responsive IDE
에서는 쿼리 기반 컴파일을 세 번째, 최후의 선택지로 소개했다. 나는 여전히 그게 대체로 맞다고 생각한다. 언어 설계자 입장에서, 내면의 Grug에 귀 기울여 쿼리의 필요성을 컴파일 파이프라인 아래쪽으로 최대한 밀어 내려는 게 가치 있다고 본다. 더 직접적인 접근을 고수하는 편이 낫다. 쿼리를 하지 않는 것이 더 단순하고, 더 빠르며, 더 빠르게 만들기도 더 쉽다(쿼리 기반 컴파일러 프로파일링은 장애물 달리기의 특수 장르다).
Zig와 Rust는 좋은 비교를 제공한다. Zig에서는 각 파일을 완전히 독립적으로 파싱할 수 있으므로, 컴파일은 모든 파일을 독립적으로(그리고 병렬로) 파싱하는 것부터 시작한다. Zig에서는 모든 이름을 명시적으로 선언해야 하기 때문에(use * 같은 것이 없기 때문에), 이름 해석(name resolution)도 쿼리 없이 파일 단위로 실행할 수 있다. Zig는 한 걸음 더 나아가, 타입이 없는 AST를 IR로 직접 변환하면서 수많은 에러를 함께 만들어 낸다(예: “var는 가변일 필요가 없다”). 자세한 내용은 Zig AstGen: AST => ZIR를 참고하라. 컴파일러가 추적되는 쿼리(tracked queries)로 넘어갈 즈음에는, 다뤄야 하는 데이터는 이미 원시 소스 코드에서 꽤 멀리 떨어져 있다. 하지만 그건 Zig 언어 가 이런 것을 가능하게 하도록 신중하게 설계되었기 때문이다.
반대로 Rust에서는 파일을 “그냥” 파싱하기가 어렵다. Rust 매크로는 새로운 소스 코드를 생성하므로, 모든 매크로가 확장되기 전에는 파싱을 끝낼 수 없다. 매크로 확장에는 이름 해석이 필요하고, Rust에서는 이름 해석이 파일 단위가 아니라 크레이트(crate) 전체 단위로 이뤄진다. a.rs에서 무언가를 타이핑하는 것이 b.rs의 파싱 결과를 바꿀 수 있다는 건 언어의 근본적 성질이며, 이는 프런트엔드의 맨 처음부터 세밀한 의존성 추적과 무효화(invalidation)를 강제한다.
비슷하게, 트레이트 시스템의 성질상 특정 메서드 호출에 관련된 impl 블록은 거의 어디에나 있을 수 있다. 각 트레이트 메서드 호출은 구현을 제공하는 impl 블록에 의존하게 되지만, 그뿐 아니라 다른 모든 파일에서 충돌하는 impl이 존재하지 않는다는 사실 에도 의존하게 된다!
쿼리를 무비판적으로 적용하면 활용하기 어려워지는 또 다른 트릭은 제자리(in-place) 업데이트다. Kotlin처럼 패키지 선언과 완전 수식 이름(fully qualified names)을 가진 언어를 생각해 보자:
package org.example
fun printMessage() { /*...*/ }
class Message { /*...*/ }
이 언어의 컴파일러는 아마 모든 공개 선언의 맵을 유지하고 싶을 것이다. 키는 완전 수식 이름이고, 값은 선언 자체다. 이 맵을 계산하는 문제를 쿼리 관점으로 접근한다면, 파일 단위 기본 쿼리가 파일의 선언 맵을 반환하고, 그 위에 디렉터리 단위 재귀 쿼리를 두는 식이 될 수 있다. 그리고 맵의 구조적 공유(structural sharing)를 통해 한 파일만 바뀌면 대부분의 엔트리를 실제로 복사하지 않고 “척추(spine)”만 업데이트하도록 할 수도 있다.
하지만 이런 구조를 변경에 반응하도록 만드는 더 직접적인 방법이 있다. “쿼리”는 두 개만 필요하다: 파일별 쿼리와 전역 쿼리. 파일이 바뀌면, 그 파일에 대한 맵의 이전 버전을 보고, 추가되거나 제거된 선언의 diff를 계산한 뒤, 이 diff를 전역 맵에 적용하면 된다.
Zig는 링킹을 증분화할 때도 비슷한 접근을 사용할 계획이다. 대부분 변하지 않은 머신 코드 조각을 다시 붙여 새로운 바이너리를 만드는 대신, 이전 바이너리를 제자리에서 패치하는 것이 아이디어다.
이 글이 마음에 들었다면, 내가 지난 몇 년 동안 쓴 인접한 글들에도 관심이 있을지 모른다. 중요도 대략 순서대로 나열하면: