인터프리터와 C backend: 클로저를 손으로 만들기

지난 회는, 인터프리터가 프로그램의 의미를 정하고, 코드 생성기는 그것을 바이트 단위로 재현해야 한다고 논했다. 이번 회는 넷 중 처음 둘 —— 기준을 세우는 인터프리터와, 먼저 그것에 일치해야 하는 C backend —— 을, 그리고 둘 사이의 간극을 구체로 만드는 하나의 문제를 본다: 클로저를 갖지 않는 언어에서, 클로저를 어떻게 표현하는가?

인터프리터와, 공짜 클로저

인터프리터는 트리 워커다: 파서가 만든 구문 트리를 취해, 각 노드를 직접, 재귀적으로 평가하고, 이름을 값에 대응시키는 환경을 지닌다. x + 1을 평가한다는 것은, x를 평가하고, 1을 평가하고, 더하는 것이다. 함수 호출을 평가한다는 것은, 함수를 평가하고, 인자를 평가하고, 한쪽을 다른 쪽에 적용하는 것이다. 여기에 교묘한 것은 아무것도 없고, 그것이 요점이다: 인터프리터는 언어의 명백히 옳은 읽기이도록, 눈으로 믿을 수 있을 만큼 단순한 판이도록 만들어진다. 그래서 그것이 다른 셋을 재는 기준이 될 수 있다.

그것을 이토록 단순하게 하는 것은, 이전의 결정이 조용히 치르고 있는 부채다. 클로저 —— 그것이 쓰인 스코프에서 변수를 포획하는 함수 —— 는, 여기서는 구현할 것이 거의 없다. 호스트 언어인 OCaml이 이미 클로저를 가지기 때문이다. 인터프리터가 fn x -> x + n을 평가할 때, n이 사는 환경을 쥐는 호스트의 클로저를 그저 만들면 된다; 포획도, 저장 공간도, 수명도, 호스트의 런타임이 돌본다. 이 연재의 초입의, OCaml을 고르는 회는, 바로 이 내기를 걸었다 —— 대수적 데이터 타입, 패턴 매칭, 그리고 호스트 자신의 클로저와 GC를 가진 호스트라면, 인터프리터와 타입 검사기가 소박하게 흘러 떨어진다고. 여기가 그 내기가 보답받는 곳이다: 클로저의 어려운 기구는 통째로 호스트에서 빌려지고, 인터프리터에는 거의 아무 비용도 들지 않는다.

C backend는 현금으로 치러야 한다

C backend는 그 어느 것도 빌릴 수 없다. C에는 클로저도, GC도, 동작을 가진 태그 유니온도 없다 —— 있는 것은 최상위에서 정의되는 함수와, 구조체와, 포인터다. 그래서 인터프리터가 OCaml에서 공짜로 얻은 모든 것을, C backend는 그 부품들로부터, 명시적으로 만들어야 한다. 그 간극 —— 풍요로운 호스트가 건네는 것과, 헐벗은 타깃이 구축을 강요하는 것 사이 —— 이야말로, 컴파일이 실은 무엇인가의 대부분이다.

그 구축은, 프로젝트 전체가 일하는 방식으로 이뤄졌다: 한 번에 하나의 언어 feature, 저마다, 다음이 시작되기 전에 인터프리터와 대조되는 작은 슬라이스로서. 먼저 정수, 다음 문자열, 다음 튜플(C의 구조체가 된다), 다음 레코드(typedef), 다음 variant(match를 태그 검사의 연쇄로 컴파일한 태그 유니온). 각 단계는 자기 완결적 번역이고, 저마다 지난 회의 차분 테스트로 검증된다 —— 컴파일하고, 돌리고, 바이트를 인터프리터가 말한 것과 비교한다. 그리고, 기계적이지 않은 하나가 온다.

구조체와 포인터로 클로저를 만들기

