Por que escrever um compilador em uma linguagem funcional é mais fácil? [fechadas]

88

Tenho pensado nessa pergunta há muito tempo, mas realmente não consegui encontrar a resposta no Google, bem como uma pergunta semelhante no Stackoverflow. Se houver uma duplicata, sinto muito por isso.

Muitas pessoas parecem dizer que escrever compiladores e outras ferramentas de linguagem em linguagens funcionais como OCaml e Haskell é muito mais eficiente e fácil do que escrevê-los em linguagens imperativas.

Isso é verdade? E em caso afirmativo - por que é tão eficiente e fácil escrevê-los em linguagens funcionais em vez de em uma linguagem imperativa, como C? Além disso - uma ferramenta de linguagem em uma linguagem funcional não é mais lenta do que em alguma linguagem de baixo nível como C?

compiler-construction haskell ocaml functional-programming wvd
fonte
5
Eu não diria que é mais fácil. Mas a natureza funcional das tarefas de compilação, como análise, provavelmente se prestam muito naturalmente à programação funcional. Linguagens funcionais como OCaml podem ser extremamente rápidas, rivalizando com a velocidade de C.
Robert Harvey
17
Pessoal, isso é realmente argumentativo? Certamente alguém tem algum insight. Eu gostaria de me conhecer.
Robert Harvey
Acho que deve haver pelo menos algumas boas razões para usar uma linguagem funcional em vez de uma imperativa. Eu encontrei um artigo que basicamente dizia que as linguagens funcionais não têm efeitos colaterais e tal. Mas não estava nada claro. No entanto, se for argumentativo, talvez seja melhor encerrá-lo ou reformular a questão.
wvd
12
É realmente argumentativo reconhecer que alguns nichos são mais adequados a um determinado estilo de linguagem? "Por que C é melhor do que Javascript para escrever drivers de dispositivo" não seria controverso, eu acho ...
CA McCann
1
Achei que seria o contrário. Estou lendo "compilador super minúsculo" e ele usa mutação variável em todo o lugar.
Rolf

Respostas:

101

Freqüentemente, um compilador trabalha muito com árvores. O código-fonte é analisado em uma árvore de sintaxe. Essa árvore pode então ser transformada em outra árvore com anotações de tipo para realizar a verificação de tipo. Agora você pode converter essa árvore em uma árvore contendo apenas elementos básicos da linguagem (convertendo notações sintáticas semelhantes a açúcar em uma forma não açúcar). Agora você pode realizar várias otimizações que são basicamente transformações na árvore. Depois disso, você provavelmente criaria uma árvore em alguma forma normal e, em seguida, iteraria nessa árvore para criar o código de destino (montagem).

A linguagem funcional tem recursos como correspondência de padrões e bom suporte para recursão eficiente, o que facilita o trabalho com árvores, por isso são geralmente consideradas boas linguagens para escrever compiladores.

sepp2k
fonte
A resposta mais completa até agora, marcarei como a resposta aceita, no entanto, acho que a resposta de Pete Kirkham também é boa.
wvd
1
E quanto a "comprovar a correção", uma vez que a correção de um compilador é um atributo importante, eu sempre ouvi que os fãs de linguagens funcionais incorporam uma "prova" de correção em seu fluxo de trabalho de alguma forma. Não tenho ideia do que isso realmente significa em termos práticos, mas como a confiabilidade do compilador é importante, parece valer a pena.
Warren P
3
@WarrenP: O conceito de "código de prova" vem de linguagens funcionais estaticamente tipadas. A ideia é que você use o sistema de tipos de forma que uma função possa apenas verificar se está correta, então o fato de o código compilar é a prova de que está correto. É claro que isso não é totalmente possível, ao mesmo tempo que se mantém o idioma completo e a verificação de tipos decidível. Porém, quanto mais forte o sistema de tipos, mais perto você pode chegar desse objetivo.
sepp2k
3
A razão pela qual esse conceito é popular principalmente na comunidade funcional é que em linguagens com estado mutável, você também teria que codificar informações sobre quando e onde a mudança de estado ocorre nos tipos. Em linguagens em que você sabe que o resultado de uma função depende apenas de seus argumentos, é muito mais fácil codificar uma prova nos tipos (também é muito mais fácil provar manualmente a correção do código porque você não precisa considerar qual estado global é possível e como isso afetará o comportamento da função). No entanto, nada disso está especificamente relacionado a compiladores.
sepp2k
3
A característica mais importante é a correspondência de padrões, na minha opinião. Otimizar uma árvore de sintaxe abstrata com correspondência de padrões é estupidamente fácil. Fazer isso sem a correspondência de padrões costuma ser frustrantemente difícil.
Bob Aman
38

Muitas tarefas do compilador são correspondência de padrões em estruturas de árvore.

OCaml e Haskell têm recursos de correspondência de padrões poderosos e concisos.

É mais difícil adicionar correspondência de padrões a linguagens imperativas, pois qualquer valor que esteja sendo avaliado ou extraído para corresponder ao padrão deve estar livre de efeitos colaterais.

