В информатике , хвост вызов является подпрограмма вызов выполняется как окончательное действие процедуры. [1] Если целью хвоста является та же самая подпрограмма, подпрограмма называется хвостовой рекурсией , что является частным случаем прямой рекурсии . Хвостовая рекурсия (или хвостовая рекурсия ) особенно полезна и часто проста в оптимизации в реализациях.
Хвостовые вызовы могут быть реализованы без добавления нового кадра стека в стек вызовов . Большая часть кадра текущей процедуры больше не нужна и может быть заменена кадром хвостового вызова, измененным соответствующим образом (аналогично наложению для процессов, но для вызовов функций). Затем программа может перейти к вызываемой подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранением хвостового вызова или оптимизацией хвостового вызова . Исключение хвостового вызова позволяет реализовать вызовы процедур в хвостовой позиции так же эффективно, как и операторы goto , тем самым обеспечивая эффективное структурированное программирование . По словамГай Л. Стил , «в общем, вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры и могут быть единообразно закодированы как инструкции JUMP [машинный код]». [2]
Не все языки программирования требуют исключения хвостовых вызовов. Однако в языках функционального программирования исключение хвостового вызова часто гарантируется стандартом языка , что позволяет хвостовой рекурсии использовать такой же объем памяти, что и эквивалентный цикл . Особый случай хвостовых рекурсивных вызовов, когда функция вызывает саму себя, может быть более податливым для исключения вызова, чем общие хвостовые вызовы. Когда семантика языка явно не поддерживает общие хвостовые вызовы, компилятор часто может оптимизировать одноуровневые вызовы или хвостовые вызовы функций, которые принимают и возвращают те же типы, что и вызывающий. [3]
Описание
Когда функция вызывается, компьютер должен «запомнить» место, откуда он был вызван, адрес возврата , чтобы он мог вернуться в это место с результатом после завершения вызова. Обычно эта информация сохраняется в стеке вызовов , простом списке мест возврата в порядке времени достижения описываемых ими мест вызова. Для хвостовых вызовов нет необходимости запоминать вызывающего - вместо этого удаление хвостового вызова вносит только минимально необходимые изменения в кадр стека перед его передачей [4], а функция, вызываемая хвостом, вернется непосредственно к исходному вызывающему. Хвостовой вызов не обязательно должен появляться лексически после всех других операторов в исходном коде; важно только, чтобы вызывающая функция возвращалась сразу после хвостового вызова, возвращая результат хвостового вызова, если таковой имеется, поскольку вызывающая функция игнорируется при выполнении оптимизации.
Для нерекурсивных вызовов функций это обычно оптимизация, которая экономит немного времени и места, поскольку для вызова доступно не так много различных функций. Однако при работе с рекурсивными или взаимно рекурсивными функциями, где рекурсия происходит через хвостовые вызовы, пространство стека и количество сохраненных возвратов могут вырасти и стать очень значительными, поскольку функция может вызывать себя прямо или косвенно, создавая новый фрейм стека вызовов. каждый раз. Исключение хвостового вызова часто снижает требования к асимптотическому пространству стека с линейных, или O (n), до постоянных, или O (1). Таким образом, исключение хвостовых вызовов требуется стандартными определениями некоторых языков программирования, таких как Scheme , [5] [6] и языков семейства ML среди других. Определение языка схемы точно формализует интуитивное понятие положения хвоста, указывая, какие синтаксические формы позволяют получить результаты в контексте хвоста. [7] Реализации, позволяющие неограниченному количеству хвостовых вызовов быть активными в один и тот же момент, благодаря исключению хвостовых вызовов, также могут быть названы «правильно хвостовыми рекурсивными». [5]
Помимо пространства и эффективности выполнения, исключение хвостового вызова важно в идиоме функционального программирования, известной как стиль передачи с продолжением (CPS), который в противном случае быстро исчерпал бы пространство стека.
Синтаксическая форма
Хвостовой вызов может быть расположен непосредственно перед синтаксическим концом функции:
функция foo ( данные ) { a ( данные ); вернуть b ( данные ); }
Здесь оба a(data)
и b(data)
являются вызовами, но b
это последнее, что процедура выполняет перед возвратом и, таким образом, находится в хвостовой позиции. Однако не все хвостовые вызовы обязательно расположены в синтаксическом конце подпрограммы:
функциональная панель ( данные ) { если ( а ( данные ) ) { вернуть б ( данные ); } return c ( данные ); }
Здесь оба вызова b
и c
находятся в хвостовой позиции. Это потому, что каждый из них находится в конце if-branch соответственно, даже если первый синтаксически не находится в конце bar
тела.
В этом коде:
Функция foo1 ( данные ) { возвращают в ( данные ) + 1 ; }
функция foo2 ( данные ) { var ret = a ( данные ); return ret ; }
функция foo3 ( данные ) { var ret = a ( данные ); возврат ( ret == 0 ) ? 1 : рет ; }
вызов a(data)
находится в хвостовой позиции in foo2
, но не в хвостовой позиции ни in, foo1
ни in foo3
, потому что управление должно возвращаться вызывающему, чтобы он мог проверить или изменить возвращаемое значение перед его возвратом.
Примеры программ
Следующая программа является примером на схеме : [8]
;; факториал: число -> число ;; вычислить произведение всех положительных ;; целые числа, меньшие или равные n. ( определить ( факториал n ) ( если ( = n 1 ) 1 ( * n ( факториал ( - n 1 )))))
Это не написано в стиле хвостовой рекурсии, потому что функция умножения («*») находится в хвостовой позиции. Это можно сравнить с:
;; факториал: число -> число ;; вычислить произведение всех положительных ;; целые числа, меньшие или равные n. ( define ( факториал n ) ( фактографический элемент 1 n )) ( define ( фактографический продукт n ) ( если ( < n 2 ) продукт ( фактографический агент ( * продукт n ) ( - n 1 ))))
Эта программа предполагает оценку в прикладном порядке . Внутренняя процедура fact-iter
вызывает себя последней в потоке управления. Это позволяет интерпретатору или компилятору реорганизовать выполнение, которое обычно выглядит следующим образом: [8]
вызов факториала (4) вызовите факт-iter (1 4) вызовите факт-iter (4 3) вызовите факт-iter (12 2) позвонить фактору (24 1) возврат 24 возврат 24 возврат 24 возврат 24 возврат 24
в более эффективный вариант как по пространству, так и по времени:
вызов факториала (4) вызовите факт-iter (1 4) заменить аргументы на (4 3) заменить аргументы на (12 2) заменить аргументы на (24 1) возврат 24 возврат 24
Эта реорганизация экономит пространство, поскольку не требуется сохранять состояние, за исключением адреса вызывающей функции, ни в стеке, ни в куче, а кадр стека вызовов для fact-iter
повторно используется для хранения промежуточных результатов. Это также означает, что программисту не нужно беспокоиться о нехватке стека или кучи для очень глубоких рекурсий. В типичных реализациях хвостовой рекурсивный вариант будет значительно быстрее, чем другой вариант, но только с постоянным коэффициентом.
Некоторые программисты, работающие с функциональными языками, будут переписывать рекурсивный код, чтобы он был хвостовой рекурсией, чтобы они могли воспользоваться этой функцией. Это часто требует добавления product
к функции аргумента «аккумулятор» ( в приведенном выше примере). В некоторых случаях (например, в списках фильтрации) и на некоторых языках полная хвостовая рекурсия может потребовать написания функции, которая ранее была чисто функциональной, чтобы она изменяла ссылки, хранящиеся в других переменных. [ необходима цитата ]
Хвостовая рекурсия по модулю минусов
Хвостовая рекурсия по модулю минусы является обобщением оптимизации хвостовой рекурсии введен Дэвид Уоррен HD [9] в контексте компиляции из Пролога , видел как явно установить один раз язык. Он был описан (хотя и не назван) Дэниелом П. Фридманом и Дэвидом С. Уайсом в 1974 году [10] как метод компиляции LISP . Как следует из названия, он применяется, когда единственная операция, которую нужно выполнить после рекурсивного вызова, - это добавить известное значение перед списком, возвращаемым из него (или, как правило, выполнить постоянное количество простых операций по построению данных). Таким образом, этот вызов был бы хвостовым вызовом, за исключением (" по модулю ") указанной операции cons . Но префикс значения в начале списка при выходе из рекурсивного вызова - это то же самое, что добавление этого значения в конец растущего списка при входе в рекурсивный вызов, таким образом создавая список как побочный эффект , как если бы неявный параметр аккумулятора. Следующий фрагмент Пролога иллюстрирует эту концепцию:
Пример пролога
% хвостовой рекурсии по модулю минусов: раздел ([], _ , [], []). раздел ([ X | Xs ], Pivot , [ X | Rest ], Bigs ) : - X @ < Pivot , !, раздел ( Xs , Pivot , Rest , Bigs ). partition ([ X | Xs ], Pivot , Smalls , [ X | Rest ]) : - раздел ( Xs , Pivot , Smalls , Rest ). | - В Haskell защищенная рекурсия: partition :: Ord a => [ a ] -> a -> ([ a ], [ a ]) partition [] _ = ( [] , [] ) partition ( x : xs ) p | x < p = ( x : a , b ) | в противном случае = ( a , x : b ), где ( a , b ) = раздел xs p |
% С явными унификациями: % нехвостовой рекурсивный перевод: раздел ([], _ , [], []). перегородка ( L , Pivot , Smalls , Bigs ) : - L = [ X | Xs ], ( X @ < Pivot -> раздел ( Xs , Pivot , Rest , Bigs ), Smalls = [ X | Rest ] ; раздел ( Xs , Pivot , Smalls , Rest ), Bigs = [ X | Rest ] ). | % С явными унификациями: % хвостовой рекурсивный перевод: раздел ([], _ , [], []). перегородка ( L , Pivot , Smalls , Bigs ) : - L = [ X | Xs ], ( X @ < Pivot -> Smalls = [ X | Rest ], раздел ( Xs , Pivot , Rest , Bigs ) ; Bigs = [ X | Rest ], раздел ( Xs , Pivot , Smalls , Rest ) ). |
Таким образом, при хвостовой рекурсивной трансляции такой вызов преобразуется в сначала создание нового узла списка и установку его first
поля, а затем выполнение хвостового вызова с указателем на поле узла в rest
качестве аргумента для рекурсивного заполнения.
Пример C
Следующий фрагмент определяет рекурсивную функцию в C, которая дублирует связанный список:
typedef struct list { void * value ; список структур * следующий ; } список ; список * дубликат ( константный список * ls ) { список * голова = NULL ; if ( ls ! = NULL ) { список * p = дубликат ( ls -> следующий ); голова = malloc ( размер * голова ); голова -> значение = ls -> значение ; голова -> следующий = p ; } вернуть голову ; } | ;; в схеме ( define ( duplicate ls ) ( if ( not ( null? ls )) ( cons ( car ls ) ( duplicate ( cdr ls ))) ' ())) |
%% в Прологе, dup ([ X | Xs ], R ): - dup ( Xs , Ys ), R = [ X | Ys ]. dup ([], []). |
В этой форме функция не является хвостовой рекурсивной, потому что управление возвращается вызывающей стороне после того, как рекурсивный вызов дублирует остальную часть входного списка. Даже если бы он выделил головной узел перед дублированием остальных, ему все равно нужно было бы вставить результат рекурсивного вызова в next
поле после вызова. [a] Таким образом, функция почти хвостовая рекурсивная. Метод Уоррена накладывает ответственность за заполнение next
поля на сам рекурсивный вызов, который, таким образом, становится хвостовым вызовом:
typedef struct list { void * value ; список структур * следующий ; } список ; недействительный duplicate_aux ( Const список * Ls , список * конец ); список * Дубликат ( Const список * Ls ) { список головы ; duplicate_aux ( ls , & head ); вернуть голову . следующий ; }void duplicate_aux ( const list * ls , list * end ) { if ( ls ! = NULL ) { end -> next = malloc ( sizeof * end ); конец -> следующий -> значение = ls -> значение ; duplicate_aux ( ls -> следующий , конец -> следующий ); } else { конец -> следующий = NULL ; } } | ;; в схеме ( define ( duplicate ls ) ( let (( head ( list 1 ))) ( let dup (( ls ls ) ( end head )) ( cond (( not ( null? ls )) ( set-cdr! end ( list ( car ls ))) ( dup ( cdr ls ) ( cdr end ))))) ( cdr head ))) |
%% в Прологе, dup ([ X | Xs ], R ): - R = [ X | Ys ], dup ( Xs , Ys ). dup ([], []). |
(Головной узел дозорного используется для упрощения кода.) Теперь вызываемый абонент присоединяется к концу растущего списка, а не заставляет вызывающего абонента добавлять его к началу возвращенного списка. Теперь работа выполняется на пути вперед от начала списка, до рекурсивного вызова, который затем продолжается, а не назад от конца списка, после того, как рекурсивный вызов вернул свой результат. Таким образом, он похож на метод накопления параметров, превращая рекурсивное вычисление в итеративное.
Для этого метода характерно то, что в стеке вызовов выполнения создается родительский фрейм , который вызываемый с хвостовой рекурсией вызываемый может повторно использовать в качестве своего собственного фрейма вызова, если присутствует оптимизация хвостового вызова.
Хвостовая рекурсивная реализация теперь может быть преобразована в явно итеративную форму в виде накапливающего цикла :
typedef struct list { void * value ; список структур * следующий ; } список ; список * Дубликат ( Const список * Ls ) { список головы , * конец ; конец = & голова ; в то время как ( ls ! = NULL ) { конец -> следующий = malloc ( sizeof * end ); конец -> следующий -> значение = ls -> значение ; ls = ls -> следующий ; конец = конец -> следующий ; } конец -> следующий = NULL ; вернуть голову . следующий ; } | ;; в схеме ( define ( duplicate ls ) ( let (( head ( list 1 ))) ( do (( end head ( cdr end )) ( ls ls ( cdr ls ))) (( null? ls ) ( cdr head ) ) ( set-cdr! конец ( список ( автомобиль ls )))))) |
%% в Прологе, %% Н / Д |
История
В документе, представленном на конференции ACM в Сиэтле в 1977 году, Гай Л. Стил резюмировал дебаты по GOTO и структурированному программированию и заметил, что вызовы процедур в конце процедуры лучше всего рассматривать как прямую передачу управления к вызываемая процедура, обычно исключающая ненужные операции манипулирования стеком. [2] Поскольку такие «хвостовые вызовы» очень распространены в Lisp , языке, где вызовы процедур являются повсеместными, эта форма оптимизации значительно снижает стоимость вызова процедуры по сравнению с другими реализациями. Стил утверждал, что плохо реализованные вызовы процедур привели к искусственному восприятию того, что GOTO дешевле, чем вызов процедуры. Стил далее утверждал, что «в целом вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры и могут быть единообразно закодированы как инструкции JUMP [машинного кода]», при этом инструкции манипулирования стеком машинного кода «считаются оптимизацией (а не наоборот!)". [2] Стил привел доказательства того, что хорошо оптимизированные числовые алгоритмы в Лиспе могут выполняться быстрее, чем код, созданный доступными в то время коммерческими компиляторами Фортрана, потому что стоимость вызова процедуры в Лиспе была намного ниже. В 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) B (данные1) вернуть A (данные2)
(где data1
и data2
являются параметрами) компилятор может перевести это как: [b]
foo: mov reg , [ sp + data1 ] ; извлечь data1 из параметра стека (sp) в рабочий регистр. push reg ; поместите data1 в стек, где B ожидает его позвонить B ; B использует data1 поп ; удалить data1 из стека mov reg , [ sp + data2 ] ; получить данные2 из параметра стека (sp) в рабочий регистр. push reg ; поместите data2 в стек там, где A ожидает позвонить А ; A использует data2 поп ; удалить data2 из стека. Ret
Оптимизатор хвостового вызова может затем изменить код на:
foo: mov reg , [ sp + data1 ] ; извлечь data1 из параметра стека (sp) в рабочий регистр. push reg ; поместите data1 в стек, где B ожидает его позвонить B ; B использует data1 поп ; удалить data1 из стека mov reg , [ sp + data2 ] ; получить данные2 из параметра стека (sp) в рабочий регистр. mov [ sp + data1 ], reg ; поместите data2 туда, где A ожидает jmp A ; A использует data2 и немедленно возвращается вызывающему.
Этот код более эффективен как с точки зрения скорости выполнения, так и с точки зрения использования пространства стека.
Через прыжки на батуте
Поскольку многие компиляторы Scheme используют C в качестве промежуточного целевого кода, хвостовая рекурсия должна быть закодирована на C без увеличения стека, даже если компилятор C не оптимизирует хвостовые вызовы. Многие реализации достигают этого с помощью устройства, известного как батут , фрагмента кода, который многократно вызывает функции. Все функции вводятся через батут. Когда функция должна следовать за другой функцией, вместо того, чтобы вызывать ее напрямую и затем возвращать результат, она возвращает адрес вызываемой функции и параметры вызова обратно в трамплин (с которого она была вызвана сама), а trampoline позаботится о следующем вызове этой функции с указанными параметрами. Это гарантирует, что стек C не будет расти, и итерация может продолжаться бесконечно.
Можно реализовать батуты с помощью функций высшего порядка на языках, которые их поддерживают, таких как Groovy , Visual Basic .NET и C # . [20]
Использование батута для всех вызовов функций, скорее дороже , чем обычный вызов функции С, так что по меньшей мере одна схемой компилятора, Цыпленок , использует технику , впервые описанный Генри Бейкер из неопубликованного предложения по Эндрю Аппель , [21] , в которой нормальной С используются вызовы, но размер стека проверяется перед каждым вызовом. Когда стек достигает максимально допустимого размера, объекты в стеке собираются мусором с использованием алгоритма Чейни , перемещая все живые данные в отдельную кучу. После этого стек разматывается ("выталкивается"), и программа возобновляет работу из состояния, сохраненного непосредственно перед сборкой мусора. Бейкер говорит: «Метод Аппеля позволяет избежать большого количества прыжков на батуте, иногда прыгая с Эмпайр-стейт-билдинг». [21] Сборка мусора гарантирует, что взаимная хвостовая рекурсия может продолжаться бесконечно. Однако этот подход требует, чтобы ни один вызов функции C никогда не возвращался, поскольку нет гарантии, что фрейм стека вызывающей стороны все еще существует; следовательно, он включает в себя гораздо более драматическое внутреннее переписывание программного кода: стиль передачи продолжения .
Отношение к while construct
Хвостовая рекурсия может быть связана с оператором потока управления while посредством преобразования, например следующего:
функция Foo ( х ) является : если предикат ( х ) , то возвращать Foo (бар ( х )) еще возвращение БАЗ ( х )
Вышеупомянутая конструкция преобразуется в:
функция Foo ( х ) является : в то время как предикат ( х ) делать : х ← бар ( х ) возвращение Баз ( х )
В предыдущем случае x может быть кортежем, включающим более одной переменной: в этом случае необходимо соблюдать осторожность при разработке оператора присваивания x ← bar ( x ), чтобы зависимости соблюдались. Может потребоваться ввести вспомогательные переменные или использовать конструкцию подкачки .
Более общее использование хвостовой рекурсии может быть связано с операторами потока управления, такими как break и continue , как показано ниже:
функция Foo ( х ) является : если р ( х ) , то обратный бар ( х ) еще , если д ( х ) , то вернуть Баз ( х ) ... иначе, если t ( x ), то верните foo (quux ( x )) ... иначе вернуть foo (quuux ( x ))
где bar и baz - это прямые обратные вызовы, тогда как quux и quuux включают рекурсивный хвостовой вызов foo . Перевод дается следующим образом:
функция Foo ( х ) является : делать : если р ( х ) , то х ← бар ( х ) перерыв еще , если д ( х ) , то х ← Баз ( х ) перерыв ... иначе, если t ( x ), то x ← quux ( x ) continue ... else x ← quuux ( x ) продолжить цикл return x
По языку
- Haskell - Да [22]
- Эрланг - Да
- Common Lisp - некоторые реализации выполняют оптимизацию хвостового вызова во время компиляции, если оптимизируются для скорости
- JavaScript - движки, совместимые с ECMAScript 6.0, должны иметь хвостовые вызовы [23], которые теперь реализованы в Safari / WebKit [24], но отклонены V8 и SpiderMonkey.
- Lua - рекурсия хвоста требуется по определению языка [25]
- OCaml - Да
- Python - стандартные реализации Python не выполняют оптимизацию хвостового вызова, хотя для этого доступен сторонний модуль. [26] Изобретатель языка Гвидо ван Россум утверждает, что трассировки стека изменяются путем исключения хвостового вызова, что усложняет отладку, и предпочитает, чтобы программисты использовали вместо этого явную итерацию [27]
- Rust - оптимизация хвостового вызова может выполняться в ограниченных случаях, но не гарантируется [28]
- Схема - Требуется определением языка [29] [30]
- Ракетка - Да [31]
- Tcl - Начиная с Tcl 8.6, в Tcl есть команда хвостового вызова [32]
- Kotlin - имеет модификатор tailrec для функций [33]
- Эликсир - Эликсир реализует оптимизацию хвостового вызова [34]. Как и все языки, в настоящее время нацеленные на BEAM VM.
- Perl - явный вариант с вариантом оператора goto, который принимает имя функции:
goto &NAME
[35] - Scala - рекурсивные функции хвоста автоматически оптимизируются компилятором. Такие функции также могут быть помечены
@tailrec
аннотацией, что делает ошибку компиляции, если функция не является хвостовой рекурсивной [36] - Objective-C - компилятор оптимизирует хвостовые вызовы, когда указана опция -O1 (или выше), но это легко нарушается вызовами, добавленными с помощью автоматического подсчета ссылок (ARC).
- F # - F # реализует TCO по умолчанию, где это возможно [37]
- Clojure - Clojure имеет повторяющуюся специальную форму. [38]
- Вперед - нет [39]
Смотрите также
- Рекурсия курса ценностей
- Рекурсия (информатика)
- Встроенное расширение
- Подпрограмма Leaf
- Corecursion
Заметки
- ^ Как это:
если ( ls ! = NULL ) { голова = malloc ( sizeof * head ); голова -> значение = ls -> значение ; head -> next = дублировать ( ls -> next ); }
- ^ Инструкция первого помещает текущее местоположение кода в стек и затем выполняет безусловный переход к месту кодауказанного на этикетке. Командасначала извлекает из стека место кода, а затем выполняет безусловный переход к полученному участку кода.
call
ret
Рекомендации
- ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Продвинутая реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2.
- ^ а б в Стил, Гай Льюис (1977). «Развенчание мифа о« дорогом вызове процедуры »или о реализациях вызова процедур, которые считаются вредными, или LAMBDA: The Ultimate GOTO». Материалы ежегодной конференции 1977 г. - ACM '77 . С. 153–162. DOI : 10.1145 / 800179.810196 . ЛВП : 1721,1 / 5753 . ISBN 978-1-4503-2308-6.
- ^ "Независимый от цели генератор кода LLVM - документация по LLVM 7" . llvm.org .
- ^ «Рекурсия - Использование памяти стека для хвостовых вызовов - Теоретическая информатика» . Cstheory.stackexchange.com. 2011-07-29 . Проверено 21 марта 2013 .
- ^ а б «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме» . R6rs.org . Проверено 21 марта 2013 .
- ^ «Пересмотренный отчет ^ 6 об алгоритмической языковой схеме - обоснование» . R6rs.org . Проверено 21 марта 2013 .
- ^ «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме» . R6rs.org . Проверено 21 марта 2013 .
- ^ а б Sussman, GJ; Абельсон, Хэл (1984). Структура и интерпретация компьютерных программ . Кембридж, Массачусетс: MIT Press. ISBN 0-262-01077-1.
- ^ DHD Уоррен, DAI Research Report 141 , Эдинбургский университет, 1980.
- ^ Дэниел П. Фридман и Дэвид С. Уайз, Технический отчет TR19: Разворачивание структурированных рекурсий в итерациях , Университет Индианы, декабрь 1974 г.
- ^ R5RS Разд. 3.5, Ричард Келси; Уильям Клингер; Джонатан Рис; и другие. (Август 1998 г.). «Пересмотренный отчет 5 по алгоритмической языковой схеме» . Вычисление высшего порядка и символическое вычисление . 11 (1): 7–105. DOI : 10,1023 / A: 1010051815785 .
- ^ Контактная информация. "перейти" . perldoc.perl.org . Проверено 21 марта 2013 .
- ^ «В чем разница между хвостовыми вызовами и хвостовой рекурсией? », Stack Overflow
- ^ " Какие ограничения JVM налагает на оптимизацию хвостового вызова ", Programmers Stack Exchange
- ^ Латтнер, Крис. «Справочное руководство по языку LLVM, раздел: Независимый от цели генератор кода LLVM, подраздел: Оптимизация хвостового вызова» . Инфраструктура компилятора LLVM . Проект LLVM . Проверено 24 июня 2018 .
- ^ «Использование коллекции компиляторов GNU (GCC): параметры оптимизации» . gcc.gnu.org .
- ^ "foptimize-sibling-calls" . software.intel.com .
- ^ «Решение хвостовых вызовов C ++» .
- ^ Пробст, Марк (20 июля 2000 г.). "правильная хвостовая рекурсия для gcc" . Проект GCC . Проверено 10 марта 2015 года .
- ^ Сэмюэл Джек, подпрыгивая на хвосте . Функциональное развлечение . 9 апреля 2008 г.
- ^ a b Генри Бейкер, "Минусы не должны ПРОТИВ его аргументов, Часть II: Чейни на MTA"
- ^ «Хвостовая рекурсия - HaskellWiki» . wiki.haskell.org . Проверено 8 июня 2019 .
- ^ Берес-Деак, Адам. «Стоит посмотреть: Дуглас Крокфорд говорит о новых хороших частях JavaScript в 2014 году» . bdadam.com .
- ^ «ECMAScript 6 в WebKit» . 13 октября 2015 г.
- ^ «Справочное руководство по Lua 5.3» . www.lua.org .
- ^ "Баручел / ТКО" . GitHub .
- ^ Россум, Гвидо Ван (22 апреля 2009 г.). «Неопифоник: устранение рекурсии хвоста» .
- ^ «FAQ по Rust» . prev.rust-lang.org .
- ^ «Пересмотренный отчет ^ 5 по алгоритмической языковой схеме» . www.schemers.org .
- ^ «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме» . www.r6rs.org .
- ^ «Ракетный справочник» . docs.racket-lang.org .
- ^ "Страница руководства по вызову - встроенные команды Tcl" . www.tcl.tk .
- ^ «Функции: infix, vararg, tailrec - язык программирования Kotlin» . Котлин .
- ^ «Рекурсия» . elixir-lang.github.com .
- ^ "goto - perldoc.perl.org" . perldoc.perl.org .
- ^ «Стандартная библиотека Scala 2.13.0 - scala.annotation.tailrec» . www.scala-lang.org . Проверено 20 июня 2019 .
- ^ «Хвостовые звонки в F #» . msdn . Microsoft.
- ^ "(повторное выражение *)" . clojure.org .
- ^ "предложение: Перейти 2: добавить оператор стал для поддержки хвостовых вызовов" . github.com .
Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.