Para cada imperativo função, existe um funcional contrapartida com desempenho idêntico, ou mesmo de instruções?

Question

Atualmente, eu ainda não aprendi sobre uma linguagem funcional que pode atingir o mesmo desempenho como C/C++.E eu aprendi que algumas linguagens que favorecem a programação funcional para programação imperativa, tais como Scala e Ferrugem, use imperativo maneiras de implementar as suas funções de biblioteca para uma melhor eficiência.

Então, aqui vem a minha pergunta, hoje comptuters que executar imperativo instruções, esta é uma limitação do compilador ou programação funcional em si?Para cada imperativo função, sem efeitos colaterais, quer numa língua sem GC, tais como C/C++/Ferrugem/assembly ou um com GC, tais como Java, existe uma pura funcional contrapartida em Haskell, Scala, etc.que pode ser compilado para ser executado com desempenho idêntico, no tempo e no espaço (não apenas assintótica mas exatamente o mesmo) ou, até mesmo, para as mesmas instruções, com uma ótima funcional compilador que utiliza os mais modernos e ainda não descobertas de técnicas de otimização, tais como recursão, preguiça, análise estática, verificação formal, e assim por diante, que eu não sei?

Estou ciente de que a equivalência entre λ-computável e de Turing computáveis, mas, mas eu não conseguia encontrar uma resposta para esta pergunta on-line.Se há, por favor, compartilhe um compilador exemplo, ou uma prova.Se não, por favor, explique por que e mostrar um contra-exemplo.Ou este é um não-trivial questão em aberto?

---

Complementar edições, como sugerido por Andrej Bauer:

Para ser mais específico, aqui são 2 exemplos que levou a pensar sobre esta questão.

Por exemplo, recursão e acumuladores podem melhorar o desempenho de algumas funções recursivas para ser idêntico a um imperativo usando a implementação for.Em alguns casos, eles podem até ter as mesmas instruções.

Outro exemplo é sobre a preguiça em Haskell.A preguiça pode ajudar a evitar cópias desnecessárias de estruturas de dados e melhorar o desempenho melhor.No entanto, a preguiça deixa embalagens, tampas, etc.em tempo de execução e ainda não pode fazer o programa como rápido como um imperativo de implementação, onde não existem tais coisas.Então, eu estou querendo saber se tais coisas podem ser estaticamente removido antes de tempo de execução durante a compilação.

Complementar edições, como sugerido por Nearoo:

A questão também pode ser declarado desta forma:existe uma linguagem que suporta ambos os puros de programação funcional e programação imperativa, emparelhado com um compilador otimizado, no qual cada função, sem efeitos colaterais implementado imperativa pode ser substituído com um implementadas puramente funcional, sem nenhum custo de desempenho ou até mesmo compilado para as mesmas instruções?

Answer 1

1. O desempenho não é uma propriedade da linguagem, é uma propriedade de programas específicos dentro de uma língua.Alguns idiomas podem ser muito rápido em algumas coisas e lento em outros.

   Por exemplo, o Chez-Esquema pode, às vezes, encontrar um desempenho comparável ao de C, não porque a linguagem é mais eficiente, mas porque defensiva práticas que os programadores utilizam frequentemente em C são menos necessárias no esquema.

   Da mesma forma, há momentos em Haskell pode fazer muito eficiente de paralelismo ou de simultaneidade, não porque ele é mais rápido do que C, mas porque a imutabilidade garantias de idioma permitem o programador a evitar coisas como bloqueios e outras técnicas de sincronização.

   E, o desempenho varia de implementação para implementação.Eu posso mão-rolo C intérprete, mas ele com certeza não vai ser rápido.C não é rápido, o GCC e o Bumbum são.

2. O que é considerado um "funcional" da linguagem?Toda prática de linguagem funcional tem algumas facilidades para mutável estado:OCaml, Haskell, Scala, Lisp, Scheme, etc.Recursão dá algo mais ou menos equivalente a mutação dentro de um ciclo.Mas quando isso não é suficiente, uma linguagem funcional dão ao programador acesso ao mutável estado.No caso do Haskell, esta é controlada pelo tipo de sistema, de modo que nunca haja implícito mutável estado, mas a mutação é muito permitido e até incentivado em Haskell.Olhar Haskell código, e você vai ver o IO mônada em todos os lugares.Da mesma forma, ML línguas distinguir entre tipos de T e ref T, então você pode dizer pela tipos se uma variável é mutável ou não.

3. Não há nenhum "ideal" de compilador, graças ao Arroz teorema.Todos os compiladores, imperativo, funcional, são a "melhor esforço:" o uso conservador de aproximações para otimizar o código.

   Se tivemos um ótimo compilador, a resposta seria que cada programa sempre correu usando o mais eficiente instruções possível, e não importa o idioma que você codificado o seu problema.A seqüência ideal de instruções de computação de um problema não depende do idioma de origem.Mas, se tivéssemos, então este compilador iria compilar todos os não-travar o programa em while(0), o que significa que pode detectar o não-interrompendo programas, o que é impossível.

4. Para Máquinas de Turing e o cálculo lambda, eu acho que é bastante trivial implementar um cálculo lambda de intérprete para Máquinas de Turing que é assintoticamente equivalente a um universal de Turing-máquina.Grande-O a complexidade não é o que as pessoas querem dizer quando dizem "Funcional línguas são lentas".Geralmente eles estão falando sobre a constante de sobrecarga, que é muito diferente.Não temos como boas maneiras matematicamente este modelo, de modo que geralmente acabava a utilização de experiências para medida precisa de desempenho.