На этом шаге мы рассмотрим решение указанной задачи.

Задача

Вы пишете код, который обходит глубоко вложенную структуру с использованием шаблона "Посетитель", но ломается, поскольку исчерпывает лимит на рекурсию. Вы бы хотели избавиться от рекурсии, но сохранить стиль программирования, использующий паттерн "Посетитель".

Решение

Генераторы иногда можно с умом применить для устранения рекурсии из алгоритмов обхода дерева или поиска. На предыдущем шаге был представлен класс-посетитель. Здесь мы покажем альтернативную реализацию этого класса, которая производит вычисления совершенно иным способом - с помощью стека и генераторов:

>>> import types
>>> class Node:
    pass

>>> class NodeVisitor:
    def visit(self, node):
        stack = [node]
        last_result = None
        while stack:
            try:
                last = stack[-1]
                if isinstance(last, types.GeneratorType):
                    stack.append(last.send(last_result))
                    last_result = None
                elif isinstance(last, Node):
                    stack.append(self._visit(stack.pop()))
                else:
                    last_result = stack.pop()
            except StopIteration:
                stack.pop()
        return last_result

    def _visit(self, node):
        methname = 'visit_' + type(node).__name__
        meth = getattr(self, methname, None)
        if meth is None:
            meth = self.generic_visit
        return meth(node)
    
    def generic_visit(self, node):
        raise RuntimeError('No {} method'.format('visit_' + type(node).__name__))

>>>

Если вы попробуете поработать с этим классом, то обнаружите, что он по-прежнему работает с существующим кодом, который мог использовать рекурсию. На самом деле вы можете использовать его в качестве прямой замены реализации класса-посетителя в предыдущем рецепте. Рассмотрим такой код с деревьями выражений:

>>> class UnaryOperator(Node):
    def __init__(self, operand):
        self.operand = operand

>>> class BinaryOperator(Node):
    def __init__(self, left, right):
        self.left = left
        self.right = right

>>> class Add(BinaryOperator):
    pass

>>> class Sub(BinaryOperator):
    pass

>>> class Mul(BinaryOperator):
    pass

>>> class Div(BinaryOperator):
    pass

>>> class Negate(UnaryOperator):
    pass

>>> class Number(Node):
    def __init__(self, value):
        self.value = value
>>>
>>># Пример класса-посетителя, выполняющего выражения
>>> class Evaluator(NodeVisitor):
    def visit_Number(self, node):
        return node.value

    def visit_Add(self, node):
        return self.visit(node.left) + self.visit(node.right)

    def visit_Sub(self, node):
        return self.visit(node.left) - self.visit(node.right)

    def visit_Mul(self, node):
        return self.visit(node.left) * self.visit(node.right)

    def visit_Div(self, node):
        return self.visit(node.left) / self.visit(node.right)

    def visit_Negate(self, node):
        return -self.visit(node.operand)

>>>
>>> # 1 + 2*(3-4) / 5
>>> t1 = Sub(Number(3), Number(4))
>>> t2 = Mul(Number(2), t1)
>>> t3 = Div(t2, Number(5))
>>> t4 = Add(Number(1), t3)
>>> # Выполнить это
>>> e = Evaluator()
>>> e.visit(t4)
0.6
>>>

Приведенный код работает для простых выражений. Однако реализация класса Evaluator использует рекурсию и может сломаться, если данные будут слишком сильно вложенными. Например:

>>> a = Number(0)
>>> for n in range(1, 100000):
	a = Add(a, Number(n))

	
>>> e = Evaluator()
>>> e.visit(a)
Traceback (most recent call last):
  File "<pyshell#29>", line 1, in <module>
    e.visit(a)
  File "<pyshell#3>", line 12, in visit
    stack.append(self._visit(stack.pop()))
  File "<pyshell#3>", line 24, in _visit
    return meth(node)
  .  .  .
  File "<pyshell#3>", line 20, in _visit
    methname = 'visit_' + type(node).__name__
RecursionError: maximum recursion depth exceeded while calling a Python object
>>>

Давайте немного изменим класс Evaluator:

>>> class Node:
    pass

>>> class Visit:
    def __init__(self, node):
        self.node = node

