[220120] 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 매크로를 보자
아래는 clojure 의 lazy-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();
}
LazySeq 는 ISeq 구현체이다. 그러므로 LazySeq 안에 있는 first 를 사용한다.
// LazySeq.java
public Object first(){
seq();
if(s == null)
return null;
return s.first();
}
seq를 수행한다.seq은sval을 수행한다.sval은 호출하지 않은fn을 호출하고,sv에 저장한다.
seq은sv를 가져와서seq로 변환한다.(lazy-seq 구현체에 의하면
sv는(cons a b)이 형태로 되어 있는 값이 될 것)이 Cons에
seq을 걸면 그대로 리턴한다.- 그래서
(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)) 형태로 만들어버린 것이다.
그러니 Cons 는 next 가 얼마나 큰지 모른다. 그저 LazySeq 이라는 객체가 들어온 것이다.
그 안에는 fib 함수를 수행할 수 있는 익명함수 thunk 가 있을 뿐이다.