명시적 스택 프레임을 값으로 표현해 호출 스택을 시뮬레이션함으로써 재귀 코드를 반복문 기반의 명령형 코드로 바꿔 스택 오버플로를 피하는 기법을 다룬다.
Joseph Junker의 소프트웨어 블로그
09 Mar 2026 재귀를 좋아한다. 전에 블로그에 썼듯, 본질적으로 재귀적인 문제를 푸는 데는 재귀 구현이 보통 가장 유지보수하기 좋다. 다만 나는 대부분의 프로그래밍을 node.js와 TypeScript로 하고, 내 코드가 스택을 넘치게 하지 않는 것도 좋아한다. 이 둘은 때때로 충돌한다.
이 글은 우아하고 유지보수하기 좋은 재귀 코드를, 명령형으로 뒤틀린 형태로 손수 변환하는 기법에 대한 것이다. 명확함(그리고 약간의 성능)을 스택 안전성과 맞바꾸는 셈이다. 이 기법은 자동화하기엔 정밀도가 조금 부족하지만, 대부분 기계적으로 진행되며, 문제 자체에 대한 창의성이나 통찰이 거의 필요 없다. 결과 구현도 그럭저럭 해독 가능하다.
이 접근의 핵심은 내가 continuation-passing style에 대한 글에서 암시했던 것이다. 스택 프레임을 일급 값으로 표현함으로써, 우리가 작업하는 언어의 호출 스택을 시뮬레이션하는 코드를 작성할 수 있다. 그 글은 CPS 함수를 표현으로 선택해(함수형 맥락에서) 재시작 가능한 예외를 흉내 내는 것 같은 초능력을 열어준다. 이번 글에서는 명령형 맥락에서, 언어 런타임의 한계를 우회하기 위해 변경 가능한 레코드를 사용해 이를 해볼 것이다.
코드 예시는 TypeScript로 제공하지만, 여기서 설명하는 일반 원리는 변경 가능성과 매개변수 다형성에 대한 기본 지원이 있는 어떤 언어로도 옮길 수 있을 것이다. TypeScript의 타입 내로잉이 우리에게 매우 유용할 것이므로, 타입 내로잉이나 패턴 매칭이 없는 언어에서는 구체 구현을 조정해야 한다.
본격 기법을 보기 전에, 문제 공간에 대한 직관을 조금 쌓는 것이 도움이 될 수 있다. 연결 리스트와 이진 트리에 대한 기본 연산부터 시작해, 어디서부터 문제가 스며들기 시작하는지 보자. 이 절은 나중 절에서 사용할 관점을 강조하기 위해 아주 기본적인 내용을 매우 꼼꼼하게 다룰 것이다.
먼저 연결 리스트를 생각해 보자:
type LinkedList<T> = {
tag: "Cons",
head: T,
tail: LinkedList<T> } | {
tag: "Nil"
};
function cons<T>(head: T, tail: LinkedList<T>): LinkedList<T> {
return { tag: "Cons", head, tail };
}
function nil<T>(): LinkedList<T> {
return {
tag: "Nil"
}
}
const exampleList = cons(1, cons(2, cons(3, nil())));A
LinkedList은 두 가지 변형을 가진 타입이다:
Cons와
Nil. 리스트를 소비한다는 것은 각 변형을 처리하는 로직을 제공한다는 뜻이다.
sumList함수를 보자:
function sumList(list: LinkedList<number>): number {
if (list.tag === "Nil") return 0;
return list.head + sumList(list.tail);
}이는 재귀 호출을 사용하므로, 리스트가 충분히 길면(내 머신에서는 대략 1만 항목 정도) node.js는 스택 오버플로를 겪고 예외를 던질 것이다. 이는 함수가 재귀 호출을 할 때마다 런타임이 이전 호출로 돌아와 남은 덧셈 연산을 끝낼 수 있도록, 이전 호출에서 “어디로 돌아가야 하는지”를 “기억”해야 하기 때문이다.
반복 형태로 변환하면 오버플로 가능성을 없앨 수 있다:
function sumListIterative(list: LinkedList<number>): number {
let sum = 0;
let pointer = list;
while (pointer.tag !== "Nil") {
sum += pointer.head;
pointer = pointer.tail;
}
return sum;
}변환된 형태에서는 리스트의 항목을 가리키는 포인터를 두고, 리스트 길이를 따라 내려가며 각 노드 내용을 더한다. 이것이 동작하는 이유는 두 가지다:
(1 + (2 + 3))는
((1 + 2) + 3)와 같은 결과를 낸다. 재귀 함수에서는 “오른쪽부터” 더하면서, 오른쪽이 끝날 때까지 해결할 수 없는 “왼쪽의” 미해결 덧셈들을 스택에 쌓는다. 반복 해법에서는 “왼쪽부터” 더하므로, 어떤 작업도 미루지 않아도 된다. 2. 연결 리스트는 본질적으로 반복적이다. 각 노드는 정확히 하나(또는 0개)의 다음 노드를 가리킨다. 데이터 구조 내부에 분기가 없기 때문에 전체를 탐색하는 것이 매우 단순하다.
이 변환의 핵심은 부분 계산을 “기억”해야 할 필요를 제거해, 상태를 들고 다닐 필요가 없는 해법으로 만드는 데 있다.
위의 2번 이점을 없애 보자. 분기 형태를 가진 데이터 구조로 바꾼다. 숫자를 담는 이진 트리를 생각하자:
type BinaryTree<T> = {
contents: T,
left: BinaryTree<T> | null,
right: BinaryTree<T> | null
}
function tree<T>(
rootContents: T,
left: BinaryTree<T> | null,
right: BinaryTree<T> | null): BinaryTree<T> {
return {
contents: rootContents,
left,
right
}
}
function leaf<T>(contents: T): BinaryTree<T> {
return {
contents,
left: null,
right: null
}
}
const exampleTree = tree(
1,
tree(2, leaf(3), leaf(4)),
tree(5, leaf(6), leaf(7))
)재귀 합계 함수는 쉽게 쓸 수 있다:
function sumTree(tree: BinaryTree<number> | null): number {
if (!tree) return 0;
const leftSum = sumTree(tree.left);
const rightSum = sumTree(tree.right);
return leftSum + rightSum + tree.contents;
}이 함수의 실행은 대략 이렇게 진행된다:
sumTree(tree.left)를 실행한다. 이때 나중에 돌아와서 마무리할 수 있도록, 원래
sumTree호출에서의 위치를 기억한다.
sumTree호출로 돌아오면,
sumTree(tree.right)를 실행한다. 다시 함수 내 위치를 기억한다.
leftSum + rightSum + tree.contents를 계산하고 호출자에게 제어를 돌려준다.
이 함수를 반복형으로 만들려면 덧셈 단계와 “기억하기” 단계를 둘 다 구현해야 한다. 이를 구현하는 표준 방법은 스택이나 큐를 쓰는 것이다:
function sumTreeIterative(tree: BinaryTree<number>): number {
const stack: Array<BinaryTree<number>> = [tree];
let total = 0;
while (stack.length) {
const node = stack.pop()!;
total += node.contents;
if (node.left) {
stack.push(node.left);
}
if (node.right) {
stack.push(node.right);
}
}
return total;
}각 노드를 만날 때마다 불행하게도 두 가지 일을 해야 한다: 왼쪽을 처리하고 오른쪽을 처리하는 일이다. 이들 또한 추가 작업을 만들어낼 수 있다. 스택은 지금 당장 탐색하지 않는 분기들을 미뤄 두고, 문제를 한 단계씩 해결하게 해준다. 반복 해법의
stack변수는 재귀 해법에서 JavaScript가 내장으로 제공하는 호출 스택과 같은 목적을 수행한다.1 원래 언어 런타임이 공짜로 제공하던 것을 직접 관리하는 부수 복잡성을 받아들이는 대신, 코드의 성능 특성을 바꿀 수 있었다.
다음 절에서는 이 책임 전가를 논리적 끝까지 밀어붙일 것이다.
연결 리스트 절에서 언급했듯, 지난 두 절의 구현은 우리가 덧셈의 결합법칙을 알아차리는 데 의존한다. 이런 알아차림은 내가 “문제의 본질에 대한 통찰”이라고 부르는 것의 예다. 문제를 잘 이해하면 창의성을 발휘해 직접적이고 우아한 해법을 구현할 수 있다. 하지만 창의성에는 한계가 있다. 어떤 문제는 이해를 잘 허용하지 않으면서도 해결은 요구한다. 그런 경우 통찰이 부족하더라도 어떻게든 헤쳐 나갈 수 있게 해주는 패턴과 휴리스틱이 바람직하다.
이 절은 대부분의 개발자가 처음부터 반복 구현을 쉽게 코딩하기 어려울 만큼 이해에 저항하는 문제를 제시한다. 그럼에도 통찰 부족을 무릅쓰고 반복 해법을 만들어낼 수 있음을 보여주겠다.
먼저 데이터 구조다. 값 하나를 담는 트리와, 트리의 연결 리스트를 담는 포리스트의 상호 재귀 쌍을 사용한다:
type Tree<T> =
| {
tag: "Empty";
}
| {
tag: "Node";
value: T;
forest: Forest<T>;
};
type Forest<T> =
| {
tag: "Nil";
}
| {
tag: "Cons";
head: Tree<T>;
tail: Forest<T>;
};
function empty<T>(): Tree<T> {
return {
tag: "Empty",
};
}
function node<T>(value: T, forest: Forest<T>): Tree<T> {
return {
tag: "Node",
value,
forest,
};
}
function nil<T>(): Forest<T> {
return {
tag: "Nil",
};
}
function cons<T>(head: Tree<T>, tail: Forest<T>): Forest<T> {
return {
tag: "Cons",
head,
tail,
};
}이 데이터 구조는 상호 재귀에 대한 Wikipedia 페이지에서 가져온 것으로, 그 페이지는 Robert Harper의 Standard ML 입문 강의 노트를 인용한다. 이 표현이 다른 대안들보다 실용적으로 더 나은 선택인 이유는(상호 재귀 데이터를 지원하는 언어 능력을 보여주는 예시 말고는) 나는 알지 못한다. 나는 이 구조가 다루기 불편하다고 느끼는데, 그래서 이 글에서 사용하기로 했다.2
예를 들어 이렇게 인스턴스화할 수 있다:
const exampleTree = node(
1,
cons(
node(2, cons(node(3, nil()), nil())),
cons(
node(4, cons(
empty(),
cons(node(6, nil()), nil()))),
nil()),
),
);시각화하면 이해가 더 쉽다. 여기서는
node호출은 보라색 타원,
cons호출은 초록색 직사각형,
empty호출은 검은 타원,
nil호출은 검은 직사각형으로 표시했다:
이 데이터 구조의 단점 하나는 “틈”이 생길 수 있다는 점이다. 4와 6으로 표시된 노드 사이의
empty()노드를 보라. 또 다른 단점은 너비와 깊이에 대한 직관적인 개념에 잘 맞지 않는다는 것이다. 노드들은 1-6으로(5가 있을 법한 곳에 빈 노드가 하나 있어 건너뛰며) 어떤 순서로든 라벨링되어 있다. 그 순서는 너비 우선인가, 깊이 우선인가, 아니면 임의인가? 답은 포리스트 안의 트리들을 형제라고 보느냐, 아니면 포리스트의 각 노드를 트리의 이진 분기라고 보느냐에 달려 있다.
이 예시 트리의 경우, 너비 우선 순회는 노드들을
12436순으로 나열하는 것으로 정의하고, 깊이 우선 순회는
12346순으로 나열하는 것으로 정의하겠다. 이 글의 나머지에서는 깊이 우선 순서를 사용할 것이다.
이제 데이터 구조를 불쾌하게 만들었으니, 재귀 함수도 다음으로 똑같이 불쾌하게 만들어야 한다. 여기서는
fold함수를 사용한다. 이는 깊이 우선 순회 중 마주치는 순서대로 트리의 노드를 소비할 수 있게 해준다. 이는 이전보다 해법에 훨씬 더 빡빡한 제약을 건다.
재귀 구현은 다음과 같다:
function foldTree<S, T>(
accumulator: S,
tree: Tree<T>,
fn: (accumulator: S, value: T) => S,
): S {
if (tree.tag === "Empty") return accumulator;
return foldForest(fn(accumulator, tree.value), tree.forest, fn);
}
function foldForest<S, T>(
accumulator: S,
forest: Forest<T>,
fn: (accumulator: S, value: T) => S,
): S {
if (forest.tag === "Nil") return accumulator;
const newAcc = foldTree(accumulator, forest.head, fn);
return foldForest(newAcc, forest.tail, fn);
}구현은 최소한이며, 내 머릿속에서는 누산기를 가지고 이 구조들을 순회하는 가장 “자연스러운” 접근이다.
노드를 만나는 대로 모으기만 하는 함수를 끼워 넣어, 중첩된 트리 구조를 평평한 배열로 단순화하면 동작을 검증할 수 있다:
function collectRecursive<T>(tree: Tree<T>): Array<T> {
return foldTree([] as Array<T>, tree, (acc, value) => [
...acc,
value,
]);
}
console.dir(collectRecursive(exampleTree));
// outputs: [ 1, 2, 3, 4, 6 ]드디어 완전한 문제 정의에 도달했다.
foldTree를 어떻게 반복 형태로 바꿀 수 있을까?
여기서의 접근은 재귀 해법을 직접 구현하려는 것이 아니다. 대신 재귀 함수를 더 명시적인 형태로 지루하게 번역할 것이다.
foldTree의 실행에 무엇이 필요한지 생각해 보자. 세 가지 인자를 받는다: 누산기, 트리, 함수. 재귀 자식 호출을 0개 또는 1개 만든다. 실행 후 반환값을 만든다.
이 모든 것을 위한 데이터 구조를 만들고, 함수 실행의 스택 프레임을 표현할 것이다:
type FoldTreeFrame<S, T> = {
tag: "FoldTreeFrame";
accumulator: S;
tree: Tree<T>;
fn: (accumulator: S, value: T) => S;
child: FoldForestFrame<S, T> | null;
returnValue: null | {
value: S;
};
parent: StackFrame<S, T>;
};또한 스택 프레임의 부모, 즉 이 프레임을 호출한 스택 프레임도 추적하고 있다. 이는 나중에 설명할 기계적인 이유 때문이다.
child는
null일 수 있는데, 이는
foldTree가 자식을 만들지 않고 조기에 종료할 수 있기 때문이다.
returnValue는 프레임이 처음 생성될 때는
null이고, 프레임 실행이 끝나면 채워진다.
마찬가지로
foldForest에 대한 스택 프레임도 정의할 수 있다:
type FoldForestFrame<S, T> = {
tag: "FoldForestFrame";
accumulator: S;
forest: Forest<T>;
fn: (accumulator: S, value: T) => S;
treeChild: FoldTreeFrame<S, T> | null;
forestChild: FoldForestFrame<S, T> | null;
returnValue: null | {
value: S;
};
parent: StackFrame<S, T>;
};마지막으로, 재귀 함수의 바깥 호출자를 나타내는 최외곽 프레임도 필요하다:
type ExternalCaller<S, T> = {
tag: "ExternalCaller";
topFrame: FoldTreeFrame<S, T> | null;
};
type StackFrame<S, T> =
| FoldTreeFrame<S, T>
| FoldForestFrame<S, T>
| ExternalCaller<S, T>;이제 재귀 함수를 시뮬레이션하는 함수를 작성할 것이다. 이는 실행 중 계산을 설명하는
StackFrame객체들을 만들고 수정한다. 재귀 함수가 호출될 때 발생하는 함수 호출 트리를 생각해 보라. 우리는 정확히 그 트리를, 우리가 순회하고 변경할 수 있는 데이터 구조로 표현하고 있다.
여러 데이터 타입을 구성하기 위한 보일러플레이트 함수를 만들어 두면 더 쉽다. 이름 선택을 제외하면 구현 자체는 흥미롭지 않다.
function callFoldTree<S, T>(
accumulator: S,
tree: Tree<T>,
fn: (accumulator: S, value: T) => S,
parent: FoldForestFrame<S, T> | ExternalCaller<S, T>,
): FoldTreeFrame<S, T> {
return {
tag: "FoldTreeFrame",
accumulator,
fn,
tree,
child: null,
returnValue: null,
parent,
};
}
function callFoldForest<S, T>(
accumulator: S,
forest: Forest<T>,
fn: (accumulator: S, value: T) => S,
parent: FoldTreeFrame<S, T> | FoldForestFrame<S, T>,
): FoldForestFrame<S, T> {
return {
tag: "FoldForestFrame",
accumulator,
forest,
fn,
treeChild: null,
forestChild: null,
returnValue: null,
parent,
};
}
function externalCaller<S, T>(
): ExternalCaller<S, T> {
return {
tag: "ExternalCaller",
topFrame: null,
};
}시작으로, 재귀 함수의 골격을 만들자. 이 함수는 바깥쪽 부모로
ExternalCaller를 만들고, 이를 가리키는
FoldTreeFrame을 만들어 초기화한다. 현재 처리 중인 프레임을 변경 가능한 변수에 저장하고, 루프에서 처리한다.
function foldIterative<S, T>(
accumulator: S,
tree: Tree<T>,
fn: (accumulator: S, value: T) => S,
): S {
const caller: ExternalCaller<S, T> = externalCaller();
const topFrame = callFoldTree(accumulator, tree, fn, caller);
caller.topFrame = topFrame;
let frame: StackFrame<S, T> = topFrame;
while (frame.tag !== "ExternalCaller") {
if (frame.tag === "FoldTreeFrame") {
// Implementation for foldTree() goes here
} else if (frame.tag === "FoldForestFrame") {
// Implementation for foldForest() goes here
}
}
return frame.topFrame?.returnValue?.value!;
}루프를 빠져나오는 조건은 현재 프레임이 최외곽 호출자일 때이며, 그 시점에 자식의
returnValue에 접근한다.
foldTree와
foldForest의 개별 구현은 각 단계에서
frame변수가 어떤 스택 프레임을 가리키는지를 바꾸는 책임을 진다.
TypeScript의 타입 내로잉은 이 구현 내내 우리의 친구가 될 것이다. 어느 시점이든 우리가 어떤 종류의 프레임을 다루는지 결정해야 하며, 그래서 타입에 있는
tag필드가 필수적이다.
먼저
foldTree경우의 구현을 보자. 참고로 우리가 대체하는 함수는 다음이다:
function foldTree<S, T>(
accumulator: S,
tree: Tree<T>,
fn: (accumulator: S, value: T) => S,
): S {
if (tree.tag === "Empty") return accumulator;
return foldForest(fn(accumulator, tree.value), tree.forest, fn);
}그리고 이를 다음처럼 대체한다:
if (frame.tag === "FoldTreeFrame") {
if (frame.tree.tag === "Empty") {
// Block 1
frame.returnValue = { value: frame.accumulator };
frame = frame.parent;
} else {
if (frame.child?.returnValue) {
// Block 2
frame.returnValue = {
value: frame.child.returnValue.value,
};
frame.child = null;
frame = frame.parent;
} else {
// Block 3
const newAccumulator = fn(
frame.accumulator,
frame.tree.value,
);
frame.child = callFoldForest(
newAccumulator,
frame.tree.forest,
frame.fn,
frame,
);
frame = frame.child;
}
}
}“Block 1”로 라벨된 코드는 트리가 비어 있을 때 실행된다. 현재 스택 프레임의 결과 값을 프레임의 누산기 인자로 설정하고, 제어를 부모 프레임으로 되돌린다(활성 프레임을 부모를 가리키게 바꿈으로써). 이는 재귀 구현의 동작과 동일하다.
마찬가지로 “Block 3”은 트리가 비어 있지 않고, 이 프레임의 자식 호출이 아직 완료되지 않았을 때 실행된다. 이 경우 누산기와 트리의 내용을
fn에 넘긴 뒤 새로운 누산기로 포리스트 폴드를 호출한다. 이 “호출”은 자식 호출을 위한 스택 프레임을 만들고
frame = frame.child로 제어를 넘기는 방식으로 이루어진다. 논리적으로는 재귀 구현의 두 번째 경우와 일치한다.
“Block 2”는 재귀 함수의 어떤 코드와도 직접적으로 대응하지 않는다. 순수한 부수 복잡성이다.
FoldTreeFrame을 처리할 때, 부모 호출이 생성한 뒤 처음 진입한 것일 수도 있고, 자식 프레임 실행이 끝난 뒤 다시 진입한 것일 수도 있다. 따라서 블록 3에서 재귀 호출을 만들기 전에 그 호출이 이미 완료됐는지 확인해야 한다. 완료됐다면 재귀 호출 이후에 해야 할 로직을 실행한다. 이 경우
foldTree에는 그런 로직이 없으므로, 부모 프레임으로 돌아가는 기계적 처리만 하면 된다.
반환하기 위해 우리는 세 가지를 한다:
null로 설정한다
frame포인터를 갱신한다
정리 단계는 이상해 보일 수 있지만 메모리 사용 최적화다. 언어 런타임이 일련의 함수 호출을 실행할 때, 이미 종료한 스택 프레임을 계속 붙잡아 둘 필요가 없다. 분기 호출들은 시간 차원에서만 트리를 이룬다. 어느 한 시점의 스냅샷에서 메모리에 존재하는 것은 오직 하나의 호출 스택뿐이며, 트리 안에서 현재 경로를 따라간다. 자식 프레임들을
null로 설정하지 않으면, 전체 트리를 메모리에 쌓아 올리고 재귀 처리가 끝날 때까지 유지하게 된다. 참조를 제거하면 런타임이 여유 있을 때 메모리를 회수할 수 있다. JavaScript에서 수동 메모리 관리를 해보고 싶었다면, 지금이 기회다!
이제 모든 트릭을 다 다뤘고,
foldForest()번역은 같은 패턴의 반복이다:
if (frame.tag === "FoldForestFrame") {
if (frame.forest.tag === "Nil") {
frame.returnValue = { value: frame.accumulator };
frame = frame.parent;
} else {
if (frame.forestChild?.returnValue) {
frame.returnValue = {
value: frame.forestChild.returnValue.value,
};
frame.treeChild = null;
frame.forestChild = null;
frame = frame.parent;
} else if (frame.treeChild?.returnValue) {
frame.forestChild = callFoldForest(
frame.treeChild.returnValue.value,
frame.forest.tail,
frame.fn,
frame,
);
frame = frame.forestChild;
} else {
frame.treeChild = callFoldTree(
frame.accumulator,
frame.forest.head,
frame.fn,
frame,
);
frame = frame.treeChild;
}
}
}포리스트를 폴드하려면 두 번의 재귀 호출이 필요하다. 따라서 둘 다 완료 여부를 확인해야 하고, 포리스트 프레임을 종료할 때 둘 다 정리해야 한다.
끝이다! 조각들을 합치면 최종 구현은 다음과 같다:
function foldTreeIterative<S, T>(
accumulator: S,
tree: Tree<T>,
fn: (accumulator: S, value: T) => S,
): S {
const caller: ExternalCaller<S, T> = externalCaller();
const topFrame = callFoldTree(accumulator, tree, fn, caller);
caller.topFrame = topFrame;
let frame: StackFrame<S, T> = topFrame;
while (frame.tag !== "ExternalCaller") {
if (frame.tag === "FoldTreeFrame") {
if (frame.tree.tag === "Empty") {
frame.returnValue = { value: frame.accumulator };
frame = frame.parent;
} else {
if (frame.child?.returnValue) {
frame.returnValue = {
value: frame.child.returnValue.value,
};
frame.child = null;
frame = frame.parent;
} else {
const newAccumulator = fn(
frame.accumulator,
frame.tree.value,
);
frame.child = callFoldForest(
newAccumulator,
frame.tree.forest,
frame.fn,
frame,
);
frame = frame.child;
}
}
} else if (frame.tag === "FoldForestFrame") {
if (frame.forest.tag === "Nil") {
frame.returnValue = { value: frame.accumulator };
frame = frame.parent;
} else {
if (frame.forestChild?.returnValue) {
frame.returnValue = {
value: frame.forestChild.returnValue.value,
};
frame.treeChild = null;
frame.forestChild = null;
frame = frame.parent;
} else if (frame.treeChild?.returnValue) {
frame.forestChild = callFoldForest(
frame.treeChild.returnValue.value,
frame.forest.tail,
frame.fn,
frame,
);
frame = frame.forestChild;
} else {
frame.treeChild = callFoldTree(
frame.accumulator,
frame.forest.head,
frame.fn,
frame,
);
frame = frame.treeChild;
}
}
}
}
return frame.topFrame?.returnValue?.value!;
}미적으로 점수를 딸 코드는 아니지만, 동작한다.
…진짜 동작하긴 하겠지?
초기 재귀 구현은 논리 코드 5줄과 타입 정의 6줄로 이루어져 있었다. 모든 데이터는 불변이었고, 구현은 데이터 모양에 의해 사실상 강제됐다. 이런 제약에서는, 틀리게 만드는 것보다 맞게 만드는 게 더 쉬울 정도다. 반면 반복 구현은(타입 정의와 헬퍼 함수는 세지도 않고) 길이가 열 배가 넘고, 변경 가능성을 마구 사용하며, 잠재적 엣지 케이스로 가득하다. 이걸 어떻게 테스트하고 유지보수하냐는 질문은 피할 수 없다.
다행히 비교적 쉬운 답이 있다. 반복 해법의 내부 구현을 전혀 들여다보지 않고도 정확성을 확신할 수 있다. 대신 먼저 더 단순한 기준(reference) 구현의 정확성을 확신하고, 그 다음 두 구현이 동등하다는 것을 확신하면 된다.
재귀 구현을 유닛 테스트하는 과정은 여기서 다루지 않겠다. 충분히 단순하므로, 이 글에서는 그 정확성을 자명한 것으로 두겠다. 여기서 집중할 것은 두 구현이 서로 교환 가능하다는 것을 확신하는 단계다.
두 구현은 가능한 모든 입력에 대해 항상 같은 출력을 만든다면 동등하다. 불행히도 가능한 모든 입력을 생성할 수는 없으므로, 매우 큰 대표 표본을 생성하는 것으로 만족해야 한다. 이는 속성 기반 테스트의 영역이다. 내가 아는 한
fast-check는 현재 TypeScript에서 가장 성숙한 속성 기반 테스트 라이브러리이며, 여기서 사용할 것이다.
fast-check와 속성 기반 테스트 전반에 대한 완전한 설명은 이 글의 범위를 벗어나며, 더 많은 정보는 프로젝트의 문서를 참고하길 권한다. 다만 요약하면, 주어진 타입의 랜덤 데이터를 생성하는 생성기(generator)를 만들 수 있다. 상호 재귀
Tree<T>타입을
Tree<number>로 특수화한 생성기는 다음과 같다:
const arbitraries = fc.letrec((tie) => ({
empty: fc.constant({ tag: "Empty" }),
node: fc.record({
tag: fc.constant("Node"),
value: fc.nat(),
forest: tie("forest"),
}),
tree: fc.oneof(tie("empty"), {
arbitrary: tie("node"),
weight: 5,
}),
nil: fc.constant({ tag: "Nil" }),
cons: fc.record({
tag: fc.constant("Cons"),
head: tie("tree"),
tail: tie("forest"),
}),
forest: fc.oneof({ depthSize: "medium" }, tie("nil"), {
arbitrary: tie("cons"),
weight: 5,
}),
}));letrec는 서로를 이름으로 참조하는 상호 재귀 데이터 타입을 정의할 수 있게 해준다.
oneof는 항목 배열 중 하나를 고르는데, 배열 앞쪽 항목에 편향된다. 따라서 비재귀 케이스를 먼저 넘겨야 한다.
weight와
depthSize는 큰 출력과 작은 출력이 적당히 섞이도록 튜닝하는 데 사용한다.
fast-check로 재귀 데이터를 생성할 때는 보통
statistics함수를 사용해 생성기들이 괜찮은 표본을 만들고 있는지 확인하는 것이 좋다3. 예시는 다음과 같다:
fc.statistics(
arbitraries.tree as fc.Arbitrary<Tree<number>>,
(tree) => {
const nodeCount = foldTree(0, tree, (acc, node) => acc + 1);
if (nodeCount < 5) return "Under 5 nodes";
if (nodeCount < 10) return "5 to 10 nodes";
return "10 nodes or more";
},
{ numRuns: 5000 },
);이를 실행해 보면 생성된 트리의 40%가 5-10 노드이고, 10%가 10+ 노드임을 보여준다. 내게는 꽤 괜찮은 표본처럼 느껴진다.
이제 테스트 데이터 생성기가 있으니, 함수 동작이 일치함을 단언(assert)하기만 하면 된다. 나는
uvu테스트 러너를 사용해 다음처럼 한다:
test("Equivalence", () => {
fc.assert(
fc.property(arbitraries.tree as fc.Arbitrary<Tree<number>>, (tree) => {
function foldingFn(
acc: Array<number>,
value: number,
): Array<number> {
return [...acc, value];
}
const recursiveResult = foldTree(
[] as Array<number>,
tree,
foldingFn,
);
const iterativeResult = foldTreeIterative(
[] as Array<number>,
tree,
foldingFn,
);
assert.equal(recursiveResult, iterativeResult);
}),
{ numRuns: 500 },
);
});
test.run();값을 배열로 모으는 폴딩 함수를 선택했는데, 이는 순회 순서가 동일함을 확인하기가 아주 쉽기 때문이다. 테스트는 몇 분 만에 작성할 수 있었고, (내 머신에서) 실행 시간도 20 ms 미만이었다. 아주 뒤틀린 코드의 정확성을 확신하기에 꽤 싼 비용이다.
속성 기반 테스트가 있다면, 재귀 기준 구현을 유지하고 테스트 오라클로 사용하기만 한다면 이 글의 기법들은 프로덕션 코드베이스에도 충분히 적절하다고 본다.
i에 점 찍고 t를 가로지르기 위해, 이 글의 기법이 성능에 어떤 영향을 주는지 보여주는 것이 중요하다고 생각한다. 스택 안전성을 얻기 위해 이 과정을 견딜 의사가 있다면, 작업 대상은 적어도 어느 정도 성능 민감할 가능성이 크다.
나는 node 성능 벤치마킹 전문가와는 거리가 멀지만, 내가 취한 접근은 다음과 같다.
먼저 랜덤 트리를 생성하는 스크립트를 작성했다:
function randomNat(): number {
return Math.floor(Math.random() * 1000);
}
function generateTree(size: number): Tree<number> {
if (size <= 1) return empty();
return node(randomNat(), generateForest(size - 1));
}
function generateForest(size: number): Forest<number> {
if (size <= 1) return nil();
const treeSizeDecrease = Math.random() < 0.5 ? 0 : -1;
const forestSizeDecrease = Math.random() < 0.5 ? 0 : -1;
const treeToForestRatio = Math.random();
const treeSize = Math.floor(size * treeToForestRatio) + treeSizeDecrease;
const forestSize =
Math.floor(size * (1 - treeToForestRatio)) + forestSizeDecrease;
return cons(generateTree(treeSize), generateForest(forestSize));
}
export function generateData(): Array<Tree<number>> {
let results: Array<Tree<number>> = [];
for (let i = 0; i < 10000; i += 10) {
results.push(generateTree(i));
}
return results;
}목표는 작은 것부터 큰 것까지 다양한 크기와 다양한 모양의 트리를 생성하는 것이었다.
generateForest는 시간이 지나며 트리 크기가 대체로 감소하도록 만들고, 크기의 어느 정도를 트리 자식과 포리스트 자식에 배분할지 무작위로 선택한다.
generateData는 점점 커지는 크기의 트리 1000개를 만든다. 출력에 대해 기본 통계를 내 보면 0에서 2000 노드 사이의 트리가 비교적 고르게 분포함을 확인할 수 있다.
성능 테스트는 두 가지 워크로드로 수행했다. 각 트리의 내용을 합산하는 것과, 내용을 배열로 수집하는 것이다.
function sumIterative(): Array<number> {
let result = new Array(trees.length);
for (let i = 0; i < trees.length; i++) {
result[i] = foldTreeIterative(0, trees[i]!, (acc, x) => acc + x);
}
return result;
}
function sumRecursive(): Array<number> {
let result = new Array(trees.length);
for (let i = 0; i < trees.length; i++) {
result[i] = foldTreeRecursive(0, trees[i]!, (acc, x) => acc + x);
}
return result;
}
function collectIterative(): Array<Array<number>> {
let result: Array<Array<number>> = new Array(trees.length);
for (let i = 0; i < trees.length; i++) {
result[i] = foldTreeIterative(
[] as Array<number>,
trees[i]!,
(acc, x) => {
acc.push(x);
return acc;
},
);
}
return result;
}
function collectRecursive(): Array<Array<number>> {
let result: Array<Array<number>> = new Array(trees.length);
for (let i = 0; i < trees.length; i++) {
result[i] = foldTreeRecursive(
[] as Array<number>,
trees[i]!,
(acc, x) => {
acc.push(x);
return acc;
},
);
}
return result;
}각 함수를 10번 실행하는 데 걸리는 시간을 측정했다. 각 실행 전에 가비지 컬렉터를 수동으로 호출했고, V8 최적화기가 워밍업되도록 타이머를 시작하기 전에 2번 반복 실행했다. 30회 실행 후 결과는 다음과 같았다(시간 단위는 밀리초):
Iterative sum results:
----------------------
minimum: 1267.5
maximum: 1286.5
mean: 1276.4
median: 1276.0
std. deviation: 4.66
Recursive sum results:
----------------------
minimum: 557.3
maximum: 582.2
mean: 566.9
median: 565.0
std. deviation: 6.9
Iteration is 2.25x slower than recursion
Iterative collection results:
-----------------------------
minimum: 1377.3
maximum: 1402.1
mean: 1391.0
median: 1391.8
std. deviation: 5.42
Recursive collection results:
-----------------------------
minimum: 651.4
maximum: 666.1
mean: 657.9
median: 656.2
std. deviation: 4.45
Iteration is 2.12x slower than recursion2.2배 느려지는 것은 생각보다 나쁘지 않다. 핵심 개념이란 게, 고도로 최적화된 C++ 엔진이 보통 수행하는 일을 사용자 수준의 JavaScript 코드로 하겠다는 것이기 때문이다.4
전체 벤치마크 코드는 GitHub에 있는 이 글의 예제 코드에서 볼 수 있다.
여기서의 주요 한계는, 이 기법들이 다형 재귀(polymorphic recursion) 함수에는 적용되지 않는다는 점이다. 다형 재귀에 관한 Wikipedia 페이지에서 가져와 각색한 다음 타입을 보자:
type Nested<T> = {
head: T;
tail: Nested<Array<T>>;
} | null;Nested는 자기 자신으로 정의되는 재귀 타입이지만,
Nested의 재귀 호출은 원래와 다른 타입을 인자로 받는다(
Array래퍼 때문이다).
Nested<number>타입의 데이터는 숫자 배열의 연결 리스트이며, 숫자 배열의 배열, 숫자 배열의 배열의 배열…처럼, 리스트의 각 항목이 이전 항목보다 더 깊게 중첩된다.
T의 타입은 타입을 펼쳐 나갈수록 변한다. TypeScript는 이 타입을 처리하는 재귀 함수를 작성하는 것을 허용한다:
function length<T>(nested: Nested<T>): number {
if (!nested) return 0;
return 1 + length(nested.tail);
}반복 구현에서는
frame이 데이터 구조 조각을 담은 스택 프레임을 가리키는 포인터다. 다형 재귀의 경우 루프를 한 번 돌 때마다
frame의 타입이 바뀌어야 하는데, TypeScript는 이를 허용하지 않는다.
Verity는 트램폴린과 존재 타입(existential type) 인코딩을 사용한 구현으로 이에 진전을 이뤘다. 반복 해법이 존재할 가능성은 매우 높지만, 여기서 보여준 기법은 이를 처리하기엔 충분히 강력하지 않은 듯하다.
이 주제에 대해 내가 알고 싶은 것들이 여럿 있다.
나는 TypeScript로 Uniplate를 포팅하는 과정에서 스스로 이런 방식의 재귀 사고법에 도달했는데, 이는 다양한 명령형 환경에서 자연스럽게 떠오를 법한 종류의 것처럼 보인다. 내가 첫 번째, 두 번째, 백 번째로 떠올린 사람이라고는 믿기 어렵다. 다른 사람들의 접근에 대한 참고 자료가 있으면 정말 좋겠다.
다형 재귀 함수를 반복 가능하게 만드는 다른 시도들에 대해 매우 궁금하다. 동시에, TypeScript에서 다형 재귀 함수가 실용적인 응용을 가질 수 있는지 자체도 궁금하다. (핑거 트리가 후보가 될 수는 있지만, 성능 때문에 “실용적”이라고 할 수 있을지는 모르겠다.) Chris Okasaki의 학위 논문 “Purely Functional Data Structures”가 좋은 출발점일 수 있다.
유지보수와 추론이 더 쉬운 코드를 만들 수 있는 대안적 접근들도 궁금하다. Verity는 지퍼(zippers)에 기반한 인코딩도 보여줬는데, 이것도 또 다른 길일 수 있다. 재귀 함수를 CPS 인코딩에서 시작하는 것도 흥미로운 가능성을 줄 것 같다.
이 질문들 중 어떤 것에 대한 답을 알고 있다면, 연락해 달라!
Abhinav Sarkar는 CPS 변환으로 시작해 재귀 함수의 변환을 바탕으로 트리 이터레이터를 기계적으로 도출하는, 비슷한 주제의 글을 썼다.
이 글의 초기 초안에 피드백을 제공해 준 tendstofortytwo, PolyWolf, Verity에게 감사한다.
이 글의 모든 코드 예시는 Creative Commons 0 라이선스에 따라 퍼블릭 도메인으로 공개된다. 코드 예시와 전체 라이선스 텍스트는 여기에서 찾을 수 있다.
실제로 종이에 풀어 보면, 반복 접근에서 수동으로 유지하는 스택 크기의 변화가 재귀 접근에서 node의 내장 호출 스택 크기 변화와 직접적으로 대응함을 알 수 있다.↩
실용적 용도로는 이 상호 재귀 트리/포리스트 쌍이 로즈 트리의 엄격히 더 나쁜 버전처럼 보인다. 로즈 트리는 다음처럼 정의할 수 있다:
type RoseTree<A> = { value: A, children: Array<RoseTree<A>>}. 로즈 트리는 내가 가장 좋아하는 데이터 구조다. 어떤 경우에는
children가 배열보다 연결 리스트가 더 적합할 수도 있어서 두 구조가 더 가까워지지만, 로즈 트리는 틈을 포함할 수 없고 정의가 상호 재귀가 아니라는 점에서 유리하다.↩
statistics호출들은 생성기 개발 중에 사용한다. 테스트 스위트 실행의 일부로 통계를 실행하진 않을 것이다.↩