Clojure를 더 지연시킨 이야기

Clojure를 더 지연시킨 이야기 (Making Clojure Lazier)

(참고: 이 페이지는 Rich가 대안인 streams를 탐구하던 때, 시퀀스에 대한 마지막 큰 업데이트에서 이루어진 변경들을 설명해요. 이 페이지는 참조 문서라기보다, 이러한 설계 결정에 대한 유용한 역사적 기록으로 취급하세요.)

streams 작업을 하면서 몇 가지가 분명해졌어요:

stream 코드는 추하고 명령형이에요 ** 안전하게 만들더라도 여전히 추하고, 상태가 있어요
streams는 완전한 지연(full laziness)을 지원해요 ** 이것은 매우 훌륭하다는 결론이 돼요
streams를 투명하게 통합하면(즉 map과 map-stream을 둘 다 갖지 않고), 핵심 시퀀스 함수(map, filter 등)의 계약을 완화하는 변경이 필요해요 ** 그렇게 한다면, Clojure의 아름다운 재귀 스타일을 유지하면서도 같은 완전한 지연을 달성할 수 있을까? *** 기존 코드와 실질적으로 호환되면서 말이죠 *** 네! **** 하지만 — 이상적으로는 일부 이름이 바뀌어야 해요

현재 seq 모델 (The current seq model)

원래 Common Lisp의 cons에 기반했어요
유효한 first를 가진 seq를 갖거나, 아무것도(nil) 없거나
seq는 논리적 커서(cursor)와 같아요
rest는 근본적으로 eager해요 ** 또 다른 seq나 nil을 반환해요 ** 반환 값이 nil인지 결정하기 위해 더 있는지 판단해야 해요 ** lazy-cons는 first/rest의 계산을 지연시킬 수 있지만, rest가 있는지의 판단은 지연시킬 수 없어요 *** 판단은 종종 내부 seq를 '당기는(pulling)' 것을 요구해서, 실제 지연을 줄여요
시퀀스 함수는 현재 seq나 nil을 반환해요

rest의 eager함은 시퀀스 함수들이 완전히 지연되지 못하게 해요 — 최소한 first가 있는지는 판단해야 하거든요.

seq 모델 향상 — seq에 대한 세 번째 연산 'next'

변경: (rest aseq) - 비어 있을 수 있는 seq(never nil)를 반환해요 ** 인자가 이미 seq가 아니면 seq를 호출해요 ** 반환된 seq는 빌 수 있어요 *** ()로 출력하지만, 단일 센티널 객체는 아니에요 ** 결코 nil을 반환하지 않아요 *** 현재 제3자 seq에는 강제되지 않아요 ** 남은 항목들(있다면)로의 (아마도 지연된) 경로
변경: seq는 비어 있을 수 있어요 ** 항상 ISeq예요
변경: seq 함수 - 더 이상 ISeq에 대한 항등(identity)이 아니에요 ** 여전히 seq 또는 nil을 반환해요 ** (seq aseq) -> 더 이상 항등이 아니고, aseq가 비어 있으면 nil을 반환해요 ** 여전히 nil에서 동작해요
first 함수는 변하지 않아요 ** 인자가 이미 seq가 아니면 seq를 호출해요 ** 첫 번째 항목을 반환해요 ** 여전히 nil에서 동작해요
새 항목: next 함수는 rest가 하던 일을 해요 ** 다음 seq(있으면), 아니면 nil을 반환해요 ** 인자가 이미 seq가 아니면 seq를 호출해요 ** (next aseq) === (seq (rest aseq)) ** nil에서 동작해요
변경: seq? ** (seq? ()) -> true
변경: 시퀀스 함수(map, filter 등)는 seq를 반환하지만 nil은 아니에요 ** seq/nil을 얻으려면 그 반환 값에 seq를 호출해야 해요 *** seq는 끝 검사로도 쓰이며, 이미 관용적(idioomatic)이에요

(when (seq coll)
  ...)

** 완전한 지연을 허용해요 ** nil punning을 지원하지 않아요 *** 시퀀스 함수가 더 이상 seq/nil을 반환하지 않으므로

레시피 - 새 모델에서 지연 시퀀스 함수 작성법

안녕 lazy-cons, 반가워 lazy-seq ** lazy-cons는 사라졌어요 ** 새 지연 매크로 - lazy-seq *** seq, nil 또는 어떤 seq-able한 것을 산출하는 body를 받아요 *** seq를 호출함으로써 seq를 구현하는 논리적 컬렉션을 반환해요 **** 처음 seq가 호출됐을 때만 body를 호출하고, 결과를 캐시해요 **** body의 반환 값이 이미 seq나 nil이 아니면 seq를 호출해요 ** 순 결과는 seq가 호출될 때까지 아무 일도 하지 않는 가상 컬렉션을 만드는 것 - 완전히 지연돼요 ** 모든 컬렉션 연산을 지원해요 ** 비어 있을 수 있어요 - 예: 그 위에 seq를 호출하면 nil을 반환할 수 있어요 *** 비었을 때는 ()로 출력돼요
lazy-seq는 지연 시퀀스 함수의 최상위에 위치해요 ** 중첩된 lazy-cons 대신에
안쪽에서는 보통의 cons 호출을 사용해요 ** 필요할 때까지 만들어지지 않아요
다른 seq를 소비한다면 next 대신 rest를 사용해요

예전 방식:

