Хвостовой звонок - Tail call

В Информатика, а хвостовой зов это подпрограмма вызов выполняется как финальное действие процедуры.^[1] Если целью хвоста является одна и та же подпрограмма, то говорят, что подпрограмма хвостовой рекурсивный, который является частным случаем прямого рекурсия. Хвостовая рекурсия (или же хвостовая рекурсия) особенно полезен и часто прост в реализации.

Хвостовые вызовы могут быть реализованы без добавления нового кадр стека к стек вызовов. Большая часть кадра текущей процедуры больше не нужна и может быть заменена кадром хвостового вызова, измененным соответствующим образом (аналогично наложение для процессов, но для вызовов функций). Затем программа может Прыгать вызываемой подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранение хвостового сигнала или же оптимизация хвостового вызова. Устранение хвостового вызова позволяет выполнять вызовы процедур в хвостовой позиции так же эффективно, как и идти к заявления, что позволяет эффективно структурное программирование. По словам Гай Л. Стил, «в общем, вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры и могут быть единообразно закодированы как инструкции JUMP [машинного кода]».^[2]

Не все языки программирования требуют исключения хвостового вызова. Однако в функциональные языки программирования, устранение хвостового вызова часто гарантируется языковой стандарт, позволяя хвостовой рекурсии использовать такой же объем памяти как эквивалент петля. Особый случай хвостовых рекурсивных вызовов, когда функция вызывает саму себя, может быть более податливым для исключения вызова, чем общие хвостовые вызовы. Когда семантика языка явно не поддерживает общие хвостовые вызовы, компилятор часто все еще может оптимизировать звонки братьев и сестер, или хвостовые вызовы функций, которые принимают и возвращают те же типы, что и вызывающий.^[3]

Описание

Когда функция вызывается, компьютер должен «запомнить» место, откуда он был вызван, обратный адрес, чтобы он мог вернуться в это место с результатом после завершения вызова. Обычно эта информация сохраняется на стек вызовов, простой список мест возврата в порядке времени достижения описываемых ими пунктов вызова. Для хвостовых вызовов нет необходимости запоминать вызывающего - вместо этого устранение хвостового вызова вносит только минимально необходимые изменения в кадр стека перед его передачей,^[4] и функция, вызываемая хвостом, вернется прямо к оригинал звонящий. Хвостовой вызов не обязательно должен появляться лексически после всех других операторов в исходном коде; важно только, чтобы вызывающая функция возвращалась сразу после хвостового вызова, возвращая результат хвостового вызова, если таковой имеется, поскольку вызывающая функция игнорируется при выполнении оптимизации.

Для нерекурсивных вызовов функций это обычно оптимизация это экономит немного времени и места, так как не так много различных функций, доступных для вызова. При работе с рекурсивным или взаимно рекурсивный функции, в которых рекурсия происходит через хвостовые вызовы, однако пространство стека и количество сохраненных возвратов могут стать очень значительными, поскольку функция может вызывать себя, прямо или косвенно, создавая каждый раз новый кадр стека вызовов. Устранение хвостового вызова часто снижает требования к пространству асимптотического стека с линейного или О (n), до постоянного, или О (1). Таким образом, исключение хвостового вызова требуется стандартными определениями некоторых языков программирования, таких как Схема,^[5]^[6] и языки в ML семья среди других. Определение языка схемы точно формализует интуитивное понятие положения хвоста, указывая, какие синтаксические формы позволяют получить результаты в контексте хвоста.^[7] Реализации, позволяющие неограниченному количеству хвостовых вызовов быть активными в один и тот же момент, благодаря исключению хвостовых вызовов, также могут называться «правильно рекурсивными хвостами».^[5]

Помимо пространства и эффективности выполнения, устранение хвостовых вызовов важно в функциональное программирование идиома известная как стиль передачи (CPS), которые в противном случае быстро исчерпали бы пространство стека.

Синтаксическая форма

Хвостовой вызов может быть расположен непосредственно перед синтаксическим концом функции:

функция фу(данные) {    а(данные);    возвращаться б(данные);}

Здесь оба а (данные) и b (данные) звонки, но б это последнее, что процедура выполняет перед возвратом и, таким образом, находится в хвостовой позиции. Однако не все хвостовые вызовы обязательно расположены в синтаксическом конце подпрограммы:

