logo
Nostrss
Published on

이번에는 지연 평가(feat: 제너레이터) 😎

Authors
Lazy Evaluation Debugging

지금까지의 여정

지금까지 함수형 프로그래밍을 위한 도구와 같은 기능들을 하나씩 만들어왔다.

지난 글에서 즉시 평가 파이프라인의 실행 흐름을 추적했다. range, map, filter가 각각 10개의 요소를 전부 처리한 뒤 take에서 2개만 골라가는 구조였고, 총 32회 연산이 필요했다.

오늘은 같은 파이프라인을 지연 평가(제너레이터) 버전으로 바꿨을 때, 실행 흐름이 어떻게 달라지는지 추적해보자.

오늘의 코드

먼저 오늘 사용할 함수들을 전부 모아보자. curry, reduce, go, take는 지난 글과 동일하고, L.range, L.map, L.filter가 제너레이터 버전으로 바뀌었다.

const log = console.log

const curry =
  (f) =>
  (a, ..._) =>
    _.length ? f(a, ..._) : (..._) => f(a, ..._)

const reduce = curry((f, acc, iter) => {
  if (!iter) {
    iter = acc[Symbol.iterator]()
    acc = iter.next().value
  }
  for (const a of iter) {
    acc = f(acc, a)
  }
  return acc
})

const go = (...args) => reduce((a, f) => f(a), args)

const L = {}

L.range = function* (l) {
  let i = -1
  while (++i < l) {
    yield i
  }
}

L.map = curry(function* (f, iter) {
  for (const a of iter) {
    yield f(a)
  }
})

L.filter = curry(function* (f, iter) {
  for (const a of iter) {
    if (f(a)) yield a
  }
})

const take = curry((l, iter) => {
  let res = []
  for (const a of iter) {
    res.push(a)
    if (res.length == l) return res
  }
  return res
})

핵심 차이를 보자. 즉시 평가의 range, map, filter는 배열을 만들어 반환했다. 지연 평가의 L.range, L.map, L.filter는 제너레이터 함수(function*)로, yield로 값을 하나씩 내보낸다.

그리고 이 함수들을 조합한 최종 코드다.

go(
  L.range(10),
  L.map((n) => n + 10),
  L.filter((n) => n % 2),
  take(2),
  log
)

결과는 동일하게 [11, 13]이다. 하지만 내부 실행 흐름은 완전히 다르다. 한 단계씩 따라가보자.

0단계: L.range(10) — 아무 일도 일어나지 않는다 ⭐

go에 들어가기 전에, 첫 번째 인자인 L.range(10)이 평가된다.

L.range = function* (l) {
  let i = -1
  while (++i < l) {
    yield i
  }
}

그런데 여기가 즉시 평가와의 핵심적인 차이다.

즉시 평가의 range(10)은 호출 즉시 while 루프를 돌며 [0, 1, 2, ..., 9] 배열을 만들어 반환했다. 10회 연산.

반면 L.range(10)은 제너레이터 함수다. 제너레이터 함수를 호출하면 함수 본체는 실행되지 않는다. 대신 이터레이터 객체만 반환된다. while 루프? 아직 한 번도 돌지 않았다.

L.range(10)  →  Generator { <suspended> }   // 이터레이터 객체만 반환
range(10)    →  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  // 즉시 10개 배열 생성

여기까지 연산 0회. 이것이 "지연"의 의미다. 값이 필요할 때까지 실행을 미룬다.

1단계: go → reduce → 제너레이터 체인 구성 ⭐⭐

이제 go 함수가 호출된다.

const go = (...args) => reduce((a, f) => f(a), args)

go에 들어온 인자들을 정리해보자.

  • args[0]: Generator { <suspended> } (L.range가 반환한 이터레이터)
  • args[1]: L.map((n) => n + 10) — curry 덕분에 함수를 반환한 상태
  • args[2]: L.filter((n) => n % 2) — 역시 함수를 반환한 상태
  • args[3]: take(2) — 역시 함수를 반환한 상태
  • args[4]: log 함수

즉시 평가 때와 비슷하다. 다만 args[0]이 배열이 아닌 제너레이터 이터레이터라는 것이 다르다.

go → reduce 초기화