Pete Kirkham
fonte
Parece uma resposta razoável, mas essa é a única coisa? por exemplo, coisas como recursão da cauda também desempenham um papel?
wvd
Isso parece indicar que é mais uma questão do sistema de tipos do que do modelo de execução real. Algo baseado em programação imperativa com valores imutáveis ​​sobre tipos estruturais pode ser bom.
Donal Fellows
@wvd: A otimização da recursão final é um detalhe de implementação, não um recurso de linguagem como tal, que torna as funções recursivas lineares equivalentes a um loop iterativo. Uma função recursiva para percorrer uma lista encadeada em C se beneficiaria disso tanto quanto a recorrência em uma lista em Scheme.
CA McCann
@wvd gcc C tem eliminação de chamada final, assim como outras linguagens de estado mutáveis
Pete Kirkham
3
@camccann: Se o padrão de linguagem garante tco (ou pelo menos garante que funções recursivas de uma certa forma nunca causarão um estouro de pilha ou um crescimento linear do consumo de memória), eu consideraria isso um recurso de linguagem. Se o padrão não garante isso, mas o compilador o faz mesmo assim, é um recurso do compilador.
sepp2k
15

Um fator importante a considerar é que uma grande parte de qualquer projeto de compilador é quando você pode hospedar o compilador e "comer sua própria comida de cachorro". Por esse motivo, quando você olha para linguagens como OCaml, onde são projetadas para pesquisa de linguagem, elas tendem a ter ótimos recursos para problemas do tipo compilador.

Em meu último trabalho do tipo compilador, usamos OCaml exatamente por esse motivo enquanto manipulávamos o código C, era a melhor ferramenta para a tarefa. Se o pessoal do INRIA tivesse construído o OCaml com prioridades diferentes, talvez não fosse uma escolha tão boa.

Dito isso, as linguagens funcionais são a melhor ferramenta para resolver qualquer problema, logo, segue-se logicamente que são a melhor ferramenta para resolver esse problema específico. QED.

/ me: retorna às minhas tarefas Java com um pouco menos de alegria ...

Ukko
fonte
4
-1 para "as linguagens funcionais são a melhor ferramenta para resolver qualquer problema." Se isso fosse verdade, todos nós os usaríamos em todos os lugares. ;)
Andrei Krotkov
15
@Andrei Krotkov: A palavra do dia de hoje é fa · ce · tious Pronúncia: \ fə-ˈsē-shəs \ Função: adjetivo Etimologia: francês médio facetieux, de facetie jest, do latim facetia Data: 1599 1: brincando ou gracejando muitas vezes de forma inadequada : waggish <apenas sendo jocoso> 2: destinado a ser bem-humorado ou engraçado: não sério <a observação jocosa> sinônimos ver espirituoso Além de não entender a piada, sua lógica ainda é falha. Você está presumindo que todas as pessoas são atores racionais e, infelizmente, não é uma suposição justa.
Ukko
5
Acho que não entendi a piada, pois conheço pessoas na vida real que diriam exatamente a coisa certa, exceto totalmente a sério. A lei de Poe, eu acho. tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw
Andrei Krotkov
13
@Andrei: Usando seu argumentum ad populum : "Se a razão é melhor do que a ignorância emocional, todos nós a usaríamos em todos os lugares."
Tim Schaeffer
9

Basicamente, um compilador é uma transformação de um conjunto de código para outro - da fonte para IR, de IR para IR otimizado, de IR para montagem, etc. Este é precisamente o tipo de coisa para a qual as linguagens funcionais são projetadas - uma função pura é apenas uma transformação de uma coisa para outra. As funções imperativas não têm essa qualidade. Embora você possa escrever esse tipo de código em uma linguagem imperativa, as linguagens funcionais são especializadas para isso.

Mandril
fonte
6

Veja também

Padrão de design F #

FP agrupa coisas 'por operação', enquanto OO agrupa coisas 'por tipo', e 'por operação' é mais natural para um compilador / interpretador.

Brian
fonte
3
Isso se relaciona com o que é chamado, em alguns círculos da Teoria da Linguagem de Programação, de "problema de expressão". Por exemplo, veja esta pergunta , na qual demonstro alguns códigos Haskell horríveis que fazem as coisas da maneira de "tipos extensíveis". Ao contrário, forçar uma linguagem OOP no estilo de "operações extensíveis" tende a motivar o padrão de visitante.
CA McCann
6

Uma possibilidade é que um compilador tende a ter que lidar com muito cuidado com uma série de casos esquivos. Acertar o código geralmente fica mais fácil com o uso de padrões de design que estruturam a implementação de uma forma paralela às regras que implementa. Freqüentemente, isso acaba sendo um design declarativo (correspondência de padrões, "onde") em vez de imperativo (sequenciamento, "quando") e, portanto, mais fácil de implementar em uma linguagem declarativa (e a maioria deles são funcionais).

BCS
fonte
4

Parece que todos perderam outro motivo importante. É muito fácil escrever uma linguagem específica de domínio incorporada (EDSL) para analisadores que se parecem muito com (E) BNF em código normal. Os combinadores de analisadores como Parsec são muito fáceis de escrever em linguagens funcionais usando funções de ordem superior e composição de funções. Não só mais fácil, mas muito elegante.

Basicamente, você representa os analisadores genéricos mais simples como funções e tem operações especiais (normalmente funções de ordem superior) que permitem compor esses analisadores primitivos em analisadores mais complicados e específicos para sua gramática.

Esta não é a única maneira de fazer frameworks parer, é claro.

snk_kid
fonte