Rust의 AsyncIterator 논의를 계기로, ‘이터레이터’와 ‘트래버서블’을 구분해야 한다는 분류학적 관점을 제시하고, 왜 AsyncIterator는 단순히 Iterator에 async 효과를 덧씌운 것이 아닌지 설명한다.
2024년 3월 13일
이는 _이터레이터_의 정의에 대한 짧은 메모입니다.
이전 글에서 나는 Rust 프로젝트 내에서 AsyncIterator와 관련해 발생했다고 생각하는 분류상의 혼란에 대해 썼습니다. 거기서 AsyncIterator는 “Iterator에 async를 덧붙인 것”으로만 여겨졌고, 동시에 그것이 “반복(iterative)으로 변형된 Future”라는 점, 즉 Iterator와 Future의 기능을 결합해 둘 모두로부터 동등하게 상속받는 코루틴이라는 점을 인식하지 못했습니다. 하지만 이런 사고방식의 밑바탕에는 또 다른 정의상의 혼란이 있는데, 바로 “iterator” 자체의 정의에 대한 혼란입니다.
특히 내가 본 몇몇 주장들은 rayon의 ParallelIterator를 AsyncIterator와 유사하게 “또 다른 변형된 Iterator”로 거론합니다. 예컨대 Yosh Wuyts는 이를 “effects generics” 이니셔티브를 지지하는 논거로 사용했는데, 이 틀에서는 “parallel” 또한 async와 유사한 방식으로 기반 Iterator 개념을 “수정”하는 효과(effect)이며, 이상적으로는 이를 추상화할 수 있어야 한다고 봅니다(이것은 여러 기술적 근거에서 실행 불가능해 보이지만, 이 글에서는 분류학적 논평에만 집중하겠습니다). 다른 관점에서, Niko Matsakis는 어느 시점에 rayon에 비유해, 외부 반복(external iteration) 대신 내부 반복(internal iteration)을 AsyncIterator의 기초로 고려하자고 제안하기도 했습니다.
내가 보기엔 이런 사고방식의 문제는 “iterator”라는 단어를 너무 광범위하게 해석한다는 데 있습니다. 나는 두 가지 범주의 추상화를 구분해야 한다고 생각하며, 이를 각각 _이터레이터_와 _트래버서블_이라 부르겠습니다(후자는 Haskell에서 가져온 용어로, 이 정의가 모나드 법칙을 어기는지 여부에는 특별히 신경 쓰지 않겠습니다):
어떤 것이든 “트래버서블”이라면 map이나 reduce 같은 콤비네이터를 지원할 수 있지만, 그 시그니처가 완전히 동일하거나 구현 방식이 같을 필요는 없습니다. 이 분류에서 “내부 반복”은 반복(iteration)이 아니라, “순회(traversal)”의 또 다른 형태입니다. 용어에 대해 왈가왈부할 수는 있습니다. 내가 “트래버서블”이라 부르는 것을 전부 이터레이터라고 부르고, 내가 “이터레이터”라 부르는 것에 새로운 이름을 붙이고 싶을 수도 있겠죠. 그건 크게 중요하지 않습니다. 중요한 것은 “값들을 하나씩 순차적으로 내놓는” 추상화와 “여러 값을 어떤 방식으로든 순회하는” 추상화를 분류학적으로 구분하는 것입니다. 전자는 후자보다 더 정밀한 정의이므로, 내 용어법으로는 모든 이터레이터는 트래버서블이지만 _모든 트래버서블이 이터레이터인 것은 아니다_라고 말할 수 있습니다.
Iterator와 보다 넓은 의미의 트래버서블 사이의 차이는 물론 이터레이터가 값을 “하나씩 순차적으로” 산출한다는 점을 알 수 있다는 것입니다. 그 결과로 표현상 더 단순해집니다. Iterator는 상태 머신으로 표현할 수 있는 반면, ParallelIterator 같은 다른 범주의 트래버서블은 실제로는 스레드 풀 전반에 작업을 분산하는 복잡한 동시성 스케줄링 인프라의 일종으로, 구현이 전혀 비슷하지 않습니다. 또 다른 결과로, ParallelIterator의 콤비네이터는 Iterator의 콤비네이터와 미묘하게 다른 시그니처를 가집니다. 예를 들어 ParallelIterator::map은 클로저가 스레드-세이프여야 할 뿐 아니라, 한 번에 하나씩 적용되는 Iterator와 달리 다수의 스레드에서 동시에 값들에 적용되기 때문에 FnMut가 아니라 Fn일 것을 요구합니다.
Rust에 AsyncIterator를 추가하려는 동기는 체크리스트 채우기 식으로 “Iterator에 async 효과를 추가하기 위해서”가 아닙니다. 값들을 하나씩 순차적으로 내놓으면서도 준비될 때까지 대기(pend)할 수 있는 상태 머신에는 분명하고 설득력 있는 사용 사례가 있으며, 이것이 곧 AsyncIterator 상태 머신의 능력입니다. 내가 스폰하는 작업의 상당수는 바로 그런 성격의 상태 머신이 산출하는 값들을 루프로 돌며 작업의 대부분을 수행하며, 비동기 제너레이터, for await, merge! 같은 기능이 이를 더 잘 지원하면 이런 작업을 훨씬 쉽게 구현할 수 있습니다. 이 기능의 설계에 다른 종류의 트래버서블까지 접어넣으려 하면 다른 비용을 강요하여 목적에 부합하지 않게 됩니다.
분류학적으로 보면, 이것은 (비동기 추상화까지 넓게 포함해 트래버서블을 정의한다면) 또 다른 범주의 트래버서블로서, 이터레이터와 유사하면서도 비동기 시스템에 통합되므로 “async 이터레이터”라고 부를 만합니다. 중요한 점은, 비동기 시스템이 부여하는 추가적인 기능 때문에 이것이 “이터레이터”의 하위 분류가 아니라는 것입니다. 이것이 “퓨처들의 이터레이터”와 어떻게 다른지, 그리고 Iterator::next 메서드에 “async 효과”를 붙여 그걸 모델링하려 하면 왜 열등한 설계가 되는지에 대해서는 이미 길게 쓴 바 있습니다.
마찬가지로 ParallelIterator의 비동기 버전, 즉 스레드 풀 전반에 걸쳐 스케줄링되어 값들의 집합을 병렬로, 비동기적으로 동시 순회하게 해 주는, 트래버서블의 또 다른 하위 분류를 상상할 수도 있습니다. 이것은 ParallelIterator가 이터레이터의 일종이 아닌 것과 마찬가지로, 어떤 의미에서도 async 이터레이터가 아닐 것입니다. 대신 이것은 또 다른 종류의 트래버서블로서 비슷한 계열의 콤비네이터를 제공하되 시그니처에는 약간의 차이가 있고, 구현은 크게 다른 별개의 추상화가 될 것입니다. 사실 rayon은 tokio의 멀티스레드 런타임 같은 워크 스틸링 기반 태스크 실행기와 이미 공통점이 많습니다. rayon은 말 그대로 워크 스틸링을 사용해 여러 스레드에 작업 단위를 스케줄링합니다. 어떤 “async rayon”도 궁극적으로는 태스크를 스케줄링하는 일종의 비동기 런타임이 될 것이며, AsyncIterator의 콤비네이터와 유사해 보이는(하지만 시그니처에는 몇 가지 차이가 있는) 콤비네이터 세트를 통해 구현되겠지만, 구현은 매우 다를 것입니다.
