0,0
рейтинг
13 января 2011 в 01:37

Разработка → Устранение Хвостовой рекурсии перевод

Я недавно написал в своем блоге Python History пост «The origins of Python's functional features» (перевод). Упоминание о том, что Python не поддерживает хвостовую рекурсию (TRE) сразу спровоцировало несколько комментариев о том, как жаль, что Python не поддерживает данную оптимизацию. Появились ссылки на недавние записи в других блогах о том, что TRE может быть добавлена в Python легко. Позвольте мне защитить свою позицию — я не хочу добавлять TRE в язык. Если Вы хотите короткий ответ, это просто unpythonic.

Вот длинный ответ.

Во-первых, как кто-то заметил в комментариях, TRE является несовместимой с нормальной трассировкой стека: когда устранена хвостовая рекурсия, нет никакого стекового фрейма, оставленного, чтобы вывести traceback, если что-то пойдет не так. Это смутит пользователей, которые непреднамеренно написали что-то рекурсивное (рекурсия не очевидна в трассировке стека), будет сложно проводить отладку. Предоставление возможности отключить TRE мне кажется неправильным: Python должен всегда быть максимально легким в отладке. Это приводит меня к следующему выводу:

Во-вторых, идея, что TRE — просто оптимизация, которую отдельная реализация Python может реализовывать или нет, является неправильной. Как только устранение хвостовой рекурсии будет введено, разработчики начнут писать код, который зависит от этой оптимизации, и их код не будет работать на реализациях, которые не поддерживают ее: типичная реализация Python позволяет сделать 1000 рекурсий, которых достаточно для нерекурсивно записанного кода и для кода, который рекурсивно вызывается, чтобы обойти, например, дерево, но недостаточно для рекурсивно записанного цикла вокруг большого списка.

В-третьих, я не верю в рекурсию как базис всего программирования. Это — фундаментальная вера определенных программистов, особенно те, кто любит Scheme и любит учить программирование, начиная с рекурсии. Но я считаю, что рекурсия — только хороший теоретический подход к фундаментальной математике, но не ежедневный инструмент для решения поставленных задач.

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

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

def f(x):
     if x > 0:
            return f(x-1)
    return 0

Вы могли бы заменить тело чем-то вроде этого:

if x > 0:
    x = x-1
    <jump to top>
return 0

Это кажется достаточно простым, но теперь добавьте это:

g = f
def f(x):
      return x
g(5)

Вызов g(5) вызывает ранее определенную функцию f, но «рекурсивный» вызов больше не является таковым! Во время выполнения имя 'f' переопределяется в нерекурсивную функцию, таким образом, возвращенное значение 4, а не 0. В то же время я соглашусь, что это плохой стиль, но это — четко определенная часть семантики Python, у которой есть много способов логичного использования, и компилятор сделал эту замену в надежде, что определение f останется неизменным, представил бы достаточно много ошибок в реальном коде.

Другое сообщение в блоге касалось декораторов, которые могут использоваться, чтобы реализовать хвостовую рекурсию, используя волшебные исключения или возвращаемые значения. Они могут быть записаны в простом Python коде (хотя то сообщение показывает оптимизированную версию Cython, которая, как утверждают, «только на 10 % медленнее». Хотя она, кажется, не ориентирована на многопоточное исполнение). Если Вам так интересно, я не буду пытаться остановить Вас, но я строго возражаю против включения чего-то вроде этого в встроенные возможности языка: есть много причин не использовать ткой декоратор, так как он предполагает, что любой рекурсивный вызов является хвостовой рекурсией и может быть устранен. В руках менее опытных пользователей это приведет к бедствиям. Например, обычное рекурсивное определение факториала не является хвостовой рекурсией:

def fact(n):
      if n > 1:
            return n * fact(n-1)
      return 1

Есть также много функций, которые содержат хвостовую рекурсию вместе с обычным рекурсивным вызовом; декораторы не поддерживают такие случаи. Другая тонкость, которую не обрабатывают такие декораторы, является хвостовыми рекурсивными вызовами в try блоках: может показаться, что их можно устранить, но этого нельзя делать, потому что TRE может удалить обработку исключений. По всем этим причинам я думаю, что такой подход обречен, по крайней мере для широкой аудитории.

