Clojure Lazy Seq

Table of Contents

1 Clojure의 LazySeq은 어떻게 구현되어 있는가

우연히 사내 부트캠프를 하는 중에 clojure에서 사용하는 lazy-seq 에 대한 날카로운 질문을 받았다. 왜 다음과 같은 코드에서 콜스택이 넘치지 않고 수행될 수 있는 것인가( clojure 에서는 recur 가 없으면 꼬리재귀를 수행하지 않는다.)

(defn fib
  ([]
   (fib 1 1))
  ([a b]
   (lazy-seq (cons a (fib b (+ a b))))))
(take 5 (fib))

나는 당연히 lazy-seq 은 매크로이며, 이것은 자바의 LazySeq 구현체로 들어가면서 평가가 지연되기 때문이라고 말했다. 하지만 어떻게 그것이 가능한지는 말하지 못했다.

그것은 자바 구현체를 보여주면서 설명해야 하기 때문이다.

2 lazy-seq 매크로를 보자

아래는 clojurelazy-seq 구현체이다.

(defmacro lazy-seq
  "Takes a body of expressions that returns an ISeq or nil, and yields
  a Seqable object that will invoke the body only the first time seq
  is called, and will cache the result and return it on all subsequent
  seq calls. See also - realized?"
  {:added "1.0"}
  [& body]
  (list 'new 'clojure.lang.LazySeq (list* '^{:once true} fn* [] body)))

여기서 '^{:one true} 는 한번만 평가됨을 말한다. Link

2.1 fn* 함수

fn* 는 클로저 컴파일러에 정의된 이름이다. [Link] 우리는 fn 이라는 함수를 쓰지만 내부적으로는 fn* 를 사용한다. 마지막에 들어오는 값을 리스트들을 하나의 묶음으로 받을텐데 (& 로 받을테니까) 그것들을 풀어서 사용할 수 있게한다.

fn*fn 만 사용하지는 않는다. 컴파일러에 다음과 같은 코드가 있다.

static final Symbol FN = Symbol.intern("fn*");
static final Symbol FNONCE = (Symbol) Symbol.intern("fn*").withMeta(RT.map(Keyword.intern(null, "once"), RT.T));

이렇게 두곳에서 사용하는 것을 볼 수 있다. FNONCE 에서 "once"RT.T(true) 를 넣는 것은 한번만 수행한다는 것을 말한다.

2.2 list* 함수

여기서 list*list 와 하는 행위가 다르다. 마지막 값은 풀어서 받는다는 것이 특징이다.

(defn spread
  {:private true
   :static true}
  [arglist]
  (cond
   (nil? arglist) nil
   (nil? (next arglist)) (seq (first arglist))
   :else (cons (first arglist) (spread (next arglist)))))

(defn list*
  "Creates a new seq containing the items prepended to the rest, the
  last of which will be treated as a sequence."
  {:added "1.0"
   :static true}
  ([args] (seq args))
  ([a args] (cons a args))
  ([a b args] (cons a (cons b args)))
  ([a b c args] (cons a (cons b (cons c args))))
  ([a b c d & more]
     (cons a (cons b (cons c (cons d (spread more)))))))

사용법은 아래와 같다.

(list* 1 2 [3 4])
;=> (1 2 3 45)

2.3 lazy-seq 를 매크로 확장

(macroexpand-1 '(lazy-seq (cons a (fib b (+ a b)))))

;;=>(new clojure.lang.LazySeq #(cons a (fib b (+ a b))))

특이한 것은 LazySeq 은 컬렉션이 아니라 함수를 받는다는 것이다. 이 함수는 cons 를 수행한다. 즉, a 와 그 다음을 값을 가질 수 있는 함수 를 cons로 더한다.

우리는 마치 Iterator 를 받은 것과 같다. 끝을 알 수 없는…

LazySeq 의 자바 구현을 보자.

public final class LazySeq extends Obj implements ISeq, Sequential, List, IPending, IHashEq {

  private Ifn fn;  // fn 는 Realized 여부를 알 수 있게 한다. 한번 평가되고 null 이 되어버린다.
  private Object sv;  // 평가되면 sv 에 그 값이 들어간다. 
  private ISeq s;  // s는 LazySeq내부적으로 갖는 seq값이다.

  public LazySeq(Ifn fn) {
    this.fn = fn;
  }

  public Object first() {
    seq();
    if (s == null) return null;
    return s.first();
  }

  public ISeq next() {
    seq();
    if (s == null) return null;
    return s.next();
  }

  public ISeq more(){
	seq();
	if(s == null)
	  return PersistentList.EMPTY;
    return s.more();
  }

  public ISeq cons(Object o){
    return RT.cons(o, seq());
  }
}

그럼 상상해보자. first 가 수행되면 어떻게 될까? 일단 RT.first 가 수행된다.

static public Object first(Object x){
  if(x instanceof ISeq)
    return ((ISeq) x).first();
  ISeq seq = seq(x);
  if(seq == null)
    return null;
  return seq.first();
}

LazySeqISeq 구현체이다. 그러므로 LazySeq 안에 있는 first 를 사용한다.

// LazySeq.java
public Object first(){
  seq();
  if(s == null)
    return null;
  return s.first();
}
  1. seq 를 수행한다.
  2. seqsval 을 수행한다.
    • sval 은 호출하지 않은 fn 을 호출하고, sv 에 저장한다.
  3. seqsv 를 가져와서 seq 로 변환한다.

    (lazy-seq 구현체에 의하면 sv(cons a b) 이 형태로 되어 있는 값이 될 것)

    이 Cons에 seq 을 걸면 그대로 리턴한다.

  4. 그래서 (class (seq (fib))) => clojure.lang.Cons 라는 답이 나오는 것이다.
// LazySeq.java
static public ISeq seq(Object coll){
  if(coll instanceof ASeq)  // Cons는 ASeq의 구현체이다.
    return (ASeq) coll;
  else if(coll instanceof LazySeq)
    return ((LazySeq) coll).seq();
  else
    return seqFrom(coll);
}

final synchronized public ISeq seq(){
  sval();
  if(sv != null) {
    Object ls = sv;
    sv = null;
    while(ls instanceof LazySeq) {
      ls = ((LazySeq)ls).sval();
    }
    s = RT.seq(ls);
  }
  return s;
}

final synchronized Object sval(){
  if(fn != null) {
    sv = fn.invoke();
    fn = null;
  }
  if(sv != null)
    return sv;
  return s;
}

Cons 구현체를 보자.

final public class Cons extends ASeq implements Serializable {
  private final Object _first;
  private final ISeq _more;

  public Cons(Object first, ISeq _more){
    this._first = first;
    this._more = _more;
  }

  public Object first(){
	  return _first;
  } 

  public ISeq next(){
    return more().seq();
  }

  public ISeq more(){
    if(_more == null)
      return PersistentList.EMPTY;
    return _more;
  }
}

Cons 가 생길 때, 어떻게 LazySeq 가 생성되서 _more 필드에 들어가는 것일까?

그것은 바로 LazySeq#sval()fn.invoke() 를 했을 때, 이미 Cons(a, new LazySeq(IFn)) 형태로 만들어버린 것이다.

그러니 Consnext 가 얼마나 큰지 모른다. 그저 LazySeq 이라는 객체가 들어온 것이다.

그 안에는 fib 함수를 수행할 수 있는 익명함수 thunk 가 있을 뿐이다.

Date: 2022-01-20 Thu 00:00

Author: Younghwan Nam

Created: 2022-09-14 Wed 01:26

Emacs 27.2 (Org mode 9.4.4)

Validate