Transducers — 요소 단위로 쪼갠 합성 가능한 변환

Transducers — 요소 단위로 쪼갠 합성 가능한 변환

Transducers(트랜스듀서)는 합성 가능한 알고리즘 변환이에요. 입력과 출력의 출처(context)와는 독립적이고, 개별 요소 하나를 기준으로 변환의 본질만을 규정해요. 트랜스듀서가 입력·출력 출처에서 분리되어 있기 때문에, 컬렉션이나 스트림, 채널, 옵저버블 같은 다양한 처리 과정에서 똑같이 쓸 수 있죠. 트랜스듀서는 입력을 의식하지도 않고 중간 집계(intermediate aggregate)를 만들지도 않은 채 직접 합성돼요.

출처: Clojure 공식문서

본문

연습 삼아, 소개용 블로그 포스트와 이 비디오, 그리고 트랜스듀서의 좋은 쓰임새에 대한 FAQ의 이 섹션도 함께 보면 좋아요.

용어

reducing function(리듀싱 함수)은 reduce에 넘기는 그런 종류의 함수예요. 누적된 결과와 새로운 입력을 받아 새로운 누적 결과를 돌려주는 함수죠.

;; reducing function 시그니처
whatever, input -> whatever

그리고 transducer(트랜스듀서, xform이나 xf라고도 불러요)는 reducing function 하나를 다른 reducing function으로 바꿔주는 변환이에요.

;; transducer 시그니처
(whatever, input -> whatever) -> (whatever, input -> whatever)

트랜스듀서로 변환 정의하기

Clojure에 포함된 대부분의 시퀀스 함수는 트랜스듀서를 만들어내는 arity를 갖고 있어요. 그 arity는 입력 컬렉션을 생략하는데, 입력은 이후에 트랜스듀서를 적용하는 과정(process)이 공급해요. 참고: 이렇게 줄어든 arity는 커링이나 부분 적용(partial application)이 아니에요.

예를 들면:

(filter odd?) ;; 홀수만 거르는 트랜스듀서를 돌려줘요
(map inc)     ;; 1을 더하는 매핑 트랜스듀서를 돌려줘요
(take 5)      ;; 처음 5개 값을 가져오는 트랜스듀서를 돌려줘요

트랜스듀서는 일반적인 함수 합성으로 합쳐져요. 트랜스듀서는 자기가 감싸는 트랜스듀서를 호출할지, 몇 번 호출할지를 결정하기 전에 자기 자신의 연산을 수행해요. 트랜스듀서를 합성하는 권장 방법은 기존의 comp 함수를 쓰는 거예요.

(def xf
  (comp
    (filter odd?)
    (map inc)
    (take 5)))

트랜스듀서 xf는 변환 스택으로, 어떤 과정이 일련의 입력 요소에 적용하게 돼요. 스택의 각 함수는 자기 뒤에 감싼 연산 앞에서 수행돼요. 변환기의 합성은 오른쪽에서 왼쪽으로 진행되지만, 실제로 만들어지는 변환 스택은 왼쪽에서 오른쪽으로 실행돼요(이 예에서는 매핑 전에 필터링이 일어나죠).

기억할 요령이 하나 있어요. comp에서 트랜스듀서 함수가 나열된 순서는 *->>*에서 시퀀스 변환이 쓰인 순서와 같아요. 위 변환은 다음 시퀀스 변환과 동일하죠.

(->> coll
     (filter odd?)
     (map inc)
     (take 5))

입력 컬렉션을 생략하면 트랜스듀서를 만들어내는 함수들은 다음과 같아요.

map cat mapcat filter remove take take-while take-nth drop drop-while replace partition-by partition-all keep keep-indexed map-indexed distinct interpose dedupe random-sample

트랜스듀서 사용하기

트랜스듀서는 여러 문맥에서 쓸 수 있어요(새로 만드는 방법은 아래에서 다뤄요).

transduce

트랜스듀서를 적용하는 가장 흔한 방법 중 하나는 transduce 함수예요. 표준 reduce와 비슷하죠.

(transduce xform f coll)
(transduce xform f init coll)

transduce는 coll을 (lazy하게가 아니라) 즉시 reduce하면서, reducing function f에 트랜스듀서 xform을 적용해요. init 값이 주어지면 그것을, 아니면 (f)를 초깃값으로 써요. f는 결과를 어떻게 누적할지를 아는 부분인데, 그 누적은 (상태를 가질 수 있는) reduce의 문맥 안에서 일어나요.

(def xf (comp (filter odd?) (map inc)))
(transduce xf + (range 5))
;; => 6
(transduce xf + 100 (range 5))
;; => 106

합성된 xf 트랜스듀서는 왼쪽에서 오른쪽으로 호출되고, 마지막에 reducing function f를 호출해요. 마지막 예에서는 입력 값이 걸러진 다음 1씩 더해지고, 마지막으로 합산돼요.

eduction

트랜스듀서를 coll에 적용하는 과정을 잡아두려면 eduction 함수를 써요. xform을 몇 개든 받은 뒤 마지막 coll을 받고, 트랜스듀서를 coll의 요소에 적용한 reducible/iterable 값을 돌려줘요. 이 적용은 reduce/iterator가 호출될 때마다 매번 수행돼요.

(def iter (eduction xf (range 5)))
(reduce + 0 iter)
;; => 6

into

트랜스듀서를 입력 컬렉션에 적용해 새 출력 컬렉션을 만들려면 into를 써요(가능하면 reduce와 transient를 효율적으로 사용해요).

(into [] xf (range 1000))

sequence

트랜스듀서를 입력 컬렉션에 적용해 시퀀스를 만들려면 sequence를 써요.

(sequence xf (range 1000))

