Chamada de cauda - Tail call

Na ciência da computação , uma chamada final é uma chamada de sub - rotina executada como a ação final de um procedimento. Se o destino de uma cauda for a mesma sub-rotina, a sub-rotina é chamada de cauda recursiva , que é um caso especial de recursão direta . A recursão de cauda (ou recursão de cauda ) é particularmente útil e, muitas vezes, fácil de lidar com a otimização em implementações.

As chamadas finais podem ser implementadas sem adicionar um novo quadro de pilha à pilha de chamadas . A maior parte do quadro do procedimento atual não é mais necessária e pode ser substituída pelo quadro da chamada final, modificado conforme apropriado (semelhante à sobreposição para processos, mas para chamadas de função). O programa pode então pular para a sub-rotina chamada. A produção desse código em vez de uma sequência de chamada padrão é chamada de eliminação de chamada final ou otimização de chamada final . A eliminação da chamada final permite que as chamadas de procedimento na posição final sejam implementadas tão eficientemente quanto as instruções goto , permitindo assim uma programação estruturada eficiente . Nas palavras de Guy L. Steele , "em geral, as chamadas de procedimento podem ser utilmente pensadas como instruções GOTO que também passam parâmetros e podem ser codificadas uniformemente como [código de máquina] instruções JUMP."

Nem todas as linguagens de programação exigem a eliminação da chamada final. No entanto, em linguagens de programação funcionais , a eliminação da chamada final geralmente é garantida pelo padrão da linguagem , permitindo que a recursão final use uma quantidade semelhante de memória como um loop equivalente . O caso especial de chamadas recursivas finais, quando uma função chama a si mesma, pode ser mais fácil de eliminar chamadas do que chamadas finais gerais. Quando a semântica da linguagem não suporta explicitamente chamadas finais gerais, um compilador pode muitas vezes ainda otimizar chamadas irmãs ou chamadas finais para funções que recebem e retornam os mesmos tipos do chamador.

Descrição

Quando uma função é chamada, o computador deve "lembrar" o local de onde foi chamado, o endereço de retorno , para que possa retornar a esse local com o resultado assim que a chamada for concluída. Normalmente, essas informações são salvas na pilha de chamadas , uma lista simples de locais de retorno na ordem dos horários em que os locais de chamada descritos foram alcançados. Para chamadas finais, não há necessidade de lembrar o chamador - em vez disso, a eliminação da chamada final faz apenas as alterações mínimas necessárias no quadro de pilha antes de passá-lo, e a função chamada final retornará diretamente ao chamador original . A chamada final não precisa aparecer lexicalmente após todas as outras instruções no código-fonte; só é importante que a função de chamada retorne imediatamente após a chamada final, retornando o resultado da chamada final, se houver, uma vez que a função de chamada é ignorada quando a otimização é realizada.

Para chamadas de função não recursivas, geralmente é uma otimização que economiza pouco tempo e espaço, uma vez que não há tantas funções diferentes disponíveis para chamar. Ao lidar com funções recursivas ou mutuamente recursivas onde a recursão acontece por meio de chamadas finais, no entanto, o espaço de pilha e o número de retornos salvos podem crescer muito significativos, uma vez que uma função pode chamar a si mesma, direta ou indiretamente, criando um novo quadro de pilha de chamadas cada vez. A eliminação da chamada de cauda frequentemente reduz os requisitos de espaço de pilha assintótica de linear, ou O (n), para constante ou O (1). A eliminação da chamada final é, portanto, exigida pelas definições padrão de algumas linguagens de programação, como Scheme , e linguagens da família ML, entre outras. A definição da linguagem Scheme formaliza a noção intuitiva da posição da cauda exatamente, especificando quais formas sintáticas permitem ter resultados no contexto da cauda. As implementações que permitem um número ilimitado de tail calls estarem ativas ao mesmo tempo, graças à eliminação da tail call, também podem ser chamadas de 'tail recursive apropriadamente'.

Além de espaço e eficiência de execução, a eliminação da chamada final é importante no idioma de programação funcional conhecido como estilo de passagem de continuação (CPS), que de outra forma ficaria rapidamente sem espaço de pilha.

