Python: Generator

 

이번 주에는 Generator에 대해서 알아보기로 했습니다.

레퍼런스는 PEP 255 문서입니다. 이 레퍼런스는 파이썬의 Generator 개념과 yield statement에 대해 설명하고 있습니다.

학습을 위해 문서의 일부를 번역, 의역하였으며, 오역이 있다면 말씀 부탁드립니다!

Generator 개념이 생겨난 이유

Motivation의 첫 번째 문장은 다음과 같습니다:

When a producer function has a hard enough job that it requires maintaining state between values produced, most programming languages offer no pleasant and efficient solution beyond adding a callback function to the producer's argument list, to be called with each value produced.

생산자(producer) 함수가 생성되는 값 사이에 상태를 유지하는 작업을 수행해야 할 때, 대부분의 프로그래밍 언어들은 생산자 함수의 인자에 값이 생성될 때마다 호출될 콜백 함수를 추가하는 방법 외에는 효과적인 솔루션을 제공하지 않는다.

문서에 있는 예시를 통해 위 문장이 어떤 의미인지 알아보겠습니다. 예시에서는 tokenize.py의 tokenize()와 tabnanny.py의 tokeneater()를 예로 들고 있습니다.

문서의 Python-Verion이 2.2이므로, 2.1의 코드를 찾아보았으며, 다음 파일을 참고하시면 되겠습니다: tokenize.py, tabnanny.py

 

tokenize() 일부

def tokenize(readline, tokeneater=printtoken):
    try:
        tokenize_loop(readline, tokeneater)
    except StopTokenizing:
        pass

def tokenize_loop(readline, tokeneater):
    lnum = parenlev = continued = 0
    namechars, numchars = string.letters + '_', string.digits
    contstr, needcont = '', 0
    contline = None
    indents = [0]

    while 1:                                   # loop over lines in stream
        line = readline()
        lnum = lnum + 1
        pos, max = 0, len(line)

        if contstr:                            # continued string
            if not line:
                raise TokenError, ("EOF in multi-line string", strstart)
            endmatch = endprog.match(line)
            if endmatch:
                pos = end = endmatch.end(0)
                tokeneater(STRING, contstr + line[:end],
                           strstart, (lnum, end), contline + line)
                contstr, needcont = '', 0
                contline = None
            elif needcont and line[-2:] != '\\\n' and line[-3:] != '\\\r\n':
                tokeneater(ERRORTOKEN, contstr + line,
                           strstart, (lnum, len(line)), contline)
                contstr = ''
                contline = None
                continue

tokeneater() 일부

def tokeneater(type, token, start, end, line,
                   INDENT=tokenize.INDENT,
                   DEDENT=tokenize.DEDENT,
                   NEWLINE=tokenize.NEWLINE,
                   JUNK=(tokenize.COMMENT, tokenize.NL) ):
        global indents, check_equal

        if type == NEWLINE:
            # a program statement, or ENDMARKER, will eventually follow,
            # after some (possibly empty) run of tokens of the form
            #     (NL | COMMENT)* (INDENT | DEDENT+)?
            # If an INDENT appears, setting check_equal is wrong, and will
            # be undone when we see the INDENT.
            check_equal = 1

        elif type == INDENT:
            check_equal = 0
            thisguy = Whitespace(token)
            if not indents[-1].less(thisguy):
                witness = indents[-1].not_less_witness(thisguy)
                msg = "indent not greater e.g. " + format_witnesses(witness)
                raise NannyNag(start[0], msg, line)
            indents.append(thisguy)

        elif type == DEDENT:
            # there's nothing we need to check here!  what's important is
            # that when the run of DEDENTs ends, the indentation of the
            # program statement (or ENDMARKER) that triggered the run is
            # equal to what's left at the top of the indents stack

            # Ouch!  This assert triggers if the last line of the source
            # is indented *and* lacks a newline -- then DEDENTs pop out
            # of thin air.
            # assert check_equal  # else no earlier NEWLINE, or an earlier INDENT
            check_equal = 1

            del indents[-1]

코드의 기능보다는 특징을 중점으로 보면 될 것 같습니다.

tokenize()의 경우, tokeneater라는 callable 인자를 받고 있습니다. 그리고 토큰이 생산되면 tokeneater(콜백함수)을 호출하게 됩니다.