Однако, если кто-то настроен добавить TRE к Cpython (например), можно изменить компилятор примерно следующим образом. Во-первых, определите «безопасные» точки хвостовой рекурсии. Например код операции CALL, сразу сопровождаемый кодом операции RETURN, и при этом полностью вне блоков try. (Отметьте: я не упоминаю различные операции CALL_*, которые достаточно легко обработать используя тот же самый подход.) Затем, замените каждую такую пару CALL-RETURN единственной операцией CALL_RETURN. Нет никакой потребности компилятору проверять, является ли имя вызванной функции тем же самым что и текущей функции: если во время выполнения произошло переопределение, данный CALL не применим для TRE и нужно выполнить обычные действия для CALL, сопровождаемого кодом RETURN. (Я предполагаю, что Вы можете добавить некоторый механизм кэширования, индексированный точкой вызова, чтобы ускорить переопределение).

Для определния, где может использоваться TRE, есть несколько уровней «агрессивности», которую Вы могли бы применить. Наименее агрессивный, «ванильный» подход — оптимизировать только тот вызов, где вызываемый объект является функцией, которая уже работает в текущем стековом фрейме. Все, что мы должны сделать в этом случае – очистить локальные переменные из текущего стекового фрейма (и другие скрытые состояния, как активные циклы), установить аргументы, и перейти к вершине. (Тонкость: новые параметры находятся, по определению, в текущем стековом фрейме. Это — вероятно, только вопрос копирования. Больше вопросов вызывают именованные аргументы, списки аргументов переменной длины, и аргументы со значением по умолчанию. Это – просто вопрос программирования).

Более агрессивная версия также распознала бы ситуацию, когда метод с хвостовой рекурсией (т.е. вызываемый объект является связанным методом, где базовая функция — та же самая как в текущем стековом фрейме). Это требует немного больше программирования. У кода интерпретатора CPython (ceval.c) уже есть оптимизация для вызовов методов. (Я не знаю, насколько полезно это было бы, но: я ожидаю, что TRE стиль будет нравиться программистам, которые любят использовать стиль функционального программирования в целом, и вероятно не используют классы вообще. :-)

В теории Вы могли бы даже оптимизировать все случаи, где вызываемый объект является функцией или методом, записанным в Python, а число локальных переменных, необходимых для нового вызова, может быть размещено в текущем стековом фрейме. (Объекты фрейма в CPython расположены в «куче» и имеют переменный размер, основанный на требуемой памяти под локальные переменные; это вопрос архитектуры, чтобы снова использовать объекты фрейма). Эти действия оптимизировали бы взаимно рекурсивные хвостовые рекурсии, которые иначе не были бы оптимизированы. Увы, это также отключило бы трассировку стека в большинстве случаев, таким образом, это не будет хорошей идеей.

Более мягкая разновидность должна была бы создать объекты стековых фреймов на уровне Python точно так же, как прежде, но снова использовать стековый фрейм C. Это создало что-то вроде Stackless Python, хотя все еще достаточно легко исчерпать стек C, деляю рекурсивные вызовы через встроенную функцию или метод.

