Объясните мне, что такое оптимизация хвостовых вызовов и зачем она нужна Python.

Так что, по-видимому, была большая шумиха по поводу того, нуждается ли Python в оптимизации хвостовых вызовов. Это дошло до апогея, когда кто-то отправил Гвидо копию SICP потому что он «не понял». Я в той же лодке, что и Гвидо. Я понимаю концепцию оптимизации хвостового вызова. Я просто не могу придумать ни одной причины, по которой Python действительно нуждается в этом.

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


python tail-recursion tail-call-optimization
person Jason Baker    schedule 20.05.2009    source источник
comment
+1, я тоже вообще не понимаю этой кутерьмы.   -  person Dan Lew    schedule 21.05.2009
comment
Обсуждение было не столько о том, что Python нуждается в совокупной стоимости владения, сколько о том, что Гвидо отверг его по неверным причинам.   -  person Mauricio Scheffer    schedule 21.05.2009
comment
Я рад, что никто не закрыл этот вопрос как в первую очередь основанный на мнении.   -  person Sergey Orshanskiy    schedule 19.12.2014

Ответы (4)


arrow_upward
15
arrow_downward

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

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

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

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

person Javier    schedule 20.05.2009
comment
Примерно об этом я и подозревал, но решил, что для этого должна быть более важная причина. Думаю, я был неправ. - person Jason Baker; 21.05.2009
comment
но помните, что те «минималистичные языки», о которых я упоминаю (например, Lua и Scheme), как правило, и приятнее, и намного быстрее, чем Python. отчасти потому, что надежная оптимизация хвостовых вызовов освобождает ваш разум и делает программы более четкими. к сожалению, я не знаю никого более практичного, чем Python. - person Javier; 21.05.2009

arrow_upward
6
arrow_downward

Если вы сильно хотите использовать рекурсию для вещей, которые в качестве альтернативы могут быть выражены в виде циклов, то «оптимизация хвостового вызова» действительно необходима. Тем не менее, Гвидо, пожизненный доброжелательный диктатор Python (BDFL), твердо верит в циклы, выражаемые в виде циклов, поэтому он не собирается использовать хвостовые вызовы в особых случаях (жертвуя дампом трассировки стека и регулярностью отладки).

person Alex Martelli    schedule 21.05.2009

arrow_upward
5
arrow_downward

Оптимизация хвостовых вызовов упрощает написание рекурсивных функций, не беспокоясь о переполнении стека:

def fac(n, result=1):
        if n > 1:
                return fac(n - 1, n * result)
        return result

Без оптимизации хвостового вызова вызов этого с большим числом может привести к переполнению стека.

person Zifre    schedule 20.05.2009
comment
Стандартный академический пример. Любой пример с использованием в реальном мире? - person ebo; 21.05.2009
comment
на самом деле это не хвостовая рекурсия. умножение в хвосте, а не рекурсия. - person Javier; 21.05.2009
comment
def fac(n): вернуть уменьшить(operator.mul, диапазон(1, n+1)) - person John Fouhy; 21.05.2009
comment
@Javier, умножение находится в хвосте, и после возврата рекурсивного вызова нет ожидающих операций. Следовательно, это делает его хвостовым рекурсивным. Пожалуйста, поправьте меня, если я ошибаюсь. - person ; 21.05.2009
comment
@Amit: Изначально он был прав, я изменил пример. Но даже с оригиналом умный компилятор мог бы его оптимизировать. - person Zifre; 22.05.2009
comment
@Zifre: правильно, новая форма настолько широко признана эффективной, что сторонники схемы называют это «итерацией, а не рекурсией», поскольку TCO создает тот же код, что и цикл while(){...} - person Javier; 22.05.2009
comment
@ebo: стандартный академический пример. Любой пример с использованием в реальном мире? Асинхронные конечные автоматы, обычно встречающиеся в серверном коде F#. - person J D; 31.01.2012

arrow_upward
1
arrow_downward

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

person barracel    schedule 20.11.2012