Clojure의 시퀀스를 더 느슨하게 — lazy-seq 모델

Clojure의 시퀀스를 더 느슨하게 — lazy-seq 모델

이 문서는 Clojure 시퀀스가 지금처럼 완전히 lazy하게 동작하기까지 거친 설계 변화를 풀어둔 글이에요. 시퀀스 함수(map, filter 등)가 왜 lazy-cons에서 lazy-seq로 옮겨갔는지, 그 과정에서 rest와 next의 역할이 어떻게 갈라졌는지를 따라가 보면, 지금 Clojure 시퀀스 함수의 규칙이 훨씬 또렷하게 보여요.

출처: Clojure 공식문서

본문

참고: 이 페이지는 Rich Hickey가 시퀀스에 큰 업데이트를 하면서, 동시에 streams라는 대안을 탐구하던 시기의 변화를 다룬 글이에요. 그러니 기준 문서라기보다, 그때의 설계 결정을 보여주는 역사적 기록으로 읽어주세요.

streams를 만들다 보니 몇 가지가 분명해졌어요.

  • stream 코드는 지저분하고 절차적이에요. 안전하게 만들더라도 여전히 보기 나쁘고 상태를 갖고 있었죠.
  • 그런데 stream은 완전한 laziness를 지원했어요. 이게 결과적으로 아주 좋았어요.
  • stream을 투명하게 기존 시퀀스에 통합하면, 핵심 시퀀스 함수(map, filter 등)의 계약을 느슨하게 바꿔야 해요.
    • 그렇게 한다면, Clojure의 아름다운 재귀 스타일을 유지하면서도 같은 완전한 laziness를 얻을 수 있을까요?
      • 기존 코드와 상당 부분 호환되면서요.
      • 네, 가능해요!
        • 다만 이상적으로는 이름 몇 개는 바뀌어야 해요.

기존의 seq 모델

  • 원래는 Common Lisp의 cons를 본떠 만들어졌어요.
  • 시퀀스는 유효한 first를 갖거나, 아니면 아무것도 없는 nil이에요.
  • seq는 논리적 커서(cursor) 같은 존재예요.
  • rest는 근본적으로 즉시(eager) 연산이에요.
    • 또 다른 seq나 nil을 돌려주죠.
    • 반환값이 nil인지 판단하려면 '뒤에 더 있느냐'를 결정해야 해요.
    • lazy-cons는 first/rest의 계산은 미룰 수 있지만, 'rest가 있느냐'를 판정하는 일까지는 미룰 수 없어요.
      • 그 판정을 하려면 안쪽 seq를 당겨봐야(pull) 하는 경우가 많아서, 효과적인 laziness가 줄어들었어요.
  • 시퀀스 함수는 현재 seq나 nil을 돌려줘요.

rest의 이런 즉시성 때문에 시퀀스 함수는 완전히 lazy하지 못해요. 최소한 'first가 있느냐'는 판단해야 했거든요.

seq 모델 확장 — 세 번째 연산 next

  • 변경: (rest aseq) — 이제는 비어 있을 수 있는 seq를 돌려주고, 절대 nil을 돌려주지 않아요.
    • 인자가 이미 seq가 아니면 seq를 호출해요.
    • 돌려주는 seq는 비어 있을 수 있어요.
      • ()로 출력되지만, 단일 sentinel 객체는 아니에요.
    • 절대 nil을 돌려주지 않아요.
      • 현재는 서드파티 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는 이미 관용적으로 끝을 검사하는 용도로 쓰이고 있어요.
(when (seq coll)
  ...)
  • 이것이 완전한 laziness를 가능하게 해요.
  • nil punning(빈 것을 nil처럼 써먹기)은 지원하지 않아요.
    • 시퀀스 함수가 이제 seq/nil을 돌려주지 않기 때문이에요.