Конечно, ни один подход не удовлетворяет мои три претензии. Неужели так сложно переписать вашу функцию, чтобы использовать цикл?
Перевод: Guido van Rossum
Андрей Кондратович @cursed
карма
101,7
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (38)

  • +3
    Спасибо, очень интересно… Обязательно продолжайте.
    И, кстати, полностью согласен с Гвидо, не вижу особой проблемы в отсутствии оптимизации хвостовой рекурсии… Python прекрасен своей умеренным сочетанием функционального и императивного подходов. Если хотите писать исключительно функционально, то существует достаточно полностью функциональных языков.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +4
      Вот именно, что только один класс алгоритмов… И именно поэтому рекурсия никак не «базис всего программирования».
      • +2
        Ещё Дейкстра писал в своей работе о структурном программирование, что рекурсии достаточно для того, что бы описать любой алгоритм, а использование циклов является избыточным (слишком много лишних сущностей). Хотя стоит заметить, что в своём Алголе, он широко применял конструкции именно для циклов, но то было начало языкостроения…
        • +1
          Рекурсия, несомненно, божественна и прекрасна… Но тоже самое я могу сказать о циклах в Python в сравнении, например, с циклами в C++ (раз уж неделя ненависти cpp))). Ну вот не вижу я КРАЙНЕЙ необходимости в разворачивании хвостовой рекурсии… Рекурсия есть в Python, просто она всего-лишь не оптимизируется так, как это сделано в функциональных языках…
          • НЛО прилетело и опубликовало эту надпись здесь
            • +4
              Да нормально она там применяется, питон в принципе не язык для «формулы-1», небольшие объёмы данных спокойно можно и рекурсивно обрабатывать. А там, где нужна скорость — всегда пишется расширение на C и там уж любые оптимизации доступны.

              Существует несколько проектов, по «оптимизации» питона, некоторые добиваются определённых результатов, и я уверен, что при должном подходе можно его ускорить раза в 4. Но практика показывает, что это никому так уж сильно и не нужно, максимум — уменьшают влияние GIL.
            • 0
              Зачем так критично? А как же бинарное дерево обойти иначе? Есть конечно способы обойти его без стека, но их осмысленность, как мне кажется, сомнительна.
        • +3
          Рекурсии достаточно чтобы описать множество алгоритмов. Описать — не значит реализовать. Может кто-то не знает, но любой рекурсивный алгоритм не очень то и сложно переписывается с использыванием явного стека (а в некоторых случаях использования явного стека позволеяет и кое-какие оптимизации производить).

          *Под «явным стеком» подразумевается реализация стека в виде явной переменной в программе вместо использования стека по умолчанию.
          • 0
            Так я нигде и не писал: «долой циклы, давайте одной рекурсией пользоваться». Это было бы по меньшей мере глупо, для большинства языков.
            Но в тоже время, если посмотреть на такой язык как smalltalk, то все циклические конструкции там реализованы через рекурсию, и результат на голову обходит Java. В случае с Python по мощности и удобству использования не мне судить, но то что реализация больше соответствует принципу бритвы Окама — уверен.
            (говорить о рекурсии в smalltalk не совсем корректно, если не ошибаюсь использованный там приём называется fractal duck, когда объект при обработке сообщения (метода), посылает себе тоже сообщение)
      • НЛО прилетело и опубликовало эту надпись здесь
    • +2
      «У любой сложной задачи есть простое и очевидное неправильное решение» (с)
      • НЛО прилетело и опубликовало эту надпись здесь
        • +2
          Совершенно неочевидна связь между «естественно описывается» и «эффективно реализуется». Как показывает практика, зачастую это — противоположности.
          • НЛО прилетело и опубликовало эту надпись здесь
        • +1
          Поправка: «разделяй и влавствуй» не является хвосторекурсивным по определению. Там неизбежно нужно собирать воедино результаты «покорения».
          Поправка №2: рекурсия для итерации не очень нужна в отсутствии паттерн-матчинга.
          • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              А зачем тогда писать про простую рекурсию в топике про отсутствие оптимизации хвостовой рекурсии (которая, на самом деле, называется tail call optimization и относится далеко не только к рекурсии)?
              • НЛО прилетело и опубликовало эту надпись здесь
              • НЛО прилетело и опубликовало эту надпись здесь
                • +2
                  Вы путаете причину и следствие.

                  В данном случае (как пишет Гвидо), TCO отсутствует по причине «unpythonic», а не наоборот.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +6
    Читал этот ответ Гвидо давно, сейчас лень перечитывать, но такое ощущение осталось от текста, что он не понимает, что такое хвостовая рекурсия.

    Хвостовая рекурсия — это не является экслюзивной фичей функциональных языков.

    Не вводить TCO из-за того, что она затрудняет дебаггинг? Это бред
    Не вводить TCO из-за того, Гвидо не считает рекурсию базисом в программировании? Это тоже бред
    Не вводить TCO из-за того, что плохо написанный, но синтаксически корректный код может порождать баги? Это тоже бред.

    Сорри, если кого обидел :)
    • +3
      >Не вводить TCO из-за того, что плохо написанный, но синтаксически корректный код может порождать баги? Это тоже бред.

      "...in the kernel we have a pretty strict «no regressions» rule, and that if
      people depend on interfaces we exported having side effects that weren't
      intentional, we try to fix things so that they still work unless there is a
      major reason not to"
      • 0
        Какое отношение это имет к TCO? Никакого :)
        • 0
          если реализация TCO ломает ранее рабочий «плохо написанный» код, то эта цитата имеет непосредственное отношение к TCO
          • 0
            Ну разве что так. Осталось доказать наличие достаточно большого количество такого кода. Ну или сделать обратно несовместимую версию :)
    • –3
      > Читал этот ответ Гвидо давно, сейчас лень перечитывать, но такое ощущение осталось от текста, что он не понимает, что такое хвостовая рекурсия.

      Да, над предложенными способами реализации можно долго чесать затылок, пока не поймёшь что он «слегка» не в теме. Это подтверждается заключением «Неужели так сложно переписать вашу функцию, чтобы использовать цикл?» О косвенной рекурсии не рассказывали в школе.
    • +5
      Вообще говоря, сочетание ТСО и стектрейсов действительно совсем неочевидная задача. А без стректрейсов в эксепшнах будет грустно, плюс некоторое количество кода, пользующегося хаком в виде разбора стектрейса для доступа к рантайм значениям переменных в вызывающем коде, перестанет работать.
      • 0
        некоторое количество кода, пользующегося хаком в виде разбора стектрейса для доступа к рантайм значениям переменных в вызывающем коде, перестанет работать.

        и поделом =) «вызывающий код» для рекурсивной функции это та же самая функция. в этом случае есть более очевидные способы передать значения переменных, нежели стектрейс. :)
        • 0
          > «вызывающий код» для рекурсивной функции это та же самая функция.

          в случае «полноценного» TCO вызов любой функции будет оптимизирован, а не только самой себя
      • +3
        Там же в комментариях попросили показать стек трейс для циклов ;)
        • 0
          В самой простой реализации ТСО подразумевает устранение стек трейса для _любого_ хвостового вызова. При чём тут циклы?
          def foo(k):
              k -= 2
              bar(k)
          
          def bar(i):
              print 2 / i
          
          foo(2)
          

          foo вы в стектрейсе эксепшна не увидите. вызов выглядит нормальным. как дебажить будем?
          • +2
            Автор предлагает рекурсию заменить циклами, ранее выдав отмазку, что TCO ломает стек-трейсы. Есть два варианта. В первом случае Гвидо придётся показать стек-трейс для итераций цикла, во втором — доказать что *любой* алгоритм, акивно использущий стек, без потери читаемости переписывается в виде цикла (опять без стек-трейса). Ставлю месячную зар.плату, что он не сможет сделать ни того ни другого, если фанаты не начнут доказывать что «на самом деле это читаемо».

            Как (хрестоматийный) пример алгоритма, активно использующего стек — лексический анализатор в виде автомата.
  • +1
    Мне почему-то кажется, что почти все те же мысли можно повторить для того, чтоб отказатся от циклов «разварачивая» их или в просто копи-пейстнутые выражения или с использованием goto.

    Я, как и многие тут, так и не понял чем же рекурсия (и хвостовая как частность) плоха?

    Дебаггинг? Простите, но деббагинг сам по себе неудобен и плох. Лучше покрывать тестами. А тем кто нравится стектрейсы пусть вспомнят что сейчас все более и более популярны многопоточные алгоритмы, где важно не только стектрейс текущего вызова, а и состояние и трейсы всей системы, что делает дебаггинг еще более неудобным… так что, отказываемся от многопоточности? Те же мысли по поводу асинхронных вызовов… тоже откажемся?

    А плохой код он на то и плохой, и не стоит его учитывать в принятии решения использовать что-то или нет.
    • 0
      Можно подумать, при преходе к Python 3 совсем ничего не ломается.
  • 0
    А в чём проблема была просто сделать вызов, подобный [tailcall] в Tcl 8.6, который делал бы переход на функцию?
  • –2
    использование всяких хаков — это всегда отстой

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.