Forma sintática

Uma chamada final pode ser localizada um pouco antes do final sintático de uma função:

function foo(data) {
    a(data);
    return b(data);
}

Aqui, a(data)e b(data)são chamadas, mas bé a última coisa que o procedimento executa antes de retornar e, portanto, está na posição final. No entanto, nem todas as chamadas finais estão necessariamente localizadas na extremidade sintática de uma sub-rotina:

function bar(data) {
    if ( a(data) ) {
        return b(data);
    }
    return c(data);
}

Aqui, as chamadas para be cestão na posição final. Isso ocorre porque cada um deles está no final do ramo if respectivamente, embora o primeiro não esteja sintaticamente no final do barcorpo de.

Neste código:

function foo1(data) {
    return a(data) + 1;
}
function foo2(data) {
    var ret = a(data);
    return ret;
}
function foo3(data) {
    var ret = a(data);
    return (ret == 0) ? 1 : ret;
}

a chamada para a(data)está em posição de cauda na foo2, mas é não em posição de cauda seja em foo1ou em foo3, porque o controle deve retornar para o chamador para permitir que ele para inspecionar ou modificar o valor de retorno antes de devolvê-lo.

Programas de exemplo

O programa a seguir é um exemplo no Scheme :

;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
 (if (= n 0)
    1
    (* n (factorial (- n 1)))))

Isso não é escrito em um estilo recursivo da cauda, ​​porque a função de multiplicação ("*") está na posição da cauda. Isso pode ser comparado a:

;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
  (fact-iter 1 n))
(define (fact-iter product n)
  (if (= n 0)
      product
      (fact-iter (* product n)
                 (- n 1))))

Este programa pressupõe avaliação de pedido de aplicativo . O procedimento interno fact-iterchama a si mesmo por último no fluxo de controle. Isso permite que um intérprete ou compilador reorganize a execução, que normalmente seria assim:

  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

na variante mais eficiente , em termos de espaço e tempo:

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

Essa reorganização economiza espaço porque nenhum estado, exceto o endereço da função de chamada, precisa ser salvo, seja na pilha ou no heap, e o quadro da pilha de chamadas para fact-iteré reutilizado para o armazenamento de resultados intermediários. Isso também significa que o programador não precisa se preocupar em ficar sem espaço de pilha ou heap para recursões extremamente profundas. Em implementações típicas, a variante recursiva de cauda será substancialmente mais rápida do que a outra variante, mas apenas por um fator constante.

Alguns programadores que trabalham em linguagens funcionais reescreverão o código recursivo para ser recursivo na cauda, ​​para que possam tirar proveito desse recurso. Isso geralmente requer a adição de um argumento "acumulador" ( productno exemplo acima) à função. Em alguns casos (como listas de filtragem) e em algumas linguagens, a recursão de cauda completa pode exigir que uma função que era puramente funcional seja escrita de forma que modifique as referências armazenadas em outras variáveis.

Módulo de recursão da cauda contras

O módulo de recursão da cauda cons é uma generalização da otimização da recursão da cauda introduzida por David HD Warren no contexto da compilação do Prolog , visto como uma linguagem uma vez explicitamente definida . Foi descrito (embora não nomeado) por Daniel P. Friedman e David S. Wise em 1974 como uma técnica de compilação LISP . Como o nome sugere, ele se aplica quando a única operação restante a ser executada após uma chamada recursiva é acrescentar um valor conhecido antes de uma lista retornada por ele (ou realizar um número constante de operações simples de construção de dados, em geral). Esta chamada seria, portanto, uma chamada de cauda salva para (" módulo ") a referida operação contras . Mas prefixar um valor no início de uma lista na saída de uma chamada recursiva é o mesmo que anexar esse valor no final da lista crescente na entrada da chamada recursiva, construindo assim a lista como um efeito colateral , como se em um parâmetro de acumulador implícito. O seguinte fragmento do Prolog ilustra o conceito:

Código de exemplo

