배경 주제
이 절에서는 이 가이드에 등장하는 여러 일반적인 컴파일러 용어를 다룹니다. 일반적인 정의를 제시하면서 Rust에 특화된 맥락도 함께 제공하고자 합니다.
제어 흐름 그래프란 무엇입니까?
제어 흐름 그래프(CFG)는 컴파일러에서 흔히 쓰이는 용어입니다. 순서도를 사용해 본 적이 있다면 제어 흐름 그래프의 개념이 꽤 익숙하게 느껴질 것입니다. 제어 흐름 그래프는 프로그램의 밑바탕에 있는 제어 흐름을 명확하게 드러내는 표현 방식입니다.
제어 흐름 그래프는 간선으로 연결된 기본 블록의 집합으로 구성됩니다. 기본 블록의 핵심 개념은 “함께” 실행되는 문장의 집합이라는 점입니다. 즉, 기본 블록으로 분기할 때마다 항상 첫 번째 문장에서 시작하여 나머지 문장을 모두 실행합니다. 블록의 끝에서만 두 곳 이상으로 분기할 가능성이 있습니다(MIR에서는 이 마지막 문장을 종결자라고 부릅니다):
bb0: {
statement0;
statement1;
statement2;
...
terminator;
}
Rust에서 익숙하게 사용하는 많은 표현식은 여러 개의 기본 블록으로 컴파일됩니다. 예를 들어 다음 if 문을 살펴보십시오:
a = 1;
if some_variable {
b = 1;
} else {
c = 1;
}
d = 1;이 코드는 MIR에서 네 개의 기본 블록으로 컴파일됩니다. 텍스트 형태로는 다음과 같습니다:
BB0: {
a = 1;
if some_variable {
goto BB1;
} else {
goto BB2;
}
}
BB1: {
b = 1;
goto BB3;
}
BB2: {
c = 1;
goto BB3;
}
BB3: {
d = 1;
...
}
그래프 형태로는 다음과 같습니다:
BB0
+--------------------+
| a = 1; |
+--------------------+
/ \
if some_variable else
/ \
BB1 / \ BB2
+-----------+ +-----------+
| b = 1; | | c = 1; |
+-----------+ +-----------+
\ /
\ /
\ BB3 /
+----------+
| d = 1; |
| ... |
+----------+
제어 흐름 그래프를 사용하면 루프는 단순히 그래프의 순환으로 나타나고, break 키워드는 그 순환을 빠져나가는 경로로 변환됩니다.
데이터 흐름 분석이란 무엇입니까?
Anders Møller와 Michael I. Schwartzbach가 쓴 Static Program Analysis는 훌륭한 자료입니다!
데이터 흐름 분석은 많은 컴파일러에서 흔히 사용되는 정적 분석의 한 종류입니다. 이는 특정한 분석이라기보다는 일반적인 기법을 가리킵니다.
기본 아이디어는 제어 흐름 그래프(CFG)를 순회하면서 어떤 값이 무엇이 될 수 있는지를 추적하는 것입니다. 순회가 끝나면 어떤 주장이 참인지, 또는 반드시 참은 아닌지를 보일 수 있습니다(예: “이 변수는 반드시 초기화되어야 함”). MIR은 이미 CFG이므로 rustc는 주로 MIR에 대해 데이터 흐름 분석을 수행합니다.
예를 들어 다음 코드 조각에서 x가 사용되기 전에 초기화되는지 확인하고 싶다고 가정해 봅시다:
fn foo() {
let mut x;
if some_cond {
x = 1;
}
dbg!(x);
}이 코드의 CFG는 다음과 같을 수 있습니다:
+------+
| Init | (A)
+------+
| \
| if some_cond
else \ +-------+
| \| x = 1 | (B)
| +-------+
| /
+---------+
| dbg!(x) | (C)
+---------+
데이터 흐름 분석은 다음과 같이 수행할 수 있습니다. 먼저 x가 초기화되었음을 알고 있는지를 나타내는 플래그 init에서 시작합니다. CFG를 순회하면서 이 플래그를 갱신합니다. 마지막에 그 값을 확인할 수 있습니다.
먼저 블록 (A)에서는 변수 x가 선언되었지만 초기화되지 않았으므로 init = false입니다. 블록 (B)에서는 값을 초기화하므로 x가 초기화되었음을 알 수 있습니다. 따라서 (B)의 끝에서는 init = true입니다.
흥미로운 부분은 블록 (C)입니다. 들어오는 간선이 두 개, 즉 (A)에서 오는 간선과 (B)에서 오는 간선이 있으며, 이는 some_cond가 참인지 아닌지에 대응한다는 점에 주목하십시오. 하지만 우리는 그것을 알 수 없습니다! some_cond가 항상 참이어서 x가 실제로는 항상 초기화되는 경우일 수도 있습니다. 또한 some_cond가 무작위적인 무언가(예: 시간)에 의존하여 x가 초기화되지 않을 수도 있는 경우일 수도 있습니다. 일반적으로 우리는 이를 정적으로 알 수 없습니다(라이스의 정리 때문입니다). 그렇다면 블록 (C)에서 init의 값은 무엇이어야 합니까?
일반적으로 데이터 흐름 분석에서 어떤 블록에 부모가 여러 개 있으면(예시의 (C)처럼), 그 블록의 데이터 흐름 값은 모든 부모(그리고 물론 (C)에서 일어나는 일)에 대한 어떤 함수가 됩니다. 어떤 함수를 사용할지는 수행하는 분석에 따라 달라집니다.
이 경우 우리는 x가 사용 전에 반드시 초기화되어야 함을 확정적으로 증명할 수 있기를 원합니다. 이 때문에 우리는 보수적으로 접근하여 some_cond가 때로는 거짓일 수 있다고 가정해야 합니다. 따라서 우리의 “병합 함수“는 “and“입니다. 즉, (A)와 (B) 모두에서 init = true이면(또는 (C)에서 x가 초기화되면) (C)에서 init = true입니다. 하지만 실제로는 그렇지 않습니다. 특히 (A)에서 init = false이고, (C)에서 x는 초기화되지 않습니다. 따라서 (C)에서 init = false이며, “x가 사용 전에 초기화되지 않았을 수 있습니다“라는 오류를 보고할 수 있습니다.
데이터 흐름 분석에 대해서는 분명히 훨씬 더 많은 이야기를 할 수 있습니다. 이 주제에 관해서는 많은 이론을 포함한 방대한 연구 문헌이 있습니다. 여기서는 전방 분석만 다루었지만, 후방 데이터 흐름 분석도 유용합니다. 예를 들어, 블록 (A)에서 시작하여 앞으로 나아가는 대신, x의 사용 지점에서 시작하여 뒤로 거슬러 올라가며 초기화 지점을 찾으려 할 수도 있었습니다.
“전칭 양화“란 무엇입니까? “존재 양화“는 무엇입니까?
수학에서 술어는 전칭 양화되거나 존재 양화될 수 있습니다:
- 전칭 양화:
- 가능한 모든 입력에 대해 참이면 술어가 성립합니다.
- 전통적인 표기법: ∀x: P(x). “모든 x에 대해 P(x)가 성립한다“라고 읽습니다.
- 존재 양화:
- 참이 되는 입력이 하나라도 있으면 술어가 성립합니다. 즉, 그러한 입력이 단 하나만 있으면 됩니다.
- 전통적인 표기법: ∃x: P(x). “P(x)가 성립하는 x가 존재한다“라고 읽습니다.
Rust에서는 타입 검사와 트레이트 해결에서 이러한 개념이 등장합니다. 예를 들면 다음과 같습니다.
fn foo<T>()이 함수는 모든 타입 T에 대해 함수가 올바르게 타입 지정되어 있다고 주장합니다: ∀ T: well_typed(foo).
또 다른 예입니다.
fn foo<'a>(_: &'a usize)이 함수는 (호출자가 결정하는) 임의의 라이프타임 'a에 대해 올바르게 타입 지정되어 있다고 주장합니다: ∀ 'a: well_typed(foo).
또 다른 예입니다.
fn foo<F>()
where for<'a> F: Fn(&'a u8)이 함수는 모든 라이프타임 'a에 대해 F: Fn(&'a u8)을 만족하는 모든 타입 F에 대해 올바르게 타입 지정되어 있다고 주장합니다: ∀ F: ∀ 'a: (F: Fn(&'a u8)) => well_typed(foo).
예를 하나 더 들겠습니다.
fn foo(_: dyn Debug)이 함수는 Debug를 구현하면서 함수가 올바르게 타입 지정되도록 하는 어떤 타입 T가 존재한다고 주장합니다: ∃ T: (T: Debug) and well_typed(foo).
de Bruijn 인덱스란 무엇입니까?
de Bruijn 인덱스는 어떤 변수가 어떤 바인더에 바인딩되어 있는지를 정수만으로 표현하는 방법입니다. 원래는 람다 대수의 평가에 사용하기 위해 고안되었습니다(자세한 내용은 이 위키백과 문서를 참고하십시오). rustc에서는 제네릭 타입을 표현하기 위해 de Bruijn 인덱스를 사용합니다.
다음은 클로저에 de Bruijn 인덱스를 어떻게 사용할 수 있는지 보여 주는 기본적인 예입니다(다만 실제로 rustc에서는 이렇게 하지 않습니다!):
|x| {
f(x) // de Bruijn index of `x` is 1 because `x` is bound 1 level up
|y| {
g(x, y) // index of `x` is 2 because it is bound 2 levels up
// index of `y` is 1 because it is bound 1 level up
}
}공변성과 반공변성이란 무엇입니까?
Rust Nomicon의 서브타이핑 장을 확인하십시오.
타입 검사기가 변성을 처리하는 방식에 대한 자세한 내용은 이 가이드의 변성 장을 참고하십시오.
“자유 영역” 또는 “자유 변수“란 무엇입니까? “바운드 영역“은 무엇입니까?
우리에게 가장 익숙한 개념인 프로그램 변수를 가지고 자유와 바인딩의 개념을 설명해 봅시다.
- 클로저를 생성하는 다음 표현식을 생각해 보십시오:
|a, b| a + b. 여기서a + b에 있는a와b는 클로저가 호출될 때 전달받을 인자를 가리킵니다. 이때a와b는 클로저에 바인딩되어 있다고 하며, 클로저 시그니처|a, b|는 이름a와b에 대한 바인더라고 합니다(그 안에서a나b를 참조하는 것은 모두 이 시그니처가 도입하는 변수를 가리키기 때문입니다). - 다음 표현식을 생각해 보십시오:
a + b. 이 표현식에서a와b는 표현식 바깥에서 정의된 지역 변수를 가리킵니다. 이러한 변수는 표현식에 자유롭게 나타난다고 합니다(즉, 이 변수들은 바인딩된(묶인) 것이 아니라 자유 변수입니다).
정리하면 다음과 같습니다: 어떤 변수가 표현식/문/기타 등의 바깥에서 정의된 무언가를 가리키면, 그 변수는 해당 표현식/문/기타 등에 “자유롭게 나타난다“고 합니다. 마찬가지로, 표현식의 “자유 변수“라는 말도 쓸 수 있는데, 이는 단순히 “자유롭게 나타나는” 변수들의 집합을 의미합니다.
그렇다면 이것이 영역(region)과 무슨 관계가 있습니까? 이와 유사한 개념을 타입과 영역에도 적용할 수 있습니다. 예를 들어, &'a u32 타입에서 'a는 자유 변수로 나타납니다. 하지만 for<'a> fn(&'a u32) 타입에서는 그렇지 않습니다.
컴파일러에 관한 추가 자료
공식 Discord에서 추천해 주신
mem,scottmcm,Levi께 감사드리며, 더 많은 추천이 담긴 Graydon Hoare의 트위터 스레드 링크를 올려 주신tinaun께도 감사드립니다!기타 자료: https://gcc.gnu.org/wiki/ListOfCompilerBooks
다른 제안이 있으시면 언제든지 이슈나 PR을 열어 주십시오.
도서
- Types and Programming Languages
- Programming Language Pragmatics
- Practical Foundations for Programming Languages
- Compilers: Principles, Techniques, and Tools, 2nd Edition
- Garbage Collection: Algorithms for Automatic Dynamic Memory Management
- 링커와 로더(Linkers and Loaders) (무료 버전도 있지만, 저희가 링크했던 버전은 현재 오프라인 상태인 것으로 보입니다.)
- 고급 컴파일러 설계 및 구현(Advanced Compiler Design and Implementation)
- 최적화 컴파일러 구축(Building an Optimizing Compiler)
- Crafting Interpreters