go가 reduce를 호출하고, reduce 내부에서 args 배열의 이터레이터를 만들어 첫 번째 값을 acc로 꺼내는 과정은 지난 글과 동일하다.

  • acc = args[0] = Generator { <suspended> } (= rangeIter라고 부르자)
  • 이터레이터에는 함수 4개가 남아있다

reduce의 for 루프 시작

for (const a of iter) {
  acc = f(acc, a)
}

반복 1: a = L.map((n) => n + 10)이 반환한 커리된 함수

f(acc, a) → a(acc) → L.map의 커리된 함수에 rangeIter가 들어간다.

L.map = curry(function* (f, iter) {
  for (const a of iter) {
    yield f(a)
  }
})

하지만 L.map도 제너레이터 함수다! 호출하면 역시 함수 본체는 실행되지 않고, 새로운 이터레이터 객체만 반환된다.

acc = Generator { <suspended> } (= mapIter라고 부르자. 내부적으로 rangeIter를 참조)

반복 2: a = L.filter((n) => n % 2)가 반환한 커리된 함수

f(acc, a) → a(acc) → L.filter의 커리된 함수에 mapIter가 들어간다.

L.filter = curry(function* (f, iter) {
  for (const a of iter) {
    if (f(a)) yield a
  }
})

L.filter도 제너레이터 함수! 역시 이터레이터 객체만 반환된다.

acc = Generator { <suspended> } (= filterIter라고 부르자. 내부적으로 mapIter를 참조)

여기까지 연산 0회! 제너레이터가 서로를 감싸는 체인만 구성됐다.

filterIter → mapIter → rangeIter

마치 러시안 인형(마트료시카)처럼 이터레이터가 겹겹이 감싸져 있다. 하지만 아무도 아직 값을 만들지 않았다.

반복 3: a = take(2)가 반환한 커리된 함수

f(acc, a) → a(acc) → take의 커리된 함수에 filterIter가 들어간다.

const take = curry((l, iter) => {
  let res = []
  for (const a of iter) {
    res.push(a)
    if (res.length == l) return res
  }
  return res
})

take는 일반 함수다! 제너레이터가 아니다. for...of로 filterIter에서 값을 당기기(pull) 시작한다. 이 순간 전체 체인이 가동된다.

2단계: take가 첫 번째 값을 요청한다 ⭐⭐⭐

take의 for (const a of iter)가 실행되면, filterIter에게 .next()를 호출한다. 여기서부터가 지연 평가의 진짜 매력이다. 한 값이 체인 전체를 세로로 통과한다.

값 0 추적

take → filterIter.next() 호출

filter 본체가 처음으로 실행된다:

// L.filter 내부
for (const a of iter) {   // iter = mapIter
  if (f(a)) yield a
}

mapIter.next() 호출

map 본체가 처음으로 실행된다:

// L.map 내부
for (const a of iter) {   // iter = rangeIter
  yield f(a)
}

rangeIter.next() 호출

range 본체가 처음으로 실행된다:

// L.range 내부
let i = -1
while (++i < l) {    // l = 10
  yield i
}

++i → i = 0, 0 < 10 ✅ → yield 0 → range가 0을 내보내고 멈춘다.

map이 0을 받는다: f(0) = 0 + 10 = 10 → yield 10 → map이 10을 내보내고 멈춘다.

filter가 10을 받는다: f(10) = 10 % 2 = 0 → ❌ 탈락! yield 하지 않는다.

filter는 다음 값을 찾기 위해 mapIter.next()를 다시 호출한다.

값 1 추적

map → rangeIter.next() 호출

range: ++i → i = 1, 1 < 10 ✅ → yield 1

map이 1을 받는다: f(1) = 1 + 10 = 11 → yield 11

filter가 11을 받는다: f(11) = 11 % 2 = 1 → ✅ 통과! → yield 11

take가 11을 받는다: res.push(11) → res = [11], res.length == 2? ❌ (1개) → 계속

여기까지의 흐름을 정리하면:

요청rangemapfiltertake
1차yield 0yield 1010%2=0 ❌-
2차yield 1yield 1111%2=1 ✅, yield 11res=[11]

연산 횟수: range 2회, map 2회, filter 2회, take 1회 = 7회

