Au dernier semestre de l'université, j'ai choisi le cours de compilateur CS444 . Là, chaque groupe de 1 à 3 personnes devait écrire un compilateur à partir d'un sous-ensemble important de Java en x86. Langue pour choisir un groupe. C'était une occasion rare de comparer les implémentations de grands programmes de la même fonctionnalité, écrits par des programmeurs très compétents dans différentes langues, et de comparer la différence de conception et de choix de langue. Une telle comparaison a donné lieu à de nombreuses réflexions intéressantes. Une telle comparaison contrôlée des langues est rarement observée. Ce n'est pas parfait, mais bien mieux que la plupart des histoires subjectives sur lesquelles les opinions des gens sur les langages de programmation sont basées.

Nous avons fait notre compilateur Rust et je l'ai d'abord comparé avec le projet de l'équipe Haskell. Je m'attendais à ce que leur programme soit beaucoup plus court, mais il s'est avéré être de la même taille ou plus grand. Il en va de même pour OCaml. Ensuite, je l'ai comparé au compilateur C ++, et là, on s'attendait à ce que le compilateur soit environ 30% plus grand, principalement en raison des en-têtes, du manque de types de somme et de la correspondance des modèles. La comparaison suivante était avec ma petite amie, qui a fait le compilateur seule en Python et a utilisé moins de la moitié du code par rapport à nous, en raison de la puissance de la métaprogrammation et des types dynamiques. Un autre ami avait un programme Scala plus petit. Ce qui m'a le plus surpris, c'est la comparaison avec une autre équipe qui utilisait également Rust, mais ils se sont avérés avoir trois fois plus de code en raison de différentes décisions de conception. En fin de compte, la plus grande différence dans la quantité de code était dans la même langue!

J'expliquerai pourquoi je considère cela comme une bonne comparaison, je donnerai des informations sur chaque projet et expliquerai les raisons des différences de taille du compilateur. Je tirerai également des conclusions de chaque comparaison. N'hésitez pas à utiliser ces liens pour accéder à la section qui vous intéresse:

Table des matières

Pourquoi est-ce que je trouve cela significatif
Rouille (base de comparaison)
Haskell : tailles 1.0-1.6, selon la façon dont vous comptez, pour des raisons intéressantes
C ++ : 1,4 tailles pour des raisons évidentes
Python : taille 0,5 grâce à une métaprogrammation sophistiquée!
Rouille (un autre groupe) : trois fois la taille grâce à un design différent!
Scala : 0,7 tailles
OCaml : taille 1.0-1.6 selon la façon dont vous comptez, similaire à Haskell

Pourquoi est-ce que je trouve cela significatif