функция бар(данные) {    если ( а(данные) ) {        возвращаться б(данные);    }    возвращаться c(данные);}

Здесь оба вызова б и c находятся в хвостовой позиции. Это потому, что каждый из них находится в конце if-branch соответственно, даже если первый синтаксически не находится в конце бартело.

В этом коде:

функция foo1(данные) {    возвращаться а(данные) + 1;}

функция foo2(данные) {    вар Ret = а(данные);    возвращаться Ret;}

функция foo3(данные) {    вар Ret = а(данные);    возвращаться (Ret == 0) ? 1 : Ret;}

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

Примеры программ

Следующая программа является примером в Схема:^[8]

;; факториал: число -> число;; рассчитать произведение всех положительных;; целые числа, меньшие или равные n.(определять (факториал п) (если (= п 1)    1    (* п (факториал (- п 1)))))

Это не написано в стиле хвостовой рекурсии, потому что функция умножения («*») находится в хвостовой позиции. Это можно сравнить с:

;; факториал: число -> число;; рассчитать произведение всех положительных;; целые числа, меньшие или равные n.(определять (факториал п)  (фактолог 1 п))(определять (фактолог товар п)  (если (< п 2)      товар      (фактолог (* товар п)                 (- п 1))))

Эта программа предполагает аппликативный порядок оценка. Внутренняя процедура фактолог называет себя последний в потоке управления. Это позволяет устный переводчик или же компилятор чтобы реорганизовать выполнение, которое обычно выглядело бы так:^[8]

  call factorial (4) call fact-iter (1 4) call fact-iter (4 3) call fact-iter (12 2) call fact-iter (24 1) return 24 return 24 return 24 return 24 return 24

в более эффективный вариант, как в пространстве, так и во времени:

  вызов факториала (4) вызов факториала (1 4) заменить аргументы на (4 3) заменить аргументы на (12 2) заменить аргументы на (24 1) вернуть 24 вернуть 24

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

Некоторые программисты, работающие с функциональными языками, будут переписывать рекурсивный код так, чтобы он был хвостовой рекурсией, чтобы они могли воспользоваться этой функцией. Это часто требует добавления аргумента «аккумулятор» (товар в приведенном выше примере) к функции. В некоторых случаях (например, в списках фильтрации) и на некоторых языках полная хвостовая рекурсия может потребовать написания функции, которая ранее была чисто функциональной, чтобы она изменяла ссылки, хранящиеся в других переменных.^{[нужна цитата ]}

Хвостовая рекурсия по модулю минусов

Хвостовая рекурсия по модулю минусов является обобщением оптимизации хвостовой рекурсии, введенной Дэвид Х. Д. Уоррен^[9] в контексте сборник из Пролог рассматривается как явно установить один раз язык. Он был описан (но не назван) Дэниел П. Фридман и Дэвид С. Уайз в 1974 г.^[10] как LISP техника составления. Как следует из названия, он применяется, когда единственная операция, которую нужно выполнить после рекурсивного вызова, - это добавить известное значение перед списком, возвращаемым из него (или, в общем, выполнить постоянное количество простых операций по построению данных). Таким образом, этот призыв был бы хвостовой зов за исключением ("по модулю ") указанный минусы операция. Но добавление значения в начале списка на выходе из рекурсивного вызова - это то же самое, что добавить это значение в конец растущего списка при входе в рекурсивный вызов, таким образом создавая список как побочный эффект, как если бы в неявном параметре аккумулятора. Следующий фрагмент Пролога иллюстрирует эту концепцию:

Пример пролога

% хвостовой рекурсии по модулю минусов:раздел([], _, [], []).раздел([Икс|Хз], Вращаться, [Икс|Отдых], Большие) :-  Икс @< Вращаться, !,  раздел(Хз, Вращаться, Отдых, Большие).раздел([Икс|Хз], Вращаться, Smalls, [Икс|Отдых]) :-  раздел(Хз, Вращаться, Smalls, Отдых).

- В Haskell защищенная рекурсия:раздел :: Ord а => [а] -> а -> ([а],[а])раздел [] _ = ([],[])раздел (Икс:хз) п | Икс < п     = (Икс:а,б)                   | иначе = (а,Икс:б)   куда      (а,б) = раздел хз п