3단계: take가 두 번째 값을 요청한다 ⭐⭐⭐

take의 for...of가 다시 filterIter.next()를 호출한다.

값 2 추적

filter → mapIter.next() → map → rangeIter.next() → range

range: ++i → i = 2, 2 < 10 ✅ → yield 2

map이 2를 받는다: f(2) = 2 + 10 = 12 → yield 12

filter가 12를 받는다: f(12) = 12 % 2 = 0 → ❌ 탈락!

filter가 다음 값을 찾기 위해 계속한다.

값 3 추적

map → rangeIter.next() → range

range: ++i → i = 3, 3 < 10 ✅ → yield 3

map이 3을 받는다: f(3) = 3 + 10 = 13 → yield 13

filter가 13을 받는다: f(13) = 13 % 2 = 1 → ✅ 통과! → yield 13

take가 13을 받는다: res.push(13) → res = [11, 13], res.length == 2? ✅ → return!

요청rangemapfiltertake
3차yield 2yield 1212%2=0 ❌-
4차yield 3yield 1313%2=1 ✅, yield 13res=[11, 13] → return

추가 연산 횟수: range 2회, map 2회, filter 2회, take 1회 = 7회

take가 return하는 순간, for...of 루프가 끝난다. filterIter에게 더 이상 .next()를 호출하지 않는다. 따라서 mapIter와 rangeIter도 더 이상 실행되지 않는다.

값 4, 5, 6, 7, 8, 9는 아예 생성조차 되지 않았다!

4단계: log 실행

reduce의 for 루프, 마지막 반복이다.

  • a: log 함수 (console.log)
  • acc: [11, 13]

f(acc, a) → a(acc) → log([11, 13]) → [11, 13] 출력!

전체 흐름 비교 — 가로 vs 세로

즉시 평가: 가로 방향

range   : 0  1  2  3  4  5  6  7  8  9     → 10개 전부 생성
             ↓↓↓↓↓↓↓↓↓↓
map     : 10 11 12 13 14 15 16 17 18 19    → 10개 전부 변환
             ↓↓↓↓↓↓↓↓↓↓
filter  :    11    13    15    17    19     → 10개 전부 검사
             ↓↓
take    :    11    13                       → 2개 가져감

한 단계를 모든 요소에 완료한 뒤 다음 단계로 넘어간다. 가로로 쭉, 가로로 쭉.

지연 평가: 세로 방향

         값0  값1  값2  값3
range  :  0    1    2    3     ← 4개만 생성 (4~9는 생성 안 함)
          ↓    ↓    ↓    ↓
map    :  10   11   12   13    ← 4개만 변환
          ↓    ↓    ↓    ↓
filter :  ❌   ✅   ❌   ✅    ← 4개만 검사
               ↓         ↓
take   :      [11]  [11, 13]   ← 2개 채우고 종료!

한 요소가 모든 단계를 통과한 뒤 다음 요소로 넘어간다. 세로로 쭉, 세로로 쭉.

필요한 2개가 채워지면 나머지 요소는 아예 건드리지 않는다. 이것이 지연 평가의 힘이다.

연산 횟수 비교

즉시 평가지연 평가
range10회4회
map10회4회
filter10회4회
take2회2회
합계32회14회

지연 평가로 바꾸기만 했을 뿐인데 연산 횟수가 56% 줄었다.

여기서 진짜 빛나는 건 데이터가 많아질 때다.

range(10)을 range(10000)으로 바꿔보자.

즉시 평가지연 평가
range10,000회4회
map10,000회4회
filter10,000회4회
take2회2회
합계30,002회14회

즉시 평가는 30,002회. 지연 평가는 여전히 14회. take(2)가 2개만 필요하다고 말하는 순간, 지연 평가는 딱 그만큼만 일한다. 데이터 크기가 아무리 커져도 필요한 만큼만 연산한다.

이것이 지연 평가의 본질이다. 소비자(take)가 "이만큼만 줘"라고 요청하면, 생산자(L.range, L.map, L.filter)는 요청받은 만큼만 값을 만들고 멈춘다.

출처

인프런 함수형 프로그래밍과 JavaScript ES6+ 강의를 학습하고 정리한 내용입니다.

함수형 프로그래밍과 JavaScript ES6+