tokeneater()는 호출될 때마다 마지막에 읽었던 토큰을 기억하고 있어야합니다. 이를 위해 tokeneater() 내부에 global variable을 사용함으로써 지금까지 읽은 토큰을 기억할 수 있고 어떤 토큰을 기대해야 할지 결정할 수 있습니다.

문서는 이러한 방식으로 작동하도록 만드는 것이 어려웠고, 다른 사람들이 이해하기도 어렵다고 합니다. 그래서 여러 대안을 내놓습니다.

1. 한번 파싱 후, 전체 토큰을 리스트로 내보내는 방법
   전체 데이터가 있으니 tokenize를 사용하는 입장에서는 편리합니다. 하지만 데이터가 커질 수 있을뿐더러, 앞부분의 토큰들만 읽고자 하는 경우 낭비입니다.
2. iterator을 사용하는 방법 (next()를 호출하여 다음 토큰을 반환)
   위의 문제를 해결할 수 있지만, 이는 결국 토큰화 과정에 상태 관리의 짐을 맡기는 셈이 됩니다. 그리고 코드를 iterator 형식으로 변경하는 것도 고려해야 합니다.
3. 생산자와 소비자 스레드 분리
   파이썬에서 synchronized-communication 방법을 제공하긴 하지만, 스레드가 없는 플랫폼에서는 작동하지 않습니다. 스레드가 존재하는 플랫폼에서도 (비교적) 느릴 것입니다.
4. Stackless 종류 구현
   스레드 옵션의 특징을 가지고 있고 더 효율적이나 논쟁의 여지가 있는(controversial) 방법이며, Jython에서 구현이 불가능할 수 있습니다.

대안을 다 소비한 상태에서 generator라는 개념이 등장합니다. 문서는 이 개념이 Sather, CLU의 iterator, Icon의 generator와 비슷한 방식이라고 설명합니다.

새로 등장하는 generator 함수는, yield를 기준으로, 함수의 로컬 상태(컨텍스트)를 유지하면서 호출자에게 결과값(next value)을 즉시 반환합니다. 함수의 상태가 유지되므로 다시 호출되었을 때 재개하여 다음 결과값을 받을 수 있습니다.

아래 코드로 generator 함수의 동작을 알아보겠습니다.

def fib():
    a, b = 0, 1
    while 1:
       yield b
       a, b = b, a+b

fib()가 처음 수행되면, a의 값을 0, b의 값을 1로 설정합니다. 그리고 호출자에게 b, 값 1을 넘깁니다. 다시 fib가 수행되면, yield 다음부터 수행되어, a의 값을 1, b의 값을 1로 설정하고 값 1을 넘깁니다.

fib()의 관점에서는 이전 콜백 방식과 같이 일련의 결과를 하나씩 넘겨줍니다. fib()의 호출자 관점에서는 호출자의 자의에 따라 재개, 결과를 받을 수 있는 iterable 객체를 가집니다.

이는 스레드의 방식과 같이 (가장) 자연스러운 방법으로 구성되면서, 스레드가 호환되지 않는 플랫폼에서도 사용할 수 있습니다. 그리고 generator를 재개하는 부담은 함수를 호출하는 부담을 넘어가지 않습니다.

이러한 방식은 producer/consumer 함수형식에 적용할 수 있습니다. 앞에서 예시를 들었던 tokenize()와 tokeneater()의 경우, tokenize()는 다음 token을 yield 하면 되고, tokeneater()는 자의에 따라 토큰을 iterate 하면 됩니다. Python generator는 특별하고 강력한 iterator로 볼 수 있습니다.

Specification: Yield

About yield keyword

yield_stmt: yield expression_list

yield는 함수 내부에서만 사용할 수 있으며, yield를 포함하는 함수를 generator 함수라고 합니다. Generator 함수는 일반 함수와 동일하나 객체의 co_flags에 CO_GENERATOR 플래그가 설정됩니다.

Generator 함수가 호출되었을 때, 주어진 인자들이 일반함수와 동일하게 bind 되지만 함수의 코드는 실행되지 않습니다. 대신 iterator protocol을 만족하는 generator-iterator 객체가 반환됩니다.

generator-iterator의 next()가 호출될 때마다, generator 함수에서 yield까지, 또는 return까지, 또는 함수의 끝에 도달할 때까지 수행됩니다.

실행 중 yield를 만나게 되면, 함수의 상태는 얼고(frozen) expression_list의 값이 next()의 호출자에게 전달됩니다. 언 상태란 다음에도 재개할 수 있도록 지역적인(local) 상태, Instruction Pointer, Stack 등이 보존된다는 의미입니다.

