Je réfléchis à cette question depuis très longtemps, mais je n'ai vraiment pas trouvé de réponse sur Google ainsi qu'une question similaire sur Stackoverflow. S'il y a un doublon, je suis désolé pour cela.
Beaucoup de gens semblent dire que l'écriture de compilateurs et d'autres outils linguistiques dans des langages fonctionnels tels que OCaml et Haskell est beaucoup plus efficace et plus facile que de les écrire dans des langages impératifs.
Est-ce vrai? Et si oui, pourquoi est-il si efficace et facile de les écrire dans des langages fonctionnels plutôt que dans un langage impératif, comme C? De plus, un outil de langage dans un langage fonctionnel n'est-il pas plus lent que dans un langage de bas niveau comme C?
Réponses:
Souvent, un compilateur travaille beaucoup avec des arbres. Le code source est analysé dans un arbre de syntaxe. Cet arbre pourrait ensuite être transformé en un autre arbre avec des annotations de type pour effectuer la vérification de type. Vous pouvez maintenant convertir cet arbre en un arbre contenant uniquement des éléments de langage de base (conversion de notations syntaxiques de type sucre en une forme non sucrée). Vous pouvez maintenant effectuer diverses optimisations qui sont essentiellement des transformations sur l'arborescence. Après cela, vous créeriez probablement une arborescence sous une forme normale, puis vous parcourriez cette arborescence pour créer le code cible (assembleur).
Les langages fonctionnels ont des fonctionnalités telles que la correspondance de motifs et une bonne prise en charge de la récursivité efficace, ce qui facilite le travail avec les arbres, c'est pourquoi ils sont généralement considérés comme de bons langages pour écrire des compilateurs.
la source
De nombreuses tâches du compilateur sont des correspondances de modèles sur des structures arborescentes.
OCaml et Haskell ont tous deux des capacités de correspondance de modèles puissantes et concises.
Il est plus difficile d'ajouter une correspondance de modèle aux langages impératifs, car quelle que soit la valeur évaluée ou extraite pour correspondre au modèle doit être sans effet secondaire.
la source
Un facteur important à considérer est qu'une grande partie de tout projet de compilateur est quand vous pouvez auto-héberger le compilateur et «manger votre propre nourriture pour chien». Pour cette raison, lorsque vous regardez des langages comme OCaml où ils sont conçus pour la recherche de langage, ils ont tendance à avoir des fonctionnalités intéressantes pour les problèmes de type compilateur.
Dans mon dernier travail de compilateur, nous avons utilisé OCaml exactement pour cette raison lors de la manipulation du code C, c'était juste le meilleur outil pour la tâche. Si les gens de l'INRIA avaient construit OCaml avec des priorités différentes, cela n'aurait peut-être pas été une si bonne solution.
Cela dit, les langages fonctionnels sont le meilleur outil pour résoudre n'importe quel problème, il s'ensuit donc logiquement qu'ils sont le meilleur outil pour résoudre ce problème particulier. QED.
/ me: revient à mes tâches Java un peu moins joyeusement ...
la source
Fondamentalement, un compilateur est une transformation d'un ensemble de code à un autre - de la source à l'IR, de l'IR à l'IR optimisé, de l'IR à l'assemblage, etc. C'est précisément le genre de chose pour laquelle les langages fonctionnels sont conçus - une fonction pure est juste une transformation d'une chose à une autre. Les fonctions impératives n'ont pas cette qualité. Bien que vous puissiez écrire ce type de code dans un langage impératif, les langages fonctionnels sont spécialisés pour cela.
la source
Voir également
Modèle de conception F #
FP regroupe les choses «par opération», alors que OO regroupe les choses «par type» et «par opération» est plus naturel pour un compilateur / interpréteur.
la source
Une possibilité est qu'un compilateur a tendance à avoir à traiter très soigneusement toute une série de cas secondaires. Obtenir le bon code est souvent facilité par l'utilisation de modèles de conception qui structurent l'implémentation de manière à mettre en parallèle les règles qu'elle implémente. Souvent, cela finit par être une conception déclarative (correspondance de modèles, «où») plutôt qu'impératif (séquençage, «quand») et donc plus facile à implémenter dans un langage déclaratif (et la plupart d'entre eux sont fonctionnels).
la source
On dirait que tout le monde a manqué une autre raison importante. Il est assez facile d'écrire un langage spécifique au domaine intégré (EDSL) pour les analyseurs qui ressemblent beaucoup à (E) BNF en code normal. Les combinateurs d'analyseurs comme Parsec sont assez faciles à écrire dans des langages fonctionnels en utilisant des fonctions d'ordre supérieur et une composition de fonctions. Non seulement plus facile mais très élégant.
Fondamentalement, vous représentez les analyseurs génériques les plus simples comme de simples fonctions et vous avez des opérations spéciales (généralement des fonctions d'ordre supérieur) qui vous permettent de composer ces analyseurs primitifs en analyseurs plus complexes et plus spécifiques pour votre grammaire.
Ce n'est bien sûr pas la seule façon d'analyser les frameworks.
la source