Я знаком с идеей базового исключения хвостовой рекурсии, когда функции, которые возвращают прямой результат вызова для себя, могут быть переписаны как итерационные циклы.
foo(...):
# ...
return foo(...)
Я также понимаю, что в особом случае функция все еще может быть переписана, если рекурсивный вызов обернут в вызов cons
.
foo(...):
# ...
return (..., foo(...))
Какое свойство cons
позволяет это? Какие функции кроме cons
могут обернуть рекурсивный хвостовой вызов, не разрушая нашу способность переписывать его итеративно?
GCC (но не Clang) способен оптимизировать этот пример « умножения хвостовой рекурсии по модулю », но неясно, какой механизм позволяет ему это обнаружить или как он выполняет свои преобразования.
pow(x, n):
if n == 0: return 1
else if n == 1: return x
else: return x * pow(x, n-1)
if(n==0) return 0;
(не возвращает 1, как в вашем вопросе).x^0 = 1
это ошибка. Не то чтобы это имело значение для остальной части вопроса, хотя; итерационный асм сначала проверяет этот особый случай. Но как ни странно, итеративная реализация вводит множество того,1 * x
чего не было в источнике, даже если мы делаемfloat
версию. gcc.godbolt.org/z/eqwine (и gcc только преуспевает-ffast-math
.)return 0
было исправлено. Умножение на 1 интересно. Я не уверен, что с этим делать.float
без них-ffast-math
, даже если это умножается на одно и то же значение каждый раз. (За исключением 1.0f`, который может быть камнем преткновения?)Ответы:
Хотя GCC, скорее всего, использует специальные правила, вы можете получить их следующим образом. Я буду использовать,
pow
чтобы проиллюстрировать, так как выfoo
так неопределенно определены. Кроме того,foo
лучше всего понимать его как пример оптимизации последнего вызова по отношению к переменным с одним присваиванием, как язык Oz и как обсуждалось в Концепциях, Методиках и Моделях компьютерного программирования . Преимущество использования переменных с одним присваиванием заключается в том, что оно позволяет оставаться в рамках декларативной парадигмы программирования. По сути, каждое полеfoo
возвращаемых значений структуры может быть представлено переменными с одним присваиванием, которые затем передаются вfoo
качестве дополнительных аргументов.foo
затем становится хвостовой рекурсивнойvoid
возвращающая функция. Для этого не нужно особого ума.Возвращаясь
pow
, во-первых, трансформируйся в продолжение прохождения стиля .pow
будет выглядеть так :Все звонки теперь являются оконечными. Однако стек управления был перемещен в захваченные среды в замыканиях, представляющих продолжения.
Далее, defunctionalize продолжений. Поскольку существует только один рекурсивный вызов, результирующая структура данных, представляющая нефункционализированные продолжения, представляет собой список. Мы получаем:
Что делать
applyPow(k, acc)
, это взять список, то есть бесплатный моноид, какk=Cons(x, Cons(x, Cons(x, Nil)))
и сделать егоx*(x*(x*acc))
. Но поскольку он*
является ассоциативным и обычно образует моноид с единицей1
, мы можем связать это с((x*x)*x)*acc
, и, для простоты,1
начать с производства(((1*x)*x)*x)*acc
. Ключевым моментом является то, что мы можем частично вычислить результат еще до того, как у нас получитсяacc
. Это означает, что вместо передачиk
в виде списка, который по сути является неким неполным «синтаксисом», который мы «интерпретируем» в конце, мы можем «интерпретировать» его по ходу дела. В результате мы можем заменитьNil
единицу моноида,1
в данном случае, иCons
операцией моноида*
, и теперь онаk
представляет «работающий продукт».applyPow(k, acc)
затем становится просто тем,k*acc
что мы можем встроить обратноpow2
и упростить производство:Хвосто-рекурсивная версия оригинала с прохождением через аккумулятор
pow
.Конечно, я не говорю, что GCC делает все эти рассуждения во время компиляции. Я не знаю, какую логику использует GCC. Моя точка зрения состоит в том, что я просто однажды сделал это, относительно легко распознать шаблон и немедленно перевести исходный код в эту окончательную форму. Тем не менее, преобразование CPS и преобразование нефункционализации являются полностью общими и механическими. Отсюда можно использовать методы слияния, вырубки лесов или суперкомпиляции, чтобы попытаться устранить утвердившиеся продолжения. Спекулятивные трансформации могут быть отброшены, если не удастся полностью исключить распределение уточненных продолжений. Я подозреваю, однако, что это было бы слишком дорого, чтобы делать все время, в полной общности, следовательно, более специальные подходы.
Если вы хотите быть смешным, вы можете проверить статью Recycling Continuations, которая также использует CPS и представления продолжений в качестве данных, но делает что-то похожее, но отличающееся от tail-recursion-modulo-cons. Здесь описывается, как вы можете создавать алгоритмы обращения указателей путем преобразования.
Этот шаблон преобразования и дефункционализации CPS является довольно мощным инструментом для понимания и эффективно используется в серии статей, которые я перечислю здесь .
источник
Я собираюсь биться вокруг куста некоторое время, но есть смысл.
Полугруппы
Ответ - ассоциативное свойство операции двоичной редукции .
Это довольно абстрактно, но умножение - хороший пример. Если x , y и z являются некоторыми натуральными числами (или целыми числами, или рациональными числами, или действительными числами, или комплексными числами, или матрицами N × N , или любой из множества других вещей), то x × y будет того же вида числа как и х и у . Мы начали с двух чисел, так что это бинарная операция, и получили одну, поэтому мы уменьшили количество чисел, которое у нас было, на единицу, сделав эту операцию сокращения. И ( x × y ) × z всегда совпадает с x × ( y ×я ), который является ассоциативным свойством.
(Если вы уже знаете все это, вы можете перейти к следующему разделу.)
Еще несколько вещей, которые вы часто видите в информатике, которые работают так же:
"a"+"b"+"c"
это"abc"
начать ли с"ab"+"c"
или"a"+"bc"
)[a]++[b]++[c]
аналогично[a,b,c]
либо сзади спереди, либо спереди назад.cons
на голове и хвосте, если вы думаете о голове как список синглтон. Это просто объединение двух списков.&
,|
и^
Некоторые вещи, которые не:
int print2(int x, int y) { return printf( "%d %d\n", x, y ); }
, какprint2( print2(x,y), z );
иprint2( x, print2(y,z) );
у разных выходных.Это достаточно полезная концепция, которую мы назвали. Множество с операцией, имеющей эти свойства, является полугруппой . Итак, действительные числа при умножении являются полугруппами. И ваш вопрос оказывается одним из способов, с помощью которых такая абстракция становится полезной в реальном мире. Полугрупповые операции могут быть оптимизированы так, как вам нужно.
Попробуйте это дома
Насколько я знаю, этот метод был впервые описан в 1974 году в статье Дэниела Фридмана и Дэвида Уайза «Складывание стилизованных рекурсий в итерации» , хотя они приобрели несколько больше свойств, чем, как оказалось, им нужно.
Haskell - отличный язык, чтобы проиллюстрировать это, потому что он имеет
Semigroup
класс типов в своей стандартной библиотеке. Он вызывает операцию универсальногоSemigroup
оператора<>
. Поскольку списки и строки являются экземплярамиSemigroup
, их экземпляры определяются, например,<>
как оператор конкатенации++
. И с правом импорта,[a] <> [b]
это псевдоним для[a] ++ [b]
, который есть[a,b]
.Но как насчет чисел? Мы только что видели , что числовые типы являются полугруппами под либо того или умножения! Так какой из них будет
<>
дляDouble
? Ну, либо один! Haskell определяет типыProduct Double
,where (<>) = (*)
(то есть фактическое определение в Haskell), а такжеSum Double
,where (<>) = (+)
.Один недостаток в том, что вы использовали тот факт, что 1 является мультипликативной идентичностью. Полугруппа с тождеством называется моноидом и определяется в пакете Haskell
Data.Monoid
, который вызывает универсальный элемент тождественности класса типовmempty
.Sum
,Product
и список каждый имеет элемент идентичности (0, 1 и[]
, соответственно), поэтому они являются экземплярами,Monoid
а такжеSemigroup
. (Не путать с монадой , так что просто забудь, что я даже поднял их.)Этого достаточно, чтобы перевести ваш алгоритм в функцию Haskell с использованием моноидов:
Важно отметить, что это хвостовая рекурсия по модулю полугруппы: каждый случай - это либо значение, либо хвостовой рекурсивный вызов, либо произведение полугруппы обоих. Кроме того, этот пример использовался
mempty
для одного из случаев, но если бы нам это не нужно, мы могли бы сделать это с более общим классом типовSemigroup
.Давайте загрузим эту программу в GHCI и посмотрим, как она работает:
Помните, как мы объявили
pow
для универсальногоMonoid
, чей тип мы назвалиa
? Мы дали GHCI достаточно информации, чтобы сделать вывод, что типa
здесьProduct Integer
- это операция, целоеinstance
изMonoid
которых<>
- целочисленное умножение. Так чтоpow 2 4
расширяется рекурсивно до того2<>2<>2<>2
, что есть2*2*2*2
или16
. Все идет нормально.Но наша функция использует только общие моноидные операции. Раньше я говорил, что есть еще один экземпляр
Monoid
вызываемогоSum
, чья<>
операция+
. Можем ли мы попробовать это?То же самое расширение теперь дает нам
2+2+2+2
вместо2*2*2*2
. Умножение - это сложение, как возведение в степень - умножение!Но я привел еще один пример моноида Хаскелла: списки, чья операция - конкатенация.
Написание
[2]
говорит компилятору, что это список,<>
в списках есть++
, так[2]++[2]++[2]++[2]
есть[2,2,2,2]
.Наконец, алгоритм (два, на самом деле)
Просто заменяя
x
на[x]
, вы преобразуете общий алгоритм, который использует рекурсию по модулю полугруппы, в тот, который создает список. Какой список? Список элементов, к которым применяется алгоритм<>
. Поскольку мы использовали только полугрупповые операции, которые есть и в списках, результирующий список будет изоморфен исходным вычислениям. И поскольку исходная операция была ассоциативной, мы можем одинаково хорошо оценивать элементы сзади-спереди или спереди назад.Если ваш алгоритм когда-либо достигнет базового случая и завершится, список будет непустым. Так как случай терминала возвратил что-то, это будет последний элемент списка, поэтому он будет иметь по крайней мере один элемент.
Как применить операцию двоичного сокращения к каждому элементу списка по порядку? Это верно, сгиб. Таким образом , вы можете заменить
[x]
наx
, получить список элементов , чтобы уменьшить путем<>
, а затем либо правой сгиб или левый сложите список:Версия с
foldr1
фактически существует в стандартной библиотеке, какsconcat
дляSemigroup
иmconcat
дляMonoid
. Это делает ленивый правый сгиб в списке. То есть расширяется[Product 2,Product 2,Product 2,Product 2]
до2<>(2<>(2<>(2)))
.Это неэффективно в этом случае, потому что вы не можете ничего сделать с отдельными терминами, пока не создадите их все. (Однажды у меня была дискуссия о том, когда использовать правые сгибы и когда использовать строгие левые сгибы, но это зашло слишком далеко.)
Версия с
foldl1'
является строго оцененным левым сгибом. То есть хвосто-рекурсивная функция со строгим аккумулятором. Это оценивается(((2)<>2)<>2)<>2
, рассчитывается сразу, а не позже, когда это необходимо. (По крайней мере, нет никаких задержек внутри самого сгиба: складываемый список создается здесь другой функцией, которая может содержать ленивую оценку.) Итак, сгиб вычисляет(4<>2)<>2
, затем сразу вычисляет8<>2
, а затем16
. Вот почему нам нужно, чтобы операция была ассоциативной: мы просто изменили группировку скобок!Строгий левый сгиб эквивалентен тому, что делает GCC. Крайний левый номер в предыдущем примере - это аккумулятор, в данном случае это работающий продукт. На каждом шаге он умножается на следующий номер в списке. Другой способ выразить это: вы перебираете значения, которые нужно умножить, сохраняя работающий продукт в аккумуляторе, и на каждой итерации вы умножаете аккумулятор на следующее значение. То есть это
while
замаскированная петля.Иногда это может быть сделано так же эффективно. Компилятор может оптимизировать структуру данных списка в памяти. Теоретически, у него достаточно информации во время компиляции, чтобы понять, что он должен делать это здесь:
[x]
это одиночный файл, то[x]<>xs
есть такой же, какcons x xs
. Каждая итерация функции может повторно использовать один и тот же кадр стека и обновлять параметры на месте.Либо правая, либо строгая левая складка может быть более подходящей, в конкретном случае, поэтому знайте, какой вы хотите. Есть также некоторые вещи, которые может сделать только правый сгиб (например, генерировать интерактивный вывод, не дожидаясь всего ввода, и работать с бесконечным списком). Здесь, однако, мы сводим последовательность операций к простому значению, поэтому нам нужно строгое сгибание влево.
Таким образом, как вы можете видеть, можно автоматически оптимизировать хвостовую рекурсию по модулю любой полугруппы (одним примером которой является любой из обычных числовых типов при умножении) либо в ленивую правую складку, либо в строгую левую складку в одну строку Haskell.
Обобщая дальше
Два аргумента двоичной операции не обязательно должны быть одного типа, если только начальное значение того же типа, что и ваш результат. (Конечно, вы всегда можете перевернуть аргументы в соответствии с порядком сгибания, который вы делаете, влево или вправо.) Таким образом, вы можете многократно добавлять патчи в файл, чтобы получить обновленный файл, или начинать с начального значения 1.0, разделите на целые числа, чтобы получить результат с плавающей запятой. Или добавьте элементы в пустой список, чтобы получить список.
Другой тип обобщения заключается в применении складок не к спискам, а к другим
Foldable
структурам данных. Часто неизменяемый линейный связанный список - это не та структура данных, которую вы хотите для данного алгоритма. Одна проблема, о которой я не упоминал выше, заключается в том, что гораздо эффективнее добавлять элементы в начало списка, чем в конец, и когда операция не является коммутативной, применениеx
слева и справа от операции не то же самое. Таким образом, вам нужно будет использовать другую структуру, такую как пара списков или двоичное дерево, чтобы представить алгоритм, который может применятьсяx
справа от<>
так и слева.Также обратите внимание, что ассоциативное свойство позволяет вам перегруппировать операции другими полезными способами, такими как «разделяй и властвуй»:
Или автоматический параллелизм, когда каждый поток уменьшает поддиапазон до значения, которое затем объединяется с другими.
источник
pow(float x, unsigned n)
версия gcc.godbolt.org/z/eqwine только оптимизируется с-ffast-math
((что подразумевает-fassociative-math
. Строгая плавающая точка, конечно, не ассоциативна, потому что разные временные = разные округления). Представляет,1.0f * x
чего не было в абстрактной машине C (но которая всегда будет давать идентичный результат). Тогда n-1 умножения аналогичныdo{res*=x;}while(--n!=1)
рекурсивным, так что это пропущенная оптимизация.