São programas em linguagens funcionais mais propensas a ter estouros de pilha?

Question

Eu estou começando a aprender ocaml, e estou realmente apreciando o poder de recursão na língua. No entanto, uma coisa que eu estou preocupado é estouros de pilha.

Se ocaml usa a pilha de chamadas de função, não ele eventualmente estourar a pilha? Por exemplo, se eu tenho a seguinte função:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

ele deve, eventualmente, causar uma pilha de estouro. Se eu fosse fazer a coisa equivalente em C ++ (usando recursão), eu sei que iria transbordar.

Então, minha pergunta é, existe construído em salvaguardas para evitar linguagens funcionais de transbordar a pilha? Se não, eles não são menos úteis como esta, uma vez que o anterior algoritmo de soma, escrito em um estilo processual com um loop for, poderia lidar com qualquer número (des-respeito integer overflow)?

Answer 1

Todos (implementações decentes de ;-) linguagens funcionais otimizar recursão de cauda, ??mas isso não é o que você está fazendo aqui, uma vez que a chamada recursiva não é a última operação (ele precisa ser seguido pela adição).

Assim, um logo aprende a usar uma função auxiliar que é recursiva cauda (e leva a corrente total a ser acumulado como um argumento) para que o otimizador pode fazer o seu trabalho, ou seja, líquido de possível sintaxe O'Caml em que eu' m enferrujado:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

Aqui, a soma acontece como um argumento para a chamada recursiva, ou seja, antes do próprio recursão, e assim otimização cauda pode chutar em (porque a recursividade é a última coisa que precisa acontecer!).

Answer 2

As linguagens funcionais normalmente têm uma pilha muito maior. Por exemplo, eu escrevi uma função especificamente para limites de pilha de teste em OCaml, e chegou a mais de 10.000 chamadas antes que ele vomitou. No entanto, seu ponto é válido. Stack-transborda ainda são algo que você precisa para estar atento em linguagens funcionais.

Uma das estratégias que as linguagens funcionais utilizar para mitigar sua dependência de recursividade é o uso de otimização de chamada . Se a chamada para a próxima recursão da função atual é a última instrução na função, a chamada atual pode ser descartado da pilha e a nova chamada instanciado em seu lugar. As instruções de montagem que são gerados será basicamente o mesmo que aqueles para while-loops em estilo imperativo.

A sua função não é chamada de laço otimizável porque a recursividade não é o último passo. Ele precisa voltar em primeiro lugar e, em seguida, ele pode adicionar x para o resultado. Normalmente, isso é fácil de se locomover, você acabou de criar uma função auxiliar que passa um acumulador, juntamente com os outros parâmetros

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;

Answer 3

Algumas linguagens funcionais, tais como Esquema especificar que cauda recursão deve ser optimizado para ser equivalente a iteração; portanto, uma função cauda-recursivo no Esquema nunca vai resultar em um estouro de pilha, não importa quantas vezes ele recurses (presumindo, é claro, que ele não também recurse ou se envolver em recursão mútua em outros lugares além do fim).

A maioria das outras linguagens funcionais não necessitam de cauda recursão a ser implementado de forma eficiente; alguns optam por fazê-lo, outros não, mas é relativamente fácil de implementar, então eu esperaria que a maioria das implementações de fazê-lo.

Answer 4

É certamente fácil para novatos para escrever recursions profundas que sopram a pilha. Objective Caml é incomum em que as funções List biblioteca não são pilha-seguro para longas listas . Aplicações como Unison realmente substituiu a biblioteca List padrão Caml com uma pilha-safe versão. A maioria das outras implementações de fazer um trabalho melhor com a pilha. (Disclaimer:. Minhas informações descreve Caml Objetivo 3,08; a versão atual, 3.11, pode ser melhor)

ML padrão de New Jersey é incomum em que ele não usa uma pilha, para que o seu profundo recursions Continue indo até você ficar sem pilha. É descrito no excelente livro de Andrew Appel Compilando com Continuations .

Eu não acho que há um problema sério aqui; é mais um "ponto de consciência" que se você estiver indo para ser escrito um monte de código recursiva, o que você está mais propenso a fazer em uma linguagem funcional, você tem que estar ciente de chamadas não-cauda e de tamanho pilha como em comparação com o tamanho dos dados que você estará processando.

Answer 5

Isto é complicado - em princípio, sim, mas os compiladores e tempos de execução para linguagens funcionais representam o maior grau de recursão em linguagens funcionais. O mais básico é que a maioria dos tempos de execução de linguagem funcional solicitar uma pilha muito maior do que os programas iterativos normais usaria. Mas, além de que um compilador de linguagem funcional é muito mais capaz de transformar código recursiva em uma função não recursiva para as restrições mais rigorosas muito da linguagem.