이터레이터(내부/외부), 제너레이터(yield), 코루틴(비대칭/대칭)과 협력 스레드의 개념과 구현, 표현력, 그리고 예제를 통해 제어의 반전을 설명한다.
프로그램은 종종 어떤 데이터 구조를 순회하면서 그 구조의 각 원소에 대해 어떤 동작을 수행해야 한다. 예를 들어, 다음은 정수의 연결 리스트 요소를 출력하는 C 코드다:
for (list l = lst; l != NULL; l = l->tail) printf("%d\n", l->head);
이 코드는 두 가지 관심사를 뒤섞고 있다: 리스트를 순회하는 것과 각 원소에 대해 “출력” 동작을 수행하는 것. 이터레이터는 이 두 관심사를 더 잘 분리하는 방법이다. 이들은 데이터 구조의 순회를 추상화하여, 서로 다른 동작과 더 쉽게 재사용할 수 있게 해준다.
이터레이터에는 두 가지 맛이 있다: 함수형 언어가 선호하는 내부 이터레이터와, 명령형 및 객체지향 언어가 선호하는 외부 이터레이터다.
내부 이터레이터는 고차 함수로, 순회할 데이터 구조와 그 요소에 적용할 함수를 인자로 받는다. 리스트에 대한 가장 단순한 이터레이터는 OCaml의 List.iter로, 리스트의 각 요소에 함수를 적용하고 함수의 결과는 버린다. 이것을 이용해 정수 리스트를 출력할 수 있다:
List.iter (fun n -> printf "%d\n" n) lst
리스트에 대한 다른 유용한 이터레이터로는 List.map(리스트의 각 요소에 함수를 적용하고 결과 리스트를 반환)과 List.fold_left(이항 함수를 이용해 리스트를 축약)가 있다. 그들의 OCaml 타입과 정의는 다음과 같다:
let rec iter : ('a -> unit) -> 'a list -> unit = fun f l ->match l with [] -> () | h :: t -> f h; iter f t let rec map : ('a -> 'b) -> 'a list -> 'b list = fun f l ->match l with [] -> [] | h :: t -> f h :: map f t let rec fold_left : ('res -> 'a -> 'res) -> 'res -> 'a list -> 'res = fun f accu l ->match l with [] -> accu | h :: t -> fold_left f (f accu h) l
외부 이터레이터는 데이터 구조 내의 위치를 추상적으로, 데이터 구조와 무관하게 표현하는 “커서” 객체다. 예를 들어 Java에서 이터레이터 객체는 두 개의 메서드를 갖는다: next(현재 위치의 값을 반환하고 커서를 다음 위치로 이동)와 hasNext(다음 원소가 있는지, 아니면 구조의 끝에 도달했는지 알려줌). 이터레이터는 보통 hasNext가 true인 동안 반복하는 루프에서 사용된다:
for (Iterator<Int> i = lst.iterator(); i.hasNext(); ) { System.out.println(i.next()); }
이 프로그래밍 관용구가 너무 흔하기 때문에 Java(버전 1.5 이상)는 이를 특별히 지원한다:
for (int n : lst) { System.out.println(n); }
Python은 이터레이터를 사용하는 많은 구문과 라이브러리 함수를 제공한다: for 루프뿐 아니라, 컴프리헨션과 sum, min, max, map 같은 많은 집계 연산도 포함된다.
제어의 반전.두 종류의 이터레이터 사이에는 근본적인 차이가 있다: 외부 이터레이터는 사용자가 제공한 동작을 호출하는 함수이고, 내부 이터레이터는 그 메서드가 사용자 제공 코드에서 호출되는 객체다. 이 차이를 제어의 반전(inversion of control)이라고 하며, 종종 “우리를 부르지 마세요, 우리가 당신을 부를게요!”라는 문구로 요약된다.
외부 이터레이터가 제공하는 반전된 제어는 여러 데이터 구조를 동시에 순회하기 쉽게 해준다. 내부 이터레이션 스타일로 이것을 하려면 보통 새로운 이터레이터를 작성해야 하며, 구현이 어려울 수 있다. 예를 들어 “동일 프린지 문제”를 생각해 보자: 두 이진 탐색 트리가 서로 다른 균형을 가지더라도 동일한 값 집합을 포함하는지 판단하는 문제다. 다음은 외부 이터레이터를 사용한 Java의 간단한 해결책이다:
boolean same_fringe(TreeSet<T> s1, TreeSet<T> s2) { Iterator<T> i1 = s1.iterator(); Iterator<T> i2 = s2.iterator(); while (i1.hasNext() && i2.hasNext()) { if (! i1.next().equals(i2.next())) return false; } return ! i1.hasNext() && ! i2.hasNext(); }
동일 프린지 문제를 두 트리에 대한 직접 재귀만으로 해결하는 것은 훨씬 더 어렵다. 독자들은 도전해 보기 바란다.
외부 이터레이터 구현은 객체지향 언어에서 쉽다: 데이터 구조를 순회하는 동안 “현재 어디에 있는지” 기억하기 위해 이터레이터 객체의 인스턴스 변수를 사용하면 된다.
예를 들어, 다음은 배열에 대한 Java 이터레이터다:
class ArrayIterator<T> { private T[] arr; private int i; boolean hasNext() { return i < arr.length; } T next() { T res = arr[i]; i++;return res; } ArrayIterator(T [] arr) { this.arr = arr; this.i = 0; } }
우리는 일반적인 for 루프를 이용한 배열의 직접 순회에서도 나타나는 코드 부분을 밑줄로 표시했다:
for (int i = 0; i < arr.length; i++) { process(arr[i]); }
이터레이터는 Scheme과 OCaml 같은 함수형-명령형 언어에서도 구현하기 쉽다. 예를 들어, 다음은 OCaml로 작성된 배열 이터레이터다:
let array_iterator (arr: 'a array) : unit -> 'a option = let i = ref 0 in fun () ->if !i >= Array.length arr then None else (let res = arr.(!i) in incr i; Some res)
array_iterator arr의 결과는 각 호출마다 다음 배열 요소(있다면)를 반환하는 함수다. 반복의 위치는 내부 가변 상태(함수에서 자유 변수로 캡처된 참조 i)로 유지된다.
또한 어떤 이터레이터에도 적용되며 반복의 끝을 예외로 알리는, Python 스타일의 next 함수를 정의할 수 있다:
exception StopIteration let next (iter: unit -> 'a option) : 'a = match iter() with Some x -> x | None -> raise StopIteration
순수 함수형 언어에서는 next 연산이 인자로 전달된 커서를 갱신할 수 없다; 대신 현재 요소와 함께 다음 요소를 가리키는 커서를 반환해야 한다. 이는 이터레이터를 열거(enumeration), 즉 수요에 따라 평가되는 요소들의 리스트로 표현하는 것으로 이어진다. 예를 들어 OCaml에서:
type 'a iter = unit -> 'a enum and 'a enum = Done | More of 'a * 'a iter
i가 이터레이터라면, i ()는 열거의 머리 평가를 유발한다. 이는 반복의 끝에 도달했다면 Done이고, 반복의 다음 요소가 x이고 나머지 반복이 j라면 More(x, j)다. 이 스타일로 배열과 트리에 대한 이터레이터를 작성할 수 있다:
let array_iterator (arr: 'a array) : 'a iter = let rec iter i () = if i >= Array.length arr then Done else More(arr.(i), iter (i+1)) in iter 0 type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree let tree_iterator (t: 'a tree) : 'a iter = let rec iter t k () = match t with | Leaf -> k | Node(l, x, r) -> iter l (More(x, iter r k)) () in iter t Done
순수 이터레이터로 프로그래밍하는 것은 리스트로 프로그래밍하는 것과 비슷하다. 예를 들어, 수요에 따라 평가되는 두 리스트를 비교하는 방식으로 “동일 프린지” 문제를 다시 보자:
let rec same_iter (i1: 'a iter) (i2: 'a iter) : bool = match i1(), i2() with | Done, Done ->true | More(h1, t1), More(h2, t2) -> h1 = h2 && same_iter t1 t2 | _, _ ->false let same_fringe (t1: 'a tree) (t2: 'a tree): bool = same_iter (tree_iterator t1) (tree_iterator t2)
7.2절은 이른바 CPS 변환을 사용해 내부 이터레이터로부터 순수한 외부 이터레이터를 도출하는 체계적인 방법을 보여준다. 제어 연산자도 이 목적에 사용할 수 있으며, 8.7절과 10.3절에서 보여준다.
제너레이터는 “직접 스타일(direct style)”로 작성된 이터레이터다. 이는 위의 4.1절에서 설명한, 인스턴스 변수나 기타 가변 상태가 호출 간 반복 상태를 명시적으로 전달하는 명시적 스타일과 대조된다. 직접 스타일에서 제너레이터는 정상적인 함수처럼 작성되지만, 하나씩 순차적으로 여러 결과를 yield(산출)한다.
예를 들어, 다음은 배열을 순회하는 Python 제너레이터다:
def elements(a): for i in range(len(a)): yield a[i]
yield 문은 반복에서 다음 값을 만들어 내고, 제너레이터 사용자에게 제어를 되돌린다. 그러나 일반 함수의 return과 달리, yield는 elements의 실행 상태(로컬 변수 a와 i, 그리고 yield 바로 다음의 프로그램 지점)도 저장한다. 반복의 다음 값이 요청되면, elements의 실행은 중단했던 곳, 즉 yield 문 바로 다음에서 재개된다. for 루프가 끝난 뒤 elements 함수가 반환되면 반복은 종료된다.
전형적인 Python 스타일로, 제너레이터는 for 루프에서 사용할 수 있다:
for i in elements([1,2,3]): print(i)
또한 반복의 다음 값을 가져오기 위해 next 문을 더 명시적으로 사용할 수도 있다:
g = elements([1,2]) # 제너레이터 반환 print(next(g)) # "1" 출력print(next(g)) # "2" 출력print(next(g)) # StopIteration 예외 발생
이처럼 yield 키워드가 한 번에 하나의 값을 생성하는 제너레이터 스타일은 1975년 CLU 언어에서 도입되었다. CLU 제너레이터는 for 루프 안에서만 사용할 수 있고 일급 값은 아니지만, 효율적인 스택 기반 구현을 갖는다(Atkinson et al., 1978). 문자열 처리 언어 Icon은 제너레이터를 광범위하게 사용하는데, 여러 값을 갖는 표현식으로 제시되며 일급 값으로 사용할 수 있다(Griswold, 1988). Python 언어는 제너레이터를 대중화했는데, 설계 과정 후반에 추가되었음에도 그렇다(Schemenauer et al., 2001).
수요에 따라 무한 수열을 생성하는 것은 제너레이터의 전형적 용례다. 예를 들어, 다음은 소수(prime) 수열을 생성하는 Python 제너레이터다:
def primes(): """소수 생성기""" p = [2]; yield 2 m = 3 while True: i = 0 while i < len(p) and p[i] * p[i] <= m: if m % p[i] == 0: break i += 1 else: p.append(m); yield m m += 2
이는 3, 5, 7, …의 연속 홀수를 소수 판정하는 체(에라토스테네스 체와 유사) 알고리즘이다. 이미 발견한 소수는 로컬 배열 p에 보관한다. 무한 루프(while True)에 주목하라: 반복은 스스로 끝나지 않는다; 결국 next 호출을 멈추는 것은 제너레이터의 사용자다. 예를 들어, 다음은 primes 제너레이터를 사용해 어떤 수의 소인수 분해를 수행하는 코드다:
def factor(n): """n의 소인수 분해를 출력""" pr = primes() while n > 1: p = next(pr) while n % p == 0: print(p); n = n // p
제너레이터 컴파일: 제너레이터는 보통 이터레이터 객체로 구현된다. 제너레이터의 각 로컬 변수는 객체의 인스턴스 변수로 바뀌어 호출 간에 지속된다. yield 문은 next 메서드의 return 문으로 바뀐다. 하지만, 제너레이터 코드에서 “현재 어디인지” 기억해 두어야 하며, 다음 next 호출이 이전 호출이 중단된 위치에서 재개되도록 해야 한다. 이렇게 하려면, 아래 예제에서 pc라고 부르는 추가 인스턴스 변수가 하나 더 필요하다. 타깃 언어가 Fortran I 스타일의 계산 점프를 지원한다면 레이블의 주소를, 아니면 프로그램 지점을 식별할 수 있는 어떤 식별자를 담는다.
예를 들어, 두 개의 yield 문을 가진 다음 Python 제너레이터를 보자:
def generator(): n = 0 while True: yield n; yield (-n); n += 1
다음은 GNU 확장(일급 레이블과 계산 goto)을 사용한 C++ 이터레이터 객체로의 구현이다:
class Generator { int n; void * pc = NULL; public: int next(void) { if (pc) goto *pc; n = 0; while (1) { pc = &&next1; return n; next1: pc = &&next2; return (-n); next2: n += 1; } } };
각 yield 문은 고유한 레이블(예: next1) 뒤에 오는 return 문이 된다. 변수 pc는 반환 직전에 pc = &&next1처럼 이 레이블의 주소로 설정된다. 다음 호출에서 next 메서드 시작의 디스패처 if (pc) goto *pc는 이전에 실행된 return 다음의 레이블로 분기한다. next가 처음 호출될 때 pc는 null이므로 제너레이터의 코드는 정상 진입하여 상단부터 yield 문에 도달할 때까지 실행된다.
이 구현은 레이블을 일급 값으로 쓰지 않고도, 레이블에 고유 정수를 부여하고 switch 문을 디스패처로 사용하는 순수 C++로도 작성할 수 있다:
class Generator { int n; enum { START, NEXT1, NEXT2 } pc = START; public: int next(void) { switch (pc) { case START: n = 0; while (1) { pc = NEXT1; return n; case NEXT1: pc = NEXT2; return (-n); case NEXT2: n += 1; } } } };
이 코드는 C/C++의 switch 문에 있는 특이한 기능을 활용한다: case와 default 선언은 goto 레이블처럼 취급되며, 이 예의 while (1) 루프 같은 다른 제어 구조 안에서도 선언될 수 있다. 이 프로그래밍 관용구는 “Duff의 장치(Duff’s device)”로 알려져 있다.
스택풀 제너레이터 대 스택리스 제너레이터: yield 문이 제너레이터 본문에서만 나타나면 그 제너레이터를 스택리스(stackless)라고 하고, 제너레이터 본문에서 호출된 함수 내부에서도 yield가 나타날 수 있으면 스택풀(stackful)이라고 한다. 지금까지 본 제너레이터 예시는 모두 스택리스였다. 스택풀 제너레이터의 예로, 이진 트리를 순회하며 노드의 값을 열거하는 것을 생각해 보자. 의사코드:
tree_elements(t) = traverse(t)
where rec traverse(t) =
if t is a node then
traverse(t.left)
yield t.value
traverse(t.right)
endif
yield t.value 문은 해당 노드의 깊이를 n이라 할 때, traverse에 대한 n번의 재귀 호출 내부에서 실행된다.
위에서 설명한 제너레이터 구현은 스택리스 제너레이터로 제한된다. 스택풀 제너레이터를 지원하려면, 값을 반환하기 전에 제너레이터에서 yield까지 이어지는 호출 스택을 어떤 지속 저장소에 보관하고, 다음에 next 함수가 호출되었을 때 그 호출 스택을 복원해야 한다. “스택풀”이라는 용어는 제너레이터의 실행 사이에 호출 스택의 일부를 지속시켜야 한다는 필요에서 비롯한다. 스택풀 제너레이터 구현에는 타깃 언어의 특별한 지원(제어 연산자; 8장, 10.3절)이나, 더 복잡한 프로그램 변환(CPS 변환; 6.5절)이 필요하다.
Python 제너레이터는 항상 스택리스다: 문법적으로, yield 문을 포함하는 모든 함수는 그것을 호출한 다른 제너레이터와 무관하게 그 자체가 제너레이터가 된다. 예를 들어, 위 이진 트리 순회의 단순한 Python 전사를 보자:
def tree_elements(t): if t: tree_elements(t.left) yield t.value tree_elements(t.right)
이 코드는 트리를 순회하지 못한다: 재귀 호출 tree_elements(t.left)와 tree_elements(t.right)는 사용되지 않는 새로운 제너레이터 두 개를 반환한다; 따라서 t.left나 t.right에서 값이 방출되지 않고, 루트 노드 t의 값만 방출된다.
이 예시는 재귀 호출에 대해 Python의 yield from 구문을 사용하면 동작하도록 만들 수 있다:
def tree_elements(t): if t: yield from tree_elements(t.left) yield t.value yield from tree_elements(t.right)
yield from g는 for v in g: yield v처럼 동작한다. 제너레이터 g가 생성한 값은 전달되어 현재 제너레이터가 생성하는 값의 시퀀스에 삽입된다. 트리에서 깊이 n인 노드의 값은 따라서 n번 전달된다. 이는 스택풀 이터레이터의 올바른 구현보다 잠재적으로 덜 효율적일 수 있지만, 앞서 설명한 단순한 이터레이터 객체 기반 스택리스 구현과는 양립한다.
“코루틴”이라는 단어는 Conway (1963)이 “주 프로그램처럼 행동하는 서브루틴”을 설명하기 위해 도입했으며, 이후 Dahl et al. (1972)는 알골 프로시저가 “주/종 관계의 형태”를 강제하는 것과 달리 “어떤 의미에서 같은 수준에서 동작하는 두 프로그램 조각을 결합하는 방법”을 가리키는 용어로 사용했다. 오늘날 “코루티닝”은 함수 호출과 반환을 넘어서는, 여러 코드 조각의 인터리브된 실행의 모든 형태를 가리킨다. 좀 더 구체적으로, 다음을 구분할 수 있다:
대칭 코루틴 대 스레드: 다음은 Python 유사 문법으로 쓴 대칭 코루틴의 예다. 하나의 코루틴이 항목을 생성하여 큐에 추가하고, 다른 코루틴이 그 항목을 소비하는 생산자-소비자 방식이다.
q = Queue(maxsize = 100) coroutine produce(): while True: while not q.full(): item = build(); q.put(item) yield to consume coroutine consume(): while True: while not q.empty(): item = q.get(); use(item) yield to produce produce()
이를 협력 스레드를 사용해 작성한 동일한 생산자-소비자 방식과 비교해 보자:
thread produce(): while True: if not q.full(): item = build(); q.put(item) yield thread consume(): while True: if not q.empty(): item = q.get(); use(item) yield spawn(produce); spawn(consume)
코루틴 기반 코드는 생산자와 소비자 사이의 연산 인터리빙을 완전히 지정한다: 먼저 생산자가 큐를 항목으로 채운다; 그런 다음에야 소비자에게 제어를 넘기고, 소비자는 큐를 비운 다음 생산자를 다시 시작한다. 반면, 스레드 기반 코드는 연산 인터리빙의 일부를 스케줄러에 맡긴다: while 루프의 각 반복에서, yield 문은 제어를 다른 스레드로 넘길 수도 있고, 현재 스레드 내에서 계속할 수도 있다. 라운드로빈 스케줄링 전략은 프로그램이 진행됨을 보장하지만, 덜 공정한 전략은 한 스레드가 결코 진행하지 못하는 “라이블록”을 초래할 수 있다. (스케줄링 전략과 무관하게 라이블록을 방지하도록 조건 변수로 코드를 다시 작성할 수도 있다.)
코루틴의 표현력: 언뜻 보기에 비대칭 코루틴, 대칭 코루틴, 협력 스레드는 서로 다른 종류의 제어 전달을 구현하며, 어떤 종류도 나머지 둘을 포괄하지 않는 듯하다. de Moura and Ierusalimschy (2009)의 분석은 그렇지 않음을 보여준다. 그들은 코루틴을 위해 세 가지 설계 차원을 식별한다: 비대칭 대 대칭(yield의 의미에 의존), 스택풀 대 스택리스(yield가 나타날 수 있는 위치에 의존), 일급 값 대 제한적 사용(예: for 루프 내에서만). 그 다음, 그들은 비대칭·스택풀·일급 코루틴이 “원샷 경계 연속(one-shot delimited continuation)”의 표현력을 가지며, 따라서 대칭 코루틴, 협력 스레드, 기타 많은 고급 제어 구조를 인코딩할 수 있음을 증명한다. 경계 연속과 원샷(선형성) 제약은 8.5절과 10.2절에 설명되어 있다. 여기서는 그 인코딩 중 두 가지만 설명한다.
비대칭 코루틴을 사용해 대칭 코루틴을 인코딩하려면, 각 yield to C 문(C는 코루틴 식별자)을 값 C의 yield로 바꾼다. 이 yield는 제어를 “트램폴린”으로 되돌리는데, 이는 yield가 만들어 낸 값 C에게 즉시 제어를 넘겨주는 사소한 스케줄러다. 예를 들어, 위의 대칭 코루틴을 사용한 생산자-소비자 구현은 다음과 같이 바뀐다:
def produce_gen(): global consume while True: while not q.full(): item = build(); q.put(item) yield consume def consume_gen(): global produce while True: while not q.empty(): item = q.get(); use(item) yield produce produce = produce_gen() consume = consume_gen() c = produce while True: c = next(c)
변수 c는 다음에 실행할 코루틴의 값을 담는다. 이는 우리 예제에서 처음 실행할 코루틴인 produce로 초기화된다. 그런 다음 트램폴린은 next(c)를 호출하여 반복적으로 코루틴 c에 제어를 넘기고, next(c)가 반환한 값(다음에 실행할 코루틴)으로 c를 갱신한다.
비대칭 코루틴을 사용해 협력 스레드를 인코딩하려면, 스케줄러를 작성하여 스레드마다 하나씩 코루틴 집합을 유지하고, 이 집합에서 코루틴 c를 하나 선택하여 next(c)로 재개하고, 다시 집합에 넣는 일을 반복한다. 예를 들어, 다음은 라운드로빈 스케줄러다:
q = Queue() q.put(produce); q.put(consume) # 스레드 두 개 생성 while not q.empty(): c = q.get() try: next(c) q.put(c) except StopIteration: pass
우리의 스케줄러는 스레드가 yield 문 대신 정상적으로 반환하는 경우도 처리한다: 이 경우 스레드가 종료되었다고 보고, 큐에 다시 넣지 않는다.
Scott and Aldrich (2025)는 이터레이터(6.5절)와 코루틴(9.5절)에 대한 좋은 입문을 제공한다. Dahl et al. (1972)의 3장은 코루틴과 객체지향 클래스 둘 다를 도입한 언어 Simula의 “계층적 프로그램 구조”를 설명한다. Johnson and Foote (1988)는 잘 설계된 객체지향 프레임워크에서 제어의 반전이 하는 역할을 지적한 초기 논문 중 하나다. de Moura and Ierusalimschy (2009)는 경계 연속에 기반한 통합된 프레임워크에서 다양한 종류의 코루틴을 설명한다.