Restrictions

1. yield는 try/finally 형태의 try 내부에서 사용할 수 없습니다. finally 코드가 수행된다는 보장이 없기 때문입니다.
2. 이미 실행 중인 generator에 대해서는 next()를 호출할 수 없습니다.

   >>> def g():
   ...     i = me.next()
   ...     yield i
   >>> me = g()
   >>> me.next()
   Traceback (most recent call last):
   ...
   File "<string>", line 2, in g
   ValueError: generator already executing

Specification: Return

return

generator 함수의 return문은 값을 반환할 수 없습니다.

generator에서 return문은 일반 함수와 동일하게 작동하며 StopIteration Exception을 raise 합니다. 명시적인 return이 없어도 함수의 끝에 도달하게 되면 StopIteration Exception이 발생합니다.

generator 함수, 일반 함수의 return은 모두 함수의 종료, 더이상 반환할 값이 없다는 것을 의미합니다.

Specification: Generators and Exception Propagation

코드 내부에서 처리되지 않은 Exception이 있다면, 일반 함수와 동일하게 호출자에게 전달됩니다. 그 후 재개(next())한다면 StopIteration이 발생합니다.

>>> def f():
...     return 1/0
>>> def g():
...     yield f()  # the zero division exception propagates
...     yield 42   # and we'll never get here
>>> k = g()
>>> k.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 2, in g
  File "<stdin>", line 2, in f
ZeroDivisionError: integer division or modulo by zero
>>> k.next()  # and the generator cannot be resumed
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
StopIteration
>>>

Specification: Try/Except/Finally

앞에서 언급했듯이, yield는 try/finally의 try 내부에서 사용할 수 없습니다. 결과적으로 generator를 사용할 때에는 자원 할당에 신중해야 합니다. finally 내부, except 내부, 그리고 try/except의 try 내부에서 yield를 사용하는 것은 괜찮습니다.

>>> def f():
...     try:
...         yield 1
...         try:
...             yield 2
...             1/0
...             yield 3  # never get here
...         except ZeroDivisionError:
...             yield 4
...             yield 5
...             raise
...         except:
...             yield 6
...         yield 7     # the "raise" above stops this
...     except:
...         yield 8
...     yield 9
...     try:
...         x = 12
...     finally:
...        yield 10
...     yield 11
>>> print list(f())
[1, 2, 4, 5, 8, 9, 10, 11]
>>>

Example

아래는 트리의 중위순회에 대한 코드입니다.

class Tree의 __iter__는 inorder 함수를 호출한 결과를 넘겨줌으로써, 호출자에게 generator-iterator을 넘겨줍니다.

inorder 함수는 generator 함수로, 문서에서는 재귀 버전과 비-재귀 버전을 제공합니다.

Generator 개념을 도입하여 traversal이 한 번에 모두 실행되는 것이 아닌, next 함수를 이용해 중위 순회 순서로 하나의 노드씩 반환받는 것이 가능해졌습니다.

# A binary tree class.
class Tree:

    def __init__(self, label, left=None, right=None):
        self.label = label
        self.left = left
        self.right = right

    def __repr__(self, level=0, indent="    "):
        s = level*indent + `self.label`
        if self.left:
            s = s + "\n" + self.left.__repr__(level+1, indent)
        if self.right:
            s = s + "\n" + self.right.__repr__(level+1, indent)
        return s

    def __iter__(self):
        return inorder(self)

# Create a Tree from a list.
def tree(list):
    n = len(list)
    if n == 0:
        return []
    i = n / 2
    return Tree(list[i], tree(list[:i]), tree(list[i+1:]))

# A recursive generator that generates Tree labels in in-order.
def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x
        yield t.label
        for x in inorder(t.right):
            yield x

# Show it off: create a tree.
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# Print the nodes of the tree in in-order.
for x in t:
    print x,
print

# A non-recursive generator.
def inorder(node):
    stack = []
    while node:
        while node.left:
            stack.append(node)
            node = node.left
        yield node.label
        while not node.right:
            try:
                node = stack.pop()
            except IndexError:
                return
            yield node.label
        node = node.right

# Exercise the non-recursive generator.
for x in t:
    print x,
print

# OUTPUT: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

주의

python2에서는 generator_iterator.next() 형식을 사용했지만, python3로부터는 next(generator_iterator) 형식을 사용해야 합니다.