레시피 — 새 모델에서 lazy 시퀀스 함수 쓰기

  • lazy-cons와 작별하고 lazy-seq에 인사해요.
    • lazy-cons는 사라졌어요.
    • 새로운 laziness 매크로 — lazy-seq.
      • seq, nil, 또는 seq로 만들 수 있는 무엇이든 산출하는 body를 받아요.
      • body를 호출해서 seq를 구현하는 논리적 컬렉션을 돌려줘요.
        • body는 seq가 처음 호출될 때 한 번만 실행되고, 결과는 캐시돼요.
        • body의 반환값이 이미 seq 또는 nil이 아니면, 그 위에 seq를 호출해요.
      • 결과적으로, seq가 호출될 때까지 아무 일도 하지 않는 가상 컬렉션이 만들어져요 — 완전히 지연되죠.
    • 모든 컬렉션 연산을 지원해요.
    • 비어 있을 수 있어요 — 예를 들어 그 위에 seq를 호출하면 nil이 나올 수 있어요.
      • 비어 있으면 ()로 출력돼요.
  • lazy-seq는 lazy 시퀀스 함수의 최상위에 와요.
    • 중첩된 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를 돌려주는 함수를 술어(predicate)처럼 쓸 수 있었던 거예요. 이제 그런 용법은 seq와 next만 가능해요 — map, filter 등은 그럴 수 없어요. 다만 seq/nil 이원성의 많은 경제성은 여전히 유효하다는 점도 눈여겨보세요. 예를 들어 위 map에서 when을 쓴 것처럼요.

ISeq 확장하기

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

레시피 — 포팅하기

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

  • 모든 rest 호출을 next 호출로 바꿔요.
  • lazy-cons로 직접 lazy 시퀀스 함수를 정의하고 있었다면, 위 레시피를 따라 lazy-seq로 바꿔요. 재귀 호출에서는 반드시 next가 아니라 rest를 호출하도록 해요.
  • 코드에서 nil punning을 점검해요. lazy 브랜치는 일종의 디버그 모드 컴파일을 지원하는데, 조건식에서 lazy seq의 진리값을 시험하려고 하면 assertion을 던져요. 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
  • 다 끝났으면 플래그 없이 다시 빌드해요. 플래그가 켜져 있으면 속도가 느려지거든요.

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

재귀적으로 정의한 lazy 시퀀스 함수는 우아하고 이해하기 쉬워요. 메모리도 매우 효율적일 수 있어서, 메모리에 다 못 들어가는 데이터 소스도 다룰 수 있어요. 데이터 구조의 현재 쓰이는 부분만 메모리에 있으면 되니까요. 다만 어떤 부분이 현재 쓰이는지는 판별하기 까다로울 수 있어요. 지역 변수에 여전히 참조돼 있을 수 있으니까요. Clojure는 꼬리 호출에서 지역 변수를 정리해서 스택에 남는 참조가 없게 하지만, 하나 남은 경우가 있었어요 — 닫혀버린 지역(closed-over locals)이에요. 특히 lazy-seq처럼 여러분 대신 클로저를 만드는 매크로를 쓸 때 통제하기 어려웠죠.

원래의, 완전히 lazy하지 않은 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 안에 있을 때예요. 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의 body는 도우미 함수로 옮겨졌고, lazy-cons는 cons로 바뀌었고, 전체 호출이 위 레시피를 따라 lazy-seq로 감싸였어요. 다만 lazy-seq도 coll을 닫는 클로저를 만든다는 점은 같아요. 어떤 개선이 없으면, 이 filter는 더 lazy하지만 옛것과 메모리 사용량은 같을 거예요. 새 lazy 브랜치는 이런 시나리오를 위한 컴파일러 개선을 담고 있어요. lazy-seq와 delay는 둘 다 body의 꼬리 호출에서 닫힌 지역 정리(closed-over local clearing)를 수행해서, 꼬리 호출이 실행될 때 클로저 자체에 참조가 남지 않게 해요. 결과를 캐시하므로 클로저가 정확히 한 번만 실행된다는 걸 알기 때문에 그게 가능해요. 그래서 lazy 브랜치는 위 filter 표현에서 문제가 없고, 여러분도 비슷한 기법으로 자신의 lazy 함수에서 메모리 사용을 통제할 수 있어요.

더 알아보기