Устранение Хвостовой рекурсии
Я недавно написал в своем блоге 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 не может достоверно определить, ссылается ли какой-либо определенный вызов именно на текущую функцию, даже если нее то же самое имя. Рассмотрите этот простой пример:
Вы могли бы заменить тело чем-то вроде этого:
Это кажется достаточно простым, но теперь добавьте это:
Вызов g(5) вызывает ранее определенную функцию f, но «рекурсивный» вызов больше не является таковым! Во время выполнения имя ‘f’ переопределяется в нерекурсивную функцию, таким образом, возвращенное значение 4, а не 0. В то же время я соглашусь, что это плохой стиль, но это — четко определенная часть семантики Python, у которой есть много способов логичного использования, и компилятор сделал эту замену в надежде, что определение f останется неизменным, представил бы достаточно много ошибок в реальном коде.
Другое сообщение в блоге касалось декораторов, которые могут использоваться, чтобы реализовать хвостовую рекурсию, используя волшебные исключения или возвращаемые значения. Они могут быть записаны в простом Python коде (хотя то сообщение показывает оптимизированную версию Cython, которая, как утверждают, «только на 10 % медленнее». Хотя она, кажется, не ориентирована на многопоточное исполнение). Если Вам так интересно, я не буду пытаться остановить Вас, но я строго возражаю против включения чего-то вроде этого в встроенные возможности языка: есть много причин не использовать ткой декоратор, так как он предполагает, что любой рекурсивный вызов является хвостовой рекурсией и может быть устранен. В руках менее опытных пользователей это приведет к бедствиям. Например, обычное рекурсивное определение факториала не является хвостовой рекурсией:
Есть также много функций, которые содержат хвостовую рекурсию вместе с обычным рекурсивным вызовом; декораторы не поддерживают такие случаи. Другая тонкость, которую не обрабатывают такие декораторы, является хвостовыми рекурсивными вызовами в 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, деляю рекурсивные вызовы через встроенную функцию или метод.
Конечно, ни один подход не удовлетворяет мои три претензии. Неужели так сложно переписать вашу функцию, чтобы использовать цикл?
Источник
Избегайте рекурсии в Python: вспомните о замыкании
Вот что получается, когда кандидат наук заморачивается рекурсией…
Раньше я был программистом, которому очень нравились рекурсивные функции, просто потому, что это очень круто, с их помощью можно продемонстрировать свои навыки программирования и интеллект. Однако в большинстве случаев рекурсивные функции имеют высокую сложность, поэтому нам следует избегать их использования.
Одно из решений намного лучше – по возможности задействовать динамическое планирование: вероятно, оно – лучший способ решать задачи, которые можно разделить на подзадачи. Одна из моих предыдущих статей демонстрирует мощь динамического планирования.
Здесь я представлю ещё одну технику Python, которую можно использовать как альтернативу рекурсивной функции. Эта техника не превосходит динамическое планирование, но она гораздо проще, с точки зрения мышления. Другими словами, иногда сложно заставить динамическое планирование работать из-за абстракции идей, тогда как проще воспользоваться замыканием.
Что такое замыкание в Python?
Прежде всего позвольте мне на простом примере продемонстрировать, что такое замыкание в Python. Посмотрите на функцию ниже:
Функция outer определяется с функцией inner внутри, а функция outer возвращает функцию inner ; именно она – возвращаемое значение outer .
Здесь вложенная функция – это и есть замыкание. Если проверить возвращаемое значение внешней функции, окажется, что оно является функцией.
Что делает замыкание? Поскольку оно вернуло функцию, мы, конечно, можем запустить её.
Видно, что внутренняя функция может обращаться к переменным, определённым во внешней функции. Обычно замыкание не применяется так, как показано выше, потому что это некрасиво. Мы обычно хотим определить другую функцию, чтобы удерживать функцию, которая возвращается замыканием.
Следовательно, мы также можем сказать, что в замыкании Python мы определили функцию, которая определяет функции.
Доступ к внешним переменным из внутренней функции
Как тогда мы можем использовать замыкание, чтобы заменить им рекурсию? Не торопитесь. Давайте посмотрим на другую проблему, связанную с доступом к внешним переменным из внутренней функции.
В замыкании выше мы хотим добавить 1 к внешней переменной x во внутренней функции. Это работает неочевидным образом.
По умолчанию вы не сможете получить доступ к внешней переменной из внутренней функции. Однако так же, как мы определяем глобальную переменную в Python, мы можем сообщить внутренней функции замыкания, что переменная не должна рассматриваться как «локальная», это делается с помощью ключевого слова nonlocal .
Теперь предположим, что мы хотим пять раз добавить единицу к переменной x. Можно просто написать цикл for .
Фибоначчи с помощью замыкания
Фибоначчи обычно используется как пример рекурсивных функций, как рекурсивный «Hello, World!». Напомню, о чём речь. Последовательность Фибоначчи – это ряд чисел, каждое следующее число – это сумма двух чисел перед ним. Первые два числа, X₀ и X₁, особенные. Это 0 и 1. Значит, X₂, как упоминалось выше, – это сумма X₀ и X₁. И так далее [сократил].
Рекурсивная функция требует, чтобы мы мыслили в обратном порядке, от «текущей ситуации» к «предыдущей ситуации» и, в конечном счёте, об условии завершения рекурсии. При помощи замыкания можно думать о проблеме более естественным образом. В коде ниже показана реализация Фибоначчи через замыкание:
Мы знаем, что Фибоначчи начинается с двух специальных чисел X₀ = 0 и X₁ = 1, поэтому просто определяем их во внешней функции. Затем внутренняя функция get_next_number просто возвращает сумму двух чисел, полученных от внешней функции. Кроме того, не забудьте обновить X₀ и X₁ с помощью X₁ и X₂. Код можно упростить:
Этот код сначала обновляет две переменные, а затем возвращает вторую, что эквивалентно коду выше. Затем мы можем использовать это замыкание, чтобы вычислить числа Фибоначчи. Например, вот последовательность Фибоначчи до двадцатого.
Сравниваем производительность
А как насчёт производительности? Давайте сравним! Сначала реализуем функцию Фибоначчи рекурсивно:
Функцию можно проверить: вывести 20-е число последовательности Фибоначчи.
Теперь напишем то же самое с замыканием.
2,79 мс против 2,75 мкс. Замыкание в 1000 раз быстрее рекурсии! Интуитивно понятно: причина в том, что все временные значения для каждого уровня рекурсии хранятся в памяти отдельно, тогда как замыкание каждый раз обновляет одни и те же переменные. Кроме того, существует ограничение глубины рекурсии. В случае замыкания, поскольку это в основном цикл for, никаких ограничений нет. Вот пример получения 1000-го числа Фибоначчи.
Это действительно огромное число, но метод замыкания может завершить вычисление примерно за 100 мкс, тогда как рекурсия сталкивается со своими ограничениями.
Как ещё применять замыкание?
Замыкания Python очень полезны не только как замена рекурсивных функций. В некоторых случаях оно также может заменить классы Python на решение изящнее, особенно когда в классе не слишком много атрибутов и методов. Предположим, у нас есть словарь студентов с их экзаменационными отметками.
Хочется иметь несколько функций, которые помогут нам фильтровать студентов по оценкам, помещать их в разные классы. Однако со временем критерии могут измениться. В этом случае можно определить замыкание Python, вот так:
Замыкание определяет функцию, которая, в свою очередь, определяет другие функции на основе динамически передаваемых параметров. Мы передадим нижнюю и верхнюю границы класса оценки, и замыкание вернёт нам функцию, которая отфильтрует студентов.
Код выше даёт нам 4 функции, которые классифицируют учащегося по соответствующим классам на основе указанных нами границ. Обратите внимание, что мы можем изменить границу в любой момент, чтобы выполнить другую функцию или переопределить текущие функции оценки. Давайте теперь проверим функции.
Выглядит очень аккуратно! Но имейте в виду, что в более сложных случаях всё равно нужно определять классы.
Что в итоге?
В этой статье я представил технику, называемую замыканием, в Python. Её можно применить, чтобы переписать рекурсивные функций и в большинстве случаев значительно превзойти их.
В самом деле, замыкание может оказаться не лучшим решением некоторых проблем, с точки зрения производительности, особенно когда применимо динамическое планирование. Однако намного проще работать с ним в плане мышления. Иногда динамическое планирование излишне: например, когда не так уж важна производительность, может быть достаточно замыкания.
Замыкание также может использоваться, чтобы заменить некоторые юзкейсы, для удовлетворения которым мы можем захотеть реализовать класс. В таких случаях замыкание выглядит аккуратнее и элегантнее.
Узнайте подробности, как получить Level Up по навыкам и зарплате или востребованную профессию с нуля, пройдя онлайн-курсы SkillFactory со скидкой 40% и промокодом HABR, который даст еще +10% скидки на обучение:
Источник