% С явными унификациями:% не хвостовой рекурсивный перевод:раздел([], _, [], []).раздел(L, Вращаться, Smalls, Большие) :- L=[Икс|Хз], (  Икс @< Вращаться -> раздел(Хз,Вращаться,Отдых,Большие), Smalls=[Икс|Отдых] ;  раздел(Хз,Вращаться,Smalls,Отдых), Большие=[Икс|Отдых] ).

% С явными унификациями:% хвостовой рекурсивный перевод:раздел([], _, [], []).раздел(L, Вращаться, Smalls, Большие) :- L=[Икс|Хз], (  Икс @< Вращаться -> Smalls=[Икс|Отдых], раздел(Хз,Вращаться,Отдых,Большие) ;  Большие=[Икс|Отдых], раздел(Хз,Вращаться,Smalls,Отдых) ).

Таким образом, в хвостовой рекурсивной трансляции такой вызов преобразуется в первое создание нового узел списка и установив его первый поле и тогда выполнение хвостового вызова с указателем на узел отдых поле в качестве аргумента, которое необходимо заполнить рекурсивно.

Пример C

Следующий фрагмент определяет рекурсивную функцию в C который дублирует связанный список:

typedef структура список {    пустота *ценить;    структура список *следующий;} список;список *дублировать(const список *ls){    список *голова = НОЛЬ;    если (ls != НОЛЬ) {        список *п = дублировать(ls->следующий);        голова = маллок(размер *голова);        голова->ценить = ls->ценить;        голова->следующий = п;    }    возвращаться голова;}