(defn map
  ([f coll]
   (when (seq coll)
     (lazy-cons (f (first coll)) (map f (rest coll)))))
...

새 방식:

(defn map
  ([f coll]
   (lazy-seq
    (when-let [s (seq coll)]
      (cons (f (first s)) (map f (rest s))))))
...

when-let을 사용해 seq를 한 번 잡아두고, first와 rest에서 재사용한다는 점에 주목하세요. first/rest가 인자에 seq를 호출하지만요. 이 새 모델에서는 이것이 성능 이점을 가져요.

희생양 - nil punning

CL의 cons가 리스트 끝에 nil을 사용하는 것의 좋은 점 하나는, nil이 조건식에서 테스트 가능하다는 것과 결합될 때, cons-반환 함수를 술어처럼 쓸 수 있다는 점이에요. 이제는 seq와 next만 그런 방식으로 쓸 수 있고, map, filter 등은 그럴 수 없어요. seq/nil dyad의 경제성이 여전히 많이 적용된다는 점에 주목하세요. 예를 들어 위 map에서 when을 사용하는 것처럼요.

ISeq 확장 (Extension ISeqs)

ISeq를 확장한다면 ISeq.more()(rest의 기반)를 지원해야 해요. 다행히 대부분의 ISeq 확장자는 ASeq에서 파생되는데, ASeq는 *more()*를 next로 정의해요. seq를 ASeq에서 파생시킨다면, more()를 정의하지 말고 ASeq가 제공하는 버전을 사용하세요. rest() 메서드를 next()로 이름만 바꾸면 돼요.

레시피 - 포팅 (Recipe - Porting)

새 모델로 옮기려면 다음 단계를 이 순서대로 밟아야 해요:

rest에 대한 모든 호출을 next를 호출하도록 이름을 바꿔요
lazy-cons를 사용해 나만의 지연 시퀀스 함수를 정의하고 있었다면, 위 레시피를 사용해 lazy-seq로 전환해요. 재귀 호출에서 next가 아니라 rest를 호출하도록 하세요.
nil-punning에 대해 코드를 감사(audit)해요. 지연 브랜치는 조건식에서 지연 시퀀스의 진리 값을 테스트하려 하면 assert하는 디버그 모드 컴파일을 지원하며, 그렇게 하면 예외를 던져요. clojure를 다음과 같이 빌드하세요: ** ant -Dclojure.assert-if-lazy-seq=true ** 그러면 다음과 같은 nil pun들이 예외를 던져요: *** (when (filter neg? [1 2]) :all-pos) *** (not (concat)) *** (if (rest (seq [])) 1 2) ** 모든 경우에 시퀀스를 seq 호출로 감싸면 nil pun을 고칠 수 있어요:

(when (seq (filter neg? [1 2])) :all-pos)
-> nil

** 끝나면 느려지므로 플래그 없이 다시 빌드하세요.

머리를 (붙)잡고 있지 마세요

재귀적으로 정의된 지연 시퀀스 함수는 우아하고 이해하기 쉬워요. 그것들은 매우 메모리 효율적일 수 있어서, 메모리에 맞지 않을지도 모르는 데이터 소스로 작업할 수 있게 해 줘요. 현재 사용 중인 데이터 구조의 일부만 메모리에 있으면 되니까요. 어떤 부분이 현재 사용 중인지 결정하는 게 때로는 까다로울 수 있는데, 지역 변수에 여전히 참조되어 있을 수 있기 때문이에요. Clojure는 스택에 잔류 참조가 남지 않도록 꼬리 호출에서 지역 변수 정리를 수행하지만, 하나 남은 경우가 있었어요 — 닫힌(closed-over) 지역 변수로, 특히 lazy-seq 같은 매크로가 사용자를 대신해 클로저를 만들 때 통제하기 어려웠어요.

원래의, 완전히 지연되지 않은 filter 정의를 생각해 보세요:

(defn filter
  "Returns a lazy seq of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
    (when (seq coll)
      (if (pred (first coll))
        (lazy-cons (first coll) (filter pred (rest coll)))
        (recur pred (rest coll)))))

함수 자신으로 recur함으로써 매 반복마다 coll 인자를 효과적으로 지우므로, 술어와 일치하지 않는 요소를 건너뛰는 동안 coll을 유지하지 않는 것처럼 보여요. 문제는 때때로 filter 호출이 lazy-cons 안에 있고, 그것이 coll을 닫는 클로저로 확장되므로 루프가 도는 동안 coll을 유지하게 되며, 호출된 함수가 할 수 있는 일이 없다는 점이에요. 이는 다음과 같은 표현식이:

(filter #(= % 20) (map inc (range 10000000)))

메모리 부족 예외를 일으킬 수 있다는 뜻이에요. 이를 피하는 유일한 방법은 filter를 변경(mutation)을 사용해 다시 쓰는 것이었어요. 윽.

새 filter는 이렇게 생겼어요:

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))

예전 filter의 본문이 헬퍼 fn에 들어가고, lazy-cons가 cons로 대체된 다음, 전체 호출이 lazy-seq로 감싸졌어요. 위 레시피를 따르는 거예요. 그러나 lazy-seq도 coll을 닫는 클로저를 만들어요. 이 filter는 이 향상 없이는, 더 지연되지만 예전과 같은 메모리 발자국을 가질 거예요. 새 지연 브랜치는 이와 비슷한 시나리오를 위한 컴파일러 향상을 포함해요. lazy-seq와 delay는 모두 body의 꼬리 호출에서 닫힌 지역 변수 정리를 수행해서, 꼬리 호출이 실행될 때 클로저 자체에 참조가 남지 않도록 보장해요. 결과를 캐시하므로 클로저가 한 번만 호출될 것임을 알기 때문에 이것이 가능해요. 따라서 위 filter 표현식에 대해 지연 브랜치는 문제가 없고, 여러분도 비슷한 기법을 사용해 자신의 지연 함수에서 메모리 사용을 통제할 수 있어요.

출처: Clojure를 더 지연시킨 이야기 (Making Clojure Lazier)

더 알아보기

시퀀스 (Sequences)