% Prolog, tail recursive modulo cons:
partition([], _, [], []).
partition([X|Xs], Pivot, [X|Rest], Bigs) :-
  X @< Pivot, !,
  partition(Xs, Pivot, Rest, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Rest]) :-
  partition(Xs, Pivot, Smalls, Rest).
-- In Haskell, guarded recursion:
partition :: Ord a => [a] -> a -> ([a],[a])
partition [] _ = ([],[])
partition (x:xs) p | x < p     = (x:a,b)
                   | otherwise = (a,x:b)
   where
      (a,b) = partition xs p
% Prolog, with explicit unifications:
%     non-tail recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs],
 (  X @< Pivot
 -> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest]
 ;  partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest]
 ).
% Prolog, with explicit unifications:
%     tail-recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs],
 (  X @< Pivot
 -> Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs)
 ;  Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest)
 ).

Assim, na tradução recursiva de cauda, ​​tal chamada é transformada em primeiro criar um novo nó de lista e definir seu firstcampo, e então fazer uma chamada final com o ponteiro para o restcampo do nó como argumento, para ser preenchido recursivamente. O mesmo efeito é obtido quando a recursão é protegida por um construtor de dados avaliado vagarosamente, o que é obtido automaticamente em linguagens de programação preguiçosas como Haskell.

Exemplo C

O fragmento a seguir define uma função recursiva em C que duplica uma lista vinculada:

typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list *head = NULL;

    if (ls != NULL) {
        list *p = duplicate(ls->next);
        head = malloc(sizeof *head);
        head->value = ls->value;
        head->next = p;
    }
    return head;
}
;; in Scheme,
(define (duplicate ls)
  (if (not (null? ls))
    (cons (car ls)
          (duplicate (cdr ls)))
    '()))
%% in Prolog,
duplicate([X|Xs],R):- 
  duplicate(Xs,Ys),
  R=[X|Ys].
duplicate([],[]).

Nessa forma, a função não é recursiva no final, porque o controle retorna ao chamador depois que a chamada recursiva duplica o restante da lista de entrada. Mesmo se fosse alocar o nó principal antes de duplicar o resto, ainda precisaria inserir o resultado da chamada recursiva no nextcampo após a chamada. Portanto, a função é quase recursiva na cauda. O método de Warren empurra a responsabilidade de preencher o nextcampo na própria chamada recursiva, que se torna chamada final:

typedef struct list {
    void *value;
    struct list *next;
} list;
void duplicate_aux(const list *ls, list *end);

list *duplicate(const list *ls)
{   
    list head;

    duplicate_aux(ls, &head);
    return head.next;
}

void duplicate_aux(const list *ls, list *end)
{
    if (ls != NULL) {
        end->next = malloc(sizeof *end);
        end->next->value = ls->value;
        duplicate_aux(ls->next, end->next);
    } else {
        end->next = NULL;
    }
}
;; in Scheme,
(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)))
%% in Prolog,
duplicate([X|Xs],R):-
   R=[X|Ys],
   duplicate(Xs,Ys).
duplicate([],[]).

(Um nó principal de sentinela é usado para simplificar o código.) O receptor agora é anexado ao final da lista crescente, em vez de o chamador anexar ao início da lista retornada. O trabalho agora é feito no caminho para a frente desde o início da lista, antes da chamada recursiva que então prossegue, em vez de retroceder a partir do final da lista, após a chamada recursiva ter retornado seu resultado. É, portanto, semelhante à técnica de acumulação de parâmetros, transformando um cálculo recursivo em iterativo.

Caracteristicamente para esta técnica, um quadro pai é criado na pilha de chamadas de execução, que o receptor recursivo final pode reutilizar como seu próprio quadro de chamada se a otimização da chamada final estiver presente.

A implementação recursiva de cauda agora pode ser convertida em uma implementação explicitamente iterativa, como um loop de acumulação :

typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list head, *end;
    end = &head;
    while (ls != NULL)
    {
        end->next        = malloc(sizeof *end);
        end->next->value = ls->value;
        ls = ls->next;
        end = end->next;
    }
    end->next = NULL;
    return head.next;
}
 ;; in Scheme,
 (define (duplicate ls)
   (let ((head (list 1)))
     (do ((end head (cdr end))
          (ls  ls   (cdr ls )))
         ((null? ls) (cdr head))
       (set-cdr! end (list (car ls))))))
%% in Prolog,
%% N/A

História

Em um artigo entregue na conferência ACM em Seattle em 1977, Guy L. Steele resumiu o debate sobre o GOTO e a programação estruturada , e observou que as chamadas de procedimento na posição final de um procedimento podem ser melhor tratadas como uma transferência direta de controle para o procedimento chamado, normalmente eliminando operações desnecessárias de manipulação de pilha. Uma vez que essas "chamadas finais" são muito comuns no Lisp , uma linguagem onde as chamadas de procedimento são onipresentes, essa forma de otimização reduz consideravelmente o custo de uma chamada de procedimento em comparação com outras implementações. Steele argumentou que chamadas de procedimento mal implementadas levaram a uma percepção artificial de que o GOTO era barato em comparação com a chamada de procedimento. Steele argumentou ainda que "em geral as chamadas de procedimento podem ser utilmente pensadas como instruções GOTO que também passam parâmetros e podem ser codificadas uniformemente como [código de máquina] instruções JUMP", com as instruções de manipulação da pilha de código de máquina "consideradas uma otimização (em vez de vice-versa!)". Steele citou evidências de que algoritmos numéricos bem otimizados em Lisp podiam executar mais rápido do que o código produzido por compiladores Fortran comerciais então disponíveis porque o custo de uma chamada de procedimento em Lisp era muito menor. No Scheme , um dialeto Lisp desenvolvido por Steele com Gerald Jay Sussman , a eliminação da chamada de cauda é garantida para ser implementada em qualquer intérprete.

Métodos de implementação

A recursão de cauda é importante para algumas linguagens de alto nível , especialmente linguagens funcionais e lógicas e membros da família Lisp . Nessas linguagens, a recursão de cauda é a forma mais comumente usada (e às vezes a única forma disponível) de implementar a iteração. A especificação de linguagem de Scheme requer que as chamadas finais sejam otimizadas para não aumentar a pilha. As chamadas finais podem ser feitas explicitamente em Perl , com uma variante da instrução "goto" que recebe um nome de função:goto &NAME;

No entanto, para implementações de linguagem que armazenam argumentos de função e variáveis ​​locais em uma pilha de chamadas (que é a implementação padrão para muitas línguas, pelo menos em sistemas com uma pilha de hardware , como o x86 ), implementando a otimização de chamada final generalizada (incluindo mútua recursão final) apresenta um problema: se o tamanho do registro de ativação do callee for diferente daquele do chamador, uma limpeza adicional ou redimensionamento do quadro de pilha pode ser necessária. Para esses casos, otimizar a recursão de cauda permanece trivial, mas a otimização geral de chamada de cauda pode ser mais difícil de implementar de forma eficiente.

Por exemplo, na máquina virtual Java (JVM), as chamadas recursivas finais podem ser eliminadas (pois isso reutiliza a pilha de chamadas existente), mas as chamadas finais gerais não podem ser (pois isso altera a pilha de chamadas). Como resultado, linguagens funcionais como Scala que têm como alvo a JVM podem implementar com eficiência a recursão de cauda direta, mas não a recursão de cauda mútua.

Os conjuntos de compiladores GCC , LLVM / Clang e Intel executam a otimização de chamada final para C e outras linguagens em níveis de otimização mais altos ou quando a -foptimize-sibling-callsopção é passada. Embora a sintaxe da linguagem fornecida possa não suportá-la explicitamente, o compilador pode fazer essa otimização sempre que puder determinar que os tipos de retorno para o chamador e o receptor são equivalentes e que os tipos de argumento passados ​​para ambas as funções são os mesmos ou exigem o mesma quantidade de espaço de armazenamento total na pilha de chamadas.

Vários métodos de implementação estão disponíveis.

Em montagem

