Pourquoi l'écriture d'un compilateur dans un langage fonctionnel est-elle plus facile?

Question

J'ai pensé à cette question, très long, mais ne pouvais vraiment pas trouver la réponse sur Google ainsi une question similaire sur Stackoverflow. Si 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 de langages fonctionnels langages comme OCaml et Haskell est beaucoup plus efficace et plus facile ensuite de les écrire dans des langages impératifs.

Est-ce vrai? Et si oui, pourquoi est-il si efficace et facile de l'écrire dans les langages fonctionnels plutôt que dans un langage impératif, comme C? Aussi, n'est-ce pas un outil de langue dans un langage fonctionnel plus lent que dans certains langage de bas niveau comme le C?

Answer 1

Souvent, un compilateur travaille beaucoup avec les arbres. Le code source est analysé dans un arbre de syntaxe. Cet arbre peut alors être transformé en un arbre avec des annotations de type pour effectuer une vérification de type. Maintenant, vous pouvez convertir l'arbre en arbre comprenant uniquement l'un des principaux éléments de langage (la conversion de sucre syntaxique comme des notations dans une sans sucre). Maintenant, vous pouvez effectuer diverses optimisations qui sont essentiellement des transformations sur l'arbre. Après cela, vous serait probablement de créer un arbre dans certaines forme normale et de parcourir l'arbre pour créer la cible (l'assemblée) de code.

Fonctionnelle de la langue ont des caractéristiques comme le pattern matching et une bonne prise en charge efficace de la récursivité, qui facilitent le travail avec les arbres, c'est pourquoi ils sont généralement considérés comme de bons langues pour l'écriture de compilateurs.

Answer 2

Un grand nombre de tâches du compilateur sont des correspondances de modèles sur des structures arborescentes.

OCaml et Haskell offrent des capacités de concordance de motifs puissantes et concises.

Il est plus difficile d'ajouter une correspondance de modèle aux langages impératifs, car toute valeur évaluée ou extraite pour correspondre au modèle doit être exempte d'effets secondaires.

Answer 3

Un facteur important à considérer est que une grande partie de n'importe quel compilateur projet, c'est quand vous pouvez vous 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 en langues, ils ont tendance à avoir beaucoup de fonctionnalités pour le compilateur type de problèmes.

Dans mon dernier compilateur-esque de travail, nous avons utilisé OCaml exactement pour cette raison lors de la manipulation de code C, il a été tout simplement le meilleur outil autour de la tâche. Si les gens à l'INRIA avait construit OCaml avec des priorités différentes, il peut ne pas avoir été un bon ajustement.

Cela dit, les langages fonctionnels sont le meilleur outil pour résoudre un problème, alors il s'ensuit logiquement qu'ils sont le meilleur outil pour résoudre ce problème particulier. CQFD.

/me: les analyses de retour à mon Java tâches un peu moins dans la joie...

Answer 4

Fondamentalement, un compilateur est une transformation d'un ensemble de code en un autre: de la source à l'infrarouge, de l'infrarouge à l'infrarouge optimisé, de l'infrarouge à l'assemblage, etc. C'est précisément le type d'objet que les langages fonctionnels sont conçus: une fonction pure est juste une transformation d'une chose à l'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.

Answer 5

Voir également

http://stackoverflow.com/questions/1936471/f-design-pattern

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ète.