A definição de um combinador Y em F # é
let rec y f x = f (y f) x
f espera ter como primeiro argumento alguma continuação para os subproblemas recursivos. Usando o yf como uma continuação, vemos que f será aplicado a chamadas sucessivas à medida que pudermos desenvolver
let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...
O problema é que, a priori, esse esquema impede o uso de qualquer otimização de chamada de cauda: de fato, pode haver alguma operação pendente nos f's, nesse caso, não podemos simplesmente alterar o quadro de pilha local associado a f.
Tão :
- por um lado, o uso do combinador Y requer uma continuação explícita diferente da própria função.
- por outro lado, para aplicar o TCO, gostaríamos de não ter nenhuma operação pendente em f e apenas chamar f em si.
Você sabe de que maneira esses dois poderiam ser reconciliados? Como um Y com truque de acumulador ou um Y com truque de CPS? Ou um argumento provando que não há como isso ser feito?
f#
recursion
tail-call
continuation
Nicolas
fonte
fonte
f
. Podemos ver quey
poderia chamarf
com um thunk(y f)
, mas, como você diz,f
pode ter alguma operação pendente. Eu acho que seria interessante saber se existe um combinador separado que seja mais amigável ao tailcall. Gostaria de saber se esta pergunta seria melhor atenção no site CS Stackexchange?Respostas:
Não, e por boas razões, IMHO.
O combinador Y é uma construção teórica e é necessária apenas para completar o cálculo do lambda (lembre-se, não há loops no cálculo do lambda, nem os lambdas têm nomes que poderíamos usar para recursão).
Como tal, o combinador Y é verdadeiramente fascinante.
Mas : na verdade, ninguém usa o combinador Y para recursão real! (Exceto talvez por diversão, para mostrar que realmente funciona.)
A otimização de chamada de cauda, OTOH, é, como o nome diz, uma otimização. Isso não acrescenta nada à expressividade de uma linguagem, é apenas por considerações práticas, como espaço na pilha e desempenho do código recursivo, que nos preocupamos com isso.
Portanto, sua pergunta é: Existe suporte de hardware para redução beta? (Redução beta é como as expressões lambda são reduzidas, você sabe.) Mas nenhuma linguagem funcional (até onde eu saiba) compila seu código-fonte para uma representação de expressões lambda que serão reduzidas beta em tempo de execução.
fonte
Não tenho certeza absoluta sobre essa resposta, mas é a melhor que pude apresentar.
O combinador y é inerentemente preguiçoso, em idiomas estritos a preguiça deve ser adicionada manualmente através de lambdas extras.
Sua definição parece exigir preguiça para terminar, ou o
(y f)
argumento nunca terminaria de avaliar e teria que avaliar se af
usava ou não . O TOC em um contexto lento é mais complicado e, além disso, o resultado(y f)
é uma composição repetida de funções sem aplicação com ox
. Não tenho certeza se isso precisa levar O (n) memória onde n é a profundidade da recursão, mas duvido que você possa obter o mesmo tipo de sumário possível com algo como (alternar para Haskell porque eu realmente não sei F #)Se você ainda não está ciente disso, a diferença entre
foldl
efoldl'
em Haskell pode lançar alguma luz sobre a situação.foldl
é escrito como seria feito em um idioma ansioso. Mas, em vez de ser um TOC, é realmente pior do quefoldr
porque o acusador armazena um thunk potencialmente enorme que não pode ser avaliado parcialmente. (Isso está relacionado ao motivo pelo qual foldl e foldl 'não funcionam em listas infinitas.) Assim, nas versões mais recentes do Haskell,foldl'
foi adicionado o que força a avaliação do acumulador cada vez que a função se repete para garantir que não seja criado nenhum thunk enorme. Tenho certeza que http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 pode explicar isso melhor do que eu.fonte