>>> class NodeVisitor:
    def visit(self, node):
        stack = [Visit(node)]
        last_result = None
        while stack:
            try:
                last = stack[-1]
                if isinstance(last, types.GeneratorType):
                    stack.append(last.send(last_result))
                    last_result = None
                elif isinstance(last, Visit):
                    stack.append(self._visit(stack.pop().node))
                else:
                    last_result = stack.pop()
            except StopIteration:
                stack.pop()
        return last_result

    def _visit(self, node):
        methname = 'visit_' + type(node).__name__
        meth = getattr(self, methname, None)
        if meth is None:
            meth = self.generic_visit
        return meth(node)
    
    def generic_visit(self, node):
        raise RuntimeError('No {} method'.format('visit_' + type(node).__name__))

>>> class UnaryOperator(Node):
    def __init__(self, operand):
        self.operand = operand

>>> class BinaryOperator(Node):
    def __init__(self, left, right):
        self.left = left
        self.right = right

>>> class Add(BinaryOperator):
    pass

>>> class Sub(BinaryOperator):
    pass

>>> class Mul(BinaryOperator):
    pass

>>> class Div(BinaryOperator):
    pass

>>> class Negate(UnaryOperator):
    pass

>>> class Number(Node):
    def __init__(self, value):
        self.value = value

>>> class Evaluator(NodeVisitor):
    def visit_Number(self, node):
        return node.value

    def visit_Add(self, node):
        yield (yield Visit(node.left)) + (yield Visit(node.right))

    def visit_Sub(self, node):
        yield (yield Visit(node.left)) - (yield Visit(node.right))

    def visit_Mul(self, node):
        yield (yield Visit(node.left)) * (yield Visit(node.right))

    def visit_Div(self, node):
        yield (yield Visit(node.left)) / (yield Visit(node.right))

    def visit_Negate(self, node):
        yield - (yield Visit(node.operand))

>>>

Если вы попробуете новую реализацию на таком же эксперименте с рекурсией, то обнаружите, что все работает. Это магия!

>>> a = Number(0)
>>> for n in range(1,100000):
	a = Add(a, Number(n))

	
>>> e = Evaluator()
>>> e.visit(a)
4999950000
>>>

Если вы захотите добавить собственную обработку в любой из методов, то и это у вас получится. Например:

class Evaluator(NodeVisitor):
    . . .
    def visit_Add(self, node):
        print('Add:', node)
        lhs = yield node.left
        print('left=', lhs)
        rhs = yield node.right
        print('right=', rhs)
        yield lhs + rhs
    . . .

Вот пример результата:

>>> e = Evaluator()
>>> e.visit(t4)
Add: <__main__.Add object at 0x1006a8d90>
left= 1
right= -0.4
0.6
>>>

Обсуждение

Этот рецепт отлично демонстрирует, как генераторы и корутины могут выполнять безумные фокусы с потоком управления, которые часто дают огромное преимущество. Чтобы понять этот рецепт, нужно уяснить для себя несколько ключевых моментов.

Во-первых, в задачах, связанных с обходом дерева, распространенной стратегией для избежания рекурсии является написание алгоритмов на основе стека или очереди. Например, обход с поиском в глубину (depth-first) может быть полностью реализован путем помещения встречающихся узлов на стек - и снятия со стека после завершения обработки. Ядро метода visit(), показанного в решении, базируется именно на этой идее. Алгоритм начинает с помещения в список stack первого узла и заканчивает работу, когда стек опустевает. Во время выполнения стек вырастает в соответствии с глубиной обрабатываемого дерева.

Второй ключевой момент касается поведения инструкции yield в генераторах. Когда встречается yield, генератор выдает значение и приостанавливается. Данный рецепт использует это свойство в качестве замены рекурсии. Например, вместо написания рекурсивного выражения

    value = self.visit(node.left)

вы используете такое:

    value = yield node.left

"Под капотом" здесь происходит отправка узла (node.left) обратно в метод visit(). Метод visit() затем выполняет подходящий для этого узла метод visitName(). В каком-то смысле это практически полная противоположность рекурсии. Вместо рекурсивных вызовов visit(), продвигающих вперед ход выполнения алгоритма, инструкция yield используется для временных откатов осуществляемого вычисления. yield - это сигнал, который говорит алгоритму, что выданный узел нужно обработать, перед тем как продвигаться дальше.

Заключительная часть этого рецепта касается распространения результатов. При использовании генераторов вы не можете применять инструкции return для выдачи значений (это возбудит исключение SyntaxError). Поэтому инструкция yield берет на себя двойную функцию для выполнения данной задачи. В этом рецепте это работает так: если значение, производимое инструкцией yield, не является узлом, то мы предполагаем, что это значение, которое будет распространяться в следующий шаг вычисления. В этом назначение переменной last_return. В типичном случае оно будет удерживать последнее значение, выданное методом-посетителем. Это значение затем будет отправлено в ранее выполнявшийся метод, где оно появится как значение, возвращенное инструкцией yield. Например, здесь:

    value = yield node.left

