Encodages initial et final : deux philosophies d’embedding

Les langages dédiés embarqués (embedded DSL) permettent de construire des mini-langages au sein d’un langage hôte, héritant de sa syntaxe, de son système de types et de son outillage.

Deux stratégies fondamentales s’opposent pour représenter les programmes de ces DSL :

• L’encodage initial, souvent appelé deep embedding
• L’encodage final, ou shallow embedding, popularisé sous le nom de tagless final par Oleg Kiselyov

Cette distinction, apparemment technique, a des conséquences profondes sur l’extensibilité, la performance et les capacités d’analyse des DSL ainsi construits.

L’encodage initial (deep embedding)

L’encodage initial représente les programmes du DSL comme des structures de données : typiquement, un arbre de syntaxe abstraite (AST).

Chaque opération du langage devient un constructeur d’un type algébrique :

Literal(n), Add(e1, e2), IfThenElse(cond, then, else)

Un programme est un arbre que l’on peut inspecter, transformer, optimiser, sérialiser. L’interprétation survient ensuite, quand on parcourt cet arbre avec une fonction récursive qui donne sens à chaque nœud.

Cette approche excelle quand on veut analyser ou transformer les programmes (optimisation, compilation, pretty-printing) car la structure est explicitement accessible.

Cependant, ajouter une nouvelle opération au DSL exige de modifier le type de l’AST et tous les interpréteurs existants.

L’encodage final (tagless final)

L’encodage final représente les programmes non comme des données mais comme des expressions polymorphes abstraites sur une interface.

Au lieu d’un type Expr avec des constructeurs, on définit une typeclass ou une interface avec des méthodes literal, add, ifThenElse. Un programme est une fonction générique qui utilise ces méthodes sans savoir quelle implémentation les fournira.

Chaque interpréteur devient une instance de cette interface :

• L’évaluateur implémente add comme l’addition réelle
• Le pretty-printer comme la concaténation de chaînes

Ajouter un nouvel interpréteur est trivial : on fournit une nouvelle instance sans toucher au code existant. En revanche, ajouter une nouvelle opération exige de modifier l’interface et toutes ses instances.

L’expression problem

Cette dualité incarne le fameux expression problem formulé par Philip Wadler :

• L’encodage initial facilite l’ajout d’interpréteurs (nouvelles fonctions sur un type fixe)
• L’encodage final facilite l’ajout d’opérations (nouvelles méthodes implémentées par des types fixes)

Le choix dépend de l’axe d’extension anticipé :

• Un DSL dont les opérations sont stables mais qui nécessitera de nombreux backends (compilation, interprétation, analyse, documentation) favorise l’encodage initial
• Un DSL qui évoluera fréquemment avec de nouvelles primitives, interprété de manière uniforme, favorise l’encodage final

Avantages pratiques du tagless final

En pratique, l’encodage final offre un avantage supplémentaire souvent décisif : l’absence d’AST intermédiaire permet une fusion naturelle des interprétations et élimine le surcoût de construction puis de parcours d’arbre.

Le programme est directement son interprétation, paramétrée par le choix de l’instance.

Cette efficacité, combinée à la sécurité apportée par le polymorphisme (on ne peut construire que des programmes bien formés), explique la popularité croissante du style tagless final dans les bibliothèques d’effets fonctionnels.

L’encodage initial reste précieux quand l’introspection est nécessaire, mais pour beaucoup de DSL métier où l’on veut simplement décrire puis exécuter, l’encodage final offre une élégance et une extensibilité difficiles à égaler.