;; в схеме,(определять (дублировать ls)  (если (нет (ноль? ls))    (минусы (машина ls)          (дублировать (CDR ls)))    '()))

%% в Прологе,обман([Икс|Хз],р):-   обман(Хз,Ys),  р=[Икс|Ys].обман([],[]).

В этой форме функция не является хвостовой рекурсивной, потому что управление возвращается вызывающей стороне после того, как рекурсивный вызов дублирует остальную часть входного списка. Даже если бы выделить голова node перед дублированием остальных, ему все равно нужно будет подключить результат рекурсивного вызова к следующий поле после звонок.^[а] Итак, функция почти хвостово-рекурсивный. Метод Уоррена выдвигает ответственность за заполнение следующий в сам рекурсивный вызов, который становится хвостовым вызовом:

typedef структура список {    пустота *ценить;    структура список *следующий;} список;пустота duplicate_aux(const список *ls, список *конец);список *дублировать(const список *ls){       список голова;    duplicate_aux(ls, &голова);    возвращаться голова.следующий;}пустота duplicate_aux(const список *ls, список *конец){    если (ls != НОЛЬ) {        конец->следующий = маллок(размер *конец);        конец->следующий->ценить = ls->ценить;        duplicate_aux(ls->следующий, конец->следующий);    } еще {        конец->следующий = НОЛЬ;    }}

;; в схеме,(определять (дублировать ls)  (позволять ((голова (список 1)))    (позволять обман ((ls  ls)               (конец голова))      (cond         ((нет (ноль? ls))          (set-cdr! конец (список (машина ls)))         (обман (CDR ls) (CDR конец)))))    (CDR голова)))

%% в Прологе,обман([Икс|Хз],р):-   р=[Икс|Ys],   обман(Хз,Ys).обман([],[]).

(Для упрощения кода используется головной узел дозорного устройства.) Теперь вызываемый абонент присоединяется к концу растущего списка, а не заставляет вызывающего абонента добавлять его к началу возвращенного списка. Работа сейчас в пути вперед с начала списка, перед рекурсивный вызов, который затем продолжается, вместо назад с конца списка, после рекурсивный вызов вернул свой результат. Таким образом, он похож на метод накопления параметров, превращая рекурсивное вычисление в итерационное.

Для этой техники характерно то, что родитель Рамка создается в стеке вызовов выполнения, который вызываемый с хвостовой рекурсией вызываемый может повторно использовать в качестве своего собственного кадра вызова, если присутствует оптимизация хвостового вызова.

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

typedef структура список {    пустота *ценить;    структура список *следующий;} список;список *дублировать(const список *ls){    список голова, *конец;    конец = &голова;    пока (ls != НОЛЬ)    {        конец->следующий        = маллок(размер *конец);        конец->следующий->ценить = ls->ценить;        ls = ls->следующий;        конец = конец->следующий;    }    конец->следующий = НОЛЬ;    возвращаться голова.следующий;}

 ;; в схеме, (определять (дублировать ls)   (позволять ((голова (список 1)))     (делать ((конец голова (CDR конец))          (ls  ls   (CDR ls )))         ((ноль? ls) (CDR голова))       (set-cdr! конец (список (машина ls))))))

%% в Прологе,%% Н / Д

История

В документе, доставленном ACM конференция в Сиэтле в 1977 г., Гай Л. Стил подвел итог дискуссии по ИДТИ К и структурное программирование и заметил, что вызовы процедур в конце процедуры лучше всего рассматривать как прямую передачу управления вызываемой процедуре, что обычно устраняет ненужные операции манипулирования стеком.^[2] Поскольку такие "хвостовые крики" очень распространены в Лисп, язык, в котором вызовы процедур являются повсеместными, эта форма оптимизации значительно снижает стоимость вызова процедуры по сравнению с другими реализациями. Стил утверждал, что плохо реализованные вызовы процедур привели к искусственному восприятию того, что GOTO дешевле, чем вызов процедуры. Стил далее утверждал, что «в целом вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры и могут быть единообразно закодированы как инструкции JUMP [машинного кода]», при этом инструкции манипулирования стеком машинного кода «считаются оптимизацией (а не наоборот!)".^[2] Стил привел доказательства того, что хорошо оптимизированные числовые алгоритмы в Лиспе могут выполняться быстрее, чем код, созданный доступными в то время коммерческими компиляторами Фортрана, потому что стоимость вызова процедуры в Лиспе была намного ниже. В Схема, диалект Лиспа, разработанный Стилом с Джеральд Джей Сассман, исключение хвостового вызова гарантированно реализовано в любом интерпретаторе.^[11]

Методы реализации

Рекурсия хвоста важна для некоторых языки высокого уровня, особенно функциональный и логика языков и членов Лисп семья. В этих языках хвостовая рекурсия является наиболее часто используемым (а иногда и единственным доступным) способом реализации итерации. Спецификация языка Scheme требует, чтобы хвостовые вызовы были оптимизированы, чтобы не увеличивать стек. Хвостовые вызовы могут быть сделаны явно в Perl, с вариантом оператора "goto", который принимает имя функции: перейти & ИМЯ;^[12]

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

Например, в Виртуальная машина Java (JVM) хвостовые рекурсивные вызовы могут быть исключены (поскольку при этом повторно используется существующий стек вызовов), но общие хвостовые вызовы не могут быть (поскольку это изменяет стек вызовов).^[13]^[14] В результате функциональные языки, такие как Scala которые нацелены на JVM, могут эффективно реализовать прямую хвостовую рекурсию, но не взаимную хвостовую рекурсию.

В GCC, LLVM / Clang, и Intel наборы компиляторов выполняют оптимизацию хвостового вызова для C и другие языки на более высоких уровнях оптимизации или когда -foptimize-sibling-calls вариант пройден.^[15]^[16]^[17] Хотя данный синтаксис языка может не поддерживать его явно, компилятор может выполнить эту оптимизацию всякий раз, когда он может определить, что возвращаемые типы для вызывающего и вызываемого эквивалентны и что типы аргументов, переданные в обе функции, либо одинаковы, либо требуют такой же общий объем памяти в стеке вызовов.^[18]

Доступны различные способы реализации.

В сборке

Хвостовые вызовы часто оптимизируются переводчики и компиляторы из функциональное программирование и логическое программирование языков к более эффективным формам итерация. Например, Схема программисты обычно выражают пока петли как вызовы процедур в хвостовой позиции и полагаться на компилятор или интерпретатор схемы, чтобы заменить хвостовые вызовы более эффективными Прыгать инструкции.^[19]

Для компиляторов, генерирующих сборку напрямую, исключить хвостовой вызов очень просто: достаточно заменить код операции вызова на код перехода после фиксации параметров в стеке. С точки зрения компилятора, первый приведенный выше пример изначально транслируется в псевдо-код.язык ассемблера (на самом деле это действительно сборка x86 ):

 foo:  вызов B  вызов А  Ret

Устранение хвостового вызова заменяет последние две строки одной инструкцией перехода:

 foo:  вызов B  jmp  А

После подпрограммы А завершится, затем он вернется прямо на обратный адрес фу, опуская ненужные Ret утверждение.

Обычно вызываемые подпрограммы должны быть снабжены параметры. Таким образом, сгенерированный код должен гарантировать, что кадр вызова for A правильно настроен перед переходом к подпрограмме, называемой хвостом. Например, на платформы где стек вызовов не просто содержит обратный адрес, но и параметры для подпрограммы, компилятору может потребоваться выдать инструкции для настройки стека вызовов. На такой платформе для кода:

функция foo (данные1, данные2) B (данные1) возвращаться A (данные2)

(куда data1 и данные2 являются параметрами) компилятор может перевести это как:^[b]

 1  foo: 2    mov  рег,[зр+data1] ; получить data1 из параметра стека (sp) в рабочий регистр. 3    толкать рег            ; поместить data1 в стек, где B ожидает 4    вызов B              ; B использует data1 5    поп                 ; удалить data1 из стека 6    mov  рег,[зр+данные2] ; получить данные2 из параметра стека (sp) в рабочий регистр. 7    толкать рег            ; поместить data2 в стек, где A ожидает 8    вызов А              ; A использует data2 9    поп                 ; удалить data2 из стека.10    Ret

Затем оптимизатор хвостового вызова может изменить код на:

1  foo:2    mov  рег,[зр+data1] ; получить data1 из параметра стека (sp) в рабочий регистр.3    толкать рег            ; поместить data1 в стек, где B ожидает4    вызов B              ; B использует data15    поп                 ; удалить data1 из стека6    mov  рег,[зр+данные2] ; получить данные2 из параметра стека (sp) в рабочий регистр.7    mov  [зр+data1],рег ; поместите data2 туда, где A ожидает8    jmp  А              ; A использует data2 и немедленно возвращается вызывающему.

Этот код более эффективен как с точки зрения скорости выполнения, так и с точки зрения использования пространства стека.

Через прыжки на батуте

Поскольку многие Схема компиляторы используют C в качестве промежуточного целевого кода хвостовая рекурсия должна быть закодирована на C без увеличения стека, даже если компилятор C не оптимизирует хвостовые вызовы. Многие реализации достигают этого с помощью устройства, известного как батут, фрагмент кода, который многократно вызывает функции. Все функции вводятся через батут. Когда функция должна следовать за другой функцией, вместо того, чтобы вызывать ее напрямую и затем возвращать результат, она возвращает адрес вызываемой функции и параметры вызова обратно в трамплин (с которого он был вызван сам), а trampoline позаботится о следующем вызове этой функции с указанными параметрами. Это гарантирует, что стек C не будет расти, и итерация может продолжаться бесконечно.

Возможна реализация батутов с использованием функции высшего порядка на языках, которые их поддерживают, например Groovy, Visual Basic .NET и C #.^[20]

Использование трамплина для всех вызовов функций намного дороже, чем обычный вызов функции C, поэтому по крайней мере один компилятор схемы, Курица, использует технику, впервые описанную Генри Бейкер из неопубликованного предложения Эндрю Аппель,^[21] в котором используются обычные вызовы C, но размер стека проверяется перед каждым вызовом. Когда стек достигает максимально допустимого размера, объекты в стеке становятся сборщик мусора с использованием Алгоритм Чейни перемещая все живые данные в отдельную кучу. После этого стек разматывается ("выталкивается"), и программа возобновляет работу из состояния, сохраненного непосредственно перед сборкой мусора. Бейкер говорит: «Метод Аппеля позволяет избежать большого количества прыжков на батуте, иногда прыгая с Эмпайр-стейт-билдинг».^[21] Сборка мусора гарантирует, что взаимная хвостовая рекурсия может продолжаться бесконечно. Однако этот подход требует, чтобы ни один вызов функции C никогда не возвращался, поскольку нет гарантии, что фрейм стека вызывающей стороны все еще существует; следовательно, он включает в себя гораздо более радикальное внутреннее переписывание программного кода: стиль передачи.

Отношении пока строить

Рекурсия хвоста может быть связана с пока поток управления оператор посредством преобразования, такого как следующее:

функция фу (Икс) является:    если предикат(Икс) тогда        возвращаться foo (бар (Икс))    еще        возвращаться баз (Икс)

Вышеупомянутая конструкция преобразуется в:

функция фу (Икс) является:    пока предикат(Икс) делать:        Икс ← бар (Икс)    возвращаться баз (Икс)

В предыдущем, Икс может быть кортежем, включающим более одной переменной: в этом случае необходимо соблюдать осторожность при разработке оператора присваивания Икс ← бар (Икс), чтобы соблюдались зависимости. Может потребоваться ввести вспомогательные переменные или использовать замена построить.

Более общее использование хвостовой рекурсии может быть связано с операторами потока управления, такими как перемена и Продолжить, как в следующем:

функция фу (Икс) является:    если п(Икс) тогда        возвращаться бар(Икс)    иначе если q(Икс) тогда        возвращаться баз (Икс)    ...    иначе если т(Икс) тогда        возвращаться foo (quux (Икс))    ...    еще        возвращаться foo (quuux (Икс))

куда бар и баз прямые обратные вызовы, тогда как quux и Quuux задействовать рекурсивный хвостовой вызов фу. Перевод дается следующим образом:

функция фу (Икс) является:    делать:        если п(Икс) тогда            Икс ← бар (Икс)            перемена        иначе если q(Икс) тогда            Икс ← баз (Икс)            перемена        ...        иначе если т(Икс) тогда            Икс ← quux (Икс)            Продолжить        ...        еще            Икс ← quuux (Икс)            Продолжить        петля    возвращаться Икс

По языку

Haskell - Да^[22]
Erlang - Да
Common Lisp - Некоторые реализации выполняют оптимизацию хвостового вызова во время компиляции при оптимизации по скорости
JavaScript - ECMAScript 6.0-совместимые двигатели должны иметь хвостовые запросы^[23] который сейчас реализован на Сафари /WebKit^[24] но отвергнут V8 и SpiderMonkey
Lua - Рекурсия хвоста требуется по определению языка^[25]
Python - Стандартные реализации Python не выполняют оптимизацию хвостового вызова, хотя для этого доступен сторонний модуль.^[26] Изобретатель языка Гвидо ван Россум утверждает, что следы стека изменяются путем исключения хвостового вызова, что усложняет отладку, и предпочитает, чтобы программисты использовали явные итерация вместо^[27]
Ржавчина - Оптимизация хвостового вызова может выполняться в ограниченных случаях, но не гарантируется^[28]
Схема - Требуется определением языка^[29]^[30]
Ракетка - Да^[31]
Tcl - Начиная с Tcl 8.6, в Tcl есть команда tailcall^[32]
Котлин - Имеет Tailrec модификатор для функций^[33]
Эликсир - В Elixir реализована оптимизация хвостового вызова^[34] Как и все языки, в настоящее время нацеленные на BEAM VM.
Perl - Явный вариант с вариантом оператора "goto", который принимает имя функции: перейти & ИМЯ;^[35]
Scala - Хвостовые рекурсивные функции автоматически оптимизируются компилятором. Такие функции также могут быть отмечены значком @tailrec аннотация, которая приводит к ошибке компиляции, если функция не является хвостовой рекурсивной^[36]
Цель-C - Компилятор оптимизирует хвостовые вызовы, когда указана опция -O1 (или выше), но это легко нарушается вызовами, добавленными Автоматический подсчет ссылок (ARC).
F # - F # реализует TCO по умолчанию, где это возможно ^[37]
Clojure - Clojure имеет повторяться особая форма.^[38]

Смотрите также

Примечания

^ Так:

если (ls != НОЛЬ) {   голова = маллок( размер *голова);   голова->ценить = ls->ценить;   голова->следующий = дублировать( ls->следующий); }

^ В вызов Инструкция сначала помещает текущую позицию кода в стек, а затем выполняет безусловный переход к позиции кода, указанной меткой. В Ret Инструкция сначала извлекает ячейку кода из стека, а затем выполняет безусловный переход к полученной ячейке кода.