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