컴파일러가 AST에서 변수 이름 때문에 동등성 비교와 치환(인라이닝)에 겪는 문제를 살펴보고, 드브뤼앵 레벨과 드브뤼앵 인덱스로 이를 해결하는 방법을 설명한다.
URL: https://thunderseethe.dev/posts/debruijn-indices/
무언가에 이름을 붙이는 일은 어렵다. 컴퓨터 과학의 두 가지 어려운 문제 중 하나라고도 하는데, 다른 하나는 캐시 무효화이고(그리고 여기에 오프바이원 에러를 끼워 넣는 사람도 있다). 사람은 좋은 이름을 짓는 데 애를 먹는다. 개인적으로 나는 AbstractProducerFactory였는지 AbstractFactoryProducer였는지 도무지 기억이 나지 않는다.
더 놀라운 건, 컴퓨터도 이 과제 앞에서 꽤나 멈칫한다는 점이다. 컴파일러는 종종 이름을 만들어 내야 하는데, 여러분과 나처럼 막막해진다. 물론 사용자가 코드를 쓰며 컴파일러에 이름을 제공하는 경우도 있다:
rustfn a_lil_fun(a_name: String, a_great_name: usize) { // do something cool with our names. }
하지만 불행히도, 사용자가 컴파일러가 필요로 하는 만큼의 이름을 모두 제공하는 일은 드물다. 함수가 기계어로 컴파일되는 과정에서, 컴파일러는 새로운 로컬 변수나 심지어 새로운 함수 매개변수 전체를 도입하기도 한다. 이들 각각은 나중에 다시 찾아 쓰기 위해 이름이 필요하다. 결국 이름의 필요성이 문을 두드리기 시작한다.
좋다. 컴파일러는 이름을 원한다. 그런데 왜 이름을 짓는 게 컴파일러에게도 어려운가? 그 딜레마를 이해하려면 컴파일러가 프로그램을 메모리에서 어떻게 표현하는지부터 봐야 한다. 이름이 달린 변수들을 갖는 간단한 AST를 하나 만들어 보자:
ruststruct Ast { Var(String), // variables Fun(String, Box<Self>), // function App(Box<Self>, Box<Self>), // application }
문제를 쉽게 보이기 위해 아주 단순한 AST를 썼다. 실제 AST에서는 노드가 더 많고 바인딩(결합) 구문도 더 다양하지만, 같은 문제가 그대로 나타난다.
우리의 두통은 AST에서 우리가 원하고 있는 두 가지 성질에서 나온다: 동등성(Equality) 과 치환(Substitution). 컴파일러는 Ast의 두 인스턴스가 같은지 판단할 수 있어야 한다. 가능하다면 Ast에 #[derive(Eq)]를 쓰는 게 가장 좋다. 타이핑을 아끼는 것뿐만 아니라, 빠른 트리 순회로 동등성을 판정할 수 있기 때문이다.
AST의 동등 비교가 컴파일에 “절대적으로” 필요하다고 할 수는 없다. 하지만 비자명한 컴파일러라면 모두 어느 형태로든 AST를 비교한다. 인터닝(interning)과 최적화 패스에서 너무 유용하기 때문인데, 특히 클로저 변환(closure conversion)이 흔한 함수형 언어에서는 더 그렇다.
우리가 신경 쓰는 다른 성질은 치환(Substitution) 이다. 치환은 함수 매개변수를 함수 본문에 인라인하는 과정이다. 인라이닝은 컴파일러의 동맥과도 같아서, 코드 조각을 여러 호출 지점으로 운반해 새로운 최적화 기회를 연다. 이름 때문에 인라이닝이 어려워지면, 컴파일러는 혈전이 생겨 나쁜 코드를 내거나, 더 나쁘게는 죽는다. 다음은 인라이닝이 잘 되는 예시다:
rustAst::app( Ast::app( Ast::fun("fst", Ast::fun("snd", Ast::Var("fst"))), Ast::Var("a"), ), Ast::Var("b"))
사실 이건 읽기 꽤 어렵다(특히 휴대폰 화면에서는). 여기서는 러스트 문법이 꼭 필요하지 않으니, 우리가 관심 있는 부분을 더 잘 드러내는 짧은 표기법을 쓰자:
textx // variables \x. M // functions M N // application
여기서 M과 N은 임의의 AST를 의미하며, Box<Self> 같은 것이라고 생각하면 된다. 여러 매개변수를 갖는 함수에 대한 문법 설탕도 쓰겠다. \x y . x는 AST \x. \y. x의 축약이라고 하자. 이름이 있는 AST에 대한 문법 설탕은 모호함을 줄여 준다: samantha = \s z. s (s (s z)). 이런 이름들은 이해를 돕기 위한 것이며, AST 자체에는 나타나지 않는다. 이제 치환 예시는 훨씬 보기 쉬워진다:
text(\fst snd. fst) a b
우리는 fst에 a를, snd에 b를 인라인해서 다음 AST를 얻고 싶다:
texta
나는 전자보다 후자에 대한 기계어를 생성하고 싶다.
이제 무엇이 걸려 있는지 알았다: 컴파일의 전부… 아마 영원히. 그런데 실제 문제는 뭘까? 이름이 AST의 동등 비교와 치환을 어떻게 방해하는가? 비슷한 두 AST 항을 보자:
textfoo = \x. x bar = \y. y
“비슷하다”고 말해야 한다. 왜냐하면 오늘 당장 이것들을 == 구현에 넣으면 false가 나오기 때문이다. 이것이 첫 번째 문제다. 당신과 나는 단순한 패턴 매칭으로 foo의 x를 y로 바꾸면:
textfoo = \y. y bar = \y. y
둘이 같아진다는 걸 안다. 변수를 x로 부르든 y로 부르든 누가 신경 쓰겠는가. 다른 이름을 붙인 변수도 결국…
어쨌든, 변수의 냄새가 어떻다는 이야기인지는 여러분이 이미 알 거라 믿는다. 이렇게 이름과 무관하게 항을 같다고 보는 것을 알파 동치(alpha equivalence)라고 한다. 우리는 이를 볼 수 있지만, 불쌍한 컴퓨터는 어떨까? 컴퓨터는 두 항을 보고 그런 사실을 평가할 수가 없다. 최소한, 패턴 매칭을 할 “눈”이 없다.
핵심은 foo와 bar가 같은 방식으로 동작함에도 겉보기에는 다르다는 점이다. 함수로서 우리는 매개변수가 무엇이라고 불리는지에 관심이 없다. 인자를 적용했을 때 같은 방식으로 동작하면 같다고 본다. 하지만 이름이 우리의 소박한 컴퓨터가 이를 알아채는 것을 방해한다.
인라이닝 측면에서도 이름은 장벽이다. 나쁜 이름을 고르는 것만으로도 인라이닝이 AST의 의미를 바꿔 버릴 수 있다. 이전 치환 예제를, 무고한 이름 변경 하나만 해서 다시 보자:
text(\fst snd. fst) snd b
이것은 다음의 기본 AST로 디슈거링된다:
text((\fst. (\snd. fst)) snd) b
즉 AST는 한 번에 하나의 치환만 본다. 괄호는 컴퓨터에게 맡기고 우리는 버릴 수 있어서 다행이다. 어쨌든 fst를 순진하게 치환하면 다음 AST가 된다:
text(\snd. snd) b
봤는가? 저 snd들은 서로 다른 변수여야 한다. 하지만 우리의 서툰 인라이닝은 그 사실을 잊어버렸다. 그리고 b까지 인라인하면 상황은 더 나빠진다:
textb
이건 우리가 원래 얻어야 했던 결과 a와 완전히 다른 AST다. 이름은 원래 우리가 어떤 변수를 말하는지 식별하도록 도와야 한다. 그런데 여기서는 AST의 의미를 바꿔 버렸다.
우리의 뛰어난 패턴 매칭 능력으로 문제는 금방 알 수 있다. a를 snd로 바꿨는데, snd는 이미 사용 중인 이름이었다. 하지만 컴파일러는 같은 문제를 알아차리기 어렵다. 특히 실제 프로그램을 나타내는 훨씬 큰 AST에서는 더더욱 그렇다.
물론 이미 사용 중인 이름을 추적하고, 모든 변수에 대해 유일한 이름을 생성하는 방법도 있다. 하지만 실제로는 꽤 비쌀 수 있다. 설령 성공하더라도, 새로운 이름을 도입하면 동등성 비교가 방해된다. 모든 AST가 모든 변수에 대해 유일한 이름을 사용한다면, 정의상 AST는 결코 같아질 수 없다. 한 걸음 앞으로 갔다가 두 걸음 뒤로 간 셈이다.
문제의 뿌리는 AST 표현이 변수가 어떻게 사용되는지 보기 어렵게 만든다는 데 있다. 이름은 가독성에는 좋지만 동등성에는 악영향을 준다. 이름에 매달리기보다는 AST의 구조에 집중하고 싶다. 변수는 몇 번 쓰이고, 그 발생 위치는 어디인가? 이 구조를 부각하는 이름을 고를 수 있다면, 이름이 우리를 방해하는 대신 도와줄 것이다.
이 글의 안도감 넘치는 소식은: 그럴 수 있다는 것이다. 핵심 통찰은 함수를, 바인딩된 변수들을 위한 “이름 배열”을 형성하는 것으로 생각하는 것이다. 다음 AST를 보자:
text\x y z. x z (y z)
Fun 노드가 이름 배열을 유지한다고 상상할 수 있다:
text\[x, y, z]. x z (y z)
이 함수는(사실 3개의 함수에 대한 문법 설탕) 3개의 변수를 바인딩하고, 이를 길이 3의 이름 배열로 볼 수 있다. 함수가 중첩되어도 된다: \[x, y]. (\[z]. x z) (\[w]. y w) 처럼. AST를 위에서 아래로 순회하면서 실행 중인 이름 배열을 유지하고, 함수를 만나면 그 변수들을 배열에 덧붙인다. x z에서는 변수 배열이 [x, y, z]이고, y w에서는 [x, y, w]다. 개념적으로 우리는 AST를 위에서 아래로 훑으며 이 이름 배열을 쌓아 간다.
배열은 이전에 없던 중요한 기능을 제공한다: 인덱싱. 변수들이 이름을 쓰는 대신, 배열에서의 인덱스로 변수를 표현하자. 예를 들어 다음 AST:
text\[x]. x
는 다음이 된다:
text\[x]. 0 ▲ │ └───┘
조금 더 복잡한 AST:
text\[x, y]. y x
는 다음이 된다:
text┌───┐ ▼ │ \[x, y]. 1 0 ▲ │ └────────┘
마지막으로 가장 복잡한 AST:
text\[x, y]. (\[z]. x z) (\[w]. y w))
는 다음이 된다:
text┌─────┐ ┌─────┐ ▼ │ ▼ │ \[x, y]. (\[z]. 0 2) (\[w]. 1 2) ▲ ▲ │ │ └──┼──────────┘ │ └──────────────────────┘
0 2를 볼 때, 이름 배열이 [x, y, z]임을 기억하면 0은 x, 2는 z임을 알 수 있다. 당신과 나를 위해 이름 배열을 같이 표기하겠지만, 이를 생략해도 구조는 잃지 않는다. 즉 \.0 또는 \.\.(\. 0 2) (\. 1 2)처럼 써도 된다.
체계적으로 인덱스를 선택하는 것은 동등성의 구원이다:
text\[x]. 0 == \[y]. 0
기억하자. 이름은 디버깅용일 뿐이다. 컴파일러가 AST를 비교할 때 보는 것은 사실상 \.0 == \.0뿐이다. 눈이나 패턴 매칭 없이도 참임을 알 수 있다. 반대도 마찬가지다. 인덱스는 두 AST가 같지 않다는 것도 쉽게 보여 준다:
text\[x, y]. 0 != \[x, y]. 1
앞서 \[x, y]. (\[z]. x z) (\[w]. y w) AST에서 보았듯, 이름 배열이 여러 개일 수 있다. 애플리케이션이 AST를 분기시키면 여러 배열을 도입할 여지가 생긴다. 그러면 같은 인덱스가 서로 다른 이름을 가리킬 수도 있다. 합리적인 사람이라면 이게 다시 예전의 곤경으로 돌아가는 게 아닌지 걱정할 것이다.
이름 문제의 일부는 서로 다른 변수가 같은 이름을 쓰는 데서 왔다. 다행히 인덱스를 쓰면 같은 문제가 생기지 않는다. AST의 구조만 보고도 2가 z를 가리키는지 w를 가리키는지 항상 분명하다. 이렇게 인덱스로 AST의 구조를 포착하는 방식을 드브뤼앵 레벨(DeBruijn Levels) 이라고 한다.
드브뤼앵 레벨은 AST를 위에서 아래로 내려가며 이름 배열을 만들고, 그 배열을 기준으로 각 변수에 인덱스를 부여한다. 우리가 본 것처럼 동등성은 쉬워진다. 치환도 쉬워진다면 완벽한 표현을 찾은 셈이다. 다음은 우리의 가설을 시험할(적절히 고른) 예시다:
text┌────────────┐ ▼ │ (\[x, y]. 0 (\[z]. 1 2)) (\[w]. 0) ▲ │ ▲ │ ▲ │ └──────┘ └─────┘ └───┘
여기서 x에 대해 (\[w]. 0)을 치환할 수 있다:
text???◄──────┐ │ \[y]. (\[w]. 0) (\[z]. 1 2) ▲ │ ▲ │ └──────────┘ └───┘
그때는 좋은 생각처럼 보였지만, 지금 완전히 망가뜨려 버렸다. 말 그대로 이 AST의 모든 인덱스가 틀려졌다. 1 2에서의 이름 배열은 [y, z]인데, 이제 2는 배열 범위를 벗어난다. 오늘 우리가 얘기해야 할 “바운드”는 그런 의미의 바운드가 아닌데 말이다.
그래도 복구는 가능하다. 새 변수 배열에 맞게 인덱스를 조정하면 된다:
text┌────────────────────┐ ▼ │ \[y]. (\[w]. 1) (\[z]. 0 1) ▲ │ ▲ │ └───┘ └─────┘
이제 다시 정상으로 돌아왔지만, AST 안의 모든 인덱스를 업데이트해야 했다. 나는 많은 인라이닝을 할 예정이었다. 매번 모든 인덱스를 수정하는 건 꽤 번거로워 보인다.
드브뤼앵도 그렇게 생각했고, 이를 고칠 아이디어를 냈다. 드브뤼앵 레벨에는 읽기 더 어려운 짝이 있는데: 드브뤼앵 인덱스(DeBruijn Indices) 다. 레벨은 위에서 아래로 이름 배열을 구성하고 그 배열을 인덱싱한다. 드브뤼앵 인덱스는 반대로 한다. 아래에서 위로 이름 스택을 쌓고, 그 스택을 인덱싱한다.
이는 변수를 인덱싱하기 전에 배열을 뒤집는 것으로 생각할 수 있다. 드브뤼앵 레벨 AST를 보자:
text┌─────┐ ┌─────┐ ▼ │ ▼ │ \[x, y]. (\[z]. 0 2) (\[w]. 1 2) ▲ ▲ │ │ └──┼──────────┘ │ └──────────────────────┘
여기서 두 이름 배열은 [x, y, z]와 [x, y, w]였다. 드브뤼앵 인덱스로 바꾸려면 먼저 이 배열들을 뒤집는다: [z, y, x]와 [w, y, x]. 그리고 새로운 순서를 사용하도록 인덱스를 조정한다:
text┌─────┐ ┌─────┐ ▼ │ ▼ │ \[x, y]. (\[z]. 2 0) (\[w]. 1 0) ▲ ▲ │ │ └──┼──────────┘ │ └──────────────────────┘
감 잡기 위해 예시를 몇 개 더 해보자. AST:
text\[x]. 0 ▲ │ └───┘
는 다음이 된다:
text\[x]. 0 ▲ │ └───┘
원소 하나짜리 배열을 뒤집는 건 별일 아니다. 더 흥미로운 AST:
text\[x, y]. 0 ▲ │ └──────┘
는 다음이 된다:
text\[x, y]. 1 ▲ │ └──────┘
인덱싱을 좀 더 뽐내기 위한 AST 하나 더:
text┌─────────┐ │ ┌──────┼────┐ ▼ ▼ │ │ \[x, y, z]. 0 2 (1 2) ▲ │ │ └─────┴────┘
는 다음이 된다:
text┌─────────┐ │ ┌──────┼────┐ ▼ ▼ │ │ \[x, y, z]. 2 0 (1 0) ▲ │ │ └─────┴────┘
나는 리트코드를 충분히 풀어 봐서 배열을 뒤집는 법은 안다. 이진 트리를 뒤집는 법만 제대로 알면 취업할 수 있을 텐데.
새로운 드브뤼앵 인덱스를 갖추었으니, 아까의 인라이닝 예시는 이제 아주 단순해진다:
text┌────────────┐ ▼ │ (\[x, y]. 1 (\[z]. 1 0)) (\[w]. 0) ▲ │ ▲ │ ▲ │ └──────┘ └─────┘ └───┘
다시 x에 대해 \[w]. 0을 치환한다:
text┌────────────────────┐ ▼ │ \[y]. (\[w]. 0) (\[z]. 1 0) ▲ │ ▲ │ └───┘ └─────┘
모든 인덱스가 맞다. 조정할 인덱스가 하나도 없다. 예제를 내가 썼으니 쉬울 건 알았지만, 이렇게까지 일이 없을 줄은 몰랐다. 드브뤼앵은 정말 뭔가를 잡아냈다.
조금만 생각해 보면 이게 말이 된다. 드브뤼앵 레벨은 트리의 “위쪽”에서부터 인덱싱을 시작하므로, 치환을 하면 트리의 위가 바뀌면서 그 영향이 트리 전체로 퍼진다. 반면 드브뤼앵 인덱스는 트리의 “아래쪽”에서부터 인덱싱을 시작한다. 치환이 트리의 위쪽을 바꾸더라도 스택의 맨 위 원소 하나를 팝(pop)하는 셈이 되고, 다른 인덱스들은 흔들리지 않는다.
또 다른 관점은 이름 배열에 무슨 일이 일어나는가다. 배열의 끝에서 원소를 하나 빼는 것은 쉽지만, 배열의 첫 원소를 제거하는 것은 훨씬 더 많은 일이 필요하다.
드브뤼앵 인덱스는 바인딩된 변수를 다루기 쉽게 해 준다. 반대로 드브뤼앵 레벨은 자유 변수(free variables)를 다루기 쉽게 해 준다. 이 강점들에 따라 둘 다 쓰임새가 있다. 하지만 우리 목적은 대부분 바인딩된 변수를 다루는 것이므로, 드브뤼앵 인덱스가 더 빛난다.
다만 가독성 문제는 남는다. 드브뤼앵 인덱스는 동등성과 치환 문제를 모두 해결하지만, 나는 그것만 보면 도대체 뭐가 뭔지 알 수가 없다. 실전에서는 이를 완화할 방법이 많이 있다. 지금까지의 예시도 참고용으로 이름 리스트를 포함해 왔다: \[x, y, z]. 2 0 (1 0). 실제 구현에서도 비슷한 전략을 쓸 수 있다.
함수 노드에 이름을 저장하되, 출력용으로만 저장하자. 내부적으로는 동등 비교와 치환을 쉽게 해 주는 드브뤼앵 인덱스를 사용한다. 사람이 읽을 수 있는 형태로 출력하고 싶을 때는 저장해 둔 이름 목록을 사용해 모든 인덱스를 이름으로 바꿔 출력한다. 이 방식은 인간을 위한 가독성을 되찾으면서도 두 세계의 장점을 모두 취할 수 있게 해 준다.
물론 이 접근이 항상 적용 가능한 것은 아니다. 때로는 단순히 정수 카운터를 하나 두고, 컴파일러가 생성하는 모든 이름에 유일한 정수를 붙이는 것으로 충분할 때도 있다. 어차피 누구도 foo__3405__ 같은 이름을 보지 않을 테니, 카운터를 증가시키고 하루를 계속 살면 된다. 하지만 두 AST가 같은지 검사하는 방법 때문에 머리를 긁적이거나, 혹은 나처럼 인라이닝이 왜 잘못된 코드를 내는지 몇 주를 허비하고 있다면, 이제 이런 고난을 해결할 도구를 손에 쥔 셈이다.