Avant de dire que la quantité de code (j'ai comparé les chaînes et les octets) est une métrique terrible, je tiens à noter que dans ce cas, elle peut fournir une bonne compréhension. Au moins, c'est l'exemple le plus bien contrôlé où différentes équipes écrivent le même grand programme que j'ai entendu ou lu.

Personne (y compris moi) ne savait que je mesurerais ce paramètre, donc personne n'a essayé de jouer des métriques, tout le monde a juste essayé de terminer le projet rapidement et correctement.
Tous (à l'exception du projet Python, dont je parlerai plus tard) ont implémenté le programme dans le seul but de réussir la même suite de tests automatisés dans le même laps de temps, de sorte que les résultats ne peuvent pas être considérablement déformés par des groupes qui résolvent différents problèmes.
Le projet a été achevé en quelques mois, avec l'équipe, et devait se développer progressivement et passer des tests connus et inconnus. Cela signifie qu'il était utile d'écrire du code clair et clair.
En plus de passer les tests du cours, le code ne sera utilisé pour rien d'autre, personne ne le lira et, étant un compilateur pour un sous-ensemble limité de Java dans l'assembleur de texte, il ne sera pas utile.
Aucune bibliothèque autre que la bibliothèque standard n'est autorisée et aucun assistant pour l'analyse, même s'ils se trouvent dans la bibliothèque standard. Cela signifie que la comparaison ne peut pas être faussée par les bibliothèques de compilateur puissantes que seules certaines commandes possèdent.
Il y avait non seulement des tests publics, mais aussi secrets. Ils ont commencé une fois après la livraison finale. Cela signifiait qu'il y avait une incitation à écrire votre propre code de test et à vous assurer que le compilateur est fiable, correct et gère les situations de frontière complexes.
Bien que tous les participants soient des étudiants, je les considère comme des programmeurs assez compétents. Chacun d'entre eux a effectué des stages pendant au moins deux ans, principalement dans des entreprises de haute technologie, travaillant parfois même sur des compilateurs. Presque tous programment depuis 7-13 ans et sont des passionnés qui lisent beaucoup sur Internet en dehors de leurs cours.
Le code généré n'a pas été pris en compte, mais les fichiers de grammaire et le code qui a généré l'autre code ont été pris en compte.

Ainsi, je pense que la quantité de code fournit une compréhension décente de combien d'efforts seront nécessaires pour soutenir chaque projet, s'il était à long terme. Je pense que pas trop de différence entre les projets vous permet également de réfuter certaines déclarations extraordinaires que j'ai lues, par exemple, que le compilateur Haskell sera plus de la moitié de la taille de C ++ en raison du langage.

Rouille (base de comparaison)

Un de mes camarades et moi-même avons écrit plus de 10 000 lignes dans Rust plus tôt, et le troisième collègue a peut-être écrit 500 lignes sur certains hackathons. Notre compilateur est sorti en 6806 lignes de wc -l , 5900 lignes de source (sans espaces et commentaires) et 220 Ko wc -c .

J'ai constaté que dans d'autres projets, ces proportions sont à peu près respectées, à quelques exceptions près, que je noterai. Pour le reste de l'article, quand je parle de chaînes ou de sommes, je veux dire wc -l , mais cela n'a pas d'importance (sauf si je remarque la différence), et vous pouvez convertir avec un coefficient.

J'ai écrit un autre article décrivant notre conception , qui a réussi tous les tests publics et secrets. Il contient également des fonctionnalités supplémentaires que nous avons conçues pour le plaisir, pas pour passer des tests, qui ont probablement ajouté environ 400 lignes. Il a également environ 500 lignes de nos tests unitaires.

Haskell

L'équipe Haskell comprenait deux de mes amis qui ont écrit peut-être quelques milliers de lignes de Haskell chacun, ainsi que beaucoup de contenu en ligne sur Haskell et d'autres langages fonctionnels similaires tels que OCaml et Lean. Ils avaient un autre coéquipier que je ne connaissais pas très bien, mais il semble qu'un programmeur fort ait utilisé Haskell auparavant.

Leur compilateur totalisait 9 750 lignes de wc -l , 357 Ko et 7777 lignes de code (SLOC). Cette équipe a également les seules différences significatives entre ces ratios: leur compilateur est 1,4 fois plus grand que le nôtre en lignes, 1,3 fois en SLOC et 1,6 fois en octets. Ils n'ont implémenté aucune fonction supplémentaire, réussi 100% des tests publics et secrets.

Il est important de noter que l'inclusion de tests a surtout affecté cette équipe. Puisqu'ils ont soigneusement abordé l'exactitude du code, ils ont inclus 1 600 lignes de tests. Ils ont détecté plusieurs situations limites que notre équipe n'a pas détectées, mais ces cas n'ont tout simplement pas été vérifiés par des tests de cours. Donc sans tests des deux côtés (6,3 mille lignes contre 8,1 mille lignes) leur compilateur n'est que 30% de plus que le nôtre.

Ici, j'ai tendance à octets comme une mesure de comparaison de volume plus raisonnable, car dans un projet Haskell, en moyenne, il y a des lignes plus longues, car il n'a pas un grand nombre de lignes d'une parenthèse fermante, et rustfmt ne casse pas les chaînes de fonctions unifilaires en plusieurs lignes.

Après avoir fouillé avec l'un de mes coéquipiers, nous avons trouvé l'explication suivante pour cette différence:

Nous avons utilisé un analyseur lexical manuscrit et une méthode de descente récursive, et ils ont utilisé un générateur NFA et DFA et un analyseur LR , puis une passe pour convertir l'arbre d'analyse en AST ( arbre de syntaxe abstraite , représentation plus pratique du code). Cela leur a donné beaucoup plus de code: 2677 lignes par rapport à notre 1705, soit environ 1000 lignes de plus.
Ils ont utilisé l'AST générique fantaisiste, qui est passé à divers paramètres de type à mesure que plus d'informations étaient ajoutées à chaque passage. Cette fonction et d'autres fonctions d'aide à la réécriture expliquent probablement pourquoi leur code AST est environ 500 lignes plus long que notre implémentation, où nous collectons des littéraux struct et mutons les champs Option<_> pour ajouter des informations au fur et à mesure.
Ils ont encore environ 400 lignes de code pendant la génération, qui sont principalement associées à la plus grande abstraction nécessaire pour générer et combiner le code de manière purement fonctionnelle, où nous utilisons simplement des lignes de mutation et d'écriture.

Ces différences plus les tests expliquent toutes les différences de volume. En fait, nos fichiers de constantes de pliage et de résolution de contexte sont de taille très proche. Mais encore, il y a une certaine différence d'octets en raison de lignes plus longues: probablement parce que plus de code est nécessaire pour réécrire l'arborescence entière à chaque passage.

Par conséquent, en mettant de côté les décisions de conception, à mon avis, Rust et Haskell sont également expressifs, peut-être avec un léger avantage Rust en raison de la possibilité d'utiliser facilement la mutation quand cela est pratique. Il était également intéressant de savoir que mon choix de la méthode de descente récursive et de l'analyseur lexical manuscrit était payant: c'était un risque qui contredisait les recommandations et les instructions du professeur, mais j'ai décidé que c'était plus facile et c'était juste.

Les fans de Haskell feront valoir que cette équipe n'a probablement pas profité pleinement de Haskell, et s'ils connaissaient mieux la langue, ils auraient pu faire un projet avec moins de code. Je suis d'accord, quelqu'un comme Edward Kmett peut écrire le même compilateur en beaucoup moins. En effet, l’équipe de mon ami n’a pas utilisé beaucoup d’abstractions super-avancées bizarres et de librairies combinatoires sophistiquées telles que les objectifs . Cependant, tout cela affecte la lisibilité du code. Tous les membres de l'équipe sont des programmeurs expérimentés, ils savaient que Haskell était capable de choses très bizarres, mais ont décidé de ne pas les utiliser parce qu'ils ont décidé que les comprendre prendrait plus de temps qu'ils n'en économiseraient et rendrait le code plus difficile à comprendre pour les autres. Cela semble être un vrai compromis, et l'affirmation selon laquelle Haskell est magiquement adapté aux compilateurs va dans quelque chose comme "Haskell nécessite des compétences extrêmement élevées dans l'écriture de compilateurs si vous ne vous souciez pas du support de code pour les personnes qui ne sont pas non plus très habiles chez Haskell."

Il est également intéressant de noter qu'au début de chaque projet, le professeur dit que les étudiants peuvent utiliser n'importe quelle langue qui s'exécute sur un serveur universitaire, mais avertit que les équipes sur Haskell sont différentes des autres: elles ont la plus grande dispersion dans les notes. Beaucoup de gens surestiment leurs capacités et les équipes Haskell ont les notes les plus mauvaises, bien que d'autres se débrouillent très bien comme mes amis.

C ++

Ensuite, j'ai parlé à mon ami de l'équipe C ++. Je ne connaissais qu'une seule personne dans cette équipe, mais le C ++ est utilisé dans plusieurs cours de notre université, donc probablement tout le monde dans l'équipe avait une expérience en C ++.

Leur projet comprenait 8733 lignes et 280 Ko, sans compter le code de test, mais comprenant environ 500 lignes de fonctions supplémentaires. Ce qui le rend 1,4 fois plus grand que notre code sans tests, qui a également environ 500 lignes de fonctions supplémentaires. Ils ont réussi 100% des tests publics, mais seulement 90% des tests secrets. Vraisemblablement parce qu'ils n'ont pas implémenté les tableaux de vtables sophistiqués requis par la spécification, qui prennent peut-être 50 à 100 lignes de code.

Je ne me suis pas trop plongé dans ces différences de taille. Je suppose que cela est principalement dû à:

Ils utilisent l'analyseur LR et le réécriveur d'arbre au lieu de la méthode de descente récursive.
Le manque de types de somme et de comparaisons de modèles en C ++, que nous avons largement utilisés et qui étaient très utiles.
La nécessité de dupliquer toutes les signatures dans les fichiers d'en-tête, ce qui n'est pas le cas dans Rust.

Nous avons également comparé le temps de compilation. Sur mon ordinateur portable, la version de débogage propre de notre compilateur prend 9,7 s, la version propre 12,5 s et la version de débogage incrémentiel 3,5 s. Mon ami n'avait pas de temps pour sa construction C ++ (en utilisant la création parallèle), mais il a dit que les chiffres sont similaires, avec la mise en garde qu'ils ont mis en œuvre de nombreuses petites fonctions dans les fichiers d'en-tête pour réduire la duplication des signatures au prix d'un temps plus long (à savoir par conséquent, je ne peux pas mesurer la surcharge de ligne nette dans les fichiers d'en-tête).

Python

Mon ami, un très bon programmeur, a décidé de faire le projet seul en Python. Elle a également implémenté des fonctionnalités plus avancées (pour le plaisir) que toute autre équipe, y compris une vue SSA intermédiaire avec l'allocation des registres et d'autres optimisations. D'autre part, comme il fonctionnait seul et implémentait de nombreuses fonctions supplémentaires, il accordait le moins d'attention à la qualité du code, par exemple, en lançant des exceptions indifférenciées pour toutes les erreurs (en s'appuyant sur des traces pour le débogage) au lieu d'implémenter des types d'erreur et des messages correspondants, comme nous.

Son compilateur comprenait 4581 lignes et a passé tous les tests publics et secrets. Elle a également implémenté des fonctions plus avancées que toute autre commande, mais il est difficile de déterminer la quantité de code supplémentaire nécessaire, car la plupart des fonctions supplémentaires étaient des versions plus puissantes de choses simples que tout le monde devait implémenter, telles que le pliage de constantes et la génération de code. Les fonctions supplémentaires sont probablement de 1 000 à 2 000 lignes, au moins, donc je suis sûr que son code est au moins deux fois plus expressif que le nôtre.

Une grande partie de cette différence est probablement le typage dynamique. Seulement dans nos ast.rs 500 lignes de définitions de types et beaucoup plus de types définis ailleurs dans le compilateur. Nous sommes également toujours limités au système de type lui-même. Par exemple, nous avons besoin d'une infrastructure pour ajouter de manière ergonomique de nouvelles informations à l'AST au fur et à mesure que nous passons et y accédons plus tard. En Python, vous pouvez simplement définir de nouveaux champs sur les nœuds AST.

La métaprogrammation puissante explique également une partie de la différence. Par exemple, même si elle a utilisé un analyseur LR au lieu d'une méthode de descente récursive, dans mon cas, je pense qu'il a fallu moins de code car au lieu de passer par une réécriture d'arbre, sa grammaire LR comprenait des morceaux de code Python pour construire l'AST, que le générateur pourrait transformer en fonctions Python en utilisant eval . Une partie de la raison pour laquelle nous n'avons pas utilisé l'analyseur LR est parce que la construction d'un AST sans réécrire l'arbre nécessitera beaucoup de cérémonies (création de fichiers Rust ou de macros procédurales) pour associer la grammaire à des fragments de code Rust.

Un autre exemple de la puissance de la métaprogrammation et de la frappe dynamique est le fichier visit.rs 400 lignes, qui est essentiellement un code répétitif qui implémente un visiteur sur un tas de structures AST. En Python, cela peut être une fonction courte d'environ 10 lignes qui introspecte récursivement les champs d'un nœud AST et les visite (en utilisant l'attribut __dict__ ).

En tant que fan de Rust et des langages typés statiquement en général, je suis enclin à noter que le système de typage est très utile pour prévenir les erreurs et pour les performances. Une métaprogrammation inhabituelle peut également rendre difficile la compréhension du fonctionnement du code. Cependant, cette comparaison m'a surpris par le fait que je ne m'attendais pas à ce que la différence dans la quantité de code soit si grande. Si la différence dans son ensemble est vraiment proche d'avoir à écrire deux fois plus de code, je pense toujours que Rust est un compromis approprié, mais toujours la moitié du code est un argument, et à l'avenir, j'ai tendance à faire quelque chose en Ruby / Python si vous avez juste besoin de construire rapidement quelque chose seul, puis de le jeter.

Rouille (un autre groupe)

La comparaison la plus intéressante pour moi a été avec mon ami qui a également fait un projet à Rust avec un coéquipier (que je ne connaissais pas). Mon ami a eu une bonne expérience de Rust. Il a contribué au développement du compilateur Rust et a beaucoup lu. Je ne sais rien de son camarade.

Leur projet comprenait 17 211 lignes brutes, 15 000 lignes source et 637 Ko, sans le code de test et le code généré. Il n'avait pas de fonctions supplémentaires, et il n'a réussi que 4 des 10 tests secrets et 90% des tests publics pour la génération de code, car ils n'avaient pas assez de temps avant la date limite pour implémenter des parties plus bizarres de la spécification. Leur programme est trois fois plus grand que le nôtre, écrit dans la même langue, et avec moins de fonctionnalités!

Ce résultat a été vraiment incroyable pour moi et a éclipsé toutes les différences entre les langues que j'ai étudiées jusqu'à présent. Par conséquent, nous avons comparé les listes de tailles de fichiers wc -l , et vérifié également comment chacun de nous a implémenté certaines choses spécifiques qui ont entraîné des tailles de code différentes.

Il semble que tout se résume à l'adoption cohérente de diverses décisions de conception. Par exemple, leur interface (analyse lexicale, analyse, création d'AST) prend 7597 lignes par rapport à notre 2164. Ils ont utilisé l'analyseur lexical DFA et l'analyseur LALR (1), mais d'autres groupes ont fait des choses similaires sans trop de code. En regardant leur dossier de désherbeur, j'ai remarqué un certain nombre de décisions de conception qui étaient différentes des nôtres:

Ils ont décidé d'utiliser un arbre d'analyse entièrement typé au lieu d'un arbre d'analyse standard, uniforme et basé sur des chaînes. Cela nécessitait probablement beaucoup plus de définitions de types et de code de conversion supplémentaire au stade de l'analyse ou un analyseur plus complexe.
Ils ont utilisé des implémentations de tryfrom tryfrom pour convertir entre les types d'arbre d'analyse et les types AST pour les valider. Cela conduit à de nombreux blocs d' impl 10-20 lignes. Pour ce faire, nous avons utilisé des fonctions qui renvoient des types de Result , ce qui génère moins de lignes, et nous libère également un peu de la structure de type, simplifiant le paramétrage et la réutilisation. Certaines des choses qui, pour nous, étaient des branches de match seule ligne, avaient des blocs impl 10 lignes.
Nos types sont structurés pour réduire le copier-coller. Par exemple, ils ont utilisé des champs séparés is_abstract , is_native et is_static , où le code de vérification des contraintes a dû être copié deux fois: une fois pour les méthodes de type vide et une fois pour les méthodes de type retour, avec de légères modifications. Alors que notre void n'était qu'un type spécial, nous avons trouvé une taxonomie de modificateurs avec mode et visibility qui appliquait des contraintes de niveau type, et des erreurs de contrainte étaient générées par défaut pour l'opérateur de correspondance, ce qui traduisait les ensembles de modificateurs en mode et visibility .

Je n'ai pas regardé le code des passes de l'analyse de leur compilateur, mais ils sont aussi super. J'ai parlé avec mon ami, et il semble qu'ils n'aient pas mis en place quelque chose de similaire à l'infrastructure des visiteurs, comme la nôtre. Je suppose que, avec quelques autres différences de conception plus petites, explique la différence de taille de cette pièce. Le visiteur permet à nos passes d'analyse de se concentrer uniquement sur les parties de l'AST dont elles ont besoin, plutôt que de faire correspondre le modèle à l'ensemble de la structure de l'AST. Cela économise beaucoup de code.

Leur partie pour la génération de code se compose de 3594 lignes, et la nôtre - 1560. J'ai regardé leur code et il semble que presque toute la différence est qu'ils ont choisi une structure de données intermédiaire pour les instructions d'assembleur, où nous avons simplement utilisé le formatage de chaîne pour la sortie directe de l'assembleur . Ils devaient définir des types et des fonctions de sortie pour toutes les instructions et tous les types d'opérandes utilisés. Cela signifiait également que la construction des instructions d'assemblage prenait plus de code. Là où nous avions un opérateur de format avec des instructions courtes, comme mov ecx, [edx] , ils avaient besoin d'un opérateur géant rustfmt , divisé en 6 lignes, qui a construit une instruction avec un tas de types imbriqués intermédiaires pour les opérandes qui incluent jusqu'à 6 niveaux de crochets imbriqués. Nous pourrions également produire des blocs d'instructions connexes, comme un préambule de fonction, dans une instruction de format unique, où ils devaient spécifier la construction complète de chaque instruction.

Notre équipe envisageait d'utiliser une abstraction comme la leur. Il était plus facile de produire un assemblage de texte ou d'émettre directement du code machine, mais ce n'était pas une exigence du cours. La même chose pourrait être faite avec moins de code et de meilleures performances en utilisant le X86Writer X86Writer avec des méthodes comme push(reg: Register) . Nous avons également pris en compte que cela pourrait simplifier le débogage et les tests, mais nous avons réalisé que la visualisation de l'assembleur de texte généré est en fait plus facile à lire et à tester à l'aide de tests de clichés , si vous insérez des commentaires généreusement. Mais nous (apparemment correctement) avons prédit que cela prendrait beaucoup de code supplémentaire, et il n'y avait aucun avantage réel, étant donné nos besoins réels, nous ne nous sommes donc pas inquiétés.

Il est bon de comparer cela avec la représentation intermédiaire que l'équipe C ++ a utilisée comme fonction supplémentaire, ce qui ne leur a pris que 500 lignes supplémentaires. Ils ont utilisé une structure très simple (pour les définitions de types simples et le code de construction) qui utilisait des opérations proches de celles requises par Java. Cela signifiait que leur représentation intermédiaire était beaucoup plus petite (et nécessitait donc moins de code de construction) que l'assembleur résultant, car de nombreuses opérations de langage, telles que les appels et les transtypages, ont été développées dans de nombreuses instructions d'assembleur. Ils disent également que cela a vraiment aidé le débogage, car cela a éliminé beaucoup de déchets et amélioré la lisibilité. Une présentation de niveau supérieur a également permis de faire quelques optimisations simples sur leur représentation intermédiaire. L'équipe C ++ a trouvé un très bon design qui leur a fait beaucoup plus de bien avec beaucoup moins de code.

En général, il semble que la raison commune de la triple différence de volume soit due à l'adoption cohérente de diverses décisions de conception, grandes et petites, dans le sens de plus de code. Ils ont implémenté un certain nombre d'abstractions, ce que nous n'avons pas fait - ils ont ajouté plus de code et ignoré certaines de nos abstractions, ce qui réduit la quantité de code.

Ce résultat m'a vraiment surpris. Je savais que les décisions de conception étaient importantes, mais je n'aurais pas deviné à l'avance qu'elles entraîneraient des différences de cette taille, étant donné que je n'ai examiné que des personnes que je considère comme de bons programmeurs compétents. De tous les résultats de comparaison, c'est le plus significatif pour moi. , , , , , , , AST , .

— . , , , . : , , . , , , , , . , , (, C++), .

: , , , , , , , .

Scala

, Scala, . 4141 ~160 , . 8 10 100% . , 5906 , 30%.

. LR. , . LR. LR 150- Python, - Java, , . - Scala, 1073 1443, .

Le reste de leur compilateur était également plus petit que le nôtre, sans grandes différences de conception évidentes, même si je ne me suis pas plongé dans le code. Je soupçonne que cela est dû à des différences dans l'expressivité de Scala et de Rust. Scala et Rust ont des fonctionnalités de programmation similaires utiles pour les compilateurs, telles que la correspondance de modèles, mais la mémoire gérée de Scala enregistre le code nécessaire pour que le vérificateur d'emprunt fonctionne dans Rust. De plus, Scala a un sucre syntaxique plus varié que Rust.

OCaml

Jane Street ( — . .), Jane Street, OCaml.

10914 377 , . 9/10 .

, , LR- , regex->NFA->DFA . ( , , AST) 5548 , — 2164, . , snapshot-, , ~600 , — 200.

5366 (461 — ) 4642 , 15%, , , . , , , Rust OCaml , , OCaml , Rust — .

Conclusion

, , . , , , , , .

Comparaison du même projet dans Rust, Haskell, C ++, Python, Scala et OCaml