- Datatype99 est une bibliothèque fondée sur des macros qui fournit, en C99 pur, des types de données algébriques, du pattern matching exhaustif et de l’introspection à la compilation
- Elle vise à détecter à la compilation les variants mal typés, les pattern matchings incomplets et les accès incorrects aux champs, et ne nécessite qu’un compilateur C99 conforme au standard
- En interne,
datatype est développé en tagged union et constructeurs de valeurs (value constructors), tandis que match est développé en instruction switch; la disposition mémoire générée suit une sémantique de génération de code formalisée
- L’installation consiste à ajouter
datatype99.h et sa dépendance Metalang99 au chemin d’inclusion; avec GCC/Clang, il est recommandé d’utiliser des options de compilation qui réduisent la sortie d’erreurs liée à l’expansion des macros
- Il peut être intégré à une base de code C avec
#include <datatype99.h>, est connu pour fonctionner avec GCC, Clang, MSVC et TCC, et prend aussi en charge C++11 et versions ultérieures
Ce que propose Datatype99
- Datatype99 fournit en C99 des types de données algébriques sûrs et intuitifs
- Son périmètre fonctionnel inclut le pattern matching exhaustif et l’introspection à la compilation
- Il fonctionne sans outil externe de génération de code, et son implémentation repose sur du C99 pur
- Principales caractéristiques
- Sécurité de typage : détecte à la compilation les variants mal typés, les pattern matchings non exhaustifs et les accès incorrects aux champs
- Portabilité : nécessite un compilateur C99 conforme au standard, sans bibliothèque standard, fonctionnalité propre à un compilateur/une plateforme, ni VLA
- Prévisibilité : une sémantique de génération de code est définie, ce qui garantit que la disposition des données générée est toujours la même
- Erreurs compréhensibles : la bibliothèque elle-même détecte certaines erreurs de syntaxe dans le code incorrect
- Cas d’usage réel : utilisé par OpenIPC pour développer un logiciel de streaming temps réel pour caméras IP, avec notamment une implémentation de RTSP 1.0 et environ 50 000 lignes de code non public
Installation et configuration de build
- Datatype99 se compose d’un unique fichier d’en-tête
datatype99.h et d’une dépendance à Metalang99
- Pour l’utiliser dans un projet, il faut ajouter
datatype99 et metalang99/include aux répertoires d’inclusion
- Avec GCC, il est recommandé de spécifier
-ftrack-macro-expansion=0, et avec Clang -fmacro-backtrace-limit=1, afin de réduire la sortie inutile d’erreurs d’expansion de macros
- Avec CMake, l’utilisation de
FetchContent est recommandée
- Le
datatype99/CMakeLists.txt par défaut télécharge Metalang99 v1.13.5 depuis GitHub Releases
- Ce comportement peut être redéfini en appelant au préalable
FetchContent_Declare
- Les en-têtes dépendant de Datatype99 peuvent être transformés en precompiled header, ce qui réduit les temps de compilation en évitant de les recompiler à chaque inclusion
Mode d’utilisation : employer des tagged unions de façon plus sûre
- Datatype99 est essentiellement du sucre syntaxique pour les tagged unions, sous une forme plus sûre et plus concise
- En C classique, représenter un arbre binaire exige d’écrire soi-même une énumération
tag et une union
- Avec Datatype99, la même structure peut être déclarée ainsi
datatype(
BinaryTree,
(Leaf, int),
(Node, BinaryTree *, int, BinaryTree *)
);
- Avec une approche
switch classique, même si l’on accède par erreur à tree->data.node après case Leaf:, le compilateur peut ne pas émettre d’avertissement
- En utilisant
match et of, les bindings propres à chaque variant ne sont visibles que dans la branche correspondante, et un accès inapproprié fait échouer la compilation
int sum(const BinaryTree *tree) {
match(*tree) {
of(Leaf, x) return *x;
of(Node, lhs, x, rhs) return sum(*lhs) + * x + sum(*rhs);
}
return -1;
}
- Les bindings fournis par
of sont des variables comme x, lhs et rhs; ils ont un type pointeur et permettent de modifier les valeurs
- La création de variants utilise les constructeurs de valeurs générés en interne
BinaryTree leaf5 = Leaf(5);
BinaryTree leaf7 = Leaf(7);
BinaryTree node = Node(&leaf5, 123, &leaf7);
Syntaxe et sémantique de génération
- Datatype99 fournit une syntaxe de macros comme
datatype, record, match, of, otherwise, MATCHES et ifLet
- Des noms de macros abrégés et des versions suffixées coexistent
- Exemple :
match99, of99, derive99
- Pour éviter les collisions de noms, il est possible de définir
DATATYPE99_NO_ALIASES avant d’inclure datatype99.h
- Dans les en-têtes de bibliothèque, l’utilisation des macros suffixées est recommandée
datatype génère les éléments suivants
- un
typedef anticipé
- des structures pour chaque variant non vide
- des
typedef pour les types de champs des variants
- un
typedef pour le sum type
- une tagged union comprenant l’énumération
tag et l’union
- des constructeurs de valeurs
inline static pour chaque variant
- les appels aux derivers indiqués dans
derive(...)
- Même si tous les variants sont vides, le standard C exige au moins un élément dans une union; un
char dummy; est donc inséré
record est une struct dont le processus de dérivation est défini, et génère aussi char dummy; lorsqu’il n’y a pas de champmatch compare séquentiellement une instance de sum type aux variants, exécute les instructions de la branche qui réussit, puis passe à l’instruction suivante- Les constructions complètes
match et ifLet sont chacune développées en une seule instruction C
MATCHES vérifie par vrai/faux si une instance de sum type correspond à un variant donnématches est deprecated; l’utilisation de MATCHES est recommandée
derive et attributs auxiliaires
derive(...) sert à générer du code global pour un sum type ou un record- Le deriver d’un sum type est appelé sous forme de macro compatible Metalang99, et la liste des variants est transmise sous forme de liste de tuples
- Le deriver d’un record est également appelé comme macro compatible Metalang99, et la liste des champs est transmise sous forme de liste de tuples
(<type>, <field-name>)
- Un attribut auxiliaire de dérivation est un argument nommé passé au deriver
- Les attributs auxiliaires utilisent la forme de macros object-like
#define <variant-name>_<namespace>_<attribute-name> attr(/* attribute value */)
- Macros fournies pour manipuler les attributs
DATATYPE99_attrIsPresent / DATATYPE99_ATTR_IS_PRESENT : vérifier la présence d’un attributDATATYPE99_attrValue / DATATYPE99_ATTR_VALUE : extraire la valeur d’un attribut existantDATATYPE99_assertAttrIsPresent : déclencher une erreur fatale si un attribut obligatoire est absent
Schémas d’utilisation à surveiller
- Il ne faut pas utiliser de
break/continue au niveau supérieur dans les instructions passées à of et ifLet
- Un
continue à l’intérieur d’une boucle for/while interne ne pose pas de problème
- Le flux de contrôle de niveau supérieur doit être remplacé par un label
goto
- Pour spécifier un tableau comme paramètre de variant, il faut l’encapsuler dans une
struct séparée
- Les bindings introduits par
of sont toujours mutables; si la valeur passée à match est const, il faut veiller à ne pas la modifier
- Pour préserver la lisibilité des définitions
datatype, on peut utiliser // clang-format off et // clang-format on avec Clang-Format
- Les attributs auxiliaires de dérivation doivent toujours être suivis d’un
#undef après la définition datatype concernée afin d’éviter de polluer le namespace
- Si la signification des paramètres de variants n’est pas évidente avec le seul contexte, on peut leur donner des noms plus descriptifs via des alias de types ou des structures séparées
Erreurs, IDE et compatibilité
- Certaines erreurs de syntaxe sont détectées par la bibliothèque elle-même
- une forme qui n’est pas un tuple, comme
Bar(int)
- une virgule manquante
- une virgule finale interdite
- D’autres erreurs apparaissent également via les diagnostics habituels du compilateur
- nom de type inexistant
match non exhaustif- nombre excessif de binders dans
of
- argument de variant mal typé
- retour sans déréférencer un binding pointeur
- D’après l’expérience rapportée, près de 95 % des erreurs apparaissent de façon significative
- Si une erreur n’est pas compréhensible, il est possible d’inspecter le code généré avec
-E; la sémantique de génération de code étant formellement définie, le code produit est généralement sans surprise
- VS Code active automatiquement les suggestions pour les types générés, mais ne prend pas en charge la coloration syntaxique de la syntaxe de macros
- Datatype99 est connu pour fonctionner avec GCC, Clang, MSVC et TCC
- C++11 et les versions ultérieures sont également pris en charge
Pourquoi cibler C, et quelles limites
- Les logiciels existants écrits en C pur peuvent bénéficier des avantages de Datatype99
- Il peut être intégré à une base de code C existante avec un simple
#include <datatype99.h>
- Certains environnements conservent le C pur pour des raisons historiques, notamment les appareils embarqués, Linux et d’autres systèmes d’exploitation
- L’ABI stable de C est importante pour des projets de systèmes de plugins comme MetaCall
- C est présenté comme un langage mature, doté d’une spécification complète et de nombreuses bibliothèques
- Si l’on peut utiliser un langage plus moderne ou de plus haut niveau, ce choix est recommandé plutôt que l’ancien C, mais pour beaucoup de personnes cette option n’existe pas ou coûte cher
- La différence entre Datatype99 et Metalang99 tient à leur rôle
- Metalang99 est un langage fonctionnel destiné à la métaprogrammation
- Datatype99 est une implémentation de types de données algébriques écrite avec Metalang99
1 commentaires
Avis sur Hacker News
Au travail, je dois utiliser Java, et même si j’en suis venu à penser que Java n’est pas aussi mauvais que je le critiquais autrefois, je me suis dit des dizaines de fois : « si seulement Java avait les unions discriminées de F# »
On peut les imiter avec diverses techniques, et il y a beaucoup de cas où un enum suffit, mais dans la plupart des situations, il manque la souplesse et la concision de vrais types de données algébriques. Et surtout, il n’y a pas ce formidable pattern matching qu’on obtient dans les langages fonctionnels
Cette extension de C a l’air plutôt bien, puisqu’elle semble offrir le pattern matching que je voudrais, donc il faut que je voie si je peux l’utiliser dans un projet Arduino
Quand on vient juste de les découvrir, on n’arrête plus d’en parler comme de la meilleure invention depuis le pain :)
Pour Java, il y a https://github.com/functionaljava/functionaljava ; le support est arrêté, mais c’est stable
C’est trop puissant pour s’en passer
Un support de pattern matching imposé par le compilateur au-dessus des sealed classes a été ajouté récemment, donc on peut considérer qu’on en est à moitié là
Si vous voulez voir comment les types de données algébriques fonctionnent en interne, libsum me semble être une bonne introduction
[1] https://github.com/naasking/libsum
Je connais C depuis presque 20 ans, mais je n’aurais jamais imaginé que le système de macros soit assez puissant pour permettre ce genre de magie noire
C’est vraiment génial
Traditionnellement, elles servaient à créer et manipuler des génériques sûrs du point de vue des types, ou à réduire le code répétitif dans les définitions de registres matériels et d’interruptions
Ça a un petit côté maudit, mais au fond c’est vraiment très simple, et dans les projets en C, c’est un outil fiable pour réduire la complexité cognitive et le boilerplate
Comme usage des macros, ce n’est pas si complexe
https://en.wikipedia.org/wiki/Tagged_union#Class_hierarchies...
Il y a aussi un long billet de blog sur le même sujet, et son auteur semble ne pas encore avoir vu cette section de Wikipedia
https://nandakumar.org/blog/2023/12/paradigms-in-disguise.ht...
Il faut saluer le fait que le développeur de datatype99 montre directement dans le README les problèmes de ce genre de solution de fortune
https://github.com/melt-umn/ableC-template-algebraic-data-ty...
Cela dit, en dehors de ça, c’est très cool
Ça m’a rappelé une interface utilisateur en mode immédiat que j’avais faite autrefois avec des macros. Dans mon cas, ce n’était pas un problème, mais on peut utiliser
breakdans certains blocsPar exemple, on peut sortir d’un bloc win_form avec
break, etgotofonctionne aussi. En revanche, un bloc win_command n’intercepte pasbreak, donc si on utilise break ou goto à l’intérieur d’un win_command, on quitte le bloc extérieur qui entoure ce win_command, probablement un bloc win_form. C’est généralement utilisé pour un bouton comme « Cancel »Ce n’est pas seulement un peu mieux sur quelques points, c’est aussi la capacité à lisser toute une accumulation de petites gênes qui se sont installées avec le temps dans l’écosystème au sens large. Un peu comme le fait qu’il y a trop de types lexicaux propres à l’univers CPython, ou certains problèmes similaires dans les bibliothèques de calcul haute performance : l’effet cumulé est important
Par exemple, la partie de cette macro qui provoque ce problème n’aurait probablement jamais posé souci dans une macro Rust bien écrite dès le départ. C’est un sous-produit de gens intelligents qui essaient de contourner les limites de C
Cependant, cette macro elle-même est à l’origine un portage d’une fonctionnalité native de Rust, donc en Rust il n’aurait probablement jamais été nécessaire de l’écrire au départ, et c’est pour cela qu’elle s’intègre naturellement dans les logiciels développés par la communauté
goton’est vraiment un piège que lorsqu’on l’utilise pour sauter d’une fonction à une autre, et en réalité « goto considered harmful » visait cette pratiqueCette habitude a disparu, et aujourd’hui l’usage de goto à l’intérieur d’une fonction est assez inoffensif, en pratique presque équivalent à
break/continueEt supposons aussi que vous sachiez déjà que Rust existe, mais que, pour les raisons habituelles bien connues de ceux qui écrivent en C, vous n’alliez pas utiliser Rust
Dans ce cas, Zig mérite au moins d’être envisagé. J’ai écrit ce genre de code en Zig il y a deux jours
en utilisant
inline elsedecomptimepour générer toutes les branches d’unswitchsur une union taguée, et ajouter un offset aux membres de l’union qui possèdent un champ"l". Si l’information de type est connue à la compilation, on peut faire varier fortement la nature des branches, et cette information est assez riche. Comme toutes les conditions sont résolues à la compilation, chaque branche duswitchne contient que la logique nécessaire pour traiter cette variante« Mais mon programme est déjà en C et je n’en ai besoin que dans un seul fichier » : même là, ça vaut le coup d’essayer Zig. Vous pourriez aimer
https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62e...
struct+union+enum, ne peut-on pas obtenir la plupart des avantages des types de données algébriques ? J’ai déjà utilisé un pattern consistant à définir uneunionde plusieurs types, accompagnée d’unenumindiquant lequel choisirstd::variantsemble aussi se comporter dans une certaine mesure comme un sum typeLe seul vrai problème est qu’on ne peut pas faire proprement un
switchsur une valeur particulière d’un champ, mais même desswitchimbriqués ne sont pas si salesLe problème de cette approche, c’est l’charge mentale importante qu’elle impose pour ne rater aucun détail. À la longue, on se fatigue et on commence à forcer de nouvelles fonctionnalités dans une classe existante au lieu d’en créer une nouvelle
Au final, l’abstraction paraît coûteuse, et on en utilise donc moins même quand elle permettrait de résoudre le problème de façon plus élégante
En résumé, la capacité à dire « Darmok and Jalad at Tanagra » au lieu de devoir répéter toute une longue histoire chaque fois qu’on veut faire référence à une idée complexe est transformatrice
Le pattern matching apporte un énorme gain d’ergonomie
C’est difficile à faire avec des macros, mais pas impossible. En gros, il faut une macro qui démarre le contexte de matching, introduit une variable pour suivre toutes les alternatives déjà vérifiées, puis organise la fin du contexte de sorte à contrôler que toutes les alternatives ont bien été couvertes
std::variantLa manière dont
std::visitsert à faire un matching exhaustif de tous les cas me paraît bricolée. Ce serait un énorme gain si cela devenait réellement une fonctionnalité de premier ordre du langageL’impact sur le code quotidien pourrait être plus grand que celui d’autres fonctionnalités sur lesquelles on a travaillé jusqu’ici, comme les coroutines