[220106]js 함수만으로 자료구조부터 지연성까지 구현하기
Table of Contents
1 지연평가
Java의 Stream, Python의 generator 등등… 지연평가는 어디에나 있다. 지연평가는 일반적인 자료구조로는 할 수 없는 일을 할 수 있게 만든다.
무한으로 생성되는 자료구조가 대표사례다.
(take 5 (cycle [1 2 3]))
;=> (1 2 3 1 2)
(take 5 (repeat "x"))
;=> ("x" "x" "x" "x" "x")
무한으로 생성될 수 있는 이유는 필요한 만큼만 평가를 할 수 있기 때문이다. 컬렉션에 당장 1000개가 있어도, 맨 앞에 있는 값 하나만 필요하다면 999개는 평가하지 않는다.
2 무엇을 하는가
지연평가를 만들기 위해서 우리는 오로지 하나 함수만을 사용할 것이다. 다른 자료구조는 없다. 배열도 없다. 오로지 함수만으로 생성할 것이다.
우리는 javascript 를 사용할 것이다. clojure 를 선호한다. 하지만 javascript 로도 충분히 가능함을 보여주기 위함과 많은 사람들이 이해하기에는 javascript 가 더 좋은 선택이라고 생각한다.
3 자료구조 만들기
자료구조를 함수만으로 만드는 것이 가능한가. 함수의 가능성은 무한하다.
3.1 interface
cons a b: 두개의 인자(a,b)를 받아서 쌍을 리턴.car cons':cons로 만들어진 인자를 받아 첫번째 값(a)을 리턴.cdr cons':b을 리턴.
3.2 js로 쌍(pair) 구현하기
var cons = (a,b) => (op) => {
switch(op) {
case "car" : return a
case "cdr" : return b
}
}
var car = (cons) => cons("car")
var cdr = (cons) => cons("cdr")
car(cons(1,2))
// 1
cdr(cons(1,2))
// 2
car(cons(1, cons(2, null)))
// 1
cdr(cons(1, cons(2, null)))
// [Function (anonymous)]
car(cdr(cons (1, cons(2, null))))
// 2
4 stream 만들기
우리는 간단한 쌍을 만들었다. 이제 지연하는 쌍을 만들어볼 차례. 이것을 stream 이라고 부르자.
4.1 인터페이스
make-stream a b: 두 인자(a,b)를 받아서 stream을 리턴.stream-car stream: a를 리턴.stream-cdr stream: b를 리턴.
4.2 js로 구현하기
var streamCar = (stream) => car(stream) var streamCdr = (stream) => force(cdr(stream)) var makeStream = (a,b) => cons(a, delay(b))
4.3 force , delay 구현 및 문제점
delay는 평가를 지연시키고, force는 지연된 값을 평가시킨다.
(defn delay [a] (fn [] a)) (defn force [stream] stream)
var delay = (stream) => () => stream var force = (stream) => stream()
아쉽게도 우린 delay 함수는 사용할 수 없다. delay 는 주어진 평가를 지연할 수 있어야 한다.
하지만 우리가 구현하는 언어에서 함수를 호출하면 인자가 먼저 평가되는 규칙을 따른다. (clojure의 경우 macro를 사용하면 해결되지만 여기서는 함수만을 사용해보자.) 그렇다는 것은 애초에 인자로 함수를 넣으면 된다.
그러므로 우리는 force는 쓸 것이지만 delay는 익명함수로 대체한다.
즉, 우리는 value2 를 지연시키기 위해 아래처럼 만들 것이다.
cons(value1, () => value2)
4.4 지연스트림을 만들어보기.
4.4.1 printStream
printStream(stream) : stream 의 모든 요소를 출력한다. 이 함수는 stream 은 아니지만 추후 출력에 사용될 것이다.
var printStream = (stream) => {
if (stream == null) return
console.log(streamCar(stream))
printStream(streamCdr(stream))
}
4.4.2 range
range(start, end) : start 부터 end 까지 숫자를 stream 으로 나열한다. (즉, 필요한 만큼만 평가할 수 있다)
var range = (start, end) => {
if (start >= end) {
return null;
} else {
return cons(start, () => range(start + 1, end))
}
}
4.4.3 repeat
repeat(n) : n 을 무한으로 리턴하는 stream 을 리턴한다.
var repeat = (n) => cons(n, () => repeat(n))
4.4.4 take
take(n, stream) : n 개만큼만 stream 에서 평가하여 cons 로 반환한다.
var take = (n, stream) => {
if (n <= 0) return null;
return cons(car(stream), () => take(n-1, streamCdr(stream)))
}
4.4.5 갖고 놀기
printStream(take(5, repeat(10))) // 10 10 10 10 10 undefined printStream(take(10, range(1, 100))) // 1 .. 10 undefined printStream(range(1, 100)) // 1 .. 99 undefined
5 source code on javascript
var cons = (a, b) => (op) => {
switch(op) {
case "car" : return a
case "cdr" : return b
}
}
var car = (cons) => cons("car")
var cdr = (cons) => cons("cdr")
/*
console.log(car(cons(1,2)))
console.log(cdr(cons(1,2)))
console.log(car(cons(1, cons(2,3))))
console.log(cdr(cons(1, cons(2,3))))
console.log(car(cdr(cons(1, cons(2, 3)))))
*/
var delay = (stream) => () => stream
var force = (stream) => stream()
var streamCar = (stream) => car(stream)
var streamCdr = (stream) => force(cdr(stream))
var makeStream = (a,b) => cons(a, delay(b))
var repeat = (n) => cons(n, () => repeat(n))
var range = (start, end) => {
if (start >= end) {
return null
} else {
return cons(start, () => range(start+1, end))
}
}
var take = (n, stream) => {
if (n <= 0) return null;
return cons(car(stream), () => take(n-1, streamCdr(stream)))
}
var printAllStream = (stream) => {
while(stream != null) {
console.log(streamCar(stream))
stream = streamCdr(stream)
}
}
// 재귀를 이용하면 StackOverFlow 예외를 볼 수 있다.
var printAllStreamRecur = (stream) => {
if (stream == null) return null
console.log(streamCar(stream))
printAllStreamRecur(streamCdr(stream))
}
// printStream(take(5, repeat(10)))
// printStream(take(10, range(1, 100)))
// printStream(range(1, 100))
// printAllStreamRecur(take(10000, range(1, 1000000))) => Uncaught RangeError: Maximum call stack size exceeded
// printAllStream(take(10000, range(1, 1000000))) => 출력함.
6 making delay function on clojure (with source code)
javascript로는 불가능했지만, clojure로는 가능하다. 왜냐하면 매크로가 있기 때문이다. 매크로로 평가를 지연시킬 수 있다.
위의 javascript 코드를 clojure로 만들어보자.
(defn cons [a b]
#(case %
"car" a
"cbr" b))
(defn car [cons] (cons "car"))
(defn cdr [cons] (cons "cdr"))
(defmacro delay [expr]
`(fn [] ~expr))
(defn repeat [n] (cons n (deplay (repeat n))))
(defn range [start end]
(when (< start end)
(cons start (delay (range (inc start) end)))))
(defn take [n stream]
(when (< 0 n)
(cons (car stream)
(delay (take (dec n)
(stream-cdr stream)))))
(defn print-all-stream [stream]
(loop [s stream]
(when s
(println (stream-car s))
(recur (stream-cdr s)))))
(defn print-all-stream-recur [stream]
(when stream
(println (stream-car stream))
(println-all-stream-recur (stream-cdr stream))))
여기서 주목할 점은 javascript에서는 delay 함수를 만들 수 없어서 계속 익명함수를 만들었다.
하지만 우리는 clojure의 macro를 이용하여 delay 함수를 만들 수 있었다.
한번 실행해보자.
(print-all-stream (take 50000 (range 1 10000000))) ;; works well (print-all-stream-recur (take 50000 (range 1 1000000))) ;; java.lang.StackOverFlowError
이렇게 쉽게 지연성을 구현할 수 있었다.
재미있는 하루가 되길 바란다.
7 lambda calculus를 이용한 쌍 만들기
람다표현식으로도 쌍을 만들 수 있다. 쌍을 만든다는 것은 리스트를 만드는 것과 같다. (위에서 본 것과 같이)
위 코드는 case 문을 편법으로 사용했지만 이번에는 진짜 함수만으로 쌍을 만드는 것이다.
LISP에 대한 경의의 표현으로 cons 라는 이름을 사용했지만 이번에는 람다표현식에서 사용하는 pair 라는 이름을 붙여보자.
var pair = a => b => f => f(a)(b) var first = a => b => a var second = a => b => b pair(1)(2)(first) // 1 pair(1)(2)(second) // 2
아름답다. 하지만 꼭 아름다움 때문에 이 코드가 중요한 것은 아니다.
고계함수는 코드를 더욱 유연하게 한다.
8 Related my another blog posts
아래는 위 코드를 만들 때 도움이 될 만한 내용이 적혀있는 필자가 기고한 회사 블로그이다.
사라질 수도 있으니 적었던 내용들을 다 개인블로그로 옮겨놓아야 할지도 모르겠다.