제너레이터, 그게 뭔데?

요즘은 알고리즘 문제를 푼 후에 ChatGPT에게서 피드백을 받는데, 종종 리스트 대신 제너레이터를 쓰라는 이야기를 듣는다. 이름은 많이 들어봤지만 무엇인지는 잘 몰라서 이 기회에 알아보려고 한다.

간단히 알아보는 제너레이터

제너레이터는 지연 평가를 위한 장치다. 지연 평가란 함수를 실행하는 시점을 늦춘다는 이야기다.

함수가 실행되는 과정은 다음과 같다. 개발자가 소스 코드를 작성하고, 컴파일 타임에 해당 내용이 바이트 코드로 변환된다. 이후 개발자가 함수를 호출하면, 함수 프레임이 스택 영역에 쌓이고, 함수가 실행을 마친 후에는 함수 프레임이 스택 영역에서 제거된다. 즉, 함수 블록 내의 모든 코드는 함수를 호출했을 때 한 번에 실행된다.

하지만 어떤 경우에는 함수의 실행 시점을 제어해야 한다.

파일로부터 데이터를 읽어와서 화면에 표시해야 하는 경우, 얼마만큼의 용량을 읽어야 할까?

파일을 전부 다 읽으려고 하니까 메모리가 걱정된다. 그렇다고 일정량만 읽으려고 하니까 화면이 크면 데이터가 부족할 수 있어 걱정이다. 이런 때가 제너레이터를 쓸 때이다. 제너레이터는 원하는 때에 원하는 만큼만 실행할 수 있는 이터레이터이다. 그렇기 때문에 함수의 실행 시점을 제어할 수 있게 해준다.

사용 방법

초기화

sequence { // 피보나치 수열을 만드는 제너레이터 함수
  var a = 0
  var b = 1
  yield(a)
  yield(b)
  while (true) {
    yield a + b
    val temp = a + b
    a = b
    b = temp
  }
}

사용 방식은 언어마다 약간씩 다르지만 대체로 비슷하다. 기존 함수는 return 키워드를 통해 값을 반환하고 함수를 종료했다면, 제너레이터 함수는 yield 키워드를 통해 값을 반환하고 제너레이터 함수가 일시 종료된다. 일시 종료되었다는 말은 해당 제너레이터 함수를 다시 호출하면 이전 종료 시점부터 이어서 실행된다는 뜻이다.

TypeScript와 Python에서도 사용 방법은 비슷하다. TypeScript에서는 function 대신 function* 키워드를 쓰고 기존 반환 타입 T를 Generator<T>로 바꾸면 된다. Python에서는 일반 함수에서 yield를 사용하면 자동으로 제너레이터가 되고, 리스트 컴프리헨션에서 대괄호([, ]) 대신 소괄호((, ))를 쓰면 된다.

제너레이터 순회

Kotlin의 경우 sequence 빌더가 Sequence<T> 타입 객체를 반환한다. iterator()을 호출하여 next()를 직접 호출해도 되고, take(), filter() 등의 함수를 사용해도 된다. TypeScript의 경우 Generator<T> 타입 객체의 next()를 호출한다. Python의 경우 제너레이터 함수가 제너레이터 객체를 반환하고, next(generator) 또는 next(generator, default_value) 와 같이 사용한다.

제너레이터 함수가 return을 호출한 이후 next()를 호출하는 경우 Kotlin과 Python에서는 예외가 발생한다(각각 NoSuchElementException, StopIteration). TypeScript에서는 { value: undefined, done: true }를 반환한다. 세 언어 모두 for문을 사용하면 제너레이터 함수가 종료될 때까지 안전하게 순회한다.

제너레이터 vs 리스트

사실 제너레이터로 할 수 있는 작업은 거의 대부분 리스트로도 할 수 있다. 그렇다면 제너레이터는 언제 써야할까? API 페이지네이션과 같이 결과 값을 저장할 필요 없이 한 방향으로 순회할 때, 또는 파일을 읽거나 무한 시퀀스를 만들 때처럼 메모리 효율이 중요할 때에도 제너레이터를 사용하면 좋다. 반면 데이터의 크기가 작은 경우, 데이터를 여러 번 순회하거나 인덱싱이 필요한 경우에는 리스트를 사용하는 것이 좋다.

어떻게 함수를 멈춘거야?

제너레이터 함수는 이전 실행 상태를 기억한다. 그게 어떻게 가능한 걸까? 기본적으로 Kotlin, TypeScript, Python 모두 yield() 호출시에 함수 실행 정보를 저장한다. 다만 실행 정보를 저장하는 방식은 약간씩 다르다.

Kotlin에서는 컴파일 타임에 제너레이터 함수를 상태 머신으로 변환한다. 즉, 제너레이터 함수를 상태에 따라 분기되는 일반 함수로 분해한다. 이후 런타임에 제너레이터 함수를 호출할 때마다 상태를 업데이트한 후에 제너레이터 함수를 실행한다. (이 역할은 Continuation 객체가 수행한다)

TypeScript, Python에서는 런타임에 제너레이터 함수의 실행 정보를 제너레이터 객체에 저장한다. 제너레이터 함수를 재호출하면 제너레이터 객체에 저장된 정보를 스택 영역에 복원해서 이전 종료 지점부터 함수가 재개된다.