В информатике хвостовой вызов — это вызов подпрограммы , выполняемый как последнее действие процедуры. [1] Если целью хвоста является одна и та же подпрограмма, то подпрограмма называется хвостовой рекурсией , что является частным случаем прямой рекурсии . Хвостовая рекурсия (или хвостовая рекурсия ) особенно полезна, и ее часто легко оптимизировать в реализациях.
Хвостовые вызовы могут быть реализованы без добавления нового кадра стека в стек вызовов . Большая часть кадра текущей процедуры больше не нужна и может быть заменена кадром хвостового вызова, модифицированным соответствующим образом (аналогично наложению для процессов, но для вызовов функций). Затем программа может перейти к вызванной подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранением хвостового вызова или оптимизацией хвостового вызова . Устранение хвостовых вызовов позволяет реализовывать вызовы процедур в хвостовой позиции так же эффективно, как операторы перехода , что позволяет эффективно структурировать программирование . По словам Гая Л. Стила , «в общем, вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры, и могут быть единообразно закодированы как инструкции [машинного кода] JUMP». [2]
Не все языки программирования требуют устранения хвостовых вызовов. Однако в языках функционального программирования исключение хвостовых вызовов часто гарантируется стандартом языка , что позволяет хвостовой рекурсии использовать аналогичный объем памяти, что и эквивалентный цикл . Особый случай вызовов хвостовой рекурсии, когда функция вызывает саму себя, может быть более подходящим для исключения вызова, чем обычные хвостовые вызовы. Когда семантика языка явно не поддерживает общие хвостовые вызовы, компилятор часто все равно может оптимизировать одноуровневые вызовы или хвостовые вызовы функций, которые принимают и возвращают те же типы, что и вызывающая сторона. [3]
Когда вызывается функция, компьютер должен «запомнить» место, из которого она была вызвана, адрес возврата , чтобы он мог вернуться в это место с результатом после завершения вызова. Обычно эта информация сохраняется в стеке вызовов — списке мест возврата в том порядке, в котором были достигнуты места вызова. Для хвостовых вызовов нет необходимости запоминать вызывающую сторону — вместо этого устранение хвостового вызова вносит только минимально необходимые изменения в кадр стека перед его передачей, [4] и функция, вызываемая хвостовым вызовом, вернется непосредственно к исходному вызывающему объекту . . Хвостовой вызов не обязательно должен стоять лексически после всех остальных операторов исходного кода; важно только, чтобы вызывающая функция возвращалась сразу после хвостового вызова, возвращая результат хвостового вызова, если таковой имеется, поскольку вызывающая функция обходится при выполнении оптимизации.
Для нерекурсивных вызовов функций обычно это оптимизация , которая экономит лишь немного времени и места, поскольку различных функций, доступных для вызова, не так много. Однако при работе с рекурсивными или взаимно рекурсивными функциями, где рекурсия происходит посредством хвостовых вызовов, пространство стека и количество сохраненных возвратов могут стать очень значительными, поскольку функция может вызывать себя прямо или косвенно, создавая новый кадр стека вызовов. каждый раз. Устранение хвостового вызова часто снижает асимптотические требования к пространству стека с линейного, или O (n), до постоянного, или O (1). Таким образом, исключение хвостовых вызовов требуется стандартными определениями некоторых языков программирования, таких как Scheme , [5] [6] и языков семейства ML среди других. Определение языка Scheme точно формализует интуитивное понятие положения хвоста, определяя, какие синтаксические формы позволяют получать результаты в контексте хвоста. [7] Реализации, позволяющие одновременно активировать неограниченное количество хвостовых вызовов, благодаря устранению хвостовых вызовов, также можно назвать «правильно хвостовой рекурсивной». [5]
Помимо пространства и эффективности выполнения, исключение хвостовых вызовов важно в идиоме функционального программирования , известной как стиль передачи продолжения (CPS), который в противном случае быстро исчерпал бы пространство стека.
Хвостовой вызов может располагаться непосредственно перед синтаксическим концом функции:
функция foo ( данные ) { a ( данные ); вернуть б ( данные ); } Здесь оба a(data)и b(data)являются вызовами, но bэто последнее, что выполняет процедура перед возвратом, и поэтому находится в хвостовой позиции. Однако не все хвостовые вызовы обязательно расположены в синтаксическом конце подпрограммы:
function bar ( данные ) { if ( a ( данные )) { return b ( данные ); } Возврат С ( данные ); } Здесь оба вызова bи cнаходятся в хвостовой позиции. Это связано с тем, что каждый из них находится в конце if-ветви соответственно, хотя первый из них синтаксически не находится в конце barтела.
В этом коде:
функция foo1 ( данные ) { возврат a ( данные ) + 1 ; } функция foo2 ( данные ) { var ret = a ( данные ); вернуть Рет ; } функция foo3 ( данные ) { var ret = a ( данные ); возврат ( рет == 0 ) ? 1 : в отставку ; } вызов a(data)находится в хвостовой позиции в foo2, но он не находится в хвостовой позиции ни в , foo1ни в foo3, поскольку управление должно вернуться к вызывающей стороне, чтобы позволить ей проверить или изменить возвращаемое значение перед его возвратом.
Следующая программа является примером на Scheme : [8]
;; факториал: число -> число ;; вычислить произведение всех положительных ;; целые числа, меньшие или равные n. ( определить ( факториал n ) ( if ( = n 0 ) 1 ( * n ( факториал ( - n 1 ))))) Это не написано в стиле хвостовой рекурсии, поскольку функция умножения ("*") находится в хвостовой позиции. Это можно сравнить с:
;; факториал: число -> число ;; вычислить произведение всех положительных ;; целые числа, меньшие или равные n. ( определить ( факториал n ) ( факт-iter 1 n )) ( определить ( факт-iter продукт n ) ( if ( = n 0 ) продукт ( факт-iter ( * продукт n ) ( - n 1 )))) Эта программа предполагает оценку аппликативного порядка . Внутренняя процедура fact-iterвызывает себя последней в потоке управления. Это позволяет интерпретатору или компилятору реорганизовать выполнение, которое обычно выглядит так: [8]
вызвать факториал (4) позвонить факт-итеру (1 4) позвонить факт-итеру (4 3) позвонить факт-итеру (12 2) позвоните факт-итеру (24 1) вернуть 24 вернуть 24 вернуть 24 вернуть 24 вернуть 24
в более эффективный вариант как с точки зрения пространства, так и с точки зрения времени:
вызвать факториал (4) позвонить факт-итеру (1 4) заменить аргументы на (4 3) заменить аргументы на (12 2) заменить аргументы на (24 1) вернуть 24 вернуть 24
Эта реорганизация экономит место, поскольку не требуется сохранять никакое состояние, за исключением адреса вызывающей функции, ни в стеке, ни в куче, а кадр стека вызовов for fact-iterповторно используется для хранения промежуточных результатов. Это также означает, что программисту не нужно беспокоиться о нехватке места в стеке или куче для чрезвычайно глубоких рекурсий. В типичных реализациях вариант с хвостовой рекурсией будет существенно быстрее другого варианта, но только на постоянный коэффициент.
Некоторые программисты, работающие с функциональными языками, переписывают рекурсивный код, делая его хвостовым, чтобы воспользоваться этой функцией. Это часто требует добавления productв функцию аргумента-аккумулятора ( в приведенном выше примере). В некоторых случаях (например, в списках фильтрации) и на некоторых языках полная хвостовая рекурсия может потребовать написания функции, которая ранее была чисто функциональной, чтобы она изменяла ссылки, хранящиеся в других переменных. [ нужна цитата ]
Хвостовая рекурсия по модулю cons — это обобщение оптимизации хвостовой рекурсии, введенной Дэвидом Уорреном [9] в контексте компиляции Пролога , рассматриваемого как явно заданный один раз язык. Он был описан (хотя и не назван) Дэниелом П. Фридманом и Дэвидом С. Уайзом в 1974 году [10] как метод компиляции LISP . Как следует из названия, он применяется, когда единственная операция, которую остается выполнить после рекурсивного вызова, — это добавить известное значение перед возвращаемым из него списком (или вообще выполнить постоянное количество простых операций по созданию данных). Таким образом, этот вызов будет хвостовым вызовом , за исключением (« по модулю ») указанной операции cons . Но префикс значения в начале списка при выходе из рекурсивного вызова — это то же самое, что добавление этого значения в конец растущего списка при входе в рекурсивный вызов, таким образом создавая список как побочный эффект , как если бы в неявный параметр аккумулятора. Следующий фрагмент Пролога иллюстрирует эту концепцию:
Таким образом, при переводе с помощью хвостовой рекурсии такой вызов преобразуется сначала в создание нового узла списка и установку его firstполя, а затем в выполнение хвостового вызова с указателем на поле узла restв качестве аргумента для рекурсивного заполнения. Тот же эффект достигается, когда рекурсия защищена лениво вычисляемым конструктором данных, что автоматически достигается в ленивых языках программирования, таких как Haskell.
Следующий фрагмент определяет рекурсивную функцию на C , которая дублирует связанный список (с эквивалентным кодом Scheme и Prolog в качестве комментариев для сравнения):
В этой форме функция не является хвостовой рекурсией, поскольку управление возвращается вызывающей стороне после того, как рекурсивный вызов дублирует остальную часть входного списка. Даже если бы он выделил головной узел перед дублированием остальных, ему все равно пришлось бы подставить результат рекурсивного вызова в поле nextпосле вызова . [a]
Таким образом, функция почти хвостовая рекурсия. Метод Уоррена возлагает ответственность за заполнение nextполя на сам рекурсивный вызов, который, таким образом, становится хвостовым вызовом. [b] Использование сторожевого головного узла для упрощения кода,
Вызываемая сторона теперь добавляется в конец растущего списка, вместо того, чтобы вызывающая сторона добавляла ее в начало возвращаемого списка. Теперь работа выполняется на пути вперед от начала списка до рекурсивного вызова, который затем продолжается дальше, а не назад от конца списка, после того как рекурсивный вызов возвратил свой результат. Таким образом, он похож на метод накопления параметров, превращающий рекурсивные вычисления в итеративные.
Характерно для этого метода то, что в стеке вызовов выполнения создается родительский кадр , который вызываемый объект с хвостовой рекурсией может повторно использовать в качестве собственного кадра вызова, если присутствует оптимизация хвостового вызова.
Реализация хвостовой рекурсии теперь может быть преобразована в явно итеративную реализацию в виде накопительного цикла :
В докладе, представленном на конференции ACM в Сиэтле в 1977 году, Гай Л. Стил подвел итог дебатам по поводу GOTO и структурированного программирования и заметил, что вызовы процедур в хвостовой позиции процедуры лучше всего рассматривать как прямую передачу управления вызываемая процедура, обычно исключающая ненужные операции манипуляции стеком. [2] Поскольку такие «хвостовые вызовы» очень распространены в Lisp , языке, где вызовы процедур встречаются повсеместно, эта форма оптимизации значительно снижает стоимость вызова процедуры по сравнению с другими реализациями. Стил утверждал, что плохо реализованные вызовы процедур привели к искусственному восприятию того, что GOTO дешевле по сравнению с вызовом процедур. Стил далее утверждал, что «в целом вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры, и могут быть единообразно закодированы как инструкции [машинного кода] JUMP», при этом инструкции по манипуляции стеком машинного кода «считаются оптимизацией (а не наоборот!)". [2] Стил привел доказательства того, что хорошо оптимизированные численные алгоритмы на Lisp могут выполняться быстрее, чем код, созданный доступными на тот момент коммерческими компиляторами Fortran, поскольку стоимость вызова процедуры в Lisp была намного ниже. В Scheme , диалекте Лиспа, разработанном Стилом совместно с Джеральдом Джеем Сассманом , исключение хвостовых вызовов гарантированно будет реализовано в любом интерпретаторе. [11]
Хвостовая рекурсия важна для некоторых языков высокого уровня , особенно функциональных и логических языков, а также членов семейства Lisp . В этих языках хвостовая рекурсия является наиболее часто используемым (а иногда и единственным доступным способом) способа реализации итерации. Спецификация языка Scheme требует, чтобы хвостовые вызовы были оптимизированы, чтобы не увеличивать стек. Хвостовые вызовы могут быть сделаны явно в Perl с помощью варианта оператора goto, который принимает имя функции: goto &NAME;[12]
Однако для реализаций языка, которые хранят аргументы функций и локальные переменные в стеке вызовов (который является реализацией по умолчанию для многих языков, по крайней мере, в системах с аппаратным стеком , таких как x86 ), реализация обобщенной оптимизации хвостовых вызовов (включая взаимную оптимизацию вызовов). хвостовая рекурсия) представляет проблему: если размер записи активации вызывающего абонента отличается от размера вызывающего, то может потребоваться дополнительная очистка или изменение размера кадра стека. В этих случаях оптимизация хвостовой рекурсии остается тривиальной, но общую оптимизацию хвостовых вызовов может быть сложнее реализовать эффективно.
Например, в виртуальной машине Java (JVM) вызовы хвостовой рекурсии можно исключить (поскольку при этом повторно используется существующий стек вызовов), но нельзя исключить общие хвостовые вызовы (поскольку это изменяет стек вызовов). [13] [14] В результате функциональные языки, такие как Scala , ориентированные на JVM, могут эффективно реализовывать прямую хвостовую рекурсию, но не взаимную хвостовую рекурсию.
Комплекты компиляторов GCC , LLVM /Clang и Intel выполняют оптимизацию хвостового вызова для C и других языков на более высоких уровнях оптимизации или при -foptimize-sibling-callsпередаче опции. [15] [16] [17] Хотя данный синтаксис языка может не поддерживать это явно, компилятор может выполнить эту оптимизацию всякий раз, когда он может определить, что типы возвращаемых значений для вызывающего и вызываемого объекта эквивалентны и что типы аргументов, передаваемые обоим функции либо одинаковы, либо требуют одинакового объема памяти в стеке вызовов. [18]
Доступны различные методы реализации.
Хвостовые вызовы часто оптимизируются интерпретаторами и компиляторами языков функционального и логического программирования для более эффективных форм итерации . Например, программисты Scheme обычно выражают циклы while как вызовы процедур в хвостовой позиции и полагаются на компилятор или интерпретатор Scheme для замены хвостовых вызовов более эффективными инструкциями перехода . [19]
Для компиляторов, генерирующих сборку напрямую, устранение хвостовых вызовов несложно: достаточно заменить код операции вызова на код перехода после фиксации параметров в стеке. С точки зрения компилятора, первый пример выше изначально переводится на язык псевдоассемблера (фактически это допустимая ассемблер x86 ):
foo: вызов B вызов A ret При исключении хвостового вызова последние две строки заменяются одной инструкцией перехода:
foo: позвонить B jmp A После Aзавершения подпрограммы она вернется непосредственно на обратный адрес foo, опуская ненужный retоператор.
Обычно вызываемые подпрограммы должны быть снабжены параметрами . Таким образом, сгенерированный код должен убедиться, что кадр вызова для A правильно настроен, прежде чем переходить к подпрограмме, вызываемой хвостом. Например, на платформах , где стек вызовов содержит не только адрес возврата , но и параметры подпрограммы, компилятору может потребоваться выдать инструкции для настройки стека вызовов. На такой платформе для кода:
функция foo(данные1, данные2) Б(данные1) вернуть А (данные2)
(где data1и data2являются параметрами) компилятор может перевести это как: [c]
фу: mov reg ,[ sp + data1 ] ; извлечь данные1 из параметра стека (sp) в рабочий регистр. нажать рег ; поместить данные1 в стек там, где их ожидает B позвонить Б ; Б использует данные1 поп ; удалить данные1 из стека mov reg ,[ sp + data2 ] ; извлечь данные2 из параметра стека (sp) в рабочий регистр. нажать рег ; поместить data2 в стек там, где его ожидает A позвонить А ; А использует данные2 поп ; удалить данные2 из стека. в отставкуОптимизатор хвостового вызова может затем изменить код на:
фу: mov reg ,[ sp + data1 ] ; извлечь данные1 из параметра стека (sp) в рабочий регистр. нажать рег ; поместить данные1 в стек там, где их ожидает B позвонить Б ; Б использует данные1 поп ; удалить данные1 из стека mov reg ,[ sp + data2 ] ; извлечь данные2 из параметра стека (sp) в рабочий регистр. mov [ sp + data1 ], reg ; поместите data2 туда, где A этого ожидает джмп А ; A использует data2 и немедленно возвращает вызывающему абоненту. Этот код более эффективен как с точки зрения скорости выполнения, так и с точки зрения использования пространства стека.
Поскольку многие компиляторы Scheme используют C в качестве промежуточного целевого кода, хвостовую рекурсию необходимо кодировать на C без увеличения стека, даже если компилятор C не оптимизирует хвостовые вызовы. Во многих реализациях это достигается за счет использования устройства, известного как батут — фрагмента кода, который неоднократно вызывает функции. Все функции вводятся через батут. Когда функция должна выполнить хвостовой вызов другой, вместо того, чтобы вызывать ее напрямую и затем возвращать результат, она возвращает адрес вызываемой функции и параметры вызова обратно в батут (из которого она была вызвана), а Trumpoline позаботится о следующем вызове этой функции с указанными параметрами. Это гарантирует, что стек C не будет расти и итерация может продолжаться бесконечно.
Реализовать батуты можно с помощью функций высшего порядка в языках, которые их поддерживают, таких как Groovy , Visual Basic .NET и C# . [20]
Использование батута для всех вызовов функций обходится гораздо дороже, чем обычный вызов функции C, поэтому по крайней мере один компилятор Scheme, Chicken , использует технику, впервые описанную Генри Бейкером на основе неопубликованного предложения Эндрю Аппеля , [21] в котором обычный C используются вызовы, но размер стека проверяется перед каждым вызовом. Когда стек достигает максимально допустимого размера, объекты в стеке удаляются с помощью алгоритма Чейни , перемещая все текущие данные в отдельную кучу. После этого стек разматывается («выталкивается»), и программа возобновляет работу из состояния, сохраненного непосредственно перед сборкой мусора. Бейкер говорит: «Метод Аппеля позволяет избежать большого количества небольших прыжков на батуте, время от времени спрыгивая с Эмпайр-стейт-билдинг». [21] Сбор мусора гарантирует, что взаимная хвостовая рекурсия может продолжаться бесконечно. Однако этот подход требует, чтобы ни один вызов функции C никогда не возвращался, поскольку нет гарантии, что кадр стека ее вызывающей стороны все еще существует; следовательно, он предполагает гораздо более радикальное внутреннее переписывание программного кода: стиль передачи продолжения .
Хвостовая рекурсия может быть связана с оператором while , явной итерацией, например, путем преобразования
процедура foo( x ) if p ( x ) return bar( x ) else return foo(baz( x ))
в
процедура foo( x ) while true if p ( x ) return bar( x ) else x ← baz( x )
где x может быть кортежем, включающим более одной переменной: в этом случае необходимо соблюдать осторожность при реализации оператора присваивания x ← baz( x ), чтобы соблюдались зависимости. Возможно, потребуется ввести вспомогательные переменные или использовать конструкцию подкачки .
В более общем смысле,
процедура foo( x ) if p ( x ) возвращает bar( x ) else if q ( x ) возвращает baz( x ) ... иначе, если r ( x ) вернет foo(qux( x )) ... иначе верните foo(quux( x ))
может быть преобразован в
процедура foo( x ) while true if p ( x ) возвращает bar( x ) else if q ( x ) возвращает baz( x ) ... иначе, если р ( Икс ) Икс ← qux( Икс ) ... иначе x ← quux( x )
Например, эта программа Julia дает нехвостовое рекурсивное определение factфакториала:
функция факториал ( n ) если n == 0 вернуть 1 еще вернуть n * факториал ( n - 1 ) конецконецДействительно, n * factorial(n - 1)завершает вызов factorial. Но его можно преобразовать в определение хвостовой рекурсии, добавив аргумент, aназываемый аккумулятором . [8]
Эта программа Julia дает хвостовую рекурсию определения fact_iterфакториала:
функция факториал ( n :: Целое число , a :: Целое число ) если n == 0 : вернуть _ еще вернуть факториал ( n - 1 , n * a ) конецконецфункция факториал ( n :: Целое число ) вернуть факториал ( n , 1 ) конецЭта программа Джулии дает итеративное определение fact_iterфакториала:
функция fact_iter ( n :: Integer , a :: Integer ) while n > 0 a = n * a n = n - 1 end возвращает конец _ функция факториал ( n :: целое число ) return fact_iter ( n , один ( n )) конец recurспециальную форму. [22]tailrecмодификатор для функций [30]goto &NAME;[32]@tailrec, что приводит к ошибке компиляции, если функция не является хвостовой рекурсивной [38]
if ( ls != NULL ) { head = malloc ( sizeof * head ); голова -> значение = ls -> значение ; head -> next = дубликат ( ls -> next ); } if ( ls != NULL ) { head = malloc ( sizeof * head ); голова -> значение = ls -> значение ; дубликат ( ls -> next , & ( head -> next )); } callсначала помещает текущее место кода в стек, а затем выполняет безусловный переход к местоположению кода, указанному меткой. Инструкция retсначала извлекает ячейку кода из стека, затем выполняет безусловный переход к полученной ячейке кода.