As chamadas finais são frequentemente otimizadas por interpretadores e compiladores de programação funcional e linguagens de programação lógica para formas mais eficientes de iteração . Por exemplo, os programadores de Scheme comumente expressam loops while como chamadas para procedimentos na posição final e contam com o compilador ou interpretador Scheme para substituir as chamadas finais por instruções de salto mais eficientes .

Para compiladores que geram assembly diretamente, a eliminação da chamada final é fácil: é suficiente substituir um opcode de chamada por um jump, após fixar os parâmetros na pilha. Da perspectiva de um compilador, o primeiro exemplo acima é inicialmente traduzido para a linguagem de pseudo- assembly (na verdade, é um assembly x86 válido ):

 foo:
  call B
  call A
  ret

A eliminação da chamada de cauda substitui as duas últimas linhas por uma única instrução de salto:

 foo:
  call B
  jmp  A

Após a Aconclusão da sub-rotina , ela retornará diretamente ao endereço de retorno de foo, omitindo a retinstrução desnecessária .

Normalmente, as sub-rotinas sendo chamadas precisam ser fornecidas com parâmetros . O código gerado, portanto, precisa ter certeza de que o quadro de chamada para A está configurado corretamente antes de pular para a sub-rotina chamada de cauda. Por exemplo, em plataformas onde a pilha de chamadas não contém apenas o endereço de retorno , mas também os parâmetros da sub-rotina, o compilador pode precisar emitir instruções para ajustar a pilha de chamadas. Em tal plataforma, para o código:

function foo(data1, data2)
   B(data1)
   return A(data2)

(onde data1e data2são parâmetros) um compilador pode traduzir isso como:

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   push reg            ; put data2 on stack where A expects it
   call A              ; A uses data2
   pop                 ; remove data2 from stack.
   ret

Um otimizador de chamada final pode então alterar o código para:

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   mov  [sp+data1],reg ; put data2 where A expects it
   jmp  A              ; A uses data2 and returns immediately to caller.

Este código é mais eficiente em termos de velocidade de execução e uso de espaço de pilha.

Através de trampolim

Como muitos compiladores Scheme usam C como um código de destino intermediário, a recursão final deve ser codificada em C sem aumentar a pilha, mesmo se o compilador C não otimizar as chamadas finais. Muitas implementações conseguem isso usando um dispositivo conhecido como trampolim , um trecho de código que chama funções repetidamente. Todas as funções são acessadas através do trampolim. Quando uma função precisa chamar outra, em vez de chamá-la diretamente e retornar o resultado, ela retorna o endereço da função a ser chamada e os parâmetros de chamada de volta para o trampolim (de onde foi chamada), e o o trampolim se encarrega de chamar essa função a seguir com os parâmetros especificados. Isso garante que a pilha C não cresça e a iteração possa continuar indefinidamente.

É possível implementar trampolins usando funções de ordem superior em linguagens que os suportam, como Groovy , Visual Basic .NET e C # .

Usar um trampolim para todas as chamadas de função é um pouco mais caro do que a chamada de função C normal, então pelo menos um compilador Scheme, Chicken , usa uma técnica descrita pela primeira vez por Henry Baker a partir de uma sugestão não publicada de Andrew Appel , na qual chamadas C normais são usadas mas o tamanho da pilha é verificado antes de cada chamada. Quando a pilha atinge seu tamanho máximo permitido, os objetos na pilha são coletados como lixo usando o algoritmo de Cheney , movendo todos os dados ativos para um heap separado. Em seguida, a pilha é desenrolada ("removida") e o programa retoma do estado salvo antes da coleta de lixo. Baker diz que "o método de Appel evita fazer um grande número de pequenas quedas de trampolim pulando ocasionalmente do Empire State Building." A coleta de lixo garante que a recursão de cauda mútua possa continuar indefinidamente. No entanto, essa abordagem requer que nenhuma chamada de função C retorne, uma vez que não há garantia de que o frame da pilha do chamador ainda exista; portanto, envolve uma reescrita interna muito mais dramática do código do programa: estilo de passagem de continuação .