переменная value получает значение last_return, которое представляет собой результат, возвращаемый методом-посетителем, вызванным для node.left. Все эти аспекты рецепта можно найти в этом фрагменте кода:

try:
    last = stack[-1]
    if isinstance(last, types.GeneratorType):
        stack.append(last.send(last_result)) 
        last_result = None 
    elif isinstance(last, Node):
        stack.append(self._visit(stack.pop()))
    else:
        last_result = stack.pop() 
except StopIteration: 
    stack.pop()

Код просто смотрит на вершину стека и решает, что делать дальше. Если это генератор, тогда вызывается метод send() с последним результатом (если он имеется), и результат добавляется на стек для дальнейшей обработки. Значение, которое возвращает send(), - это то же самое значение, которое было передано в инструкцию yield. Поэтому в такой инструкции, как yield node.left, экземпляр класса Node node.left возвращается send() и помещается на вершину стека.

Если на вершине стека лежит экземпляр Node, он замещается результатом вызова подходящего для этого узла метода-посетителя. Здесь мы избавляемся от рекурсии. Вместо того чтобы различные методы-посетители напрямую рекурсивно вызывали visit(), он выполняется тут. Пока методы используют yield, все будет работать.

И наконец, если на вершине стека что-то другое, то предполагается, что это какое-то возвращенное значение. Оно выталкивается со стека и помещается в last_result. Если следующий элемент стека - это генератор, тогда он посылается в качестве возвращаемого значения для yield. Стоит отметить, что конечное возвращаемое значение visit() также присваивается last_result. Это заставляет данный рецепт работать с традиционной рекурсивной реализацией. Если генераторы не были использованы, это значение просто хранит значение, переданное какой-либо из инструкций return, использованных в коде.

Потенциальная проблема этого рецепта касается различия между выдачей значений-экземпляров Node и значений, не являющихся экземпляром Node. В этой реализации все экземпляры Node обходятся автоматически. Это означает, что вы не можете использовать Node как возвращаемое значение, которое будет распространяться дальше. На практике это может и не быть важным. Однако если это все же важно, вам может потребоваться немного адаптировать алгоритм. Например, можно добавить еще один класс:

class Visit:
    def __init__(self, node):
        self.node = node

class NodeVisitor:
    def visit(self, node):
        stack = [Visit(node)]
        last_result = None
        while stack:
            try:
                last = stack[-1]
                    if isinstance(last, types.GeneratorType):
                        stack.append(last.send(last_result))
                        last_result = None
                    elif isinstance(last, Visit):
                        stack.append(self._visit(stack.pop().node))
                    else:
                         last_result = stack.pop()
            except StopIteration:
                stack.pop()
    return last_result

def _visit(self, node):
    methname = 'visit_' + type(node).__name__
    meth = getattr(self, methname, None)
    if meth is None:
        meth = self.generic_visit
    return meth(node)

def generic_visit(self, node):
    raise RuntimeError('No {} method'.format('visit_' + type(node).__name__))

При такой реализации различные методы-посетители будут выглядеть вот так:

class Evaluator(NodeVisitor):
    . . .
    def visit_Add(self, node):
        yield (yield Visit(node.left)) + (yield Visit(node.right))

    def visit_Sub(self, node):
        yield (yield Visit(node.left)) - (yield Visit(node.right))
    . . .

Посмотрев на этот рецепт, вы можете задуматься о том, чтобы поискать решение, не использующее yield. Однако это может привести к тому, что у вас получится код, которому придется разбираться с теми же проблемами, которые мы обсудили здесь. Например, чтобы устранить рекурсию, вам потребуется поддерживать стек. Вы также должны будете реализовать некую схему для управления обходом и вызова различной логики, связанной с посещениями. Без генераторов все это закончится очень сложными манипуляциями со стеком, функциями обратного вызова (коллбэками) и прочими костылями. Собственно, главное преимущество использования yield как раз и заключается в том, что вы можете написать код без рекурсии в элегантном стиле, практически идентичном рекурсивной реализации.

На следующем шаге мы рассмотрим управление памятью в циклических структурах данных.

Предыдущий шаг Содержание Следующий шаг