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

J’ai longuement réfléchi à cette question, mais je n’ai pas vraiment trouvé la réponse sur Google, mais 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? En outre, un outil linguistique dans un langage fonctionnel n’est-il pas plus lent dans certains langages de bas niveau tels que C?

Souvent, un compilateur fonctionne beaucoup avec les arbres. Le code source est analysé dans un arbre de syntaxe. Cet arbre peut ensuite être transformé en une autre arborescence avec des annotations de type pour effectuer une vérification de type. Vous pouvez maintenant convertir cet arbre en une arborescence contenant uniquement des éléments de langage de base (conversion de notations syntaxiques en sucre en une forme non gravée). Vous pouvez maintenant effectuer diverses optimisations qui sont essentiellement des transformations sur l’arbre. Après cela, vous créerez probablement un arbre sous une forme normale, puis effectuerez une itération sur cet arbre pour créer le code cible (assemblage).

Le langage fonctionnel possède des fonctionnalités telles que la correspondance de modèles et une bonne prise en charge de la récursivité efficace, ce qui facilite le travail sur les arbres. C’est pourquoi ils sont généralement considérés comme de bons langages pour écrire des compilateurs.

Un grand nombre de 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èle puissantes et concises.

Il est plus difficile d’append une correspondance de modèle à des langages impératifs, car la valeur évaluée ou extraite pour correspondre au modèle doit être exempte d’effet secondaire.

Un facteur important à prendre en compte est qu’une grande partie de tout projet de compilateur consiste à héberger automatiquement 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 linguistique, ils ont tendance à présenter de grandes fonctionnalités pour les problèmes de type compilateur.

Dans mon dernier travail de compilation, nous avons utilisé OCaml pour exactement 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é aussi bon.

Cela dit, les langages fonctionnels sont le meilleur outil pour résoudre tous les problèmes. Il s’ensuit logiquement qu’ils sont le meilleur outil pour résoudre ce problème particulier. QED.

/ moi: retourne à mes tâches Java un peu moins joyeusement …

Fondamentalement, un compilateur est une transformation d’un ensemble de codes à 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 langage conçu pour les langages fonctionnels. 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 lui sont spécialisés.

Voir également

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

Une des possibilités est qu’un compilateur ait tendance à faire très attention à toute une série de cas en coin. Il est souvent plus facile d’obtenir le code en utilisant des modèles de conception qui structurent l’implémentation d’une manière parallèle aux règles qu’elle implémente. Souvent, cela finit par être un concept déclaratif (appariement 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).

On dirait que tout le monde a manqué une autre raison importante. Il est assez facile d’écrire un langage spécifique au domaine (EDSL) pour les parsingurs qui ressemblent beaucoup au (E) BNF en code normal. Les parsingurs d’parsingurs tels que Parsec sont assez faciles à écrire dans des langages fonctionnels en utilisant des fonctions et une composition de fonctions plus élevées. Non seulement plus facile mais très élégant.

Fondamentalement, vous représentez les parsingurs 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 parsingurs primitifs en parsingurs plus compliqués et plus spécifiques pour votre grammaire.

Ce n’est pas la seule façon de faire des frameworks de cours.