Relação com a declaração while

A recursão de cauda pode estar relacionada à instrução while , uma iteração explícita, por exemplo, transformando

procedure foo(x)
    if p(x)
        return bar(x)
    else
        return foo(baz(x))

em

procedure foo(x)
    while true
        if p(x)
            return bar(x)
        else
            x ← baz(x)

onde x pode ser uma tupla envolvendo mais de uma variável: nesse caso, deve-se tomar cuidado ao implementar a instrução de atribuição x ← baz ( x ) para que as dependências sejam respeitadas. Pode ser necessário introduzir variáveis ​​auxiliares ou usar uma construção de troca .

De forma geral,

procedure foo(x)
    if p(x)
        return bar(x)
    else if q(x)
        return baz(x)
    ...
    else if r(x)
        return foo(qux(x))
    ...
    else
        return foo(quux(x))

pode ser transformado em

procedure foo(x)
    while true
        if p(x)
            return bar(x)
        else if q(x)
            return baz(x)
        ...
        else if r(x)
            x ← qux(x)
        ...
        else
            x ← quux(x)

Por exemplo, este programa Python fornece uma definição recursiva sem cauda factdo fatorial:

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

Na verdade, n * fact(n - 1)encerra a chamada para fact. Mas pode ser transformado em uma definição recursiva de cauda adicionando um argumento achamado de acumulador .

Este programa Python fornece uma definição recursiva de cauda fact_iterdo fatorial:

def fact_iter(n, a):
    if n == 0:
        return a
    else:
        return fact_iter(n - 1, n * a)

def fact(n):
    return fact_iter(n, 1)

Este programa Python fornece uma definição iterativa fact_iterdo fatorial:

def fact_iter(n, a):
    while True:
        if n == 0:
            return a
        else:
            n, a = n - 1, n * a

def fact(n):
    return fact_iter(n, 1)

Por idioma

  • Haskell - Sim
  • Erlang - Sim
  • Common Lisp - Algumas implementações realizam otimização de chamada final durante a compilação, se otimizando para velocidade
  • JavaScript - motores compatíveis com ECMAScript 6.0 devem ter chamadas finais, que agora são implementadas no Safari / WebKit, mas rejeitadas pelo V8 e SpiderMonkey
  • Lua - a recursão da cauda é exigida pela definição da linguagem
  • OCaml - Sim
  • Python - as implementações Stock Python não realizam otimização de chamada final, embora um módulo de terceiros esteja disponível para fazer isso. Idioma inventor Guido van Rossum afirma que os rastreamentos de pilha são alteradas pela eliminação tail-call fazer a depuração mais difícil, e prefere que os programadores usam explícita iteração vez
  • Ferrugem - a otimização da chamada final pode ser feita em circunstâncias limitadas, mas não é garantida
  • Esquema - Requerido pela definição de linguagem
  • Raquete - Sim
  • Tcl - Desde Tcl 8.6, Tcl tem um comando tailcall
  • Kotlin - tem modificador tailrec para funções
  • Elixir - Elixir implementa otimização de chamada final Como fazem todos os idiomas atualmente direcionados ao BEAM VM.
  • Perl - explícito com uma variante da instrução "goto" que leva um nome de função:goto &NAME;
  • Scala - As funções recursivas de cauda são otimizadas automaticamente pelo compilador. Essas funções também podem ser marcadas opcionalmente com uma @tailrecanotação, o que torna um erro de compilação se a função não for recursiva na cauda
  • Objective-C - O compilador otimiza as chamadas finais quando a opção -O1 (ou superior) é especificada, mas é facilmente perturbada por chamadas adicionadas pela contagem automática de referência (ARC).
  • F # - F # implementa TCO por padrão, sempre que possível
  • Clojure - Clojure tem uma forma especial recorrente .
  • - Não

Veja também

Notas

Referências

Este artigo é baseado em material retirado do Dicionário On-line Gratuito de Computação anterior a 1 de novembro de 2008 e incorporado sob os termos de "relicenciamento" do GFDL , versão 1.3 ou posterior.