클로저는 융합된 두 가지다: 어떤 코드와, 그 코드가 참조하는 포획된 변수. OCaml에서는, 즉 인터프리터에서는, 그 둘이 단일한 값으로 닿고, 이음매를 생각할 필요가 없다. C에는 그런 값이 없으므로, backend는 클로저를 두 부분으로 되가르고, 그것들을 명시적으로 날라야 한다 —— 클로저 변환이라 불리는 기법이다.

그것은 몇 수로 일어난다. 다른 함수의 안쪽에 쓰인 함수는, 최상위로 끌어올려진다. C에는 최상위 함수밖에 없기 때문이다. 그 포획된 변수는, 한때는 단지 이름으로 닿았지만, 끌어올려진 뒤로는 더는 그 방식으로 닿지 않는다 —— 그래서 heap 할당의 환경 구조체로 모아지고, 포획 변수로의 참조는 모두, 그 구조체에서 읽어 내도록 재작성된다. 들려 다니는 클로저의 값은, 그러면 작은 쌍이 된다: 끌어올려진 함수로의 포인터와, 그 환경으로의 포인터다. 그것을 부른다는 것은, 환경 포인터를 숨은 첫 인자로 하여 함수 포인터를 부르는 것이다 —— c.fn(c.env, x). 아무것도 포획하지 않는 순수 최상위 함수도, 값으로 넘겨질 수 있어야 하므로, 사소한 어댑터와 빈 환경을 받아, 같은 쌍의 형태에 들어맞는다. 컴파일러가 어느 함수가 불리고 있는지를 정확히 볼 수 있는 곳에서는, 쌍을 통째로 건너뛰고 직접 호출을 빠른 경로로 뱉는다 —— 속도를 바꾸고, 출력은 결코 바꾸지 않는 최적화이므로, parity는 유지된다.

여기에는 언어 자신의 사상의 조용한 메아리가 있다. 클로저의 포획된 환경은, 대부분의 언어에서, 암묵적인 것의 정의 그 자체다 —— 함수가 잠자코 끌고 다니는, 둘레 상태의 보이지 않는 자루. 클로저 변환은 그 자루를 명시적으로 만든다: 구체적인 구조체, 어딘가 정해진 곳에 할당되고, 평범한 인자로 넘겨지고, 내용은 이름 붙여지고 닿는다. 컴파일러는 클로저에, 언어가 이펙트와 메모리에 하는 것과 꼭 같은 것을 하고 있다 —— 주변적이고 보이지 않는 것을 취해, 가리킬 수 있는 값으로 바꾼다. 다른 것은 다만, 여기서는 그것이, 그렇지 않은 척을 거부하는 C 타깃을 위해, 후드 아래에서 일어난다는 것뿐이다.

두 backend, 하나의 의미

이것이 끝날 무렵, 두 backend는, 이 Part 전체가 의존하는 관계에 선다. 인터프리터는 언어의 짧고 믿을 수 있는 정의로, 어려운 부분을 호스트에 기댄다. C backend는, 같은 그 의미의, 더 길고 더 글자 그대로인 재구축으로, 인터프리터가 빌린 모든 것을 —— 끌어올려진 함수, 환경 구조체, 태그 유니온으로 —— 손으로 써 낸다. 그리고 각 슬라이스가 떨어질 때마다 인터프리터와 대조되었으므로, 둘은 같은 바이트를 낸다: 전혀 다른 두 구현이, 하나의 의미로 유지된다.

그 재구축은 이식 가능한 C이고, C 컴파일러가 있는 곳이면 어디서나 돈다. 하지만 C는, 컴파일할 가치가 있는 유일한 타깃도 아니고, 최적화에 대해 가장 좋은 이야기를 가진 타깃도 아니다. 다음 회: LLVM backend —— C 소스 대신 LLVM의 중간 표현을 뱉는 것, 그리고 타깃이, 사람을 위해 설계된 언어가 아니라, 컴파일러를 위해 설계된 IR일 때, 무엇이 바뀌는가.