결과 시퀀스의 요소는 점진적으로 계산돼요. 이 시퀀스들은 필요할 때 입력을 점진적으로 소비하고, 중간 연산을 완전히 실현(realize)해요. 이런 동작은 lazy 시퀀스에 대한 동일한 연산과는 달라요.

트랜듀서 만들기

트랜스듀서는 다음과 같은 모양을 가져요(맞춤 코드는 "..."에 들어가요).

(fn [rf]
  (fn ([] ...)
      ([result] ...)
      ([result input] ...)))

핵심 시퀀스 함수들(map, filter 등) 대부분은 연산별 인자(프레디킷, 함수, 개수 등)를 받아서, 그 인자들을 클로저로 닫는 이 모양의 트랜스듀서를 돌려줘요. cat 같은 몇몇 경우에는 핵심 함수 자체가 트랜스듀서 함수라서 rf를 받지 않아요.

안쪽 함수는 목적이 다른 3개의 arity로 정의돼요.

  • Init (arity 0) — 중첩된 변환 rf의 init arity를 호출해야 해요. 이는 결국 트랜스듀싱되는 과정(transducing process)까지 이어져요.
  • Step (arity 2) — 표준 reducing function이지만, 트랜스듀서에 맞게 rf의 step arity를 0회 이상 호출할 것으로 기대돼요. 예를 들어 filter는 (프레디킷에 따라) rf를 호출할지 정하고, map은 항상 정확히 한 번 호출하며, cat은 입력에 따라 여러 번 호출할 수 있어요.
  • Completion (arity 1) — 끝나지 않는 과정도 있지만, transduce처럼 끝나는 과정을 위해 completion arity가 최종 값을 만들거나 상태를 비우는 데 쓰여요. 이 arity는 rf의 completion arity를 정확히 한 번 호출해야 해요.

completion을 쓰는 예로 partition-all을 들 수 있어요. 입력이 끝났을 때 남은 요소를 비워야 하거든요. completing 함수는 기본 completion arity를 추가해서 reducing function을 transducing function으로 바꿔줘요.

조기 종료(Early termination)

Clojure는 reduce의 조기 종료를 지정하는 메커니즘을 갖고 있어요.

  • reduced — 값을 받아 reduced 값을 돌려주며, reduction이 멈춰야 함을 나타내요.
  • reduced? — 값이 _reduced_로 만들어졌으면 true를 돌려줘요.
  • deref 또는 @는 reduced 안의 값을 꺼내는 데 써요.

트랜스듀서를 사용하는 과정은 step 함수가 reduced 값을 돌려주면 그것을 확인하고 멈춰야 해요(이는 뒤의 '트랜스듀서 가능한 과정 만들기'에서 더 다뤄요). 또한 중첩된 reduce를 쓰는 트랜스듀서 step 함수는 reduced 값을 만나면 확인하고 전달해야 해요. (cat의 구현이 좋은 예예요.)

reduction 상태를 가진 트랜스듀서

take, partition-all 같은 일부 트랜스듀서는 reduction 과정 동안 상태가 필요해요. 이 상태는 트랜스듀서 가능한 과정이 트랜스듀서를 적용할 때마다 매번 새로 만들어져요. 연속된 중복 값을 하나로 접는 dedupe 트랜스듀서를 생각해 봐요. 이 트랜스듀서는 현재 값을 내보낼지를 결정하려면 이전 값을 기억해야 해요.

(defn dedupe []
  (fn [xf]
    (let [prev (volatile! ::none)]
      (fn
        ([] (xf))
        ([result] (xf result))
        ([result input]
          (let [prior @prev]
            (vreset! prev input)
              (if (= prior input)
                result
                (xf result input))))))))

dedupe에서 prev는 reduction 동안 이전 값을 저장하는 상태 보관소예요. 성능을 위해 prev 값은 volatile이지만, atom이어도 돼요. prev 값은 트랜스듀싱 과정이 시작될 때(예를 들어 transduce 호출에서) 비로소 초기화돼요. 그래서 상태 상호작용은 트랜스듀서 가능한 과정의 문맥 안에 갇혀 있게 돼요.

reduction 상태를 가진 트랜스듀서는 completion 단계에서, 중첩된 step에서 reduced 값을 미리 본 적이 없다면 중첩된 변환기의 completion 함수를 호출하기 전에 상태를 비워야 해요. reduced 값을 이미 봤다면 보류 중인 상태는 버려야 하죠.

트랜스듀서 가능한 과정(Transducible Process) 만들기

트랜스듀서는 다양한 종류의 과정에서 쓰이도록 설계됐어요. 트랜스듀서 가능한 과정은 각 단계가 입력 하나를 받는 연속된 단계로 정의돼요. 입력의 출처는 과정마다 달라요(컬렉션에서, 반복자에서, 스트림에서 등). 마찬가지로 과정은 각 단계가 만들어낸 출력을 어떻게 처리할지도 스스로 골라야 해요.

트랜스듀서를 적용할 새 문맥이 있다면, 알고 있어야 할 일반적인 규칙이 몇 가지 있어요.

  • step 함수가 reduced 값을 돌려주면, 트랜스듀서 가능한 과정은 step 함수에 더 이상 입력을 공급하면 안 돼요. reduced 값은 completion 전에 deref로 풀어야 해요.
  • 끝나는 과정은 마지막 누적 값에 completion 연산을 정확히 한 번 호출해야 해요.
  • 트랜스듀싱 과정은 트랜스듀서를 호출해 돌아온 함수에 대한 참조를 캡슐화해야 해요. 그 함수들은 상태를 가질 수 있고, 스레드 간 사용에 안전하지 않을 수 있거든요.

더 알아보기