람다의 암묵적 캡처를 클로저로 명시화하고, 이를 위한 새로운 IR과 구현 과정을 Rust 기반 컴파일러 패스 관점에서 설명한다.
URL: https://thunderseethe.dev/posts/closure-convert-base/
이 글은 언어 만들기 시리즈의 일부입니다. Rust로 프로그래밍 언어를 구현하는 방법을 가르치는 시리즈죠.
오늘 글은 기본 단형화(base monomorphization) 패스 뒤에 이어집니다. 단형화와 마찬가지로, 클로저 변환은 이전 패스의 산출물에 의존하지 않습니다. 로워링에서 도입한 IR(및 동반 타입들)에 의존할 뿐입니다. 본격적으로 들어가기 전에 IR을 다시 훑어보겠습니다.
이전 패스인 단형화는 중간 표현(IR)에서 다형성을 제거했습니다. 오늘은 그보다 더 가까운 측근, 바로 함수(function)를 잘라내려 합니다. 컴파일 정복의 길에서 우리는 대체 몇 명의 친구를 잃어야 할까요. 놀라울 수도 있지만, 함수는 우리 언어에 깊이 얽혀 있습니다. 이름에 ‘함수형 프로그래밍(functional programming)’이 들어가잖아요. ‘al 프로그래밍’이 뭔지는 모르겠고, 알고 싶지도 않습니다.
함수가 없다면 정수만 남습니다. 결국 모든 건 1과 0이지만, 정수만으로 계산을 하려면 최소한 무한히 길 수 있는 테이프라도 있어야 할 것 같군요. 걱정은 내려놓으셔도 됩니다. 우리는 함수를 제거하지만, 대신 새로운 무언가로 바꿀 겁니다. 무엇으로 바꾸는지 보기 전에, 왜 함수를 바꾸는지부터 이야기해 봅시다.
다형성과 달리, 머신에는 함수를 위한 명령이 있습니다. 오히려 별로 이국적이지도 않죠. 반환(return)과 함수 인자 전달(passing arguments)을 위한 명령이 없는 아키텍처를 찾기란 어렵습니다. 그러면 “왜 함수를 제거하느냐?”는 질문이 생깁니다. 여기서 생기는 불협화음은 ‘함수’라는 정의의 차이에서 나옵니다. 우리 언어에서 쓰는 함수와 하드웨어가 구현하는 함수는 같은 함수가 아닙니다.
우리 언어의 함수는 사실 람다(lambda)입니다. 람다는 주변의 렉시컬 스코프(lexical scope)를 환경(environment)으로 캡처하는 함수입니다. 하드웨어 함수는 이런 기능이 없죠. Rust 코드로 차이를 보면:
// A hardware function
fn foo(
x: usize
) -> usize {
x + 1
}
let a = 1;
let y = 10;
// A lambda
let bar = |x: usize| x * y + a;
하드웨어 함수인 foo는 환경이 필요 없습니다. 필요한 인자만 넘기면 답을 받죠. 반면 bar는 a와 y를 환경에 캡처해서, bar를 호출할 때마다 그 환경이 함께 제공됩니다.
변수 캡처의 편의성은 과소평가할 수 없습니다. 수많은 프로그래밍 패턴이 “다른 람다를 캡처하는 람다”로 귀결되죠. 람다는 가치가 있지만, 더 컴파일하기 쉬운 형태—클로저(closure)—로 바꿔야 합니다.
클로저는 람다의 암묵적 캡처를 명시적으로 만듭니다. 클로저는 구조체(struct)로, 람다 본문을 위한 필드 하나와 캡처된 값마다 필드 하나를 갖습니다. bar 예제로 돌아가면 bar는 다음 클로저가 됩니다:
fn bar_impl(env: Bar, x: usize) -> usize {
x * env.y + env.a
}
let bar = Bar {
fun: bar_impl,
a: 1,
y: 10,
}
원래 람다의 본문은 이제 최상위(top level) 함수 bar_impl 안에 들어갑니다. 이는 우리가 실행할 줄 아는 하드웨어 함수이니 올바른 방향으로 한 걸음 나아간 셈입니다. 그리고 본문에서 자유 변수(free variable) a, y에 접근하던 부분을 새 env 파라미터를 통해 접근하도록 바꿨습니다.
람다 본문에서 최상위 함수를 만들 때 새 파라미터 env를 추가합니다. 이는 이전에는 암묵적으로 접근하던 캡처 변수를 이제 명시적으로 접근할 수 있게 해줍니다. env 파라미터의 타입 Bar는 클로저의 타입과 동일합니다. Bar는 캡처 변수마다 필드가 하나씩 있고, 생성된 최상위 함수에 대한 참조를 담는 fun 필드도 있으니, 클로저 타입이면서 동시에 환경 타입 역할도 합니다.
람다를 클로저로 바꾸면 적용(application)도 바뀝니다. 클로저는 함수가 아니라 구조체이므로, 이전에는 람다에 인자를 넘겨 호출하던 것을:
bar(3)
이제는 클로저의 fun 필드를 호출하면서 env(즉 클로저 자신)를 함께 넘겨야 합니다:
bar.fun(bar, 3)
추상적으로 보면, 이게 클로저 변환의 전부입니다. 마주치는 모든 함수와 적용을 변형하면 끝이죠. 다만 이 작업은 침습적입니다. 너무 침습적이라서, 원래는 아예 피하려고 했습니다. 처음엔 이 패스에서 람다 리프팅(lambda lifting)을 사용했는데, 람다 리프팅도 람다를 제거하지만 클로저를 쓰지 않습니다. 캡처 변수를 담는 구조체를 만드는 대신, 각 Fun을 새 최상위 함수로 끌어올리고 자유 변수마다 새 파라미터를 추가합니다. bar 예제를 람다 리프팅해 보면 차이가 보입니다:
let a = 1;
let y = 10;
// A lambda
let bar = |x: usize| x * y + a;
bar(3)
은 이렇게 바뀝니다:
fn bar(
a: usize,
y: usize,
x: usize
) -> usize {
x * y + a
}
bar(1, 10, 3)
bar 호출을 조정해서 a, y를 직접 넘기면 람다는 사라지고, 그 자리엔 상태 없는(stateless) 최상위 함수가 남습니다. 구조체나 클로저가 필요 없죠. 이 단순함 때문에 람다 리프팅은 매력적이지만 비용이 있습니다. 람다의 또 다른 흔한 사용을 보죠:
fn foo(
a: usize
) -> impl Fn(usize) -> usize {
|b: usize| a + b
}
이 람다를 리프팅하면 잘 되지 않습니다:
fn foo_lambda(a: usize, b: usize) -> usize {
a + b
}
fn foo(
a: usize
) -> impl Fn(usize) -> usize {
foo_lambda(a, ???)
}
이 람다는 b가 나중에 주어질 때까지 a를 저장해 두기 위해 존재합니다. 클로저는 a를 들고 있을 수 있는 구조체라서 이 역할을 잘 수행합니다. 하지만 이를 대신할 유효한 최상위 함수는 없습니다. 최상위 함수는 모든 파라미터를 한 번에 받아야 하므로, 람다를 반환하는 것과 호환되지 않습니다.
람다 리프팅은 클로저 변환과 달리 부분적인 해법만 제공합니다. 그렇다고 가치가 없다는 건 아닙니다. 클로저를 피하는 건 훌륭한 목표라서, 실제 프로덕션 컴파일러들은 선택적 람다 리프팅(selective lambda lifting)을 수행하기도 합니다. 하지만 여기의 간단한 컴파일러에서는 모든 경우를 다루는 클로저 변환을 사용합니다. 다만 이 선택에는 대가가 따릅니다.
클로저 변환의 대가는 새 IR입니다. 로워링에서 사용하던 기존 IR과 꽤 비슷하지만, Fun 대신 Closure가 있습니다. 새 IR이 필요한 이유는 두 가지입니다.
IR에 반영하고 싶습니다.IR에는 없는 새로운 타입들을 사용합니다.이를 반영한 새 IR은 다음과 같습니다:
enum IR {
Var(Var),
Int(i32),
Closure(Type, ItemId, Vec<Var>),
Apply(Box<Self>, Box<Self>),
Local(Var, Box<Self>, Box<Self>),
Access(Box<Self>, usize),
}
Fun은 Closure가 되었고, App은 Apply가 되었습니다. 그리고 완전히 새로운 노드 Access가 생겼습니다. Access는 env 파라미터에서 캡처된 변수를 꺼내는 방식입니다. 그 외에는 나머지 IR은 동일합니다.
클로저를 구조체로 소개했지만 IR에는 Struct 노드가 없습니다. 하지만 클로저가 구조체라는 사실은 변하지 않습니다. 다만 클로저가 제기하는 타입 문제를 매끄럽게 처리하기 위해 Closure 노드를 따로 둡니다.
모든 람다는 캡처 여부와 상관없이 같은 타입으로 간주됩니다. 클로저는 이를 명시적으로 깨지만, 적용 시에는 여전히 클로저를 불투명한 함수(opaque function)처럼 다루고 싶습니다. 적용에 대한 타입 검사에서 다음 클로저 타입들을:
{ fun: fn(usize) -> usize }{ fun: fn(usize) -> usize, a: usize }{ fun: fn(usize) -> usize, a: usize, b: usize }모두 동일하게 fn(usize) -> usize로 취급하고 싶습니다. 이 미묘함을 처리하는 가장 쉬운 방법은 해당 상황을 나타내는 전용 노드를 도입해, 일반 구조체와 다른 방식으로 클로저를 타입 검사할 수 있게 하는 것입니다.
Closure 노드는 변환을 위해 필요한 두 가지 데이터 타입도 도입합니다: Type과 ItemId입니다. ItemId는 로컬 변수용 VarId와 유사하지만, 로컬 변수가 아니라 최상위 함수(top level function)를 가리킵니다. 클로저는 최상위 함수가 필요하므로, AST와 로워링 IR에는 없었지만 여기서는 아이템(items)을 추가합니다. 람다 본문을 최상위 함수로 바꾸면, 클로저는 그 최상위 함수를 ItemId로 참조합니다.
Type은 새 IR에서 로워링 타입에 해당하는 타입입니다:
enum Type {
Int,
Closure(Box<Self>, Box<Self>),
ClosureEnv(Box<Self>, Vec<Self>),
}
IR과 마찬가지로 Fun 타입을 Closure 타입으로 바꿨습니다. 새 타입 ClosureEnv는 env 파라미터에 부여할 타입입니다. Closure와 ClosureEnv는 같은 값을 위한 두 가지 타입입니다. 어떤 클로저든 Closure 타입을 받아(올바른 인자가 전달됐는지 검사하는 데 사용), 동시에 env로 최상위 정의에 넘길 때는 ClosureEnv 타입을 받습니다.
미들엔드 패스들은 공통 IR 위에서 동작합니다:
enum IR {
Var(Var),
Int(i32),
Fun(Var, Box<Self>),
App(Box<Self>, Box<Self>),
TyFun(Kind, Box<Self>),
TyApp(Box<Self>, Type),
Local(Var, Box<Self>, Box<Self>),
}
이 IR은 명시적으로 타입이 붙어 있고, 타입 함수(type functions)와 타입 적용(type applications)으로 제네릭을 표현합니다. 또한 엄밀히 필수는 아니지만 단순화에 매우 유용한 Local을 도입합니다. IR과 함께, AST 타입에서 로워링된 Type도 있습니다:
enum Type {
Int,
Var(TypeVar),
Fun(Box<Self>, Box<Self>),
TyFun(Kind, Box<Self>),
}
Type에는 AST에는 없던 Kind가 있습니다. 값(value)에 타입(type)이 있듯, 타입에도 킨드(kind)가 있습니다. 기본 Kind는 공허(vacuous)합니다:
enum Kind {
Type
}
Type은 kind Type을 가집니다. 사실이라고는 믿지만, 이런 원형(circular) 문장을 굳이 공리로 둘 필요가 있는지는 의문입니다. 어쨌든 IR에 대해 알아야 할 건 이게 전부고, 다시 클로저 변환으로 돌아가죠.
구현을 시작해봅시다. 엔트리 포인트 closure_convert부터 위에서부터 내려갑니다:
fn closure_convert(
ir: lowering::IR
) -> ClosureConvertOutput {
todo!()
}
ir은 지금까지 써 왔던 IR입니다. 클로저 변환은 자체 IR을 도입하므로 lowering::IR이라고 명시해야 합니다. closure_convert는 ClosureConvertOutput을 반환하는데, 이는 아이템 묶음(bundle)입니다:
struct ClosureConvertOutput {
item: Item,
closure_items: BTreeMap<ItemId, Item>,
}
입력 ir을 최상위 함수 하나로 바꿀 것입니다. 그 함수가 출력의 item이 됩니다. closure_items의 나머지 아이템들은 변환 중 마주치는 람다 본문을 담기 위해 생성됩니다. 아이템(item)은 최상위 함수로서, 파라미터들과 본문으로 구성됩니다:
struct Item {
params: Vec<Var>,
ret_ty: Type,
body: IR,
}
편의를 위해 반환 타입을 Item에 넣었지만, 꼭 필요하진 않습니다. Item은 함수와 비슷하지만, 변수를 캡처하지 않는다는 점이 보장되어 아이템에 대한 코드 생성이 더 쉽습니다. 이제 목표가 보이니, 어떻게 거기까지 가는지 시작해봅시다.
fn closure_convert(ir: lowering::IR) -> ClosureConvertOutput {
let (params, ir) = ir.split_funs();
let mut var_supply = VarSupply::default();
let mut env = im::HashMap::default();
todo!()
}
첫 줄은 단순화에서 봤던 split_funs를 사용합니다. 이는 IR 루트에 연속으로 붙어 있는 함수 노드들을 모아, 그 파라미터 리스트와 함수 노드들 안쪽의 본문을 돌려줍니다. 루트에 함수가 없다면 params는 빈 리스트이고 본문은 IR 자체입니다. 이렇게 최상위 파라미터들을 분리하는 이유는, 그들을 클로저로 변환하고 싶지 않기 때문입니다.
IR을 아이템으로 바꿀 때 본문이 중첩된 클로저들의 연쇄가 되는 건 원치 않습니다. 루트 함수들 안으로 들어간 뒤에야 함수를 클로저로 바꾸기 시작하고 싶습니다. 이후에는 관례적인 보조 구조들을 준비합니다:
var_supply는 변환 중 필요한 Var를 제공합니다.env는 lowering::Var를 새 Var로 매핑합니다.다음 과제는 최종 아이템의 파라미터와 반환 타입을 결정하는 일입니다:
let params = params
.into_iter()
.map(|param| match param {
Param::Ty(_) => panic!("ICE: Type function encountered after monomorphizing"),
Param::Val(lower_var) => {
let id = var_supply.supply_for(lower_var.id);
let var = Var {
id,
ty: lower_ty(&lower_var.ty),
};
env.insert(lower_var, var.clone());
var
}
})
.collect();
let ret_ty = lower_ty(&ir.type_of());
클로저 변환은 단형화 이후이므로 타입 파라미터가 더 이상 없어야 합니다. 각 값 파라미터에 대해 새 변수를 만들고 env에 넣습니다. 새 변수를 만들면서 타입도 로워링합니다. 전체 ir의 타입도 로워링해서 반환 타입을 얻습니다.
이 둘은 lower_ty로 수행됩니다. lowering::Type을 새 Type으로 바꾸는 함수이며 구현은 간단합니다:
fn lower_ty(ty: &lowering::Type) -> Type {
match ty {
lowering::Type::Int =>
Type::Int,
lowering::Type::Fun(arg, ret) =>
Type::closure(
lower_ty(arg),
lower_ty(ret)),
lowering::Type::Var(_)
| lowering::Type::TyFun(_, _) =>
panic!("ICE: Type function or variable appeared in closure conversion. This should've been handled by monomorphization."),
}
}
Fun은 Closure로, Int는 Int로 바뀝니다. 제네릭은 없어야 하니 나타나면 패닉합니다. 다시 closure_convert로 돌아가 실제 변환을 시작합니다:
let mut conversion = ClosureConvert {
var_supply,
item_supply: Default::default(),
items: Default::default(),
};
let body = conversion.convert(ir, env);
ClosureConvert는 변환 중 필요한 상태(state)를 담습니다:
struct ClosureConvert {
var_supply: VarSupply,
item_supply: ItemSupply,
items: BTreeMap<ItemId, Item>,
}
ItemSupply는 VarSupply처럼 새 ItemId를 제공합니다. var_supply는 이전에도 봤고, 구현이 궁금하면 전체 코드를 보면 됩니다. items는 클로저용으로 생성한 아이템을 담는데, 최종적으로 출력의 closure_items가 됩니다. ClosureConvert는 convert 메서드를 제공하기 위한 구조체입니다:
fn convert(
&mut self,
ir: lowering::IR,
env: im::HashMap<lowering::Var, Var>
) -> IR {
match ir {
// ...
}
}
convert는 lowering::IR을 새 IR로 바꾸는 동시에, 람다를 클로저로 바꾸는 곳입니다. 입력 ir에 대한 매치(match) 형태로 작성합니다. 먼저 몇 가지 케이스는 단순히 lowering::IR에서 IR로 옮기는 보일러플레이트입니다:
lowering::IR::Int(i) =>
IR::Int(i),
lowering::IR::Var(var) =>
IR::Var(env[&var].clone()),
lowering::IR::TyFun(_, _)
| lowering_base::IR::TyApp(_, _) => {
panic!("ICE: Generics appeared after monomorphizing")
}
lowering::IR::Local(var, defn, body) => {
let defn = self.convert(*defn, env.clone());
let v = Var {
id: self.var_supply.supply_for(var.id),
ty: lower_ty(&var.ty),
};
let body = self.convert(*body, env.update(var, v.clone()));
IR::local(v, defn, body)
}
Local은 구성 요소들을 변환해 다시 local로 재구성할 뿐입니다. Fun에서 비로소 실제 변경이 일어납니다:
lowering::IR::Fun(fun_var, body) => {
let var = Var {
id: self.var_supply.supply_for(fun_var.id),
ty: lower_ty(&fun_var.ty),
};
self.make_closure(
var.clone(),
*body,
env.update(fun_var, var))
}
바인딩된 파라미터를 변환하고, 핵심 작업기 make_closure로 위임합니다:
fn make_closure(
&mut self,
var: Var,
body: lowering_base::IR,
env: im::HashMap<lowering::Var, Var>,
) -> IR {
todo!()
}
이름 그대로 make_closure는 람다의 조각들을 받아 클로저를 만듭니다. 하지만 클로저를 만들기 전에 분석이 필요합니다. 해야 할 일은:
env 접근으로 바꾼다.이 과제들을 마치면 클로저 생성이 준비됩니다. 자유 변수 구하기는 간단합니다. 그냥 물어보면 됩니다:
let ret = lower_ty(&body.type_of());
let mut body = self.convert(body, env);
let mut free_vars = body.free_vars();
free_vars.remove(&var);
자유 변수를 구하기 전에 본문을 새 IR로 변환합니다. body 변환은 body를 소비(consumes)하므로, 그 전에 type_of로 반환 타입을 저장해둡니다. free_vars는 항(term)을 순회하며 자유 변수 집합을 구성합니다. 구현은 소스 코드에 있습니다. 여기서는 잘 동작한다고 믿겠습니다. body 관점에서 람다가 바인딩한 변수는 자유 변수입니다. 하지만 우리는 그것이 바로 바깥 람다에 의해 곧 바인딩된다는 걸 아니까, 자유 변수 집합에서 제거합니다.
다음은 자유 변수를 환경 접근으로 옮기는 일입니다. 먼저 env용 변수를 만듭니다:
let vars: Vec<Var> =
free_vars.iter()
.cloned()
.collect();
let closure_ty =
Type::closure(var.ty.clone(), ret.clone());
let env_var = Var {
id: self.var_supply.supply(),
ty: Type::closure_env(
closure_ty.clone(),
vars.iter()
.map(|var| var.ty.clone())
.collect(),
),
};
env의 타입은 자유 변수들의 타입과 클로저의 타입으로 결정됩니다. 이제 env가 있으니 자유 변수를 치환(substitution)할 수 있습니다:
let subst = free_vars
.into_iter()
.enumerate()
.map(|(i, var)| {
let id = self.var_supply.supply();
let new_var = Var {
id,
ty: var.ty.clone(),
};
body = IR::local(
new_var.clone(),
IR::access(IR::Var(env_var.clone()), i + 1),
body.clone(),
);
(var, new_var)
})
.collect::<HashMap<_, _>>();
body.rename(&subst);
각 자유 변수는 env에 대한 Access가 됩니다. 놀랍게도 접근 인덱스가 1만큼 오프셋됩니다. env가 곧 클로저이기도 해서, 첫 필드(인덱스 0)는 최상위 함수에 대한 참조이기 때문입니다. 자유 변수들은 인덱스 1부터 시작합니다.
접근 순서는 중요합니다. env에서 접근하는 인덱스가 클로저를 구성할 때의 변수 순서와 일치해야 합니다. 다행히 free_vars는 일관된 순서를 유지하는 BTreeSet입니다. subst를 만들 때 반복(iteration) 중에 body를 Local로 감싸 수정하는데, 이는 본문 곳곳에서 여러 번 환경 접근을 하는 대신 본문 시작 부분에서 한 번씩 로드하게 합니다.
즉, x * y + a를 x * env.y + env.a로 직역하는 대신:
let t0 = env.y;
let t1 = env.a;
x * t0 + t1
처럼 바뀝니다.
이 단순 예제에서는 변화가 미미하거나 오히려 나빠 보일 수 있지만, 대부분의 클로저에서는 공유(sharing)를 늘리고 힙 접근 횟수를 줄일 것으로 기대합니다. 단, 필요 없는 로드를 할 수도 있습니다. 예를 들어 if x { env.a } else { env.b }는:
let t0 = env.a;
let t1 = env.b;
if x { t0 } else { t1 }
가 되어, 필요한 필드만 로드하는 대신 항상 둘 다 로드하게 됩니다. 지금은 이 트레이드오프를 받아들이겠습니다. 이런 코드는 실사용에서 자주 나오지 않을 가능성이 높습니다. 정말 문제가 된다면 더 정교한 휴리스틱을 적용할 수 있습니다.
이 접근 때문에 subst는 HashMap<Var, Var>이지 HashMap<Var, IR>가 아닙니다. 덕분에 본문에 rename을 사용할 수 있습니다. rename은 항을 순회하며 subst에 등장하는 변수를 치환합니다. 일부만 보면 기능이 충분히 드러납니다:
fn rename(&mut self, subst: &HashMap<Var, Var>) {
match self {
IR::Var(var) => {
if let Some(new_var) = subst.get(var) {
*var = new_var.clone();
}
}
// the rest of our cases are standard
}
}
make_closure의 마지막 작업은 아이템을 만드는 것입니다:
let params = vec![env_var, var];
let item = self.item_supply.supply();
self.items.insert(
item,
Item {
params,
ret_ty: ret,
body,
},
);
IR::Closure(closure_ty, item, vars)
아이템은 env와 람다가 받던 변수, 두 파라미터를 갖고, 반환 타입과 손질된 람다 본문을 가집니다. 이를 items에 저장해 클로저의 최상위 함수가 되게 합니다. 결과 클로저는 타입, 아이템, 자유 변수 목록으로 구성됩니다.
이제 convert로 돌아가 마지막 케이스를 처리합니다:
lowering::IR::App(fun, arg) => {
let closure = self.convert(*fun, env.clone());
let arg = self.convert(*arg, env);
IR::apply(closure, arg)
}
어… 음. Fun에 비해 너무 담담하군요. 그냥 재귀적으로 convert를 호출하고 Apply를 만들 뿐입니다.
Apply가 필요한가?Apply는 그냥 App처럼 보일 수 있습니다. 실제로 이름만 바꾸지 않고 그대로 둘 수도 있습니다.
이름을 바꾸는 이유는 클로저와 함께 사용되는 의미를 강조하기 위해서입니다. 결국 우리는 최상위 아이템을 갖게 되고, 그 아이템들에 대해서는 인자를 전달하는 일반적인 호출로서 App을 사용할 수 있습니다. 그러면 구분이 의미를 갖게 됩니다: Apply는 클로저를 풀어서(unpack) 호출하고, App은 최상위 아이템을 호출합니다.
이제 convert의 모든 케이스를 다뤘으니, closure_convert에 남은 일이 있나 보죠:
fn closure_convert(ir: lowering::IR) -> ClosureConvertOutput {
// ... all our previous code
let body = conversion.convert(ir, env);
ClosureConvertOutput {
item: Item {
params,
ret_ty,
body,
},
closure_items: conversion.items,
}
}
여기도 별로 할 일이 없네요. ir을 변환한 뒤 출력 구조를 만들고 바로 반환합니다.
생각보다 덜 끔찍했습니다. 가장 큰 변화는 사실 Fun에 국소화되어 있죠.
이쯤에서 우리가 “하지 않은 것”을 말해볼 좋은 타이밍입니다. 이 클로저 변환은 몇 가지 단순화 가정을 합니다. 그중 가장 큰 것은 모든 클로저가 단 하나의 파라미터만 받는다는 점입니다.
중첩 람다 여러 개를 변환하면:
IR::fun(...,
IR::fun(...,
IR::fun(..., <body>)))
각 Fun이 자기만의 구조체와 최상위 함수를 갖게 됩니다. 하지만 낭비처럼 보이죠? 앞의 두 함수는 즉시 클로저를 반환하기만 하고, 실제 동작은 <body>에 도달해야 시작됩니다.
“진짜 일”을 하는 함수에 대해 구조체 하나와 최상위 함수 하나만 만들 수 있다면 좋겠습니다. 구조체 필드에 앞의 두 파라미터도 담고, 세 번째 파라미터까지 모두 준비됐을 때만 호출하도록 말이죠. 실제 프로덕션의 클로저 변환은 커리된(chained) 람다를 이런 식으로 처리합니다. 장점은 분명하지만 구현 복잡도가 올라갑니다.
자세한 내용은 Making a Fast Curry에 잘 정리되어 있습니다. 클로저와 필요한 런타임 지원에 대한 접근하기 쉬운 설명입니다. 다중 인자 클로저는 적용이 인자를 저장해야 하는지, 아니면 최상위 함수를 호출해야 하는지 판단하기 위한 arity 추적이 필요합니다. 모든 클로저가 단일 인자라면 이 판단은 자명합니다. 여기서는 구현을 단순화하기 위해 성능 잠재치를 일부 포기하지만, 대안이 있음을 알아두면 좋습니다.
이제 이전 IR이 클로저 변환 IR로 어떻게 바뀌는지 예제를 통해 보겠습니다. IR 항들이 커지므로, 보기 좋게 출력(pretty printing)한 형식으로 보여주겠습니다. 간결함을 위해 타입은 생략하지만 실제 IR에는 타입이 존재합니다. 이 예제에서는 사람이 읽기 쉬운 이름을 쓰지만, 실제 IR에서는 v0, v1 같은 식일 수 있다고 상상해도 됩니다. 먼저 로워링 IR부터 시작합니다:
(fun [add]
(let [
(b 3)
(f (fun [x] (add x 1)))
(g (fun [a] (add (f a) (f b))))
(id (fun [t] t))
] (id (g 2))))
클로저 변환 후보는 세 개입니다(최상위 함수는 변환하지 않는다는 점을 기억하세요): f, g, id.
첫 람다 f는 자유 변수 add 하나를 포함합니다. 본문을 담을 새 아이템을 만들고, add를 우리가 만든 env 파라미터 접근으로 바꿉니다:
(defn f_clos [env, x]
(let
[(t0 env[1])]
(apply (apply t0 x) 1)))
아이템을 만들 때 f의 본문을 변환하며, App 노드를 새 Apply 노드로 바꿉니다. 또한 env 접근을 let 바인딩하고, add를 새 이름 t0로 바꿉니다. env의 0번째 요소는 item0 자기 자신에 대한 참조입니다.
g도 비슷하게 변환됩니다:
(defn g_clos [env, a]
(let [
(t0 env[1])
(t1 env[2])
(t2 env[3])
] (apply (apply t0 (apply t1 a)) (apply t1 t2))))
이번엔 let으로 바인딩할 자유 변수가 더 많습니다. g는 add, f, b를 캡처해서 각각 t0, t1, t2가 됩니다. apply로 바뀌면서 클로저를 얼마나 자주 언패킹하는지도 잘 드러나죠.
마지막 람다 id는 사실 아무 변수도 캡처하지 않지만, 망치만 들고 있으면 모든 게 못으로 보인다고… 여전히 클로저 변환합니다:
(defn id_clos [env, t] t)
캡처 변수가 없으니 id 아이템은 짧지만, 그래도 캡처가 없는 env 파라미터를 도입합니다.
모든 것을 합치면 최종 IR은 네 개의 아이템 집합이 됩니다:
(defn f_clos [env, x]
(let
[(t0 env[1])]
(apply (apply t0 x) 1)))
(defn g_clos [env, a]
(let [
(t0 env[1])
(t1 env[2])
(t2 env[3])
] (apply (apply t0 (apply t1 a)) (apply t1 t2))))
(defn id_clos [env, t] t)
(defn main [add]
(let [
(b 3)
(f (closure f_clos [add]))
(g (closure g_clos [add, f, b]))
(id (closure id_clos []))
] (apply id (apply g 2))))
세 개의 fun이 모두 클로저로 바뀐 것을 볼 수 있습니다. 클로저는 우리가 생성한 최상위 함수를 참조하고, 캡처한 변수들을 명시적으로 추적합니다. 이 캡처 리스트로 클로저로 동작할 구조체를 구성합니다.
클로저 변환은 코드 방출(code emission)에서 남아 있던 마지막 장애물 중 하나였던 “변수 캡처”를 제거합니다. 이제 IR에는 정수, “구조체”(일반 구조체는 없지만 클로저가 그 역할을 함), 그리고 최상위 함수만 남았습니다. 모두 하드웨어에 충분히 가깝고, 머신에 어떻게 매핑되는지 상상할 수 있습니다. 늘 그렇듯 자세한 내용은 making a language 저장소에서 확인할 수 있습니다. 다음 패스는 흥미롭게도 코드 방출입니다.