Étendre des interpréteurs par détournement, ou comment étendre des interpréteurs sans en modifier le code

JavaScript est le langage de programmation des pages web. Ce n’est pas juste le langage le plus populaire, c’est le seul langage supporté nativement par les navigateurs majeurs. Les alternatives comme les applets Java de feu Sun ou les programmes Flash d’Adobe nécessitent l’installation de plugins, ou ne sont pas compatibles avec toutes les plates-formes, mais surtout sont abandonnées par leurs constructeurs. JavaScript demeure le seul langage qui peut accompagner une page web et être exécuté par tous ces navigateurs sans installation supplémentaire.

JavaScript est utilisé pour rendre les pages web dynamiques (animer des boutons, valider des formulaires, …), voire les transformer en complètes applications (cartographie, portail social, ou même éditeur d’objets 3D). JavaScript dispose d’une interface riche avec tous les éléments d’une page web, et plus généralement de l’ordinateur: on peut facilement modifier l’arbre d’une page HTML et son style, mais on peut tout aussi aisément capturer le pointeur de la souris, redimensionner la fenêtre du navigateur, ou accéder à la caméra de l’ordinateur.

Les programmes JavaScript ne sont pas restreints aux navigateurs. Les interpréteurs JavaScript comme V8 (de Chrome) ou SpiderMonkey (de Firefox) sont exécutables en dehors du navigateur, et JavaScript devient alors comparable à l’utilité faite du langage Python: un langage simple à prendre en mains, disposant d’une riche collection de bibliothèques, et exécutable partout ou des interpréteurs sont disponibles. Le projet Electron [ele16], par exemple, permet d’écrire des applications multiplateformes en JavaScript.

À l’origine le langage était destiné à faire l’interface entre les pages web et les applets Java. Son auteur, Brendan Eich, est recruté par la compagnie Netscape dans le but de faire une version du langage Scheme pour leur navigateur web, le simplement nommé Netscape Navigator. En raison d’un partenariat avec Sun, le langage devait ressembler à Java; de là aussi vient son nom. Netscape souhaitait un langage de programmation qui pouvait être inclus dans des les fichiers HTML des pages web, un langage pour débutants, un langage pour des petits bouts de code, des scripts, qui viendraient suppléer les applets Java.

En mai 1995, Brendan Eich produit le premier prototype du langage, qui accompagnera la sortie de Netscape Navigator 2.0 dix mois plus tard. Le langage connaît un vif succès, ce qui pousse le concurrent de Netscape, Microsoft, à implémenter à son tour un interpréteur de JavaScript dans son navigateur Internet Explorer. Les deux versions cohabitent avec de légères différences, ce qui conduit à la standardisation du langage sous le nom d’ECMAScript en juin 1997.

Sous ses allures de langage impératif, Eich dit s’être principalement inspiré de Self (pour les prototypes) et Scheme (pour les fonctions de première classe) [Eic08]. Contrairement à Java, JavaScript n’est pas un langage à classes. L’unité structurante majeure est la fonction:

function f(a, b) { /* code */ }

Les fonctions sont de première classe, c’est-à-dire qu’une fonction est une valeur comme une autre, qui peut être passée en argument, retournée par une fonction, mise dans une variable, etc.

function f(x) { return 2 * x }
var function_in_var = f
function_in_var(4) //: 8

JavaScript est typé dynamiquement. Les déclarations de variables, d’arguments, ou de valeurs de retour n’ont pas d’annotation de type. Une même variable peut très bien contenir une fonction, puis un nombre, puis une chaîne de caractères. Toujours pour simplifier la prise en main, il n’y a pas de gestion manuelle de la mémoire: le glaneur de cellules (garbage collector, ou GC) se charge de collecter les objets alloués mais inaccessibles.

Le langage a une syntaxe dédiée pour deux structures de base: les tableaux, et les objets. Un tableau peut contenir n’importe quelle valeur, et n’est pas nécessairement homogène:

var tab = [0,1,2,3,"quatre", function cinq() {}]
tab[0] //: 0
tab[4] //: "quatre"

Les tableaux n’ont pas de taille fixe. On peut leur ajouter des éléments et en retirer à n’importe quel moment. En ce sens, ils ressemblent davantage aux vecteurs qu’aux tableaux de C++:

var tab = []
tab.push(6)
tab.length == 1 //: true

Ce que JavaScript appelle un objet ressemble surtout à un dictionnaire: une structure associative où à chaque nom correspond une valeur:

var obj = {
  "a": 0,
  "b": "un",
  "c": function() { return 2 }
}

obj["a"] //: 0
obj.b //: "un"
obj.c() //: 2

Comme les tableaux, les objets peuvent être modifiés à n’importe quel moment. On peut ajouter une association, la supprimer, ou modifier la valeur associée à un nom. Notons la syntaxe pour appeler une fonction associée dans un objet (obj.c()), qui est identique à l’invocation d’une méthode en Java. Mais en JavaScript, la fonction n’est pas liée à l’objet par construction. On pourrait tout aussi bien l’invoquer de la sorte:

var obj = {
  "c": function() { return 2 }
}

var f = obj.c
f() //: 2

Néanmoins, cette structure associative peut être utilisée pour représenter des objets au sens de la programmation par objets. Les objets de JavaScript disposent d’un lien de prototype, qui permet la délégation, et donc le partage de méthodes, entre objets.

var A = {
  "a": function() { return 0 }
}

var B = {
  __proto__: A,
  "b" : function() { return 1 }
}

A.a() //: 0
B.b() //: 1
B.a() //: 0

Ici on a deux objets, A et B. L’objet A contient une seule fonction, a. L’objet B contient une seule fonction, b, mais déclare A comme prototype à l’aide de la propriété spéciale __proto__. En conséquence, même si la fonction a n’est pas déclarée sur B, B.a() appellera la fonction a qui existe dans son prototype, A. On parle d’une chaîne de prototypes comme une liste chaînée. L’algorithme de recherche d’une propriété dans une chaîne de prototypes est d’ailleurs analogue à la recherche d’une valeur dans une liste chaînée.

La propriété __proto__ n’est pas la seule façon d’affecter le prototype d’un objet à sa création. On peut créer un objet qui hérite d’un autre à l’aide d’Object.create:

var B = Object.create(A)
B.b = function() { return 1 }

Et on peut aussi modifier le prototype d’un objet déjà créé à l’aide d’Object.setPrototypeOf:

var B = {}
B.b = function() { return 1 }
Object.setPrototypeOf(B, A)
Object.getPrototypeOf(B) == A //: true

Dony, Malenfant et Bardou classifient les langages à prototypes [DMB98]. Selon cette classification, JavaScript a toutes les caractéristiques d’un langage à prototypes. La seule omission notable est l’absence de mécanisme pour cloner des objets:

• les objets ne sont pas associés à des classes, ils sont concrets;
• les objets sont des ensembles de couples clé-valeur;
• les objets communiquent par envoi de messages, mais notons que toutes les valeurs ne sont pas des objets: la distinction avec les types « primitifs » (entiers, booléens…) est due à la proximité avec Java voulue par Sun;
• les objets peuvent être créés vides (syntaxe {}), ou en étendant un autre objet (via Object.create ou via la syntaxe {__proto__: parent}), mais il n’y a pas de mécanisme pour cloner un objet;
• le mécanisme des prototypes réalise la notion « est-extension-de », et le lien parent est matérialisé par la propriété spéciale __proto__ (ou la fonction Object.getPrototypeOf);
• pour activer une propriété héritée d’un objet (comme B.a dans l’exemple ci-dessus), l’interpréteur cherche la propriété sur son parent et l’active s’il la trouve, sinon il continue jusqu’à ce que l’objet soit sans parent, auquel cas la propriété n’est pas définie sur le receveur;
• le langage dispose du mot-clé this, qui dans une méthode fait référence au receveur du message, et non à l’objet qui définit la méthode.

Voici un exemple d’utilisation de this:

var point = {
  x: 0, y: 0,
  moveTo: function(x, y) {
    this.x = x
    this.y = y
  }}
var p1 = Object.create(point)
p1.moveTo(1,2)
p1 //: Object {x:1,y:2}
point //: Object {x:0,y:0,moveTo:function}

L’objet point contient deux coordonnées et une fonction moveTo qui remplace ces cordonnées. L’objet p1 a point comme parent, et peut donc répondre au message moveTo. Après cette invocation, on voit que p1 a deux propriétés x et y qui correspondent aux valeurs passées à l’appel de moveTo, tandis que les coordonnées de l’objet point sont restées à zéro. C’est que this dans moveTo fait bien référence au receveur de l’appel, ici p1.

Parnas est souvent cité pour ses travaux sur la modularité, à juste titre, mais son message principal n’est pas toujours bien entendu. On trouve dans l’article déterminant de 1972 les avantages d’un système modulaire, et un critère pour les concevoir: le critère d’encapsulation. Quelles parties du système ont besoin de pouvoir être changées? D’une machine à l’autre, ou en réponse à des besoins futurs? Ces parties déterminent les modules du système selon le critère d’encapsulation. De ce critère découlent des notions de séparation des préoccupations et de type de données abstrait (qu’il ne nomme pas). L’encapsulation est un critère supérieur à la façon usuelle de découper les programmes selon le processus de traitement des données, en suivant un logigramme.

Parnas nous permet donc de qualifier la modularité d’un système. Un système simplement découpé en modules arbitraires n’est pas modulaire. Mais si pour changer la base de données utilisée par le système il suffit de modifier le code d’un seul module, alors ce système est modulaire par rapport à la base de donné utilisée. La base de donnée initiale est un choix de conception, mais un choix qui peut être changé ultérieurement sans demander la refonte totale du système. Le système est modulaire par rapport à un ensemble de choix qui peuvent être altérés ultérieurement.

On peut donc voir la modularité comme une des fonctionnalités du système; une fonctionnalité à destination des programmeurs chargés de la maintenance et de l’évolution du système, plutôt qu’une fonctionnalité destinée aux utilisateurs. Et comme toute fonctionnalité, la modularité impose un coût de complexité au système. Si le programme est flexible, s’il permet de changer la base de donnée utilisée, alors il faut que le reste du système soit capable de fonctionner non plus avec une seule base de donnée, mais avec plusieurs bases différentes. Gérer cette compatibilité impose de traiter plus de cas, ce qui inévitablement se traduit en code. De plus, pour implémenter un système modulaire, on fera souvent appel à des interfaces, des indirections, des appels de procédures qui encapsulent les décisions de conception. Et ces interfaces ont souvent un impact négatif sur l’efficacité du programme. Ces compromis modularité/complexité et modularité/efficacité semblent difficiles à éviter.

Naur établit une distinction importante entre le code source d’un programme, et la connaissance que le programmeur a de son fonctionnement. C’est une distinction intuitive pour quiconque a une expérience même modeste de programmation. Cette distinction nous permet notamment de comprendre pourquoi modifier un programme n’est pas simplement modifier du texte, modifier son code source. Il faut prendre en compte les choix faits au moment de la conception du programme, et considérer comment les changements que l’on souhaite apporter affectent ces choix. Comprendre la théorie.

Naur estime que la théorie n’est pas communicable; qu’elle reste toujours interne au programmeur qui la construit. Mais à l’évidence le programmeur est toujours capable de la communiquer en partie. La théorie, c’est savoir comment le programme fonctionne, pourquoi telle partie est nécessaire, comment étendre le programme… Naur dit lui-même plusieurs fois qu’un programmeur qui possède la théorie est capable de répondre à ces questions sur le programme, c’est bien qu’il y a une personne qui doit interpréter ces réponses et reconstruire la théorie. Quand bien même la théorie ne peut être communiquée exactement comme telle d’un programmeur à l’autre, il suffit d’en communiquer une partie suffisante pour satisfaire les besoins de l’autre.

Le message général est proche de Parnas: l’important dans la programmation ce ne sont pas les formalismes, les langages ou les outils; c’est de réfléchir, de comprendre le problème, et construire une solution qui satisfait les contraintes données. Et c’est cette aptitude à résoudre le problème qui devraient être enseignée principalement aux novices. En cela, la programmation n’est pas différente d’autres activités:

This problem of education of new programmers in an existing theory of a program is quite similar to that of the educational problem of other activities where the knowledge of how to do certain things dominates over the knowledge that certain things are the case, such as writing and playing a music instrument. The most important educational activity is the student’s doing the relevant things under suitable supervision and guidance. In the case of programming the activity should include discussions of the relation between the program and the relevant aspects and activities of the real world, and of the limits set on the real world matters dealt with by the program.

C’est avec le langage Smalltalk qui débute la programmation par objets [Ing78,Ing81,Kay93]. Alan Kay, alors employé au laboratoire de recherche de Xerox à Palo Alto (PARC), souhaite développer l’ordinateur personnel pour tous. Il est inspiré par le NLS (Online System) de Douglas Engelbart [EE68], un système qui permet d’organiser des documents de travail, de créer de multiples vues de ces documents, d’établir des relations (prémices de l’hypertexte), et de collaborer à distance; tout cela dans le but « d’accroître l’intelligence humaine ». Kay voit dans l’ordinateur personnel à la fois un support qui permettrait à tout un chacun de décupler ses facultés de raisonnement et d’analyse, mais aussi un catalyseur de créativité. Chacun pourrait créer une simulation interactive pour mieux comprendre un phénomène, développer un outil pour résoudre un problème de la vie courante, mais aussi composer des mélodies inédites, ou tracer des esquisses improbables. L’ordinateur personnel serait à l’intellect ce que l’exosquelette est au corps humain.

Dans le but de construire cet ordinateur personnel pour tous, Kay crée au sein de PARC le Learning Research Group en 1971. Inspiré par les travaux de Piaget et Bruner sur le développement intellectuel chez les enfants, il souhaite construire un ordinateur intuitif utilisable par les enfants « de tout âge ». Programmer ce système serait simple comme bonjour, et c’est pourquoi il nomme son langage de programmation « Smalltalk ».

Smalltalk est inspiré par Sketchpad [Sut63], SIMULA [DN66], LISP [McC60]. De Sketchpad, il retient l’utilisation des contraintes et l’interactivité. De SIMULA, il tire la différence entre les classes de procédures et leurs instances, et le mécanisme d’héritage. Et de LISP, il emprunte le style de construction récursif, l’absence de gestion manuelle de la mémoire, et la relation symbiotique entre programme et structures de données.

Pour Kay, les objets de Smalltalk sont comme des cellules: des constituants quasi-autonomes, capables de se reproduire:

For the first time I thought of the whole as the entire computer and wondered why anyone would want to divide it up into weaker things called data structures and procedures. Why not divide it up into little computers, as time-sharing was starting to? But not in dozens. Why not thousands of them, each simulating a useful structure?

Ce qui se traduit, en Smalltalk, par le principe du « tout objet ». Un nombre entier est un objet. Une chaîne de caractères est un objet. Une liste chaînée est un objet. Un fichier est un objet. Une image est un objet. Et un objet, bien entendu, est un objet.

Les objets ont leur propre mémoire: ils sont les seuls maîtres des données qu’ils manipulent. L’objet liste chaînée contient les références vers ses objets cellules; l’objet fichier contient la référence vers le descripteur fourni par le système d’exploitation. On dit que les objets encapsulent ces données: c’est une forme de type de donnée abstrait.

Pour communiquer entre eux, les objets s’envoient des messages. Il n’y a pas de procédures, seulement des méthodes qui répondent à certains messages. Pour additionner deux entiers par exemple, on écrit 2 + 3, comme en arithmétique classique. Mais en Smalltalk il faut lire cette expression comme « Passer le message +3 à l’objet 2 ». L’objet 2 contient une méthode qui interprète le message +3 comme une addition avec l’objet 3, ce qui retourne un nouvel objet: 5. On ne pense plus alors en termes d’opérateur (+) et d’opérandes (2 et 3), mais d’un objet (2) qui reçoit un message (+3). C’est le changement de paradigme majeur de la programmation par objets:

On the one hand, the act of assembling expressions into statements and then into methods is not very different from conventional programming. On the other hand, the experience is totally different, for the objects which populate and traverse the code are active entities, and writing expressions feels like organizing trained animals rather than pushing boxes around. [Kay93]

Le passage de messages est une métaphore uniforme. Pour additionner deux points p1 et p2, on écrira p1 + p2. Pour concaténer deux chaînes de caractères s1 et s2, on écrit de même s1 + s2. Le sens du message + dépend de l’objet qui le reçoit et l’interprète. C’est le mécanisme de liaison dynamique.

+ t1
  [^ Point new x: x + t1 as PtX y: y + t1 as PtY]

Le programmeur ne crée pas des objets directement. Il décrit des classes. Une classe est un moule à partir duquel on peut créer des objets. Une classe contient les données privées manipulées par l’objet (ses attributs), et ses méthodes, qui sont partagées entre toutes les instances de cette classe.

Si un objet appartient à une classe, il observe le comportement décrit par cette classe. Mais les classes sont elles-mêmes des objets, et peuvent hériter d’autres classes. Lorsqu’une classe B hérite d’une classes A, tous les messages non capturés par la classes B sont traités par la classe A. La classe Integer va par exemple hériter de la classe Number, qui définit les opérations de comparaison <, > et =. Ces comparaisons sont définies à partir de la soustraction, qui n’est pas un message interprété par Number directement, seulement par les classes qui en hérite: Integer, mais aussi Float ou Natural. En conséquence, la classe Integer hérite du comportement de la classe Number, ce qui permet de réutiliser les comportements, et de factoriser le code.

< t1
  [^ self - t1 < 0]
> t1
  [^ self - t1 > 0]
= t1
  [^ self - t1 = 0]

Pour Ingalls, co-auteur de Smalltalk, la modularité dans un système complexe c’est de ne jamais dépendre des détails internes d’un autre objet. Les classes et le passage de message contribuent à forcer cette barrière:

Objects are created and manipulated by sending messages. The communication metaphor supports the principle of modularity, since any attempt to examine or alter the state of an object is sent as a message to that object, and the sender need never know about internal representation.

[…]

The class is the natural unit of modularity, as it describes all the external messages understood by its instances, as well as all the internal details about methods for computing responses to messages and representation of data in the instances. [Ing78]

Le paradigme objet favorise l’extensibilité. Ingalls donne comme exemple l’ajout d’un nouvel objet au système, et les modifications nécessaires pour représenter cet objet sur la sortie standard. Dans un système qui contiendrait une fonction print centrale, c’est cette fonction qu’il faudrait modifier. Elle pourrait être large et compliquée, et il faudrait faire attention à ne pas affecter l’affichage des autres objets. En Smalltalk, tous les objets sont affichables s’ils répondent au message printon: s. Du coup, il suffit d’ajouter cette méthode dans le nouvel objet, sans avoir à toucher au reste du système. La nouvelle fonctionnalité est localisée dans l’objet que l’on ajoute. Le système est extensible.

Un autre avantage est la recompilation indépendante des classes. Les objets ne dépendent pas de la représentation interne d’autres objets. Modifier ou ajouter un champ à la classe Rectangle n’impacte que le code généré pour cette classe, jamais le code des classes extérieures. Les classes peuvent donc être compilées indépendamment.

L’héritage de classes permet la réutilisation de code. Mais une classe ne peut avoir qu’un seul parent, ce qui force une hiérarchie des objets du système sous forme d’arbre qui peut s’avérer inflexible. Dans l’exemple ci-contre, trois classes ont des opérations en commun qui ne peuvent pas être partagées seulement par héritage car leur intersection est nulle. L’implémentation de Smalltalk pour l’ordinateur STAR de Xerox permet à une classe de réutiliser les méthodes de plusieurs classes à la fois par le mécanisme des traits [CBL+82].

Un trait décrit une fonctionnalité qui peut être réemployée par plusieurs classes; il contient une ou plusieurs méthodes et leurs implémentations, ainsi que les attributs utilisés par ces méthodes. Une classe peut implémenter plusieurs traits; on passe d’un arbre à un graphe dirigé acyclique. Un trait peut en outre implémenter des traits à son tour, ce qui permet de regrouper des traits souvent utilisés ensemble.

Pour Kay, l’ingrédient clé de la flexibilité de la programmation par objets est le retard de liaison causé par le passage de messages. On n’appelle plus une procédure qui correspond à un code spécifique, mais on passe une requête. L’opération effectuée, le code invoqué, dépend entièrement de l’objet qui reçoit cette requête. Avec l’héritage, cet objet n’est pas nécessairement connu du code appelant; on peut effectuer des opérations sur des Number sans savoir si ce sont des instances d’Integer ou de Float avec lesquelles on traite. Le message est un lien indirect, et puisqu’il est indirect, il peut être plus facilement modifié, comme l’exemple d’Ingalls le montre.

L’indirection est donc un principe général utile pour le détournement que l’on souhaite réaliser. Mais cette indirection n’est pas restreinte aux seuls langages à classes. On peut aussi faire de la programmation par objets avec des prototypes.

Les langages à prototypes poursuivent l’approche du tout objet. Il n’y a plus de classes, plus d’instances, seulement des objets.

Taivalsaari [Tai97] voit entre ces deux approches une distinction philosophique. Les langages à classes (SIMULA, Smalltalk, Java) suivent l’école d’Athènes: de Platon et d’Aristote. Platon distingue les formes, qui sont les descriptions idéales des choses, des instances de ces formes, qui sont leur manifestation concrète et imparfaite. Platon considère que les formes sont plus réelles que leurs instances. Pour Aristote, il existe une unique taxonomie correcte de toutes les choses naturelles, et il souhaite l’établir. Il classe une chose à partir de ses propriétés essentielles (le genre), et ses propriétés qui la distinguent les autres choses du même genre (le différentiel).

Aristote, comme Platon, voyaient la classification comme absolue: la taxonomie est la seule vraie hiérarchie des choses. À l’inverse, Wittgenstein la considère subjective [Wit53]. Certains concepts sont difficiles à définir en intension, par une liste de propriétés communes à toutes ses instances. Wittgenstein propose plutôt la notion de ressemblance familière. La chose n’est plus déterminée par une définition absolue, mais par ses similarités avec des prototypes représentatifs.

De cette distinction philosophique, Taivalsaari tire trois conclusions:

• Il n’y a pas de hiérarchie de classe optimale. Le choix est subjectif et dépend non seulement des besoins de l’application, mais surtout de son concepteur. Les langages à classes nécessitent d’établir une hiérarchie, et celle-ci est souvent inflexible. Lorsque le choix de cette hiérarchie sera remis en question, il sera difficile de la modifier sans impacter une grande partie du système.
• Dans une hiérarchie de classes, ce sont les classes du milieu qui sont souvent les plus représentatives des objets de l’application. Les classes les plus hautes sont trop abstraites pour être utiles, et les classes les plus basses trop spécifiques pour être réutilisables.

• Les prototypes correspondent davantage au processus de réflexion humain. En abordant un domaine, on ne commence pas par établir des classes abstraites qui capturent l’essence des objets considérés. On part d’exemples, de cas particuliers, que l’on relie entre eux par similarités. Et ce n’est qu’après avoir accumulé de nombreux exemples que leurs similarités résonnent suffisamment pour qu’émergent des formes abstraites. La généralisation est la dernière étape de la réflexion.

Ces conclusions suggèrent que les langages à prototypes sont plus flexibles pour modéliser le monde. Les classes sont trop rigides, trop abstraites; les prototypes sont plus dynamiques. Ce point de vue fait écho à Lieberman [Lie86], qui illustre la différence entre les deux mécanismes à l’aide d’un éléphant nommé Clyde.

Si je rencontre Clyde l’éléphant, je vais construire un modèle mental de Clyde qui contiendra tout ce que j’ai appris sur lui: sa taille, la couleur de sa peau, son nombre de pattes, la forme de ses oreilles, etc. Ce savoir, je peux le réutiliser lorsque je rencontre un autre éléphant, Fred. Mais comment ce partage s’effectue exactement? De deux façons: on peut utiliser les classes, ou les prototypes.

En utilisant les classes, on construit le concept abstrait d’éléphant, qui contient toutes les propriétés que l’on juge essentielles aux éléphants. Clyde et Fred sont des instances de ce concept (cette classe); l’instantiation est un premier mécanisme de partage du savoir. Le second est l’héritage: si Fred et Clyde ont des propriétés communes, non essentielles, comme des grandes oreilles, alors je peux créer un sous-concept d’éléphant africain qui hérite du concept d’éléphant pour les représenter spécifiquement.

En utilisant les prototypes, je ne crée pas de concept. Si Clyde est le premier éléphant que je rencontre, il devient mon éléphant prototype. Si on me demande la couleur d’un éléphant, je suppose qu’ils sont tous de la même couleur que Clyde, et je réponds « gris ». Puis je rencontre Fred, et il ressemble beaucoup à Clyde. Je lie les deux en disant que Clyde est le prototype de Fred; il est comme Clyde, mais avec un nom différent. Si Fred a d’autres particularités, s’il a la peau bleue, je l’inscris seulement dans sa représentation. Si on me demande la couleur de Fred, je n’ai besoin que d’inspecter la représentation de Fred. Mais si on me demande combien de pattes a Fred, il en a autant que Clyde, son prototype. L’information non spécifique à Fred est sauvegardée par son prototype: c’est le mécanisme de délégation.

Self [US91], est un langage à prototypes plutôt représentatif. Comme en Smalltalk, tout est objet. Mais à l’inverse de Smalltalk, il n’y a pas de classes. Le programmeur ne crée pas une hiérarchie de concepts, mais des familles d’objets. Cette absence de structure est un avantage dans un processus de développement interactif: on peut raffiner les objets à l’exécution. Mais pour ses auteurs, c’est aussi un inconvénient en pratique:

Reducing the number of basic concepts in a language can make the language easier to explain, understand, and use. However, there is a tension between making the language simpler and making the organization of a system manifest. As the variety of constructs decreases, so does the variety of linguistic clues to a system’s structure.

[…]

The absence of class-instance distinction may make it too hard to understand which objects exist solely to provide shared information for other objects. Perhaps SELF programmers will create entirely new organizational structures. In any case, SELF’s flexibility poses a challenge to the programming environment; it will have to include navigational and descriptive aids.

Les langages à prototypes sont particulièrement adaptés pour représenter des objets qui ont un comportement unique, comme dans des interfaces graphiques [Smi95]. Mais il arrive souvent que l’on doive gérer de nombreux objets similaires. Les concepteurs de Self décrivent une façon de structurer ces objets à l’aide de traits [UCC+91]. Comme en Smalltalk, un trait est un objet qui regroupe les méthodes utilisées par plusieurs objets. On crée ensuite un objet prototype qui étend ce trait, et fournit une implémentation et des valeurs d’attributs par défaut. Tous les objets de la même famille étendent ce prototype. Cette structure permet de séparer les méthodes (le comportement) des attributs (l’état).

Les traits de Self sont proches des traits de Smalltalk, a une distinction près. En Smalltalk, le langage fait une distinction syntaxique entre classes, traits, et instances, alors qu’en Self ce sont tous des objets qui ont juste des rôles différents.

Les concepteurs de Self remarquent que le mécanisme de délégation est plus général que l’héritage. Le premier émule le second, mais pas l’inverse. En outre, la délégation et le clonage facilitent l’adaptation dynamique du programme. Sans hiérarchie à respecter, il est plus facile de remplacer des objets par d’autres, qui ont un comportement différent. La délégation est un autre exemple d’indirection, et donc un mécanisme utile pour le détournement.

D’un autre côté, les langages à classes, en imposant une structure supplémentaire, peuvent être mieux optimisés, mais sont moins adaptés pour des situations où la taxonomie n’est pas bien définie.

Mais cette opposition n’est pas irréconciliable. Les mécanismes réflexifs sont capables de proposer aussi bien l’héritage que la délégation au sein d’un même langage. Et ils sont sont aussi très utiles pour le détournement.

La réflexion n’est pas restreinte aux implémentations de langages à objets, ni aux langages de programmation. Les membres de Xerox PARC se sont donc intéressés à appliquer la réflexion à d’autres systèmes, ce qu’ils appellent plus généralement « implémentation ouverte » [Rao91,Kic96,MLM+97,KLL+97].

One meaning of the word reflect is to consider some subject matter. Another is to turn back something (e.g. light or sound). Punning on these two meanings, we get the notion of turning back one’s consideration or considering one’s own activities as a subject matter. Our ability as humans to reflect in this sense has been credited, since Aristotle, with our success in adapting to new situations and mastering our environment. Naturally, it was widely conjectured in the artificial intelligence community that by providing reflective capabilities to computational systems, we would obtain systems with greater plasticity and consequently, enhanced functionality. [Rao91]

[Rao91] commence par remarquer que tout système définit une interface qui peut être vue comme un langage. Tout système est donc aussi un interpréteur de son interface. Alors, la réflexion dans les langages de programmation n’est qu’un cas particulier, et on peut l’appliquer à tout système qui expose une interface. Et comme un interpréteur réflexif permet au programme d’inspecter et de modifier le processus engendré par l’interpréteur, il en va de même pour un système plus général.

Mais à quoi ressemble un système réflexif, en général? Rao définit un système à implémentation ouverte comme un système ayant deux interfaces: l’interface de base, qui est l’interface classique associée au système, et l’interface de métaniveau, qui révèle en partie l’implémentation de l’interface de base.

Pour illustrer ces deux interfaces, il prend l’exemple d’un système de gestion de fenêtres pour CLOS, appelé Silica. Dans un système de gestion de fenêtres, l’interface de base permet de construire des arbres de fenêtres, d’interroger et de modifier ces arbres (pour accéder aux fenêtres, en ajouter, les retirer…), et de lire et écrire dans les fenêtres.

Comment les fenêtres et la structure d’arbre sont implémentés peut impacter l’utilisateur du gestionnaire de fenêtres. En particulier, Rao prend l’exemple d’un tableur qui crée une fenêtre pour chaque cellule de la feuille de calcul. Ce choix peut paraître curieux, mais est justifié par la réutilisation des fonctionnalités du gestionnaire de fenêtres (capture de la souris, peindre les cellules en fonction de leur visibilité, …) pour simplifier l’implémentation du tableur. Dans un gestionnaire de fenêtres naïf, il faut allouer de la mémoire pour chaque fenêtre, alors que dans le cas du tableur on pourrait partager bon nombre de propriétés entre les fenêtres utilisées comme cellules. De même, lorsque qu’un clic de souris est détecté par le gestionnaire de fenêtres, il faut parcourir les arbres de fenêtres pour déterminer la fenêtre qui est actuellement au dessus des autres, car les fenêtres peuvent se superposer. Mais dans un tableur, les cellules ne peuvent pas se superposer, donc on peut déterminer le clic de souris directement grâce à ses coordonnées. Ces optimisations ne sont possibles que si le gestionnaire de fenêtres laisse au programme client la possibilité de modifier son implémentation. En l’occurrence, Silica est un système à implémentation ouverte, et Rao montre qu’il peut supporter ces optimisations en utilisant l’interface d’implémentation.

Pour réaliser cette interface, Silica est construit en deux couches: une couche qui implémente les fenêtres, pour fournir l’interface de base; et une couche qui implémente les contrats, pour stipuler la politique d’utilisation des fenêtres par le client de l’interface (comment redessiner une fenêtre, comment rapporter les événements souris, comment gérer les sous-fenêtres, …).

Le client de l’interface de base n’a pas besoin de modifier les contrats par défaut. En revanche, c’est par cette couche qu’il faut passer pour réaliser les optimisations du tableur.

Mais il ne s’agit pas ici de simplement séparer le mécanisme de la politique; un système à implémentation ouverte ne propose pas nécessairement toute liberté au client. Tout comme un interpréteur peut n’exposer que certaines parties du langage par une interface réflexive, ici aussi un système à implémentation ouverte peut choisir l’étendue de son interface d’implémentation.

[KLL+97] donne des recettes pour construire ces systèmes, en fonction des besoins des programmes clients:

1. Le client n’a aucun contrôle: le système adapte son implémentation en observant le programme client.
2. Le client déclare son utilisation du système, et le système sélectionne une stratégie pré-établie.
3. Le client spécifie la stratégie parmi celles pré-établies par le système.
4. Le client fournit la stratégie au système.

Le degré 4 donne le plus de contrôle au client, mais on voit que d’autres styles d’implémentation ouverte sont possibles.

En somme, le concept d’implémentation ouverte répond au besoin de certains programmes d’avoir à optimiser des choix d’implémentation du système qu’ils utilisent. Le système laisse au programme la possibilité de modifier ces choix, statiquement ou même dynamiquement, via une interface d’implémentation. Le système peut être adapté à plus de cas qu’un système qui ne proposerait pas d’interface d’implémentation; le système à implémentation ouverte promet davantage de réutilisation de code.

On ne spécifie pas comment cette interface d’implémentation est rendue disponible par le système. Dans les interpréteurs, la réflexion est souvent utilisée, mais d’autres solutions sont envisageables suivant le système: l’inversion de contrôle, ou le patron de conception Stratégie seraient envisageables. Un autre bon candidat est la programmation par aspects.

Pour expliquer ce qu’est un aspect, [MKL97] part d’un exemple. Le système qui les intéresse prend une image en noir et blanc et lui applique une série de filtres; c’est une partie d’un système de reconnaissance de caractères. Ils souhaitent que le système soit facile à développer et à maintenir, mais aussi efficace, car les images traitées sont grandes, et les filtres rapidement coûteux à calculer.

Pour faciliter le développement, il suffit de créer des filtres composables. D’abord des filtres basiques, comme Or, And, Not, analogues des opérateurs communs sur les bits, mais appliqués aux images, pixel par pixel. Voici le code du filtre Or [KLM+97]:

(defun or! (a b)
  (let ((result (new-image)))
    (loop for i from 1 to width do
      (loop for j from 1 to height do
        (set-pixel result i j
          (or (get-pixel a i j)
              (get-pixel b i j)))))
     result))

Puis, à partir de ces filtres élémentaires, on peut en définir des plus complexes:

(defun remove! (a b)
  (and! a (not! b)))

(defun top-edge! (a)
  (remove! a (down! a)))

(defun horizontal-edge! (a)
  (or! (top-edge! a)
       (bottom-edge! a)))
...

On voit que les filtres complexes se définissent très facilement à partir des filtres élémentaires. Le code est clair, simple et direct, donc facile à écrire et à maintenir. Et pour ce faire, on n’a besoin que de composer des procédures.

En revanche, côté efficacité, c’est loin d’être optimal. Tous les filtres élémentaires, Or, And, Not créent une nouvelle image intermédiaire, et bouclent sur les pixels de l’image. Un filtre composite comme Remove appelle deux filtres élémentaires, et donc va créer deux images intermédiaires, et itérer deux fois sur tous les pixels de l’image: une fois dans And, et une fois dans Not. Le gaspillage est encore plus important pour les filtres plus complexes, comme HorizontalEdge.

Une version optimisée de Remove ne contiendrait qu’une seule boucle et ne créerait qu’une seule image, le résultat. Mais si on écrit cette version optimisée directement, on perd alors la composition des filtres élémentaires. Cherchant l’efficacité, les auteurs ont réécrit tous les filtres complexes directement. Le système efficace comporte trois optimisations majeures: la fusion de boucle, l’utilisation d’un bassin d’objets pour éviter l’allocation d’images intermédiaires, et la mémoïsation des résultats. Le système efficace comporte 35213 lignes de code, alors que la version simple, mais non efficace, en comporte 768; 5 fois moins de code à écrire, et à maintenir. C’est d’autant plus dommage que les versions optimisées suivent toujours le même motif: fusionner les boucles, pour combiner les opérations à l’intérieur des boucles plutôt qu’à l’extérieur.

Alors, peut-on réconcilier l’efficacité avec la simplicité de la composition des filtres? Peut-on arranger les procédures différemment, pour satisfaire les deux buts à la fois? Les auteurs pensent que non. La composition hiérarchique des filtres est incompatible avec la composition nécessaire pour optimiser les boucles. Composer les filtres hiérarchiquement c’est composer les fonctionnalités offertes par les filtres, de façon simple et homogène. Mais pour optimiser ces filtres complexes, il faut fusionner les boucles qui appartiennent à des procédures différentes. La composition hiérarchique est réalisée par la composition des procédures du langage de programmation, mais la seconde composition, qui dépasse l’unité de la procédure, n’est pas supportée par le langage, et doit être réalisée manuellement.

C’est la distinction que les auteurs font entre composants et aspects. Si une fonctionnalité du système peut être implémentée par une procédure (ou une méthode, un objet, une API), alors c’est un composant; sinon, c’est un aspect. Dans leur expérience, un aspect ne concerne pas la fonctionnalité principale du système, mais plutôt des propriétés orthogonales ou complémentaires au système, comme la performance, ou la gestion d’erreurs. Le but de la programmation par aspects est de pouvoir exprimer clairement ces deux catégories de fonctionnalités:

The goal of AOP is to support the programmer in cleanly separating components and aspects from each other, by providing mechanisms that make it possible to abstract and compose them to produce the overall system. This is in contrast to [classic] programming, which supports programmers in separating only components from each other by providing mechanisms that make it possible to abstract and compose them to produce the overall system.

Une implémentation par aspects reflète cette distinction. Pour une application écrite dans un langage classique, il y a trois éléments importants: le programme, le langage dans lequel le programme est écrit, et le compilateur pour ce langage. Pour une application écrite en programmation par aspects, on distingue: le programme des composants, le (ou les) programme des aspects, le langage des composants, le langage des aspects, et un compilateur qui prend en compte les deux langages en même temps, qu’on appelle le tisseur d’aspects.

Dans l’exemple des filtres d’images, le langage de composants est CommonLisp avec des primitives de plus haut niveau. Le filtre Or ne s’exprime plus avec une boucle, mais avec une construction plus déclarative:

(define-filter or! (a a)
  (pixelwise (a b) (aa bb) (or aa bb)))

Plutôt que de définir une fonction, on définit un filtre, qui itère sur chaque pixel avec l’itérateur pixelwise.

Les filtres ainsi définis sont passés au tisseur d’aspects, qui va interpréter le code pour récolter les filtres et itérateurs utilisés: un filtre complexe, comme Remove, va faire appel aux filtres primitifs And et Not; le tisseur lui associe donc ces filtres. Ce faisant, le tisseur construit la seconde composition, la composition que le langage procédural ne pouvait pas exprimer.

Dans un second temps, le tisseur passe cette information aux programmes d’aspects, qui vont pouvoir réaliser les trois optimisations; la fusion de boucle, la mémoisation, et le bassin d’objets. Chaque optimisation est un programme d’aspects différent. La fusion de boucle par exemple teste si les arguments d’un filtre ont une itération compatible avec l’itération faite par le filtre; si c’est le cas, on peut générer une seule boucle qui applique les opérations des arguments et du filtre:

(cond ((and (eq (loop-shape node) 'pixelwise)
            (eq (loop-shape node) 'pixelwise))
       (fuse loop input 'pixelwise
             ...)))

Enfin, dans ce système, le tisseur génère du code C pour chaque filtre.

Au final, l’implémentation par aspects a une performance comparable à l’implémentation optimisée manuellement, en seulement 4500 lignes de code (dont 3500 pour le tisseur), soit seulement 13% du code de la version optimisée. La version par aspects permet de clairement séparer les composants des aspects, ce qui atteint le but de simplicité d’écriture et de maintenance, mais sans sacrifier l’efficacité.

Dans cet exemple, il est intéressant de noter la place importante du tisseur. La version simple, mais inefficace, du programme ne comportait que 770 lignes. En 1000 lignes, la version par aspects décrit les filtres, et les trois programmes d’aspects qui correspondent aux optimisations. Même ordre de grandeur. Mais pour que la version par aspects fonctionne, elle nécessite le tisseur, et celui-ci fait 3 fois la taille du programme client. Même si des parties du tisseur peuvent être réutilisées pour d’autres programmes, le langage reste spécifique à la création de filtres pour traiter des images en deux dimensions. On peut se poser la question: si l’on souhaite appliquer la programmation par aspects, faut-il réimplémenter un tisseur pour chaque application? Y a-t-il d’autres façons de faire?

La caractéristique principale de la programmation par aspects est la distinction entre composants et aspects. Cette distinction, si elle apparaît au moment de la conception du programme doit être maintenue dans son implémentation. Tout mécanisme, toute façon de réaliser cette distinction dans le programme est donc compatible avec la programmation par aspects. Un langage spécifique pour l’application, qui permet de distinguer composants et aspects, est une façon de faire. La réflexion en est une autre.

Un système réflexif permet d’observer et de modifier le processus d’exécution du programme, au delà de la séparation entre procédures. Un système réflexif peut observer la pile d’appels, ou tous les messages reçus par une classe, ou par tous les objets du programme. La réflexion permet de composer un programme selon un axe complémentaire à celui des procédures; c’est donc un mécanisme de programmation par aspects. Les auteurs, certainement familiers avec le concept, le notent:

A reflective system provides the base language and (one or more) meta-languages that provide control over the base language’s semantics and implementation. In AOP terms, meta-languages are lower-level aspect languages whose join points are the « hooks » that the reflective system provides. AOP is a goal, for which reflection is one powerful tool. [KLM+97]

Et il y a d’autres mécanismes connus. Le try/catch, ou le mécanisme d’exceptions, transcende la frontière des procédures. Les exceptions ne sont qu’un cas particulier des continuations (call/cc en Scheme), qui permettent de manipuler le flot d’exécution du programme de façon arbitraire. Les variables à portée dynamique permettent de changer le comportement d’une procédure qu’on n’appelle pas directement; c’est une forme de recomposition, mais moins puissante que les précédentes.

Les auteurs de la programmation par aspects justifient la présence de ces mécanismes par le besoin des programmeurs d’exprimer les aspects dans des langages qui proposent de n’assembler que des composants. Mais bien qu’ils permettent d’exprimer des aspects, ces mécanismes sont considérés de bas-niveau, au même titre que la réflexion. Un langage d’aspects dédié, comme celui utilisé pour optimiser les filtres d’image, est déclaratif, et correspond plus directement à l’intention du programmeur. Fournir les outils qui permettent au programmeur d’exprimer cette intention est un des buts de la programmation par aspects:

When we say « separation of concerns » we mean the idea that it should be possible to work with the design or implementation of a system in the natural units of concern – concept, goal, team structure etc. – rather than in units imposed on us by the tools we are using. We would like the modularity of a system to reflect the way « we want to think about it » rather than the way the language or other tools force us to think about it. In software, Parnas is generally credited with this idea. [KHH+01]

Néanmoins, créer un langage dédié pour chaque application peut avoir un coût trop élevé pour adopter la programmation par aspects. Et tous les langages ne supportent pas les mécanismes de bas-niveau qui pourraient servir à exprimer des aspects. Ce sont les raisons qui vraisemblablement motivent le développement d’AspectJ.

AspectJ est un langage d’aspects pour Java [KHH+01]. Dans un système par aspects, il y a un langage d’aspects, ici AspectJ, et un langage de composants, ici ce sera Java. AspectJ est un langage d’aspect général, qui fournit des mécanismes de recomposition applicables à tout programme Java. Et pour ce faire, AspectJ propose deux types de recomposition.

En premier, les déclarations inter-types permettent de définir, au sein d’un même aspect, des attributs et des méthodes pour une ou plusieurs classes [Asp03]. Ces attributs augmentent les classes au moment de la compilation. La classe est, en Java, et comme dans d’autres langages à classes pour la programmation objet, l’unité de composition. Elle décrit les attributs et les méthodes partagées par toutes ses instances; c’est l’élément clé de la structure statique du programme. Comme c’est une unité de composition, une classe n’a pas vocation à pouvoir affecter les attributs et méthodes d’une autre classe. Mais un aspect est une unité de composition qui traverse la composition des composants, et c’est donc naturel de permettre, dans un aspect, d’ajouter attributs et méthodes à plusieurs classes. C’est une recomposition de la structure statique.

public int Point.x = 0;
public int Point.getX() { return this.x; }

Le second type de recomposition d’AspectJ permet de modifier la structure dynamique du programme; de modifier le comportement du programme à l’exécution. C’est rendu possible par trois constructions:

• les jonctions (joinpoints) sont des points d’exécution du programme bien définis: l’appel d’une méthode, l’affectation d’un attribut, la création d’une instance de classe, etc.
• les coupes (pointcuts) permettent de sélectionner un ensemble de jonctions, et d’en extraire de l’information comme le nom de la méthode appelée, et ses arguments.
• les méthodes d’aspect (advice) contiennent le code à exécuter lorsque le programme atteint les jonctions décrites par la coupe de la méthode. Une méthode d’aspect décrit également comment le code doit s’insérer dans le processus d’exécution: avant, après, ou autour de la jonction.

Le programmeur ne manipule pas les jonctions directement, mais utilise les coupes pour les sélectionner dans des méthodes d’aspect. On pourra ainsi écrire:

after(): call(void Point.setX(int)) {
  System.out.println("setX was called")
}

pour déclencher l’affichage sur la sortie standard après (after) tout appel (call) de la méthode Point.setX(int) dans le programme.

Les coupes sont des prédicats, et peuvent être combinées avec les opérateurs booléens &&, ||, et !:

execution(void Point.setX(int))
|| execution(void Point.setY(int))

call(void FigureElement.incrXY(int, int))
&& !instanceof(FigureElement)

Ce qui permet de capturer des ensembles de jonctions pertinents pour cibler une préoccupation particulière. AspectJ permet d’ailleurs de nommer les coupes pour plus de clarté, et pour pouvoir les partager:

pointcut moves():
  execution(void FigureElement.incrXY(int, int))
  || execution(void Point.setX(int))
  || execution(void Point.setY(int));

after(): moves() {
  ...
}

Une coupe nommée peut être utilisée par une méthode d’aspect, mais aussi par n’importe quelle autre coupe, ce qui encourage la composition, et réduit la duplication de code.

Les jonctions exposées par AspectJ évoquent fortement les réifications du protocole des métaobjets (voir 3.4): appel et exécution de méthode, création d’une instance. Mais il y a d’autres coupes intéressantes qui sont applicables à n’importe quel langage à procédures: withincode(method) permet de cibler n’importe quelle jonction qui émane de la méthode donnée. C’est particulièrement utile associé à d’autres coupes:

call(void m()) && withincode(void m())

Là on capture uniquement les appels récursifs directs de m. Inversement, si l’on souhaite capturer les appels non récursifs à m, on peut utiliser cflow:

call(void m()) && !cflow(call(void m()))

cflow(coupe) capture toutes les jonctions qui sont dans le flot de contrôle de la coupe passée en argument; c’est à dire, ici, toutes les jonctions qui existent après qu’au moins un appel de m soit présent sur la pile d’appels. Dans l’exemple, la coupe composée capture les appels de m lorsqu’aucun appel à m n’existe sur la pile, ce qui exclut les appels récursifs (directs et indirects).

À travers les différents types de jonctions observées, le langage d’aspects d’AspectJ permet de capturer de nombreux points d’exécution du programme, et d’exécuter du code au delà des frontières délimitées par les classes et les méthodes de Java. Contrairement au langage spécifique d’aspects du premier papier, le mécanisme est ici général; il s’applique à n’importe quel programme Java. Le langage permet donc de séparer les composants des aspects, et ce pour n’importe quelle application.

Les auteurs donnent l’exemple d’un aspect qui enregistre toutes les erreurs levées par toutes les méthodes publiques d’un package:

aspect SimpleErrorLogging {
  Log log = new Log();

  pointcut publicEntries():
    execution(public * com.xerox.printers.*.*(..));

  after() throwing(Error e): publicEntries() {
    log.write(e)
  }
}

Cet aspect est équivalent à enrober chaque appel dans un bloc try/catch et appeler log.write sur l’erreur levée. Mais ici c’est fait en 8 lignes, pour toutes les classes du package, même les classes futures.

Un désavantage du langage spécifique est qu’il faut réécrire le programme des composants dans le nouveau langage à composants. Ici, le langage d’aspects manipule directement le langage à composants déjà existant: Java. Un programmeur peut donc directement appliquer la programmation par aspects à un programme Java existant, simplement en ajoutant des programmes d’aspects, et en invoquant le tisseur à la compilation. Aucune modification du programme des composants n’est nécessaire, mais pourtant ce programme va être modifié par des aspects. Les déclarations inter-types peuvent étendre des classes sans modifier le code source de celles-ci. Et les méthodes d’aspect vont modifier le comportement à l’exécution de plusieurs classes, ici encore sans en altérer le code source.

La programmation par aspects nous donne donc deux façons de modifier un programme: dans les filtres d’images, la modification est explicite, car il faut réécrire les filtres pour expliciter quel type de boucle est utilisé; mais dans AspectJ, le programme est modifié implicitement par les aspects.

En revanche, dans les deux cas, les programmes des composants ne dépendent pas des programmes d’aspects pour fonctionner. Dans l’exemple de l’aspect de journalisation des erreurs, on pourrait compiler le programme sans cet aspect (sans tisser l’aspect), et on obtiendrait un programme qui a les mêmes fonctionnalités, mais sans la journalisation. Aucune modification du code du programme n’est nécessaire pour activer ou désactiver la journalisation; c’est uniquement le choix des aspects à activer au moment du tissage qui détermine les fonctionnalités du programme final. De même, dans les filtres d’image, ne pas inclure les programmes d’aspects n’impacte que l’efficacité du programme, mais pas son résultat. On dira alors que, dans ces deux cas, les aspects sont oubliables (obliviousness property).

Le but de la programmation par aspects est louable: distinguer les composants des aspects dans le programme, c’est mettre de l’ordre, c’est séparer les choses différentes, et regrouper les fonctionnalités similaires. Le bénéfice, c’est qu’un code source ordonné est, a priori, plus simple, et donc plus facile à maintenir. Mais il y a aussi des inconvénients à faire cette distinction [Ste06].

Le fait que les aspects capturent l’exécution de façon implicite nuit à la compréhension modulaire du programme. On ne peut plus raisonner sur le comportement d’un module seulement en regardant son code, il faut prendre en compte tous les aspects qui peuvent intervenir pendant l’exécution du code du module. La compréhension du programme devient nécessairement globale: il faut connaître tous les aspects qui peuvent s’y appliquer, et en prenant en compte les aspects qui pourraient être activés dynamiquement. C’est un problème considéré par Kiczales et Mezini comme inhérent à l’approche de la programmation par aspects [KM05].

Une façon d’atténuer ce problème est de faire apparaître, dans l’environnement de développement du programmeur, les endroits du code où des aspects pourraient s’exécuter. L’article qui introduit AspectJ [KHH+01] montre une telle fonctionnalité dans l’éditeur de texte Emacs. Les aspects deviennent explicites, mais l’intégrité du module demeure compromise. Le système nécessite toujours une analyse globale pour être compris, et les aspects traversent encore la barrière du module, ce qui empêche de développer le module indépendamment des aspects.

Les aspects capturent les points d’exécution du module, ce qui revient à dire que tout module expose une interface implicite qui est utilisée par les aspects. Que cette interface soit implicite rend les aspects fragiles: tout changement du code peut rendre des aspects inopérables. Mais c’est aussi le fait qu’elle soit implicite qui permet aux aspects d’être oubliables, et donc de pouvoir s’appliquer à plusieurs points d’exécution sans avoir à modifier le code des composants. L’interface implicite est donc un choix de conception du système, à adopter si le besoin de modifier plusieurs modules en un seul lieu (dans un aspect) surpasse le besoin de comprendre et développer les modules indépendamment.

La contribution principale de la programmation par aspects est de distinguer deux types de programmes qui cohabitent dans un même système: les composants, en charge de la fonctionnalité du système, et les aspects, qui décrivent des préoccupations orthogonales à la fonctionnalité principale. La programmation par aspects est donc avant tout une méthodologie.

Le langage des jonctions et des coupes, popularisé par AspectJ, est le mécanisme principalement associé à la programmation par aspects. Mais il y d’autres façons de réaliser la séparation des composants et des aspects: on peut utiliser la programmation événementielle, les try/catch, les variables à portée dynamique, ou créer un langage dédié pour les composants et un pour les aspects. Dans le monde de la programmation fonctionnelle, les monades sont aussi un moyen de séparer les préoccupations orthogonales [Meu97,HO07].

Il ne faut donc pas mélanger la méthodologie—le but philosophique de la programmation par aspects—et les (multiples) mécanismes qui permettent d’atteindre ce but. En particulier, on peut faire de la programmation par aspects sans AspectJ, sans jonctions, sans coupes, et sans méthodes d’aspects. C’est le cas du langage des filtres d’images.

Enfin, la programmation par aspects n’est pas une balle en argent. Les jonctions et les coupes sont oubliables par les composants, mais sacrifient le raisonnement modulaire. Les autres mécanismes qui permettent de séparer les composants des aspects ont également cette caractéristique: recomposer le flot d’exécution dynamiquement rend le programme moins prévisible, et moins compréhensible. Tous ces mécanismes présentent donc des avantages et des inconvénients, et le choix du bon compromis est dans les mains du concepteur du système.

Wadler définit le problème ainsi [Wad98]:

The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).

Dans un langage fonctionnel, une façon courante d’implémenter un interpréteur est en utilisant un type algébrique de données pour représenter les termes. En Haskell par exemple, on définit un simple langage arithmétique par le type algébrique suivant:

data Term = Constant Int
	  | Plus Term Term
	  | Mult Term Term

Term est un type qui a trois variantes: un terme est soit une constante (Constant, un entier), une addition (Plus), ou une multiplication (Mult).

La syntaxe du type algébrique correspond à la façon usuelle de définir des grammaires: la forme de Backus-Naur (BNF). Une BNF pour le langage arithmétique pourrait être:

<term> ::= <int> | <term> + <term> | <term> * <term>
<int>  ::= 0 | 1 | 2 ...

Ici encore, un terme a trois variantes. L’addition et la multiplication contiennent d’autres termes, et la variante int ne contient qu’un nombre terminal. On voit que le type algébrique est suffisamment proche de la BNF pour rendre la traduction en code Haskell triviale. Les grammaires pour les langages de programmation étant souvent définies par une BNF, le type algébrique est la solution la plus évidente pour les représenter.

Constant, Plus et Mult sont les constructeurs du type Term, qui permettent de créer des expressions du langage. L’expression 2 + 5 * 3 sera construite par:

Plus (Constant 2) (Mult (Constant 5) (Constant 3))

Cette valeur représente l’expression 2 + 5 * 3, et nous donne en même temps un arbre syntaxique abstrait de cette expression.

Pour évaluer l’expression arithmétique, il faut évaluer l’arbre syntaxique et produire un nombre en retour. C’est le rôle de l’interpréteur du langage, qui sera donc une fonction du type algébrique. Dans la terminologie de Wadler, ces fonctions sont appelées des opérations.

L’opération principale est l’opération d’évaluation qui donne un sens à chaque terme du langage. Par exemple, on souhaite évaluer les expressions de notre langage arithmétique en suivant le sens usuel de l’addition et de la multiplication d’entiers. C’est à dire, pour évaluer Plus t1 t2, on évalue t1 et t2 pour obtenir des entiers, puis on les additionne. En Haskell, on écrira l’évaluation en traitant les trois variantes séparément, par pattern matching:

1: eval :: Term -> Int
2: eval (Constant n) = n
3: eval (Plus t1 t2) = eval t1 + eval t2
4: eval (Mult t1 t2) = eval t1 * eval t2

La première ligne donne le type de l’opération: elle consomme un terme pour produire un entier. Chaque variante de terme est traitée explicitement sur chaque ligne. Si le terme est une constante, c’est la ligne 2 qui sera exécutée, si c’est un Plus, la ligne 3, et ainsi de suite.

On remarque que l’évaluation est récursive pour Plus et Mult. La définition du type algébrique l’était déjà: Term est utilisé dans sa propre définition. Les grammaires de langage sont souvent récursives, pour permettre la construction de grandes expressions à partir de simples éléments. Même un langage aussi simple que celui-ci exhibe cette récursion.

On peut maintenant évaluer l’expression 2 + 5 * 3:

> eval (Plus (Constant 2)
             (Mult (Constant 5) (Constant 3)))
17

Un interpréteur peut définir plusieurs opérations. Wadler prend l’exemple d’un afficheur (pretty-printer), une opération d’affichage des arbres syntaxiques dont la sortie est plus amicale pour l’œil humain. Typiquement, l’afficheur d’un langage transforme l’arbre syntaxique en code source que le programmeur a l’habitude de lire. Appliqué aux expressions arithmétiques, il faut transformer le Plus, qui est préfixe, en + infixe, et faire disparaître le mot Constant qui n’apporte pas d’information capitale.

pp :: Term -> String
pp (Constant n) = show n
pp (Plus t1 t2) = pp t1 ++ " + " ++ pp t2
pp (Mult t1 t2) = pp t1 ++ " * " ++ pp t2

Si on affiche ainsi l’arbre syntaxique de l’expression 2 + 5 * 3, on obtient:

> pp (Plus (Constant 2)
           (Mult (Constant 5) (Constant 3)))
2 + 5 * 3

L’implémentation de l’affichage a la même structure que de l’implémentation de l’évaluation. On traite les trois variantes du type algébrique dans trois lignes différentes. Les deux variantes Plus et Mult sont définies récursivement, mais pas la variante Constant, qui est un terminal dans la grammaire. L’opération traite l’arbre syntaxique en partant de la racine, puis s’applique récursivement sur les nœuds de l’arbre jusqu’aux feuilles. Ce processus, commun aux interpréteurs, est parfois appelé une descente récursive.

Dans le problème de l’expression, on cherche à étendre le langage et son interpréteur de deux façons: en rajoutant des nouveaux termes au langage, et en rajoutant de nouvelles opérations.

Avec pp, on a déjà vu comment ajouter une nouvelle opération à l’interpréteur: il suffit de définir son comportement pour toutes les variantes des termes du langage. Term a 3 variantes, donc pp définit 3 cas. Notons aussi que pour ajouter l’opération il suffit d’ajouter du code à l’interpréteur. Aucune modification au code existant n’est requise. C’est une distinction importante, car il est souvent plus facile d’ajouter du code que de modifier du code existant.

On peut caractériser la complexité d’un changement de l’interpréteur comme la complexité d’un algorithme. L’opération pp comporte autant de lignes qu’il y a de variantes de Term, plus une pour sa signature. S’il y a v variantes, ajouter une opération aura une complexité de l’ordre de v lignes de code (O(v)). On note que ces lignes sont des additions par un ’+’: +O(v).

Étendre le langage demande de modifier le code existant. Si on veut rajouter un terme pour la soustraction, il faut commencer par étendre le type algébrique Term:

data Term = Constant Int
	  | Plus Term Term
	  | Mult Term Term
~         | Minus Term Term

C’est une ligne de code ajoutée. Mais c’est surtout une redéfinition du type algébrique. Typiquement, ajouter une variante induit une recompilation. On compte donc cette ligne comme une modification, et non un simple ajout.

Mais il faut aussi traiter cette nouvelle variante dans les opérations existantes:

  eval :: Term -> Int
~ eval (Minus t1 t2) = eval t1 - eval t2

  pp :: Term -> String
~ pp (Minus t1 t2) = pp t1 ++ " - " ++ pp t2

Au total, si on a p opérations dans l’interpréteur, le changement a une complexité de ~O(p).

Les deux changements sont linéaires en lignes de code ajoutées. Mais ajouter une opération et ajouter un terme ne sont pas des changements similaires pour autant. Ajouter un terme demande de modifier des définitions existantes dans l’interpréteur, alors que pour ajouter une opération il suffit d’adjoindre une nouvelle fonction.

Le problème de l’expression touche à la fois à la modularité et à l’extensibilité. À l’extensibilité, parce qu’on cherche à étendre l’interpréteur. Et à la modularité, parce qu’on cherche à découper les termes et les opérations en modules, à réduire leurs dépendances. Chaque extension devrait être restreinte à un module. Dans l’exemple en Haskell, ajouter une opération revient à ajouter un module sans affecter les autres, mais ajouter un terme requiert de modifier plusieurs modules.

Le problème de l’expression se pose aussi en programmation par objets.

Une façon classique d’implémenter un interpréteur en programmation par objets est de suivre le patron Interpréteur [GHJ+94]. Dans ce patron, chaque terme du langage est représenté par une classe, et chaque classe possède une méthode par opération.

abstract class Term { abstract int eval(); }

class Constant extends Term {
  int n;
  Constant(int n) { this.n = n; }
  int eval() { return n; }
}

class Plus extends Term {
  Term t1, t2;

  Plus(Term t1, Term t2) {
    this.t1 = t1;
    this.t2 = t2;
  }

  int eval() {
    return t1.eval() + t2.eval();
  }
}

class Test {
  public static void main(String[] args) {
    Term e1 = new Plus(new Constant(1),
                       new Constant(2));
    System.out.println(e1.eval()); //: 3
  }
}

Ici on a deux classes Constant et Plus qui implémentent l’opération eval. Tous les termes héritent de la classe abstraite Term qui définit les opérations supportées. Comme précédemment, l’évaluation de Plus.eval est récursive. Cette fois en revanche, la définition de l’opération eval n’est pas localisée en un seul endroit dans le code source, mais répartie dans les objets. Chaque classe de terme définit sa propre évaluation.

En conséquence, ajouter un terme au langage se fait simplement en ajoutant une nouvel classe:

class Mult extends Term {
  Term t1, t2;

  Mult(Term t1, Term t2) {
    this.t1 = t1;
    this.t2 = t2;
  }

  int eval() {
    return t1.eval() * t2.eval();
  }
}

On n’a pas à modifier le code des autres classes. Ajouter un terme au langage revient à ajouter +O(p) lignes, s’il y a p opérations.

En revanche, pour ajouter une opération comme l’affichage il faut modifier toutes les classes existantes:

abstract class Term {
~  abstract String pp();

class Constant extends Term {
~  String pp() { ... }

class Plus extends Term {
~  String pp() { ... }

class Mult extends Term {
~  String pp() { ... }

Cela implique de rajouter l’opération sur Term, puis de la définir pour tous les termes. Pour v termes, on a ~O(v) lignes modifiées. C’est la situation inverse que dans la décomposition fonctionnelle précédente.

Le problème de l’expression se manifeste ici aussi, puisqu’on peut ajouter des termes sans recompiler les classes existantes, mais ajouter des opérations demande de modifier les classes existantes.

Dans la décomposition fonctionnelle, le problème peut être résolu si l’on est capable d’étendre le types de données algébriques qui représente les termes, ainsi que les fonctions qui représentent des opérations. C’est la solution proposée par Löh et Hinze [LH06]. Ils suggèrent une extension à Haskell dans laquelle certains types de données algébriques et certaines fonctions sont ouverts. Il suffit de préfixer la définition d’un type ou d’une fonction par le mot-clé open pour les ouvrir. Par exemple, on définirait Term de cette façon:

open data Term :: *

Puis, chaque constructeur de terme sera donné par sa signature:

Constant :: Int -> Term
Plus :: Term -> Term -> Term
Mult :: Term -> Term -> Term

L’intérêt c’est que ce type reste ouvert: on peut lui ajouter des constructeurs après la déclaration du type.

De même, les fonctions ouvertes se déclarent ainsi:

open eval :: Term -> Int

Et de nouveaux cas peuvent être rajoutés pour traiter de nouvelles variantes de Term:

Plus :: Term -> Term -> Term
eval (Plus t1 t2) = eval t1 + eval t2

Ils proposent en outre de changer la stratégie de résolution du pattern-matching. Le comportement par défaut d’Haskell est de choisir le premier motif qui correspond (first-fit). Pour des fonctions ouvertes, ils suggèrent plutôt de choisir le motif le plus précis (best-fit). Ils décrivent la sémantique de cette nouvelle stratégie, ainsi que la sémantique des types et fonctions ouverts, et esquissent une implémentation par réécriture vers du code Haskell.

Ils notent au passage que l’on peut simuler cette extension avec des classes types (typeclasses). Les constructeurs de termes deviennent des types, et les opérations deviennent des classes types avec une seule méthode:

data Constant = Constant Int

class Eval a where
  eval :: a -> Int

instance Eval Constant where
   eval (Constant n) = n

data Plus a b = Plus a b

instance (Eval a, Eval b) => Eval (Plus a b) where
  eval (Plus a b) = eval a + eval b

On peut ainsi continuer d’ajouter de nouveaux termes et de nouvelles opérations, sans avoir à étendre le langage Haskell. Cette solution a l’avantage de séparer complètement les termes et les opérations; il n’y a plus de pression imposée par un axe principal (termes d’abord, ou opérations d’abord) car les relations entre variantes et opérations sont toutes décrites indépendamment.

Un inconvénient d’utiliser les classes types est que le type des expressions du langage dépend de l’expression. Les expressions 1 +2 et 1 n’ont pas de type commun:

Plus (Constant 1) (Constant 2) :: Plus Constant Constant
Constant 1 :: Constant

Avec les types et fonctions ouverts, toutes les expressions avaient le même type Term. Mais ici, on ne peut plus écrire des fonctions qui prennent des termes en paramètre, il faut nécessairement passer par les contraintes des classes types. En particulier, on ne peut plus inspecter les arbres syntaxiques.

Swierstra propose une solution au problème de l’expression qui contourne cet inconvénient [Swi08]. Sa solution est basée sur les classes types et la monade gratuite (free monad). Là aussi, chaque terme est implémenté par un type de données algébriques, et chaque opération est une classe type. Mais toutes les expressions ont le terme commun Term:

data Term f = In (f (Term f))

si bien que le type des expressions contient explicitement les termes qu’elle utilise:

e1 :: Term (Constant :+: Plus)
e1 = plus (plus (constant 1) (constant 2))
	  (constant 3)

Précédemment, le type était lié à l’arbre syntaxique de l’expression. Ici, ce n’est pas le cas; Constant et Plus n’apparaissent qu’une seule fois. Puisque le type Term est destiné à être étendu, il faut pouvoir distinguer les expressions suivant les termes qu’elles contiennent. La représentation des termes choisie ici permet cette distinction.

En revanche, l’approche de Swierstra requiert d’élaborer une machinerie complexe avant de pouvoir combiner les termes ainsi. L’utilisation de la monade gratuite est aussi critiquable pour son inefficacité [KI15].

Dans la décomposition objet qui suit le patron interpréteur, ajouter des opérations requiert de modifier toutes les classes. Gamma et al. notent que pour y remédier, on peut utiliser le patron visiteur [GHJ+94]. Dans le patron visiteur, les classes qui représentent les termes n’ont plus qu’une seule méthode accept(Visitor):

abstract class Term {
  abstract <T> T accept(Visitor<T> v); }

class Constant extends Term {
  int n;
  Constant(int n) { this.n = n; }
  <T> T accept(Visitor<T> v) {
    return v.forConstant(this); }
}

class Plus extends Term {
  Term a, b;
  Plus(Term a, Term b) {
    this.a = a; this.b = b; }

  <T> T accept(Visitor<T> v) {
    return v.forPlus(this); }
}

Les appels v.forConstant et v.forPlus impliquent l’interface suivante pour le visiteur:

interface Visitor<T> {
  T forConstant(Constant c);
  T forPlus(Plus p);
}

Pour ajouter une opération, il faut maintenant créer un visiteur qui doit obéir à cette interface:

class Eval implements Visitor<Integer> {
  public Integer forConstant(Constant c) {
    return c.n;
  }

  public Integer forPlus(Plus p) {
    return p.a.accept(this) + p.b.accept(this);
  }
}

À chaque terme correspond une méthode. Pour tester, il suffit de passer une instance de ce visiteur à une expression:

Term e1 = new Plus(new Constant(1), new Constant(2));
System.out.println(e1.accept(new Eval()));

D’un premier coup d’œil on pourrait se dire que l’on a juste retrouvé la décomposition fonctionnelle, en plus verbeux. L’opération Eval contient une méthode pour chaque terme, et si l’on souhaite ajouter des termes, il faudra ajouter une méthode pour ce terme à Eval et à l’interface Visitor.

Krishnamurthi et al. [KFF98] proposent donc le protocole du visiteur extensible pour pouvoir ajouter des termes sans affecter les opérations existantes. Pour ajouter un terme dans le visiteur extensible, il faut ajouter une classe qui représente ce terme:

class Mult extends Term {
  Term a, b;
  Mult(Term a, Term b) { this.a = a; this.b = b; }
  <T> T accept(Visitor<T> v) {
    return ((VisitorForMult<T>)v).forMult(this);
  }
}

Notons ici la conversion forcée de Visitor en VisitorForMult. L’interface Visitor ne sait pas traiter un terme Mult, mais on peut étendre cette interface par une autre. Si un visiteur ne sait pas traiter des Mult, cette conversion causera une exception. Le programme n’est donc pas sûr.

Il faut maintenant définir cette nouvelle interface:

interface VisitorForMult<T> extends Visitor<T> {
  T forMult(Mult m);
}

On ne modifie pas Visitor; on ajoute seulement une interface pour Mult. De même, pour étendre l’opération Eval:

class EvalForMult extends Eval
  implements VisitorForMult<Integer>
{
  public Integer forMult(Mult m) {
    return m.a.accept(this) * m.b.accept(this);
  }
}

Si bien que l’ajout du terme Mult ne modifie aucune classe existante. Et comme ajouter une opération sur tous les termes existants revient à implémenter les différents visiteurs, là non plus on ne modifie pas de classes existantes.

L’inconvénient restant de cette approche est la lourdeur structurelle du protocole. Il faut implémenter des interfaces, des visiteurs, jongler avec des types génériques, des conversions…

D’autres solutions plus simples existent. Odersky et Zenger utilisent le langage Scala, et notamment les mixins et l’auto-référence pour résoudre le problème de l’expression en préservant la sûreté [OZ05]. Findler et Flatt utilisent également les mixins pour résoudre le problème en MzScheme [FF98]. Pour Ernst, la solution est triviale dans les langages qui disposent du polymorphisme de famille [Ern04]. Et plus récemment, Wang et Oliveira montrent que la covariance peut suffire pour préserver la sûreté, ce qui donne une solution simple même en Java [WdSO16].

Oliveira et Cook ont une autre façon d’utiliser le patron visiteur qu’ils appellent une algèbre d’objets [dSOC12].

Dans leur solution, les termes du langage sont toujours des classes:

abstract class Term { abstract int eval(); }

class Constant extends Term {
  int n;
  Constant(int n) { this.n = n; }
  public int eval() { return n; }
}

class Plus extends Term {
  Term a, b;
  Plus(Term a, Term b) { this.a = a; this.b = b; }
  public int eval() { return a.eval() + b.eval(); }
}

Ici on a un langage minimal. Les classes peuvent implémenter différentes opérations; ici l’opération d’évaluation.

L’idée de l’algèbre d’objets est de construire des expressions virtuelles, qui seront évaluées par différentes algèbres. Plutôt que de construire l’expression 1 + 2 en utilisant les constructeurs Constant et Plus:

Term e2 = new Plus(new Constant(1), new Constant(2));

on utilise les constructeurs virtuels constant et plus:

<T> T e2(Visitor<T> v) {
  return v.plus(v.constant(1), v.constant(2));
}

Ces constructeurs virtuels sont des méthodes d’un visiteur qui représente l’algèbre d’objet. C’est le visiteur qui détermine le type de retour de cette fonction. L’expression e2 ne fait que décrire la structure plus(constant, constant).

L’interface Visitor est similaire à celle du visiteur extensible; une méthode pour chaque terme:

interface Visitor<T> {
  T constant(int n);
  T plus(T e1, T e2);
}

Sauf que dans le visiteur extensible, la méthode forConstant prenait une Constant comme paramètre. Ici, les méthodes sont des constructeurs virtuels (factory) pour les termes.

On peut d’ailleurs implémenter un visiteur qui produit des Constant et des Term directement:

class ASTVisitor implements Visitor<Term> {
  public Term constant(int n) {
    return new Constant(n);
  }

  public Term plus(Term a, Term b) {
    return new Plus(a, b);
  }
}

Pour l’utiliser, il suffit d’invoquer l’expression e2 avec ce visiteur:

e2(new ASTVisitor()).eval();

3

Mais on peut aussi passer un autre visiteur, qui correspond à une autre opération sur le langage. Si on ajoute l’opération d’affichage:

interface PP { String pp(); }

class PPVisitor implements Visitor<PP> {
  public PP constant(int n) {
    return () -> new Integer(n).toString();
  }

  public PP plus(PP a, PP b) {
    return () -> a.pp() + " + " + b.pp();
  }
}

On peut ensuite exécuter cette opération sur l’expression e2 en substituant le visiteur:

e2(new PPVisitor()).pp();

1 + 2

Ajouter un terme comporte les même étapes que dans le visiteur extensible: ajouter une classe pour représenter le terme, étendre l’interface du visiteur pour supporter ce terme, et implémenter cette nouvelle interface pour chaque opération.

Les algèbres d’objets sont donc très proches du visiteur extensible. Elles éliminent cependant le problème de sûreté, et réduisent le bruit structurel, mais sans pour autant l’éliminer complètement.

L’utilisation des constructeurs virtuels est intéressante car non seulement elle rend les expressions lisibles, mais en même temps ces expressions n’ont aucune sémantique attachée. Cette approche rend évidente le fait que l’expression construit simplement un arbre syntaxique, et que le visiteur peut être vu comme un interpréteur de cet arbre.

Les différentes solutions au problème de l’expression montrent que même si le langage de programmation peut favoriser une certaine décomposition (selon les termes, ou selon les opérations), ce biais est contournable. La décomposition par opérations est plus évidente en Haskell (et autres langages de la famille de ML), tandis que la décomposition par termes est plus évidente en Java (et autres langages objets). Mais en utilisant divers mécanismes de ces langages, on peut réconcilier ces deux décompositions.

Comme le problème de l’expression est lié à l’extension des interpréteurs, les mécanismes que l’on vient d’étudier pourront être pertinents pour l’extension de Narcissus.

Mais le problème de l’expression est différent du problème que l’on a posé. Les solutions au problème de l’expression permettent d’étendre des interpréteurs, à condition qu’ils suivent une certaine structure. Les termes sont des classes qui acceptent un visiteur; ou les termes sont les variantes d’un type de données algébrique.

Pour étendre Narcissus, on cherche à minimiser les changements apportés à l’interpréteur existant. S’il ne suit pas une des structures extensibles exposées ici, il faudrait alors le refactoriser, ce qui impliquerait des modifications de son code source trop importantes.

Néanmoins, ces solutions restent applicables au problème plus large, qui est de construire des interpréteurs extensibles.

La superposition regroupe un ensemble de techniques qui visent à étendre le programme au niveau du code source plutôt qu’au niveau du langage.

Hyper/J est un système pour le séparation pluridimensionnelle des préoccupations en Java [TOH+99,TO00]. C’est un paradigme qui permet de séparer les préoccupations d’un système selon plusieurs axes, en regroupant tous les artefacts liés à une préoccupation: le code source, mais aussi la documentation, et les documents de conception. Le but de cette séparation et de minimiser l’impact d’un changement. Les auteurs prennent l’exemple de problème de l’expression, où, on l’a vu, ajouter un terme ou une opération n’est pas équivalent.

The goal of low impact of changes requires additive, rather than invasive, change. Yet conceptually simple changes, like those in the expression system, often have widespread and invasive effects, both within the modified artifact and on related pieces of other artifacts. This is primarily because units of change often do not match the units of abstraction and encapsulation within the artifcats. Thus, additive changes in one artifact, like requirements, may not translate to additive changes in other artifacts, like design and code.

Pour les auteurs, si un ajout de fonctionnalité ne se traduit pas en ajout de code, c’est que les abstractions du langage de programmation ne sont pas adaptées. L’abstraction proposée en Hyper/J pour résoudre le problème de l’expression est l’hypercoupe.

L’hypercoupe regroupe tous les artefacts liés à la préoccupation. Pour le problème de l’expression, il y aura par exemple hypercoupe pour chaque opération: eval, display (pretty-printing), ou bien encore check pour une analyse du programme. Les artefacts peuvent apparaître dans plusieurs hypercoupes. C’est le cas ici: les classes qui représentent les termes apparaissent dans toutes les hypercoupes. Les hypercoupes sont simplement des vues différentes d’un même système.

Dans Hyper/J, la superposition intervient lorsqu’il s’agit de composer les hypercoupes pour synthétiser le programme. Composer le code source se fait à partir des noms de classes et des méthodes: deux classes homonymes dans deux hypercoupes différentes combineront leurs méthodes. Dans les hypercoupes de l’exemple, on obtient une seule classe Term qui comportera trois méthodes: eval, display, et check. La superposition s’applique aussi aux méthodes homonymes, mais on peut en plus préciser de quelle façon combiner comme en programmation par aspects (after, before, around).

L’intérêt de cette approche, c’est qu’elle ne dépend pas (ou peu) du langage concerné. On peut créer des hypercoupes regroupant des extraits de programmes dans différents langages de programmation. Ce qui importe, c’est de préciser comment ces extraits sont combinés pour synthétiser le programme final.

Il y d’autres exemples de superposition, notamment dans le domaine de la programmation par fonctionnalités (Feature-Oriented Programming) et des lignes de produit [ABK+13]. FeatureHouse [AKL13] est similaire à Hyper/J dans la mesure où l’on peut superposer plusieurs extraits de la même classe. Combiner trois extraits ou plus est aussi possible, et résolu comme dans un système de contrôle de version. FeatureHouse se base sur un arbre syntaxique réduit du programme, et comme Hyper/J, est essentiellement indépendant du langage de programmation.

De la même manière, les patches sémantiques [PLM07] reconnaissent des arbres syntaxiques partiels afin de reproduire des changements automatiquement. L’application principale est de pouvoir modifier des pilotes lorsque l’interface du noyau Linux change. Dans un patch sémantique, on décrit le motif général du changement à l’aide d’ellipses:

@ rule2 @
identifier proc_info_func;
identifier hostptr;
@@
proc_info_func (
+ struct Scsi_Host *hostptr,
- int hostno
) {
  ...
- struct Scsi_Host *hostptr;
  ...
- hostptr = scri_host_hn_get(hostno);
  ...
- if (!hostptr) { ... return ...; }
  ...
- scsi_host_put(hostptr);
  ...
}

L’ellipse peut correspondre à n’importe quelle séquence d’instructions dans le code du driver. Les patches sémantiques sont donc applicables à tous les fichiers qui contiennent ce motif, ce qui permet d’automatiser le changement.

Enfin, si on ne peut pas séparer les préoccupations avec ces outils, on peut toujours l’émuler en créant ses propres vues. C’est l’idée de l’information transparente [Gri01], que l’on retrouve aussi sous le nom de séparation virtuelle des préoccupations [AK09]. Le principe de l’information transparente est d’exploiter les similarités du code, et en particulier les similarités cohérentes:

Code elements likely to be changed together as part of a complete, consistent change should look similar, and code elements unlikely to be changed together should look different.

Par exemple, pour adapter une analyse de programmes C pour analyser également des programmes Ada, on peut réutiliser l’analyse des boucles while en C pour les boucles loop en Ada. Si le code de l’outil est cohérent, les variables et les fonctions qui manipulent le while de C s’appelleront WHILE, ou WhileStmt. Du coup, il suffira de faire une simple recherche sur tous les fichiers du projet, avec grep par exemple, pour trouver tous les endroits qu’il faudra adapter pour les programmes Ada.

Ce principe ne s’applique pas seulement au code. Une pratique courante est d’inclure les mots TODO, FIXME ou REFACTOR dans les commentaires d’un code source pour indiquer un problème que l’auteur note dans le feu de l’action, dans l’intention de le résoudre ultérieurement. On peut ensuite facilement obtenir une liste de toutes ces notes avec une simple recherche dans le texte. L’environnement de développement Eclipse affiche par exemple toutes les tâches d’un projet à partir de ces mots-clés.

L’information transparente a l’avantage de pouvoir s’appliquer à n’importe quel programme, puisqu’elle ne repose que sur des conventions. Elle n’impose pas de changements structurels, ce qui la rend plus économique à adopter qu’un nouveau paradigme. En contrepartie, elle n’offre aucune garantie. Si l’on écrit TOOD plutôt que TODO, la note sera peut être oubliée à jamais.

Austin, Disney et Flanagan proposent d’étendre les langages à l’aide de valeurs virtuelles [ADF11]. Une valeur virtuelle est une valeur dont le comportement peut être redéfinie par le programmeur. Par exemple, lorsqu’une valeur virtuelle est utilisée comme indice dans un tableau, ou dans un test d’égalité, ou invoquée comme une fonction, le programmeur peut intercepter cet usage et y substituer son propre comportement.

Avec les valeurs virtuelles, on peut par exemple implémenter la mémorisation de valeurs. Les auteurs donnent l’exemple d’une fonction delay qui prend comme argument une fonction qui représente le calcul à mémoriser. La valeur retournée par delay est une valeur virtuelle, qui se comporte comme une valeur primitive: pour le reste du programme, ce n’est plus une fonction. La première fois que le programme utilise cette valeur virtuelle, le calcul sera exécuté et mémorisé. Le calcul est donc effectué au plus une seule fois, de façon transparente pour le programme.

var v = delay(() => large_computation_to_int())
return Math.max(v, threshold)

Les auteurs donnent aussi l’exemple de valeurs virtuelles pour de l’analyse de flot d’information. Une valeur virtuelle peut être colorée par la fonction taint, ce qui colore toutes les valeurs avec lesquelles elle interagit, elles-mêmes devenant des valeurs virtuelles. Ajouter 1 et 2, où 1 est une valeur colorée donnera la valeur colorée 3. Les valeurs colorées sont en tout point semblables aux valeurs primitives, mais elles propagent leur couleur.

L’intention des valeurs virtuelles est d’implémenter des stratégies d’interprétation alternatives, sans avoir à modifier l’interpréteur. Il faut néanmoins que l’interpréteur gère les valeurs virtuelles dans un premier temps. Mais une fois cette modification effectuée, les différentes stratégies d’interprétation peuvent se faire à travers les valeurs virtuelles directement.

Un inconvénient potentiel de cette approche est qu’il faut implémenter la stratégie d’interprétation du point de vue de la valeur: quoi faire quand la valeur est ajoutée à une autre valeur, quoi faire quand elle est utilisée dans une conditionnelle, quoi faire quand elle est appelée comme fonction, etc. Suivant la stratégie d’interprétation, modifier l’interpréteur peut être plus direct.

Mais plus important, toutes les modifications de l’interpréteur ne sont pas réalisables à l’aide des valeurs virtuelles. Comme une valeur virtuelle est toujours créée explicitement à partir d’une valeur primitive, on ne peut pas capturer toutes les valeurs primitives du programme pour tracer l’interprétation par exemple. Intuitivement, les valeurs virtuelles sont plus adaptées pour des stratégies d’interprétations qui n’affectent que certaines valeurs, et non tout le comportement du programme. Par exemple, la mémorisation est utile pour retarder l’évaluation d’une valeur ponctuelle, mais les valeurs virtuelles ne transforment pas pour autant les expressions qui les contiennent en expressions paresseuses. Si l’on souhaitait changer évaluer tout un programme paresseusement avec les valeurs virtuelles, il faudrait manuellement rajouter des appels à delay absolument partout. Modifier l’interpréteur directement serait alors bien plus simple.

Une valeur virtuelle est essentiellement un mandataire (proxy) autour d’une valeur primitive. Les auteurs baptisent d’ailleurs leur langage λ_proxy. Un mandataire s’intercale entre le reste du programme et la valeur primitive, et permet de redéfinir comment cette valeur réagit aux opérations usuelles du langage qui d’habitude échappent au contrôle du programmeur. Les valeurs virtuelles ont inspiré l’implémentation des mandataires en JavaScript [CM13], qui n’est cependant pas aussi riche pour des raisons de compatibilité. Néanmoins, Keil et Thiemann ont utilisé ces mandataires avec succès pour améliorer leur moniteur d’effets JSConTest qui était précédemment basé sur de la transformation de code [KT13].

La portée dynamique est aussi un moyen de détourner des programmes. C’est un des ingrédients de l’extensibilité de l’éditeur de texte Emacs [Sta81]. Stallman prend l’exemple de l’association temporaire d’une séquence de touche à une action, tant qu’un mode d’édition spécifique est actif. Si le mode fait référence à la table des raccourcis bind-map, on peut, par portée dynamique, redéfinir temporairement bind-map lors de l’activation de ce mode:

(let ((bind-map ...))
  (specific-edit-mode))

Et ce, sans besoin de modifier la façon dont le mode accède à bind-map. De façon générale, la portée dynamique permet à l’appelant de redéfinir les variables libres d’une fonction.

Historiquement, la portée dynamique est d’abord une erreur de programmation dans les premières implémentations de Lisp [McC81], ce qui a été rectifié par l’ajout de l’opérateur FUNCTION [Mos70]. Un Lisp traditionnel peut donc comporter des variables à portée dynamique, et d’autres à portée lexicale. C’est un avantage, car en plus du scénario mentionné ci-dessus, Moreau note que la portée dynamique apporte de l’expressivité à un langage purement fonctionnel [Mor98]. Il remarque que la plupart des langages courants n’offrent que la portée lexicale; Perl, TeX, CommonLisp et Bash sont des langages où la portée dynamique est encore présente. La raison étant que la portée lexicale est bien moins surprenante; la portée dynamique peut modifier le comportement des fonctions appelées par inadvertance. Néanmoins, le langage Haskell propose tout de même la portée dynamique dans une extension, sous la forme de paramètres implicites [LLM+00].

En JavaScript, l’héritage est réalisé par la délégation. Ce n’est pas très différent de la situation en Java, si bien que les mêmes remarques s’y appliquent. JavaScript permet cependant de modifier le lien de délégation après la création de l’objet, ce qui ouvre des possibilités intéressantes pour le détournement.

Prenons un simple objet qui représente une constante dans le langage:

var num = {
  new(n) { return {__proto__: this, n }},
  eval() { return this.n }
}

var n1 = num.new(2)
n1.eval() //: 2

Le diagramme à côté du code illustre les objets manipulés par l’interpréteur JavaScript. Les objets y sont représentés par des boîtes qui contiennent des paires, chaque paire associant une clé à une valeur. Lorsque la valeur est une référence, elle est représentée par une puce d’où part un trait vers l’objet référencé (). Par exemple, ici num est une référence vers un objet qui contient les clés new et eval. Habituellement, on désigne un objet par la clé qui le réfère: on parlera ici de l’objet num, de l’objet n1, etc. Une puce qui part du coin d’un objet représente le lien de délégation vers l’objet parent (le prototype). Par exemple, n1 a num pour parent (l’objet référencé par n1 a pour parent l’objet référencé par num). Les références en pointillés sont omises par concision: ici new est une référence vers une fonction qui a peu d’importance pour la suite.

On a plusieurs façons de modifier l’évaluation de n1 après sa définition. On peut surcharger la fonction sur l’objet lui-même:

n1.eval = function() { return this.n * 2 }
n1.eval() //: 4

On voit sur le diagramme correspondant que cette nouvelle fonction n’existe que sur l’objet n1. Cette modification n’affecte donc que l’objet n1, et aucune autre instance dérivée de num, existante ou future.

Alternativement, on peut changer la fonction eval du prototype num:

n1.eval() //: 2
num.eval = function() { return this.n * 4 }
n1.eval() //: 8

Cette fois, tous les objets qui délèguent l’appel de la fonction eval à num utiliseront cette nouvelle version. L’objet n1 est affecté, ainsi que toutes les instances de num que l’on pourrait créer en appelant num.new.

Si l’on souhaite éviter de toucher à num, on peut proposer un objet num3 qui servira de prototype alternatif pour n1:

var num3 = {
   __proto__: num,
   eval() { return this.n * 3 }
}

Object.setPrototypeOf(n1, num3)
n1.eval() //: 6

En redéfinissant le prototype de n1 de num à num3, la fonction eval qui est utilisée lors de l’appel n1.eval est maintenant celle de num3. On a changé le prototype de n1 dynamiquement, et de cette façon on n’a pas besoin de modifier le code existant de num. La modification n’affecte que n1, mais on pourra créer d’autres instances de num3 en appelant num3.new.

La modification dynamique de prototype peut donc être utilisée pour détourner un interpréteur. Un exemple crédible serait d’avoir un interpréteur capable de changer de mode de fonctionnement pendant l’exécution d’un programme. Par exemple, un interpréteur qui rentrerait dans un mode où toutes les évaluations sont consignées.

La forme minimale de cet interpréteur est la suivante:

// Terms
var num = (n) => ({type: 'num', n })
var plus = (a, b) => ({type: 'plus', a, b })

// Standard interpretation
var interp = {
  rules: {
    num(num) { return num.n },
    plus(plus) {
      return this.eval(plus.a) + this.eval(plus.b)
    },
  },

  eval(node) {
    return this.rules[node.type].call(this, node)
  },
}

var e1 = num(2)
interp.eval(e1) //: 2

var e2 = plus(num(1), num(2))
interp.eval(e2) //: 3

Les termes cette fois ne sont plus des objets qui portent leur évaluation, mais de simples structures de données qui contiennent une étiquette de type pour les distinguer, analogues à un enum ou aux variantes d’un type algébrique.

L’interpréteur contient une méthode eval qui prend un nœud de l’arbre de syntaxe en argument, et qui appelle la fonction d’évaluation adéquate pour le type de ce nœud. Les fonctions d’évaluations sont dans l’objet rules, interne à interp; on peut voir cet objet comme un visiteur de l’arbre syntaxique.

Pour évaluer les programmes e1 ou e2, il suffit de les passer en paramètre à la méthode interp.eval.

Avec cette structure, on peut créer un interpréteur alternatif par simple délégation. Un interpréteur qui double les constantes aura juste besoin de redéfinir la règle d’évaluation des constantes, de la sorte:

var interp_double = derive(interp, {
  num(num) { return interp.eval(num) * 2 },
})

interp_double.eval(e1) //: 4
interp_double.eval(e2) //: 6

La fonction num d’interp_double réutilise l’évaluation de num de l’interpréteur précédent interp, comme un appel via super en Java à la méthode de classe parente. En JavaScript, il n’y a pas de structure de classe, mais la fonction derive nous permet tout de même de partager le code par délégation. En l’occurrence, elle ne fait qu’établir deux liens de prototype: un pour l’objet interp_double lui-même (qui délègue à interp), et l’autre pour l’objet interne interp_double.rules (vers interp.rules).

function derive(interp, rules) {
  Object.setPrototypeOf(rules, interp.rules)
  return {__proto__: interp, rules }
}

De la même façon, on peut dériver un interpréteur qui consigne sur la sortie standard chaque fonction d’évaluation utilisée:

var interp_log = {__proto: interp,
  eval(node) {
    console.log(`eval ${node.type}`)
    return interp.eval.call(this, node)
  }
}

interp_log.eval(e2) //: 3

L’évaluation de e2 affichera:

eval plus
eval num
eval num

Cette fois on n’utilise pas derive, car plutôt que de changer chaque règle, on change directement la fonction d’évaluation eval pour introduire l’instruction console.log.

Maintenant, le but est d’avoir un interpréteur capable de changer de mode d’évaluation: par défaut, il ne consigne rien sur la sortie standard, mais en réponse à l’instruction start_trace, il bascule vers le mode d’évaluation d’interp_log. Puis, lorsqu’il rencontre l’instruction end_trace, il bascule à nouveau vers l’évaluation standard.

Pour commencer, il faut ajouter les termes pour start_trace et end_trace:

var start_trace = () => ({type: 'start_trace'})
var end_trace = () => ({type: 'end_trace'})

Ces termes ne prennent aucun argument, et contiennent juste une étiquette qui permet de les distinguer.

Pour écrire un programme avec ces termes, il nous faut un autre terme qui représente des séquences d’instruction. On l’appellera progn:

var progn = (...stmts) => ({type: 'progn', stmts })

Ce terme accepte n arguments qui sont des sous-termes. Il faut donner un sens à ce terme dans l’interpréteur standard, donc on rajoute une règle pour progn directement dans l’objet interp.rules:

interp.rules.progn = function(progn) {
  var result
  progn.stmts.forEach(s => { result = this.eval(s) })
  return result
}

Pour évaluer un progn, on évalue récursivement et dans l’ordre chacun de ses sous-termes, puis on retourne le résultat du dernier sous-terme. Notons qu’en ajoutant la règle pour progn ainsi sur l’objet interp.rules, les interpréteurs dérivés interp_double et interp_log sont aussi enrichis de cette fonctionnalité.

Voici un simple programme qui utilise progn:

var e3 = progn(
  num(1),
  plus(num(3), num(4))
)

interp_log.eval(e3) //: 7

Évaluer ce programme avec interp_log affiche sur la console:

eval num
eval plus
eval num
eval num

Ce qui indique que tous les sous-termes sont bien évalués par la fonction eval redéfinie par interp_log.

Maintenant, on dérive un interpréteur capable d’évaluer l’instruction start_trace:

var interp_traceable = derive(interp, {
  start_trace() {
    Object.setPrototypeOf(this, interp_log)
  },
})

Le seul effet d’une instruction start_trace est de remplacer le prototype de l’interpréteur par interp_log. Quand l’interpréteur arrive sur cette instruction, il change de prototype, ce qui aura pour effet de consigner les évaluations ultérieures jusqu’à la fin du programme, ou jusqu’à la prochaine instruction end_trace. Cette instruction end_trace doit donc être interprétable par interp_log:

interp_log.rules.end_trace = function() {
  Object.setPrototypeOf(this, interp_traceable)
}

Intuitivement, évaluer cette instruction a l’effet inverse d’évaluer start_trace: on rétablit le prototype de l’interpréteur vers interp_traceable. On ne souhaite pas modifier les prototypes des objets interp_traceable ou interp_log en revanche, donc on utilisera un objet interp_model dont le seul but est de contenir le pointeur vers le prototype du mode courant d’évaluation.

Le mode par défaut est traceable, soit:

var interp_modal = Object.create(interp_traceable)

L’objet interp_modal change de prototype suivant l’évaluation du programme. Son prototype initial est interp_traceable, mais après l’évaluation d’une instruction start_trace, son prototype devient interp_log. Dans cet état, évaluer l’instruction end_trace restaure le prototype initial, interp_traceable. Ainsi, cet interpréteur pourra évaluer le programme e4:

var e4 = progn(
  plus(num(1), num(2)),
  start_trace(),
  plus(num(3), num(4)),
  end_trace(),
  num(42)
)

interp_modal.eval(e4) //: 42

L’affichage sur la sortie standard est le suivant:

eval plus
eval num
eval num
eval end_trace

La sortie est restreinte aux instructions évaluées entre les instructions start_trace et end_trace. L’interpréteur interp_modal a changé de mode d’évaluation dynamiquement, pendant l’exécution d’un programme, et ce sans que le code source des interpréteurs précédents n’ait été modifié. C’est le changement dynamique du lien de délégation par prototype, autorisé par le langage, qui nous permet ce détournement.

Le détournement de cet exemple est rendu possible parce que l’on a un contrôle total sur la structure de l’interpréteur: on a profité du fait que toutes les fonctions d’évaluation étaient regroupées dans un même objet rules. Dans Narcissus, ce n’est pas le cas: l’évaluation de chaque terme se fait au sein d’une même fonction. Donc le changement dynamique de prototype peut permettre le détournement, tant que les pièces du programme que l’on cherche à détourner sont regroupées au sein d’un même objet.

Malheureusement, les outils de programmation par aspects en JavaScript sont moins développés qu’AspectJ. La solution la plus flexible est certainement AspectScript [TLT10], qui permet d’insérer des aspects dynamiquement, et même de capturer les affectations aux variables à l’intérieur des appels de fonction.

Pour le module JavaScript suivant:

var m = (function() {
  var a = 1;
  function f(x) { return x + a; }
  function g(x) { return f(x); }
  return {g: g, f: f};
}());

On peut intercepter les appels à f ou les lectures de a dans la fonction f en utilisant AspectScript ainsi:

AspectScript.around(
  AspectScript.Pointcuts.exec(m.f),
  function (jp) {
          return 2 * jp.proceed()
  })

AspectScript.around(
  AspectScript.Pointcuts.get('a'),
  function(jp) {
    return 2
  })

Le premier aspect capture les exécutions de la fonction f du module m pour en doubler le résultat. Le second aspect capture la référence faite à a dans le corps de f pour modifier la valeur retournée: sans l’aspect, a vaut 1 à l’intérieur du module car c’est une variable capturée lexicalement. Avec l’aspect, on peut modifier la valeur de cette variable lexicale, et donc simuler une portée dynamique.

Mais AspectScript a deux inconvénients majeurs qui sont la performance et la compatibilité avec le standard JavaScript. Pour capturer et redéfinir les évaluations, AspectScript définit son propre analyseur de syntaxe, et réécrit le programme ciblé pour ensuite le réinterpréter. Ce procédé, qui donne à AspectScript sa flexibilité, rend le programme 5 à 15 fois plus lent. Puisque AspectScript réinterprète le programme ciblé, il introduit également des variations indésirables avec le comportement d’un interpréteur standard. Par exemple, la construction with n’est pas supportée.

On a exploré différentes façons de détourner un interpréteur minimal. Bien que dans plusieurs cas on ait réussi à modifier le comportement de l’interpréteur sans en modifier le code, aucune de ces solutions ne peut s’appliquer directement à Narcissus. Il ne se dégage pas de moyen générique de détourner un interpréteur; pour trouver la méthode la plus adéquate il faut étudier l’interpréteur ciblé afin de déterminer les endroits où introduire de l’indirection. Par exemple, savoir quelles fonctions sont en charge de l’évaluation de tel terme, et surtout, quel langage est utilisé pour l’implémentation.

Un mécanisme simple pour introduire de l’indirection est la portée dynamique. La portée dynamique n’est pas disponible en JavaScript, mais dans les chapitres suivants, on va montrer comment reproduire une forme de portée dynamique en utilisant des constructions JavaScript standard, afin de détourner un interpréteur simplement, et ultimement, de détourner Narcissus.

Ce détournement a trois ingrédients principaux: la délégation, les extensions représentées par des fonctions, et la manipulation de portée. La délégation nous a permis la représentation différentielle des extensions. Dans l’extension double, on réutilise le constructeur new et la fonctionnalité de base de eval par délégation. C’est en partie grâce à la délégation que l’on peut composer les extensions de l’interpréteur: l’objet num créé par double, quand il est évalué, invoque la fonction eval du module de base; à son tour, ce module peut être une composition, etc. Le code de l’évaluation de num est écrit une seule fois, et réutilisé par les extensions par délégation. La délégation permet d’indiquer quel code réutiliser.

Composer les extensions est facilité par leur représentation par des fonctions. Nos extensions double, show et state sont toutes des fonctions qui prennent en argument le module à étendre. Rappelons qu’il n’y a pas de système de module en JavaScript; les modules dont on parle ici sont de pures conventions. En l’occurrence, ce sont justes des objets JavaScript (des structures associatives). En faire des fonctions incite naturellement à les composer. La construction with n’est d’ailleurs pas nécessaire:

var d = double(double(double({num})))
plus.new(d.num.new(1), d.num.new(2)).eval() //: 6

On voit qu’en réalité, on ne fait que composer des fonctions qui retournent des objets (modules) qui contiennent plusieurs fonctions, que l’on va ensuite appeler. Donc, la délégation permet la réutilisation, et les modules en tant que fonctions permettent la composition. Le problème, c’est que ce n’est pas suffisant pour détourner l’interpréteur, car on doit modifier le code (ajouter le préfixe d.) en fonction de l’extension. C’est la manipulation de portée qui vient résoudre ce problème.

Dans tous les exemples donnés, on évalue toujours la même ligne de code, à savoir l’arbre syntaxique qui représente l’expression 1 + 2:

plus.new(num.new(1), num.new(2)).eval()

Mais cette même expression, suivant les extensions activées, donne différents résultats. L’astuce consiste à changer, pour chaque exemple, les références plus et num grâce à with:

with (double(..)) {
  plus.new(num.new(1), num.new(2)).eval()
}

Dans cette expression, num fait référence à l’objet exporté par double, mais double n’exporte pas d’objet plus. Pour savoir à quel objet plus fait référence, il faut connaître les environnements actifs et leur portée. S’il y a une extension qui définit plus (comme show) au dessus de double, c’est cet objet qui sera utilisé, sinon, ce sera le plus de base.

On pourrait faire référence explicitement aux objets retournés par double:

var d = double({num})
plus.new(d.num.new(1), d.num.new(2)).eval()

De cette façon, on voit de quels modules sont tirés les objets num et plus. Mais ça nous demanderait de modifier le code de l’expression. La construction with crée un environnement à partir de l’objet passé en argument, mais qui hérite de l’environnement courant. Si à l’extérieur du with, l’environnement contient les associations:

Environnement global
num = objet de base
plus = objet de base

alors, à l’intérieur d’un with(double), on a l’environnement:

Environnement parent: Environnement global
num = objet de double
plus = objet de base

La construction with ne nous est utile que parce qu’elle construit cet environnement. En suivant la sémantique du langage, on n’a plus à préfixer num par d.; les préfixes sont implicitement donnés par l’environnement. La création de cet environnement est la clé du détournement, car si l’on change ce que plus et num et eval signifient, alors on contrôle le résultat.

Il est important de remarquer que ces trois mécanismes ne sont pas spécifiques à JavaScript, ni au scénario de l’extension d’un interpréteur. La délégation est présente dans d’autres langages à prototypes, mais pour satisfaire la réutilisation, l’héritage de classes pourrait tout aussi bien convenir. Représenter les modules comme des fonctions pourrait se faire par convention dans de nombreux langages (en Python, ou en Scheme par exemple). Les analogues de la création d’environnements sont moins évidents, mais on peut y substituer des mécanismes qui désambiguïsent les noms.

Par exemple, dans le langage Rust [Rus], on pourrait obtenir un résultat semblable en utilisant les traits:

enum Term {
  Num(u64),
  Plus(Term, Term),
}

fn num(u64) -> Term { ... }
fn plus(Term, Term) -> Term { ... }

mod base   { trait Eval { fn eval(..) }
	     impl Eval for Term { fn eval(..) {}}}
mod double { trait Eval { fn eval(..) }
	     impl Eval for Term { fn eval(..) {}}}

fn main() {
  { use base::Eval;   num(3).eval(); } //: 3
  { use double::Eval; num(3).eval(); } //: 6
}

Ici les termes sont représentés par un type algébrique à deux variantes. On ajoute des fonctions de constructions de ces termes num et plus. Les deux modules base et double définissent le trait d’évaluation Eval et fournissent chacun une implémentation de ce trait pour Term. On voit ensuite que dans la fonction main, on construit et évalue le même terme num(3), mais suivant le module importé localement par use, le résultat est différent. La même instruction num(3).eval() donne 3 quand on importe le trait base::Eval et 6 quand on importe le trait double::Eval. Ces deux appels à eval sur num sont équivalents aux appels suivants:

base::Eval::eval(num(3))
double::Eval::eval(num(3))

On voit alors qu’on invoque deux fonctions eval différentes. Le mécanisme d’import du module ne fait que fournir un sucre syntaxique pour évoquer la syntaxe de la liaison dynamique, mais il n’y a aucune liaison ici, simplement des appels de fonctions. De façon analogue, notre utilisation de with en JavaScript revient à camoufler les appels aux constructeurs fournis par chaque module sous une seule et même syntaxe.

Dans tous les exemples que l’on a donnés, on a pu voir qu’enrober le code d’un with nous permettait de modifier son résultat. Avec un with(double) on activait l’évaluation qui double les valeurs des nombres, avec with(show) on permettait d’utiliser l’opération show sur les arbres syntaxiques, etc.

Un inconvénient, c’est que l’on doit construire l’arbre syntaxique à l’intérieur du with. On ne peut pas construire l’arbre une seule fois, et réutiliser sa valeur pour différentes évaluations. Autrement dit, on voudrait écrire:

1: var t = plus.new(num.new(1), num.new(2))
2: 
3: with (double({num})) {
4:   t.eval() //: 3
5: }

Sauf que évaluer t ici nous donne 3, et non 6. L’extension double ne s’applique pas, car double ne fait que remplacer les références num et plus. Or, à l’intérieur du with, on n’utilise pas plus et num directement: ils ont déjà été utilisés à la construction ligne 1.

On peut simuler une réutilisation du même arbre syntaxique; il suffit d’en faire une fonction:

1: var p1 = function(m = {}) {
2:   with (m) {
3:     return plus.new(num.new(1), num.new(2))
4:   }
5: }

La variable p1 représente un arbre syntaxique, un programme de notre langage arithmétique. Ce langage est paramétré par le module m, qui sera actif lors de la construction de l’arbre syntaxique ligne 3.

On peut maintenant utiliser cette fonction, mais avec différents modules:

p1().eval() //: 3
p1(double({num})).eval() //: 6
p1(double(double({num}))).eval() //: 12
p1(show({num,plus})).show() //: "1+2"

Par défaut, si aucun module n’est passé en argument, on utilisera les plus et num de base déclarés globalement. En revanche, si on passe double, on construit un arbre syntaxique avec ce module activé. On peut ensuite évaluer cet arbre avec eval, pour obtenir 6. La composition de modules est possible par composition de fonctions, et les modules qui offrent de nouvelles opérations fonctionnent tout aussi bien.

On a alors une fonction, p1, dont le résultat est entièrement déterminé par l’argument qu’on lui passe. Cette fonction en réalité appelle les plus et num passés en argument à travers with. C’est une inversion de contrôle: la fonction p1 définit la structure du programme, mais le code exécuté est fourni par l’appelant. Et cette inversion est rendue possible par l’utilisation du with à l’intérieur de la fonction qui vient manipuler les références plus et num. Autrement dit, la manipulation de la portée suffit pour détourner le programme.

Dans ce chapitre, on a construit l’interpréteur de toutes pièces. Mais on peut utiliser la manipulation de portée sur un programme existant. Dans le chapitre suivant, on montre comment la manipulation de portée peut être employée pour détourner l’interpréteur Narcissus.

L’interpréteur Narcissus est construit à partir du motif module. Il n’y a pas de système de module en JavaScript, et c’est ce motif simple qui est souvent utilisé à la place. Le motif utilisé par Narcissus se présente ainsi:

 1: var Narcissus = (function(){
 2:   var globalBase = { ... }
 3: 
 4:   function ExecutionContext(type, version) { ... }
 5:   function getValue(v) { ... }
 6:   function putValue(v, w) { ... }
 7:   function evaluate(code) { ... }
 8: 
 9:   return {
10:     globalBase: globalBase,
11:     evaluate: evaluate,
12:     ...
13:   }
14: }())

Le but de ce motif est de créer un environnement pour toutes les définitions du module. En JavaScript, une définition faite à la racine d’un fichier (une déclaration de variable avec var ou une définition de function) créée une entrée dans l’environnement global. Les entrées de l’environnement global sont accessibles en lecture et écriture par n’importe quel point du code, et même par du code d’autres fichiers chargés dynamiquement. Mettre ses définitions dans l’environnement global a deux désavantages immédiats: 1) n’importe quel code peut écraser ces définitions, et 2) vos propres définitions peuvent écraser les définitions faites précédemment par d’autres fichiers, et même écraser des parties de l’API standard du langage. Écraser une définition ne lève pas d’erreur ou d’avertissement en JavaScript; donc utiliser l’environnement global peut facilement casser du code chargé précédemment, et rend votre propre code fragile pour les mêmes raisons. En outre, les différents moteurs d’exécution de JavaScript peuvent proposer différentes extensions à l’API standard, ce qui se traduit par différents noms supplémentaires dans l’environnement global. Pour toutes ces raisons, les programmeurs JavaScript apprennent rapidement à enrober leurs définitions dans un environnement séparé. Cet environnement est créé en enrobant les définitions dans une fonction, ouverte à la ligne 1 et fermée à la ligne 14. Toutes les définitions de variables et fonctions des lignes 2 à 7 sont ainsi protégées de tout code extérieur au module, car inaccessibles.

Si le module est là pour fournir une fonctionnalité spécifique, ce qui est le cas de l’interpréteur qui fournit une fonction d’évaluation, alors il doit exposer au moins une définition au monde extérieur, l’exporter. Exporter des définitions se fait à travers un objet JavaScript (un simple dictionnaire, qui associe des chaînes de caractères à des valeurs), aux lignes 9 à 13. Cet objet, appelons-le l’objet exporté, est la valeur de retour de la fonction qui créée l’environnement du module.

Enfin, l’objet exporté est assigné à la variable Narcissus (ligne 1), une définition faite à la racine et qui peut être utilisée par n’importe quel code chargé dynamiquement, pour accéder à la fonctionnalité proposée par le module. La fonction qui crée l’environnement du module est appelée juste après sa définition (les () ligne 14 appellent la fonction), on la nomme donc une fonction immédiatement appelée, ou FIA.

Essayons de comprendre exactement les mécanismes du langage en jeu dans ce module. D’abord, on va construire un exemple minimal de module qui a un comportement observable:

1: var m = (function(){
2:   var a = 1
3:   function f(x) { return x + a }
4:   function g(x) { return f(x) }
5:   return {g: g}
6: }())
7: 
8: m.g(0) //: 1

On a ici un simple module qui retourne une seule fonction, g. Cette fonction applique la fonction f à son argument et retourne le résultat, et f à son tour retourne l’addition de son argument et de a, une variable interne au module. Quand on appelle m.g(0) à l’extérieur du module, on obtient 1, qui est la valeur de a.

On peut expliquer le motif module en regardant le diagramme qui accompagne le code. Dans le diagramme, les environnements, comme les objets, sont représentés par des boîtes. Une puce dans le coin d’un environnement indique le lien vers l’environnement parent: par exemple l’environnement qui contient a, f et g a pour parent l’environnement qui contient m. Lorsqu’un nom est recherché dans un environnement et que ce nom n’est pas présent dans les propriétés de cet environnement, la recherche continue dans l’environnement parent, et récursivement jusqu’à ce que soit la propriété est trouvée, soit il n’y a plus d’environnement parent. Si la propriété est trouvée, elle est retournée, sinon il y aura une erreur à l’exécution. Dans cet exemple, l’environnement global est en haut à gauche du diagramme (il contient m).

Avant d’exécuter le code de l’exemple, l’environnement global est vide. Lorsque la FIA est appelée, elle crée l’environnement en ▬ . Puisque la FIA est définie à la racine, l’environnement parent est l’objet global. À l’intérieur de la FIA, trois noms sont définis: une variable a et deux fonctions f et g (lignes 2 à 4). Lorsqu’une fonction est définie, un objet fonction est créé qui contient son code et son environnement lexical. Cet environnement sera utilisé pour exécuter le corps de la fonction lorsqu’elle sera invoquée. Avant que la FIA ne retourne, elle crée l’objet exporté (ligne 5) qui contient la propriété g. Cette propriété réfère la fonction g définie à l’intérieur du module. Notons qu’il y a deux références à la fonction g à l’exécution. Enfin, la FIA retourne l’objet exporté, qui devient la valeur de la variable globale m.

On peut aussi suivre le flot de contrôle suscité par l’appel à la ligne 8 sur ce second diagramme. D’abord, la référence m.g est résolue en cherchant la propriété m dans l’environnement courant, c’est à dire, l’environnement global. m existe et pointe vers un objet, donc l’interpréteur cherche maintenant la propriété g dans cet objet. g existe, et réfère un objet fonction, on peut donc procéder à l’appel m.g(0). Lorsque la fonction est appelée dans l’environnement global, l’interpréteur crée un environnement pour le corps de la fonction qu’on appelle l’objet d’activation de g. Cet objet associe les noms des paramètres déclarés par la fonction aux valeurs passées par l’appel; ici, il y a donc une seule entrée x : 0. L’objet d’activation de g est un environnement, et il a comme environnement parent l’objet référencé par la propriété env de l’objet fonction de g. Puis, le contrôle est transféré au corps de la fonction g, qui contient f(x). L’interpréteur résout les noms f et x en cherchant à travers la chaîne d’environnements: d’abord dans l’environnement courant (l’objet d’activation de g). f n’existe pas dans cet objet, mais il existe dans son objet parent. x existe, et sa valeur est utilisée pour continuer l’exécution de l’appel f(x). Lorsque f est appelée, l’interpréteur crée un nouvel objet d’activation pour les paramètres formels, qui a l’environnement de la FIA comme environnement parent. Après ça, l’interpréteur continue l’exécution avec le corps de f, x+a. La propriété x se trouve dans l’objet d’activation de f (0), et la propriété a dans l’environnement parent (1). L’interpréteur somme les deux valeurs et retourne le résultat.

Ce dernier diagramme sert à illustrer deux points importants sur le motif module:

1. La seule façon que du code extérieur au module a d’accéder aux définitions faites à l’intérieur du module est de passer par l’objet exporté. Dans l’exemple que l’on a suivi, g est la seule référence exportée, mais c’est un alias. Remarquons que si on essayait de changer la valeur de m.g par une autre fonction, m.g = function() { ... }, seule la référence m.g serait affectée, mais la propriété g dans l’environnement de la FIA ferait toujours référence à la fonction g définie dans le module. Si l’on veut modifier les références internes au module, il faut accéder directement à l’environnement de la FIA.
2. Toutes les fonctions créées à l’intérieur du module utilisent l’environnement de la FIA comme environnement parent. Autrement dit, les fonctions se referment sur leur environnement de définition (leur environnement lexical), et c’est pourquoi on appelle ces fonctions des fermetures. Si l’on a accès à l’environnement de la FIA, on peut changer le comportement des fonctions internes au module en changeant les références de cet environnement.

On voit alors que l’environnement de la FIA est le point central du module, là où tous les noms utilisés par le module sont recherchés. On voit aussi que le motif module ne permet pas, en l’état, d’accéder à ces noms de l’extérieur du module. C’est son rôle, mais ça s’oppose à notre but d’extensibilité.

On cherche maintenant à accéder à l’environnement de la FIA de l’extérieur du module, à obtenir une référence vers cet environnement. En regardant les diagrammes précédents, on pourrait penser que m.g.env suffit: il s’agit bien d’une référence à l’environnement qui nous intéresse depuis l’extérieur du module. Malheureusement, cette référence est interne au moteur d’exécution du langage, donc n’est pas accessible par le code exécuté. Mais même si on modifiait le moteur d’exécution pour rendre cette référence publique, elle n’est pas fiable. Suivant la construction de g, l’environnement qu’elle retourne pourrait très bien être différent de celui de la FIA.

1: var m = (function(){
2:   var mkG = function() {
3:     return function(x) { return x }
4:   }
5:   return {g: mkG()}
6: }())

Dans cet exemple, la fonction g exportée par le module ne capture pas l’environnement de la FIA. À la ligne 5 on exporte la valeur de retour de la function mkG sous le nom g. La fonction mkG retourne exactement la même fonction g que dans l’exemple précédent, avec une différence notable: cette fonction g capture l’environnement de l’appel à mkG. Le diagramme ci-contre illustre cette différence par l’apparition d’un nouvel objet d’activation pour mkG qui est référencé comme environnement de g. On a m.g.env qui pointe vers l’environnement créé par mkG (▬ ), et non l’environnement créé par la FIA (▬ ). On voit alors que la propriété env d’une fonction n’est pas garantie de pointer vers l’environnement dont nous avons besoin.

On va maintenant s’éloigner du comportement standard de JavaScript que nous avons suivi jusqu’ici. Supposons que nous pouvons accéder à l’environnement créé par la FIA grâce à une nouvelle propriété E qui serait automatiquement ajoutée à l’objet exporté par le module. Supposons également que cet environnement se comporte comme un objet JavaScript régulier; on peut lire et changer ses propriétés.

 1: var m = (function(){
 2:   var a = 1
 3:   function f(x) { return x + a }
 4:   function g(x) { return f(x) }
 5:   return {g: g}
 6: }())
 7: 
 8: m.g(0) //: 1
 9: m.E.a = 2
10: m.g(0) //: 2

Reprenons le module du début, mais avec l’addition de cette nouvelle propriété E. Si on exécute m.g(0) à la ligne 8, on obtient toujours 1. Par contre, cette fois on a accès à l’environnement interne au module via la propriété m.E. Si on change la valeur de a dans cet environnement (ligne 9), alors l’appel m.g(0) qui suit utilise cette nouvelle valeur, et c’est pourquoi le même appel donne le résultat différent, 2, à la ligne 10. Le diagramme qui accompagne l’exemple donne une autre façon de voir ce qui se passe. On y voit la nouvelle propriété E en ▬ sur l’objet exporté et référencé par la propriété globale m. Cette propriété m.E donne un accès en lecture et écriture sur l’environnement de la FIA. Ainsi, l’affectation de la ligne 9 modifie la valeur de a dans le module; dans le diagramme a a la valeur 2 en conséquence.

En ajoutant cette référence directe à l’environnement interne du module, on est déjà capable de changer les résultats de l’appel m.g, juste en changeant la valeur de la variable a. Mais on peut aussi changer les fonctions. Si l’on souhaite changer la fonction f pour qu’elle retourne x + 2 * a au lieu de x + a, la ligne 4 de l’exemple suivant nous indique comment:

1: var m = (function() { ... }())
2: 
3: m.g(0) //: 1
4: m.E.f = function(x) { return x + 2 * m.E.a }
5: m.g(0) //: 2
6: m.E.a = 2
7: m.g(0) //: 4

Notons qu’on ne peut pas simplement écrire x + 2 * a. Si on changeait la définition de f à l’intérieur du module, on pourrait référencer a directement. Mais ici, on crée une fonction à l’extérieur du module, qui doit faire référence au a qui n’est déclaré que dans l’environnement du module. Si on écrit juste a, ce sera une variable libre pour cette fonction. Mais puisqu’on a une référence à l’environnement du module via m.E, on peut accéder au a à travers elle.

Le diagramme ci-contre illustre clairement le problème: la nouvelle fonction f (▬ ) n’a pas le même environnement que l’ancienne. Puisqu’elle est créée en dehors du module, son environnement est l’objet global (lien ▬ ). Le diagramme nous indique aussi une autre solution: modifier la propriété env de la fonction qui vient remplacer f. Si l’on modifie cette propriété pour pointer vers l’environnement de la FIA, la variable a ne sera recherchée dans le même environnement que pour la fonction f d’origine; c’est comme si l’on créait une fermeture dans le module, mais défini de l’extérieur:

m.E.f = function(x) { return x + 2 * a }
m.E.f.env = m.E

Les deux approches pour référencer a sont des compromis différents. Utiliser m.E est plus explicite, et permet à la nouvelle fonction de capturer l’environnement dans lequel elle est définie. Modifier l’environnement de définition permet d’écrire le code de la fonction comme si on l’écrivait à l’intérieur du module, ce qui rend les différences de code plus lisibles.

Dans les deux cas, on peut voir que l’appel m.g(0) qui suit la redéfinition de f est bien affecté par le changement. Qui plus est, puisque cette nouvelle version de f fait référence au a du module, on peut changer a (ligne 6) et constater que le dernier appel m.g(0) utilise à la fois la nouvelle fonction f et la nouvelle valeur de a. On peut donc modifier le comportement de la fonction g en manipulant les variables et les fonctions définies à l’intérieur du module, mais en écrivant ces changements de l’extérieur du module. On n’a pas à toucher le code du module pour pouvoir changer les résultats des appels à m.g.

Mais les changements que l’on a apporté au module sont destructifs. En changeant la valeur de a, on détruit sa valeur initiale. En changeant la fonction f aussi. Dans les deux cas, on modifie la valeur directement dans l’environnement de la FIA. Comme ces redéfinitions sont de simples affectations, on peut sauvegarder la valeur initiale dans une variable pour pouvoir les réutiliser après:

var a_orig = m.E.a
var f_orig = m.E.f

Ce qui revient à simuler un mécanisme de pile manuellement. Il y a une solution plus élégante qui tire partie du mécanisme de résolution des noms de variable dans une chaîne d’environnements.

On a vu que tout environnement a un environnement parent. Si un nom n’est pas trouvé dans un environnement, la recherche se poursuit dans l’environnement parent. La recherche continue ainsi jusqu’à ce que le nom soit trouvé, ou que la chaîne d’environnement s’arrête car le lien vers l’environnement parent est à null. On peut profiter de ce mécanisme pour construire une façon élégante de changer les définitions internes au module.

Nous allons faire une seconde addition à notre variante de JavaScript. On suppose que lorsqu’un module est créé, un nouvel environnement vide, appelé l’environnement frontal est créé également. L’environnement frontal a pour parent l’environnement de la FIA, mais les fonctions définies à la racine du module capturent l’environnement frontal plutôt que celui de la FIA. La propriété m.E est modifiée également pour pointer vers cet environnement frontal.

Si l’on reprend exactement le code du module, sans modifications, mais qu’on l’exécute avec cette modification sémantique, on obtient la situation de la figure ci-contre. La redéfinition de a à 2 est enregistrée par l’environnement frontal (▬ ), plutôt que par l’environnement de la FIA. Puisque les deux fonctions f et g capturent l’environnement frontal, elles utilisent bien la valeur redéfinie de a quand elles sont appelées. Le mécanisme de résolution des noms de variable examine les environnements de bas en haut, en suivant les liens des coins des objets. On voit donc que n’importe quelle propriété présente dans l’environnement frontal a priorité sur les propriétés de l’environnement de la FIA. C’est pourquoi la redéfinition de a affecte bien l’appel m.g(0) de la même manière que dans les exemples précédents. Mais on a maintenant la possibilité d’annuler cette redéfinition en supprimant la propriété m.E.a de l’environnement frontal. Puisque l’environnement frontal ne contient que notre redéfinition, la valeur originale n’est jamais altérée. Lorsque l’on supprime m.E.a, on vide l’environnement frontal, et l’appel final m.g(0) va trouver la propriété a dans l’environnement de la FIA, où la valeur est restée à 1.

1: var m = (function() { ... }())
2: 
3: m.g(0) //: 1
4: m.E.a = 2
5: m.g(0) //: 2
6: delete m.E.a
7: m.g(0) //: 1

Avec cet environnement frontal, on peut surcharger et masquer les définitions du module sans toucher au code à l’intérieur du module. Dans la pratique, on ne se contenterait pas de changer une seule valeur mais plusieurs, et on voudrait pouvoir les injecter dans le module et les supprimer d’un coup. En outre, si on souhaite expérimenter différents ensembles de changements, on voudrait pouvoir activer un premier ensemble, puis un second, puis désactiver le premier. L’environnement frontal n’est pas suffisant pour ce scénario, mais on peut en utiliser plusieurs.

Pour cela, il faut faire une dernière addition à la sémantique du langage: on suppose que l’on peut récupérer et modifier le parent de n’importe quel environnement à travers la propriété parent. Avec cette propriété, on peut étendre la chaîne d’environnements utilisée par les fonctions définies dans le module avec un nombre quelconque d’environnements. Puisque tout environnement a un parent, et que l’on a une référence vers l’environnement par lequel débute la résolution de noms (m.E), la chaîne d’environnement a une structure similaire à une liste chaînée, où l’environnement frontal serait la tête de la liste. Et puisqu’on peut modifier le parent d’un environnement, on peut insérer de nouveaux environnements à n’importe quel point dans cette chaîne.

 1: var m = (function() { ... }())
 2: 
 3: m.g(0) //: 1
 4: 
 5: var e1 = { a:2, f: function(x) {
 6:   return x + 2 * m.E.a }}
 7: pushEnv(e1, m.E)
 8: m.g(0) //: 4
 9: 
10: var e2 = { f: function(x) { return -m.E.a }}
11: pushEnv(e2, m.E)
12: m.g(0) //: -2
13: 
14: removeEnv(e1, m.E)
15: m.g(0) //: -1

Sans changer le module, on ajoute toutes les redéfinitions de e1 en appelant pushEnv (ligne 7). On change à nouveau le comportement de f dans l’environnement e2 qu’on insère dans le module grâce au second appel à pushEnv. On voit que l’appel m.g(0) qui suit utilise la fonction f de e2, puisque le résultat est négatif, et la valeur de a de l’environnement e1, puisque la valeur est -2. Puis, on retire les changements de e1 grâce à removeEnv. L’appel m.g(0) utilise encore le f de e2, mais la valeur de a est la valeur initiale du module, 1.

Le diagramme illustre la chaîne d’environnements quand l’exécution atteint la ligne 12. L’environnement frontal (vide) a pour parent l’environnement e2 (▬ ), qui lui a comme parent e1 (▬ ), qui délègue à l’environnement de la FIA. Chaque ensemble de changements est isolé des autres, ce qui permet de les supprimer sans toucher aux autres, et tous sont ordonnés linéairement (le fil ▬ ), comme les couches d’un gâteau. Ainsi, la priorité de redéfinition est toujours déterministe: les définitions qui se trouvent le plus en tête (plus proches de l’environnement frontal) ont toujours priorité sur celles des environnements du bout de la chaîne.

On a donc une façon de modifier le comportement d’un module sans toucher au code qui le définit. Les changements sont écrits à l’extérieur du module, et peuvent même être déclarés dans des fichiers séparés. De plus, on peut dynamiquement activer ou désactiver des ensembles de changements d’un seul coup. Mais pour l’instant rien de ce qu’on a définit n’est exécutable. Il s’agissait d’illustrer le modèle de fonctionnement dans le cadre d’un langage inspiré de JavaScript. Ce faisant, on a dévié de JavaScript en supposant:

1. que les environnements se comportent comme des objets JavaScript standards, comme des dictionnaires auxquels on peut ajouter des propriétés, récupérer leur valeur;
2. qu’un environnement frontal est créé lors d’un appel à une fonction immédiatement appelée (FIA) sur laquelle repose le motif module, et qu’une référence vers cet environnement est retournée par la FIA;
3. que l’on pouvait obtenir et modifier le parent de n’importe quel environnement.

Aucune de ces suppositions n’est valide en JavaScript. Cependant, il y a moyen de réaliser ce modèle en utilisant des constructions standards de JavaScript. C’est l’objet de la section suivante.

On a vu dans l’étude de cas que l’implémentation de l’évaluation multi-facettes sur Narcissus pouvait être répartie en trois catégories de changements. La première catégorie était l’ajout du program counter par extension de l’objet ExecutionContext et d’arguments supplémentaires à la fonction getValue. On peut maintenant effectuer ce changement de l’extérieur du module:

 1: var N = Narcissus.interpreter._env
 2: 
 3: var EC = N.ExecutionContext
 4: function ExecutionContext(type, version) {
 5:   EC.call(this, type, version)
 6: 
 7:   this.pc = getPC() || new ProgramCounter()
 8: }
 9: 
10: ExecutionContext.prototype = Object.create(EC.prototype)
11: 
12: function getPC() {
13:   var x = EC.current
14:   return x && x.pc
15: }
16: 
17: var GV = N.getValue
18: function getValue(v, pc) {
19:   pc = pc || getPC()
20: 
21:   if (v instanceof FacetedValue)
22:     return derefFacetedValue(v, pc)
23: 
24:   return GV(v)
25: }
26: 
27: N.ExecutionContext = ExecutionContext
28: N.getValue = getValue

On commence par définir un nom raccourci ligne 1 pour l’environnement exporté par Narcissus. Puis on modifie le constructeur ExecutionContext après avoir sauvegardé l’original ligne 3, pour pouvoir y faire référence dans le nouveau constructeur, mais aussi dans getPC. Le nouveau constructeur appelle le constructeur original (équivalent à un appel à super en Java) et ajoute la valeur courante du program counter comme propriété pc. Les autres propriétés de l’objet ExecutionContext sont héritées par la ligne 10. Ligne 18, on définit une nouvelle fonction getValue qui va remplacer et appeler l’originale, mais qui récupère le program counter courant soit donné en argument, soit par un appel à getPC si l’argument n’est pas renseigné. De cette façon, les appels à getValue dans l’interpréteur ne nécessitent pas de modification pour l’argument supplémentaire, mais le code de l’instrumentation peut appeler getValue en passant une valeur pour pc. Enfin, on installe ces modifications dans l’environnement frontal de l’interpréteur (lignes 27 et 28).

La seconde catégorie de changements concernait l’extension de la fonction execute pour chaque nœud de l’AST, dans le but de scinder l’évaluation des valeurs à facettes en appelant la nouvelle fonction evaluateEach sur chacune des facettes. La fonction execute est essentiellement un long switch (600 lignes) avec un case pour chaque type de nœud de l’AST. On redéfinit la fonction execute en suivant la même structure.

29: var EX = N.execute
30: function execute(n.x) {
31:   switch (n.type) {
32:     case IF:
33:       var cond = N.getValue(
34:         N.execute(n.condition, x), x.pc)
35:       evaluateEach(cond, function(v, x) {
36:         if (v)
37:           N.execute(n.thenPart, x)
38:         else if (n.elsePart)
39:           N.execute(n.elsePart, x)
40:       }, x)
41:     break
42: 
43:     ... // other instrumented cases
44: 
45:     default: var v = EX(n, x)
46:   }
47:   return v
48: }
49: 
50: N.execute = execute

L’évaluation multi-facettes ne redéfinit le comportement que pour quelques types de nœuds de l’AST, donc on délègue à la fonction initiale dans le default ligne 45. En déclarant un case IF, on redéfinit le traitement des nœuds de type IF dans l’AST. Notons qu’ici on appelle récursivement N.execute, et que dans le code de la fonction d’origine, l’appel récursif est noté execute, mais après la ligne 50, les deux noms pointeront vers la même fonction: celle que l’on vient de définir.

Enfin, la troisième catégorie de changements regroupait les ajouts de propriétés à l’objet globalBase. Il s’agit donc de définir un nouvel objet globalBase qui hérite de l’objet original, mais auquel on rajoute les propriétés supplémentaires:

51: var globalBase = Object.create(N.globalBase)
52: 
53: globalBase.isFacetedValue = function(v) {
54:   return (v instanceof FacetedValue)
55: }
56: 
57: ...  // other properties
58: 
59: N.globalBase = globalBase

Mais ce n’est pas suffisant. Dans le module de Narcissus, l’objet globalBase est utilisé juste après sa création pour peupler l’objet global du code client. Ce processus prend place dans le module, avant que les propriétés exportées ne soient retournées. Or dans notre façon d’étendre le module, on ne peut modifier les valeurs qu’après l’export. Il nous faut donc modifier le code du module pour pouvoir effectuer ce changement. Il suffit de fournir une fonction populateEnvironment qui construit l’objet global à partir de globalBase, et qui devra être appelée après la construction du module. Ça nous laisse maintenant la possibilité d’étendre l’objet globalBase. Cette modification au module consiste à déplacer les 30 instructions qui peuplaient l’objet global dans la fonction populateEnvironment, et à rajouter cette nouvelle fonction dans les propriétés exportées.

Un dernier changement du module a été nécessaire, plus léger cette fois. Une fonction cruciale, la fonction utilisée par le code client pour déclencher un appel de fonction, était anonyme dans le module. Sans nom, il n’y avait aucun moyen de la redéfinir de l’extérieur du module; le motif « module ouvert » ne peut surcharger que des valeurs identifiées. Pour pouvoir redéfinir cette fonction, nous lui avons simplement donné un nom.

En plus de l’évaluation multi-facettes, on a défini trois autres analyses sur l’interpréteur: une simple analyse de trace, une analyse de flot d’information, FlowR, décrite par Pasquier, Bacon et Shand [PBS14], et une analyse qui extrait les objets et les environnements alloués par l’interpréteur, afin de récolter les informations pour dessiner les diagrammes de cette section.

L’analyse de trace est la plus simple: il suffit d’intercepter les appels à execute pour écrire sur la sortie standard quel le type du nœud de l’AST passé en paramètre, ce qui nous donne l’ordre d’évaluation du programme. Puisque execute est appelée récursivement, on indente aussi la sortie suivant la profondeur de la pile d’appel. Le simple code:

$ cat tests/function.js
function f(a) { return a }
f(1+1)

génère la trace:

$ ./njs -l trace -f tests/function.js
SCRIPT
  FUNCTION f(a)
  SEMICOLON
    CALL f((1 + 1))
      IDENTIFIER f
      LIST
        PLUS
          NUMBER 1
          NUMBER 1
      SCRIPT
        RETURN
          IDENTIFIER a

Ce qui donne suffisamment d’information pour suivre le chemin emprunté par l’interpréteur lorsqu’il évalue ce programme.

La nouvelle version de la fonction execute est simple:

function execute(proceed, n, x) {
  printIndentation(indentation);
  print(nodetypesToNames[n.type]);

  indentation += indentationStep;
  let ret = proceed(n, x);
  indentation -= indentationStep;

  return ret;
}

On instrumente aussi la fonction print, qui peut être utilisée par le code client et qui pourrait venir se mêler à la trace, puisque les deux écrivent sur la même sortie. On pourrait redéfinir le print client pour écrire sur une autre sortie (ou la trace), mais ici on a choisi de simplement préfixer les appels clients de print:

function printStdout(...args) {
  printIndentation(indentation);
  putstr('#output ');
  print(...args);
}

Il suffit ensuite d’insérer ces redéfinitions dans l’environnement du module. Comme l’insertion est systématique pour définir une analyse, on a défini une interface d’instrumentation légère, qui permet de masquer les détails de la manipulation des environnements, et de donner du code plus déclaratif:

i13n.pushLayer(_env, {
  execute: i13n.around(_env.execute, execute),
  globalBase: i13n.delegate(_env.globalBase,
                            {print: printStdout}),
});

La fonction i13n.pushLayer est un alias de la fonction pushEnv (cf. précedemment).

La fonction i13n.around(fn, a) retourne simplement une nouvelle fonction qui appelle la fonction a en lui passant fn, la fonction d’origine, en premier argument:

function around(fn, a) {
  return function(...args) {
    return a(fn, ...args);
  }
}

Le nom évoque le pointcut d’AspectJ éponyme; l’effet est proche. Cependant ici aucun tissage ne prend place: le code de fn n’est pas modifié. On retourne juste une nouvelle fonction.

L’autre motif récurrent est l’extension d’un objet défini par l’interpréteur. On pourrait directement ajouter notre nouvelle propriété dans l’objet en question (ici, globalBase), mais le changement serait irréversible. Pour que ce changement soit désactivable par i13n.removeLayer, il faut mettre dans notre couche d’instrumentation un objet qui contient la nouvelle propriété, et qui délègue les autres propriétés à l’objet initial. C’est conceptuellement le même principe que pour around, mais appliqué aux objets.

Et en JavaScript, il suffit d’utiliser la délégation par prototype pour réaliser ce motif d’extension:

function delegate(o, r) {
  var n = Object.create(o)
  Object.assign(n, r)
  return n
}

Le principe de l’analyse FlowR est d’empêcher des flots de données illicites dans le programme. Pour cela, on colle des étiquettes sur les fonctions, comme « privée » ou « interne », une approche similaire aux principals des valeurs à facettes. Il y a deux catégories d’étiquettes: les étiquettes d’envoi et les étiquettes de réception. Une étiquette d’envoi est propagée aux données retournées par la fonction, et une étiquette de réception indique quelles données peuvent être passées en argument à la fonction. L’algorithme de FlowR intercepte chaque appel de fonction, vérifie les étiquettes de réception pour s’assurer que les arguments reçus sont compatibles, puis exécute la fonction, et propage les étiquettes d’envoi sur la valeur retournée.

Un exemple, tiré de [PBS14], où, après affectation des étiquettes aux objets Patient et PublicData, le premier appel de méthode est exécuté, mais le second est interrompu pour cause de flot invalide de données:

$ cat tests/flowr.js
setTag(Patient, 'receive', 'medical', 1);
setTag(Patient, 'receive', 'default', 0);
// [...] set other tags

var p = new Patient();
var d = new PublicData();

d.add(p.generate_anonymized_record());  // should pass
d.add(p.get_record());                  // should fail

$ ./njs -l flowr -f tests/flowr.js
Illegal flow: undefined to [object Object]

Pour réaliser cette analyse, il suffit donc de permettre au code client d’ajouter des étiquettes aux fonctions (via une fonction qu’on appellera setTag), et de capturer chaque appel de fonction afin d’appliquer l’algorithme. Narcissus traite l’appel de fonction dans la fonction __call__ de l’objet FunctionObject. On remplace la fonction __call__ par notre propre version, qui exécute l’algorithme de FlowR. Voici notre version:

function flowrCall(__call__, receiver, args, caller)
{
  // [...] check send labels

  let ret = __call__.call(this, receiver,
                          args, caller);

  // [...] propagate labels to return value

  return ret;
}

Il n’est pas utile de s’attarder sur le code qui applique l’algorithme; ce sont de simples appels à des fonctions définies dans le même module. En revanche, on peut voir que l’on fait ici appel à la fonction __call__ d’origine, reçue comme premier argument. Donc notre flowrCall pourra être installé sur FunctionObjet en utilisant la fonction i13n.around définie plus haut.

L’objet FunctionObject est l’objet à partir duquel toutes les fonctions du code client sont créées—leur objet prototype. Lorsque l’interpréteur exécute un appel de fonction, il délègue le travail à la propriété __call__ de la fonction en question. Si on installe notre version flowrCall sur cet objet, on remplace donc la fonction __call__ sur toutes les instances de fonctions client. Mais on ne veut pas modifier directement un objet de l’interpréteur, car ce serait un changement irréversible.

Comme pour l’analyse de trace, on va créer un nouvel objet qui va contenir notre nouvelle version flowrCall, et déléguer le reste des propriétés à l’objet FunctionObject d’origine. On insère ensuite ce nouvel objet dans une couche, avec i13n.pushLayer, ce qui permettra de pouvoir le retirer dynamiquement. Et comme pour l’analyse de trace, on peut utiliser i13n.delegate pour cela.

Mais il y a une légère différence ici: FunctionObjet, contrairement à globalBase, est utilisé comme constructeur d’objet (pour créer les fonctions clientes). Donc il faut aussi créer notre propre constructeur. Toute cette machinerie est mise en place par la fonction i13n.override, qui utilise simplement around et delegate après avoir créé le constructeur:

function override(base, methods) {
  var newConstr = function(...args) {
    return base.apply(this, args)
  }

  for (var m in methods)
    methods[m] = around(base.prototype[m], methods[m])

  newConstr.prototype = delegate(base.prototype, methods)

  return newConstr
}

Et celle-ci nous permet d’installer l’analyse FlowR en quatre lignes:

i13n.pushLayer(_env, {
  FunctionObject: i13n.override(_env.FunctionObject, {
    __call__: flowrCall }),
  globalBase: i13n.delegate(_env.globalBase, {setTag}),
})

Les techniques que l’on propose dans ce chapitre sont basées essentiellement sur la manipulation d’environnements. Pour mieux comprendre ces manipulations, on a utilisé des diagrammes qui représentent les objets et les environnements créés par l’interpréteur, et leurs relations. Ces diagrammes sont un modèle simplifié du fonctionnement de l’interpréteur, mais sont basés sur les informations récoltées par l’analyse d’environnements.

L’analyse d’environnements est à la fois le dernier exemple d’analyse, mais aussi un outil qui a servi pour construire les diagrammes de ce chapitre. On va donc s’intéresser à son fonctionnement en plus de la façon de l’implémenter sur l’interpréteur.

L’analyse collecte tous les environnements créés par l’intepréteur, et les inspecte pour récolter tous les objets créés, en suivant les références des propriétés, les liens de prototype, et les liens d’envrionnement parent.

Mais tous les objets ne nous intéressent pas de la même façon. De nombreux objets font partie de l’API standard offerte par le langage, comme Array ou String. Ce n’est pas nécessaire de voir toutes leurs fonctions, toutes leurs propriétés, quand on s’intéresse au fonctionnement de with. On peut donc paramétrer le collecte d’objet par:

• une liste noire, qui indique quels objets il n’est pas nécessaire d’inspecter. Si l’analyse récolte un objet présent dans la liste noire, ses propriétés ne sont pas collectées récursivement. Typiquement, Object.prototype est un bon candidat pour la liste noire;
• une liste blanche, qui permet d’inspecter seulement les propriétés nommées dans un objet, et d’ignorer les autres. Quand on sait quel objet nous intéresse, cette liste permet de réduire considérablement le bruit dans le graphe créé. Dans l’exemple ci dessous, seule la propriété m de l’objet global est inspectée;
• la profondeur de recherche, qui limite le nombre d’appels récursifs quand l’analyse suit les références d’un environnement. Au delà, les objets sont « opaques »: leurs propriétés ne sont pas affichées. La boîte dessinée contient juste un identifiant unique.

Sur cet exemple d’utilisation de with, que l’on a vu de nombreuses fois dans ce chapitre:

$ cat tests/with.js
var m = (function() {
  var E = {};
  with (E) {
    var a = 1;
    return {E:E};
  }
}());

m.E.a = 2;

// [...] set up whitelist and blacklist of objects

printScope(2, whitelist, blacklist);

L’analyse produit un graphe au format DOT [dot] utilisé par GraphViz. On peut donc produire une image en invoquant dot:

$ ./njs -l scope -f tests/with.js | dot -Tsvg

Le rendu, visible en marge, est un peu brouillon, mais toute l’information est là. On peut y retrouver l’objet E, l’objet d’activation de la FIA, l’environnement créé par with. Et en faisant quelques simplifications, et en réorganisant les boîtes manuellement, on obtient les diagrammes du chapitre.

Pour collecter les environnements, il suffit de se greffer dans la fonction execute de l’interpréteur, et de conserver les environnements dans un ensemble.

let scopeObjects = new Set();

function harvestScopeObject(n, x) {
  scopeObjects.add(x.scope);
}

i13n.pushLayer(_env, {
  execute: i13n.before(_env.execute,
                       harvestScopeObject),
  globalBase: i13n.delegate(_env.globalBase,
                            {printScope}),
});

On utilise cette fois i13n.before plutôt que around, qui fait aussi écho au pointcut d’AspectJ. La fonction harvestScopeObject sera invoquée avant chaque appel d’execute, et récoltera l’environnement courant.

La fonction printScope, que l’on rajoute dans l’environnement client, va d’abord construire le graphe en parcourant tous les objets récoltés, puis produire le fichier au format DOT.

Notre instrumentation de Narcissus pour ajouter l’évaluation multi-facettes consiste en 440 lignes de code, dans un seul fichier séparé de l’interpréteur; l’instrumentation faite par Austin et Flanagan comportait 640 lignes mêlées au code de l’interpréteur. Notre version factorise quelques changements, ce qui explique la différence. L’intérêt d’avoir tous les changements dans un seul fichier à part c’est qu’on peut les étudier et avoir une idée de comment l’évaluation multi-facettes vient modifier l’interpréteur. On peut par exemple comparer le code de l’instrumentation avec la sémantique de référence de [AF12].

Pour ajouter l’évaluation multi-facettes, on a ajouté 19 lignes à Narcissus pour ouvrir le module avec with, et changé 43 lignes pour ajouter la fonction populateEnvironment et nommer la fonction anonyme. En tout 62 lignes sur 1300 sont touchées, à comparer avec les 640 lignes de l’instrumentation d’Austin et Flanagan. Mais même si les changements sont restreints, il est important de noter qu’il était tout de même nécessaire de modifier le code de Narcissus. Les changements, même mineurs, ont nécessité d’inspecter et de comprendre les différentes étapes de construction de l’interpréteur.

En plus de l’évaluation multi-facettes, on a défini trois autres analyses sur l’interpréteur: une analyse de flot d’information, une simple analyse de trace, et une analyse qui extrait les environnements alloués par l’interpréteur. On a pu écrire ces trois analyses dans des fichiers séparés, sans avoir besoin de modifier le code de l’interpréteur. Qui plus est, on a pu extraire des motifs communs d’instrumentation de fonctions (around, before), d’objets (delegate), ou les deux (override).

En utilisant la technique de disposition en couches (cf. précedemment), on peut activer plusieurs analyses à l’exécution avec des options de lancement. Par exemple:

./njs -l flowr -l trace -f tests/flowr.js

lance l’interpréteur, active l’analyse FlowR, et active aussi la trace avant d’exécuter le code du fichier « tests/flowr.js ». Un extrait de la sortie montre que les deux analyses fonctionnent en même temps:

    CALL d.add(p.get_record())
      DOT d.add
        IDENTIFIER d
      LIST
        CALL p.get_record()
          DOT p.get_record
            IDENTIFIER p
          LIST
          SCRIPT
Illegal flow: undefined to [object Object]

Le Illegal flow est produit par FlowR, et les autres lignes par la trace. L’union des deux sorties permet de visualiser à quel moment de l’interprétation les flots non autorisés se produisent, sans avoir à rajouter du code spécifique à la trace dans l’analyse FlowR.

La trace ne modifie qu’une seule fonction de l’interpréteur, et cette modification est compatible avec les modifications apportées par FlowR. Intuitivement, on voit bien que la trace est orthogonale au contrôle d’accès effectué par FlowR. C’est pourquoi les deux analyses peuvent être activées en même temps sans que l’on ait besoin de rajouter du code spécifique à l’intégration des deux. Ce n’est pas le cas pour l’évaluation multi-facettes et FlowR. L’évaluation multi-facettes modifie les valeurs manipulées par l’interpréteur, et FlowR rajoute des labels sur ces valeurs. Du coup, les deux analyses touchent à la représentation des valeurs dans l’interpréteur. En regardant leur spécification, on ne peut pas dire clairement comment les deux analyses doivent se combiner, ni ce que le résultat d’une évaluation devrait produire. Il faut donc retenir que la disposition en couches permet de facilement activer plusieurs modifications de l’interpréteur en même temps, mais que le résultat n’a de sens que si ces modifications n’interfèrent pas entre elles.

Pour s’assurer qu’appliquer with pour ouvrir Narcissus n’a pas changé son fonctionnement, nous avons comparé le comportement de la version d’origine et la version avec with sur la suite de tests test262. Cette suite contient plus de 11000 tests de conformité de la spécification ECMAScript 5.1. Nous avons utilisé un sous-ensemble de cette suite, utilisé pour tester le moteur JavaScript SpiderMonkey de Mozilla. Sur environ 3300 tests validés par SpiderMonkey, Narcissus en passe 2600. Nous avons donc lancé la version originale de Narcissus et la version avec with sur ces 3300 tests. Pour la version avec with, aucune analyse n’était activée: l’objet de liaison restait donc vide. Pour chaque test, notre script comparait les sorties des deux versions; un test réussissait seulement si les deux sorties étaient identiques. Au final, les deux versions ont un comportement strictement identique sur ce jeu de tests.

Nous avons aussi pu comparer Narcissus avec et sans l’évaluation multi-facettes sur ce même jeu de tests. Lorsque le program counter de l’évaluation multi-facettes est vide, l’interpréteur se comporte de façon identique sur les tests considérés. Un résultat démontré par Austin et Flanagan sur la sémantique de l’évaluation basée sur un lambda-calcul, mais pas sur l’implémentation basée sur le langage JavaScript.

En exécutant les tests, nous avons aussi mesuré le temps d’exécution de chaque version. Pour chaque version, le jeu de test a été lancé dix fois, sur un seul thread, toujours sur la même machine. Le tableau donne la moyenne arithmétique du temps pour une exécution complète sur ces dix lancers.

L’écart type est à moins de 1% pour toutes les versions de Narcissus, donc les temps moyens sont représentatifs. Si on compare l’interpréteur non instrumenté avec la version où on ajoute juste with autour du code du module, la seconde version prend 17% de temps supplémentaire pour exécuter le jeu de tests. Ce surcoût est probablement dû à l’utilisation de with, qui rajoute un environnement dans la chaîne de résolution des noms. Non seulement ça fait un objet de plus à parcourir lors de la résolution de n’importe quel nom du module, mais en plus les fonctions qui ont des variables libres ne peuvent pas être optimisées par le compilateur. Là où, sans with, un accès à une variable libre peut être résolu statiquement en regardant dans l’environnement lexical de la fonction, avec with la variable peut changer dynamiquement, donc le moteur d’exécution doit toujours résoudre le nom dynamiquement; aucun raccourci n’est possible.

Si on compare l’interpréteur instrumenté par Austin et Flanagan pour l’évaluation multi-facettes, le surcoût de temps n’est plus que 7%. Notons cependant que notre implémentation de l’évaluation multi-facettes factorise quelques changements par rapport à l’implémentation de base, on ne mesure pas seulement l’utilisation de with.

De toute façon, comme l’indique le tableau, exécuter n’importe quel exemple avec Narcissus est d’un ordre de grandeur plus lent qu’avec SpiderMonkey directement. C’est évidemment dû au fait que Narcissus est écrit en JavaScript. Mais pour nos besoins, les plus gros exemples qu’on a voulu exécuter avec les différentes analyses ajoutées à Narcissus n’ont pris que quelques secondes. À cette échelle, une différence de 17% est insignifiante.

Le gain de temps en écriture de code et en clarté de l’instrumentation est, quant à lui, tangible. Avant de pouvoir exécuter la suite test262 avec Narcissus, il a fallu corriger quelques erreurs dans son interprétation du code JavaScript et compléter sa couverture du standard. En corrigeant ces erreurs dans l’interpréteur d’origine, il a fallu dupliquer les correctifs dans la version instrumentée par Austin et Flanagan, mais pas dans notre instrumentation. Notre version de l’évaluation multi-facettes ne duplique pas le code de l’interpréteur, donc une fois le correctif appliqué à l’interpréteur de base, l’évaluation multi-facettes bénéficiait du correctif automatiquement. Cette anecdote illustre l’intérêt d’une décomposition qui cherche à minimiser la duplication de code.

On peut voir la propriété E qui expose l’environnement manipulable du module comme une interface spéciale, une interface d’instrumentation, qu’on peut rapprocher du concept d’« implémentation ouverte » de [Kic96]. Cette interface spéciale expose tous les noms de l’interpréteur, et confère donc aux programmeurs non seulement le pouvoir de modifier le code du module, mais également de casser ce code en créant des situations non anticipées par le créateur du module. Comme on a pu changer la fonction execute pour étendre sa fonctionnalité, on aurait pu tout aussi bien fournir une version qui lance une exception. Pas très utile dans notre cas, mais ça montre qu’il est très facile de rompre la fonctionnalité offerte par le module dès lors que cette interface spéciale est offerte.

On a alors une situation quelque peu paradoxale où le programmeur soucieux de l’intégrité de son code le ficelle dans un module, mais ce faisant empêche tout autre programmeur d’étendre son code dynamiquement. Le code a beau utiliser un module, il ne peut être étendu; il est modulaire, sans être extensible, car il faut modifier le code source à l’intérieur du module pour pouvoir y effectuer des changements. Et à l’inverse, la solution proposée ici casse la protection offerte par le module, mais ce faisant permet d’étendre le code en écrivant les changements et fonctionnalités supplémentaires dans des fichiers distincts; l’interpréteur devient extensible, mais perd l’encapsulation du module.

La version originale du module, et notre version modifiable dynamiquement sont deux points opposés sur un même axe. D’un côté, un programme prévisible, sur lequel il est facile de raisonner statiquement, car son comportement ne peut être modifié dynamiquement; et de l’autre, un programme ouvert, dont le comportement peut changer à tout moment de l’exécution, mais qui offre une grande flexibilité. Les propriétés offertes par l’un et l’autre sont toutes désirables: a priori, on préférerait avoir un programme prévisible et reconfigurable à souhait. Mais il est facile de voir que les deux buts sont antagonistes.

Prenons une simple fermeture:

const a = 1
function f() { return a }

À voir le code, on peut déclarer que lorsqu’on appelle f, elle renvoie toujours 1. C’est une fermeture sur a, et la valeur de a ne peut pas être modifiée car a est constante. « f renvoie 1 » est donc un invariant qui est utile pour le programmeur, une garantie du code qui permet de mieux comprendre les comportement des sites d’appels de f.

Mais en même temps, cette garantie rend la fonction inflexible. On ne peut pas changer le comportement de f sans violer cette garantie. Si on applique la technique de ce chapitre pour ouvrir la fonction avec with:

const a = 1
var E = {}
with (E) {
  function f() { return a }
}

f() //: 1

E.a = 2
f() //: 2

alors maintenant on peut modifier la valeur de retour de f, car on peut modifier a. C’est donc que la garantie ne tient plus. Tout ce qu’on peut dire de f c’est quelle retourne la valeur de a contenue dans E, si elle existe, et 1 sinon. Mais comme on ne sait rien de la valeur de a contenue dans E, autant dire que f renvoie n’importe quoi. On n’a plus aucune garantie sur f, mais une flexibilité complète pour la modifier.

On pourrait retrouver certaines garanties. Par exemple, si on veut que a soit toujours un nombre plus petit que 10, on peut protéger l’objet E et renvoyer un proxy:

const a = 1

var m = (function() {
  var E = {}
  with (E) { function f() { return a } }

  return {f,
    E: {
      set a(v) {
        if (typeof v === 'number' && v < 10)
          E.a = v
      }
  }}
}())

m.f() //: 1

m.E.a = 2
m.f() //: 2

m.E.a = "44"
m.f() //: 2

De cette façon, on retrouve une garantie: m.f renverra toujours un nombre plus petit que 10. Mais en échange, on perd en flexibilité, puisque a doit obéir à cette contrainte. Dès lors qu’on ajoute une contrainte, comme a < 10, la négation de cette contrainte n’est plus un cas possible pour le programme. Chaque contrainte restreint le programme, et assure ainsi des garanties supplémentaires, mais chaque contrainte exclut également des possibilités.

Si on ne peut pas complètement réconcilier la flexibilité dynamique et la garantie statique, on peut choisir le compromis entre ces deux extrêmes. Il y a toute une dimension entre le motif module, qui fixe les définitions, et l’utilisation de with dans le module, qui permet de les changer. C’est au programmeur de choisir le compromis le mieux adapté au problème.

Il y a d’autres façons, plus évidentes, d’ouvrir le module. Pour commencer, puisqu’on cherche à briser la protection offerte par la fonction anonyme, pourquoi ne pas l’enlever? Et définir nos fonctions directement à la racine:

var a = 1
function f(x) { return x + a }
function g(x) { return f(x) }

g(0) //: 1

Ainsi, on peut redéfinir les fonctions et les valeurs comme on le souhaite, et même dans des fichiers séparés, puisque toutes les définitions résident dans le même environnement.

var a = 1
function f(x) { return x + a }
function g(x) { return f(x) }

g(0) //: 1

function f(x) { return 2 }
g(0) //: 2

Mais utiliser with pour ouvrir le module n’anéantit pas toutes les protections offertes par la FIA. Avec with, on bénéficie encore de l’espace de nommage fourni par la fonction: toutes les définitions sont exportées dans un objet m, ou Narcissus.interpreter, ce qui réduit les chances d’une redéfinition accidentelle. Si on met toutes les définitions à la racine, alors on perd cet avantage.

On peut utiliser un objet pour protéger les définitions mais garder la possibilité de les modifier:

var m = {
  a: 1,
  f(x) { return x + m.a },
  g(x) { return m.f(x) },
}

m.g(0) //: 1

m.f = function(x) { return 2 }
m.g(0) //: 2

Ça demande de toujours préfixer les références aux définitions du module par l’identifiant de l’objet (ici, m). Pour cet exemple, ça ne fait que deux caractères en plus. Mais pour modifier un module existant, comme Narcissus, il faudrait préfixer des centaines de références. Et cette tâche ne peut pas être automatisée à tout coup, puisque le langage nous permet d’accéder à des références indirectement (m["f"]). C’est donc une solution moins pratique que de juste ajouter with autour du code.

Une autre solution, plus classique, serait de commencer par établir les points d’extension nécessaires pour les différentes analyses qu’on envisage d’utiliser (la fonction execute, par exemple), puis de rajouter un mécanismes explicite d’appel aux analyses quand l’interpréteur entre dans ces points. On pourrait utiliser des hooks, ou le patron Observateur, ou encore accepter un Visiteur; les trois méthodes permettent d’appeler du code extérieur au module à un moment précis du flot d’exécution.

Avec des hooks, ou un Observateur, il faut rajouter du code à l’intérieur du module à tous les endroits où le programmeur d’un module externe voudrait injecter du code, pour appeler explicitement soit une liste de fonctions, soit une liste d’observateurs. Le code externe doit à son tour déclarer quelles fonctions ou quel observateur il souhaite ajouter dans l’interpréteur. Le transfert de contrôle est explicite: il suffit de suivre le code dans l’interpréteur pour voir les appels à des hooks, ou une levée d’événements pour des observateurs. L’inconvénient est d’avoir à identifier les endroits qui peuvent intéresser du code externe, et d’ajouter des hooks explicitement dans le code pour chacun d’eux.

On utilise généralement ces techniques pour appeler du code qui ne change pas le flot de contrôle du module. Une fonction appelée par un hook n’effectue que des effets de bord (affichage sur la sortie standard), ou modifie des valeurs de son propre module; le processus de l’interpréteur n’est pas impacté. Ce serait donc une technique suffisante pour implémenter l’analyse de trace ou d’environnement, qui ne font qu’observer la descente récursive de l’interpréteur, mais l’analyse multi-facettes et l’analyse de flot requièrent de changer le résultat.

Le patron Visiteur permettrait de changer le résultat de l’interpréteur. Si on suit ce patron, il faut réécrire l’interpréteur pour appeler, pour chaque nœud de l’AST, la méthode correspondante de l’objet visiteur. Cet objet est passé à l’interpréteur avant l’évaluation de code, et c’est ce visiteur qui contient la logique d’évaluation. L’évaluation du code JavaScript standard devrait donc être mise dans un tel objet, pour obéir à l’interface du visiteur. Et les analyses pourraient alors également obéir à cette interface, et réutiliser le code de l’évaluation standard par simple délégation.

Ici encore, le flot de contrôle est explicite: toute la logique est déléguée au visiteur. L’inconvénient majeur est qu’il faut d’abord établir une interface de visiteur qui convienne à tous les besoins des différentes analyses, puis complètement réécrire l’interpréteur pour se conformer à cette interface.

Toutes ces techniques demandent donc de modifier l’interpréteur en profondeur, alors qu’on a vu que with suffisait pour redéfinir n’importe quelle fonction de l’interpréteur, sans avoir à définir d’interface au préalable, et en n’ajoutant que quelques lignes.

Une différence majeure néanmoins est que si le module utilise un hook, un observateur, ou un visiteur, alors les extensions de ce module (les analyses dans le cas de l’interpréteur) doivent nécessairement passer par l’interface d’extension définie par l’interpréteur. Avec with, ce sont les extensions elles-mêmes qui peuvent redéfinir n’importe quelle fonction du module; comme si l’interface d’extension était totale, mais sans avoir à le déclarer explicitement. Avec with, le programmeur des extensions a la responsabilité de maintenir le lien qui lui permet d’inclure son code dans le processus de l’interpréteur (les appels à around, override, delegate, …); le programmeur de l’interpréteur ne peut pas savoir où les extensions vont se greffer, il n’a pas à s’en soucier, d’où moins de code à maintenir.

Étendre un module par du code extérieur sans que le code du module n’expose d’interface pour, activer et désactiver les extensions dynamiquement, les combiner … ces objectifs rappellent fortement la programmation par aspects.

Comme on l’a vu dans les différentes analyses ajoutées à Narcissus, on utilise le vocabulaire d’AspectJ: around, before, proceed. Donc pourquoi ne pas utiliser directement la programmation par aspects, qui est un paradigme général, plutôt que de passer par with et les prototypes, qui sont des mécanismes propres à JavaScript?

En utilisant une bibliothèque d’aspect pour JavaScript, on pourrait définir chaque analyse dans son propre fichier, puis l’intégrer dynamiquement à l’exécution de l’interpréteur avec des méthodes d’aspect qui ciblent les jonctions adéquates (l’appel de execute). On pourrait activer et désactiver les méthodes d’aspect pour activer ou désactiver dynamiquement les analyses. On aurait effectivement le même résultat, mais exprimé en terme d’aspects; une technique qui pourrait plus facilement se transporter à tout langage disposant d’une bibliothèque de programmation par aspects.

Idéalement.

On a initialement cherché à utiliser une bibliothèque d’aspects pour instrumenter Narcissus: AspectScript est la plus complète [TLT10]. Il y a deux raisons majeures de préférer l’approche de ce chapitre à AspectScript pour l’instrumentation de Narcissus: la compatibilité et la performance.

AspectScript est une bibliothèque d’aspects qui réifie tout le code qui doit être instrumenté. Pour qu’un module puisse émettre des jonctions, il faut l’envoyer à AspectScript, qui va en faire l’analyse syntaxique, et émettre du code qui réifie les déclarations, les appels de fonction, les affectations de variable, toutes les constructions du langage en appels explicites à AspectScript. C’est comme ça qu’AspectScript peut capturer n’importe quel évènement du module.

AspectScript transforme ce module:

var m = (function() {
  var a = 1;
  function f(x) { return x + a; }
  function g(x) { return f(x); }
  return {g: g, f: f};
}());

en ce code:

var m = AS.i13n.propWrite(
  AS.globalObject, "m",
  (AS.i13n.call(
    AS.globalObject,
    AS.i13n.wrap(function(){return (function (){
      {arguments.callee = arguments.callee.wrapper;
       var f = AS.i13n.varWrite(
         "f",
         AS.i13n.wrap(function(){return (function f(x){
           {var f = arguments.callee
                  = arguments.callee.wrapper;
            return (AS.i13n.varRead("x",x))
                   + (AS.i13n.varRead("a",a));
           }})}),undefined);
       var g = AS.i13n.varWrite(
         "g",
         AS.i13n.wrap(function(){return (function g(x){
           {var g = arguments.callee
                  = arguments.callee.wrapper;
            return AS.i13n.call(
              AS.globalObject,
              (AS.i13n.varRead("f",f)),
              [(AS.i13n.varRead("x",x))],this);
           }})}),undefined);
       var a = (AS.i13n.varWrite("a", 1, undefined));
       return AS.i13n.creation2(
         function(){
           var $__this__=arguments[0];
           arguments=arguments[1];
           AS.i13n.propWrite($__this__, "g",
                             (AS.i13n.varRead("g",g)));
           AS.i13n.propWrite($__this__, "f",
                             (AS.i13n.varRead("f",f)));
         },this,arguments);
      }})}),[],this)));

En somme, AspectScript interprète le code du module, délègue l’évaluation au moteur d’exécution sous-jacent. Au passage, il émet des joinpoint pour chaque construction, teste les pointcut pour tous les advice enregistrés, et exécute le code si le pointcut correspond.

Ce mode de fonctionnement a deux inconvénients. D’abord, AspectScript duplique évidemment le travail du moteur d’exécution de JavaScript, ce qui est inefficace, mais surtout qui peut changer la sémantique du programme instrumenté. Puisqu’AspectScript interprète le code du module ciblé, et délègue l’évaluation au moteur d’exécution, on n’a aucune garantie qu’un appel de fonction capturé par AspectScript obéit aux mêmes invariants qu’un appel de fonction standard. Quand on instrumente un module aussi large que Narcissus, on cherche à éviter d’introduire des erreurs subtiles dans du code qu’on ne maîtrise pas. Mais comme AspectScript ajoute une étape d’interprétation supplémentaire, si on cherche à comprendre un bogue de Narcissus il faut aussi prendre en compte l’implémentation d’AspectScript.

call: function (obj, fun, args, context){
  acChecker.checkCall(obj, fun);

  if(!weavingNeeded()){
    return fun.apply(obj, args);
  }

  var call = jpPool.get(JP_CALL, obj, fun, args,
                        context, currentJoinPoint);
  if(systemObjects.indexOf(obj) >= 0){
    try{
      return call._proceed();
    }
    finally{
      jpPool.release(call);
    }
  }

  return weave(call);
},

Le second inconvénient est que pour faire l’analyse syntaxique du code, AspectScript utilise son propre analyseur, ce qui encore une fois peut introduire des déviations par rapport à l’analyseur du moteur d’exécution. JavaScript est un langage en évolution, et l’analyseur d’AspectScript ne suit pas cette évolution. Du code qui utilise des extensions de syntaxe des dernières versions de JavaScript s’exécutera correctement sur le navigateur, mais pas s’il est instrumenté par AspectScript.

Parce qu’AspectScript réinterprète le code, et utilise son propre analyseur, il pose des problèmes de compatibilité. Mais ces mécanismes ont également un coût important en temps d’exécution et espace mémoire. AspectScript est 5 à 15 fois plus lent qu’un moteur d’exécution de JavaScript. Sachant qu’on cherche ici à instrumenter un interpréteur de JavaScript, et qu’on perd déjà un ordre de grandeur de performance en utilisant un interpréteur métacirculaire, rajouter une couche d’interprétation d’AspectScript n’est pas idéal, surtout s’il y a une alternative qui nous permet d’étendre l’interpréteur avec la même flexibilité à un coût de performance moindre.

La programmation par aspects est donc un bon candidat pour le scénario d’instrumentation de Narcissus, mais l’implémentation d’AspectScript n’est pas une solution adéquate pour des raisons techniques. Une autre implémentation d’aspects pour JavaScript existe dans la littérature [LVG10], mais elle ne cible qu’une version interne modifiée du navigateur Internet Explorer.

On n’a pas utilisé une bibliothèque d’aspects, mais l’approche de ce chapitre est certainement ancrée dans le paradigme de la programmation par aspects. Et c’est justement intéressant de voir que la simple manipulation de la portée des variables suffit pour obtenir la flexibilité souhaitée pour ajouter des analyses à l’interpréteur.

AspectJ fournit des coupes bien plus riches que celles qu’on a utilisées ici. On n’a pas eu besoin d’intercepter des appels de fonction en testant les paramètres (le pointcut args), ni de connaître l’état de la pile d’appels (cflow). Les fonctions que l’on a emprunté à AspectJ, around, before, sont triviales, définies en 3 lignes.

Le seul mécanisme dont on a eu besoin existait déjà en JavaScript: la possibilité d’intercepter la résolution d’un nom (de variable ou de fonction) via with. Autrement dit, la manipulation de la portée des variables suffit pour détourner Narcissus.

Et la portée est un concept qui se retrouve dans de nombreux langages de programmation, pas seulement en JavaScript. Ce qui veut dire que la manipulation de portée effectuée dans ce chapitre, et illustrée par les diagrammes, est applicable à d’autres langages, même s’ils ne disposent pas d’une construction analogue à with. Il suffit de permettre au code client de manipuler directement la résolution de portée, par un mécanisme réflexif par exemple.

L’utilisation de with comporte néanmoins quelques inconvénients. On utilise with ici juste parce que c’est le seul moyen qu’on a de manipuler la portée des variables du code du module en JavaScript standard. Ça nous évite d’avoir à modifier le moteur d’exécution pour exposer le mécanisme de résolution de portée, ce qui permet à notre solution de fonctionner sur n’importe quel interpréteur JavaScript.

Néanmoins, certaines constructions ne peuvent pas être instrumentées. L’environnement créé par with ne capture pas les déclarations de fonctions qui ne sont pas écrites à la racine du module. Une fonction interne ne peut donc pas être instrumentée. Les alias de fonctions ne sont pas instrumentés automatiquement non plus: si m.a et m.b sont deux références au même objet dans le module, alors redéfinir m.a ne change pas m.b, puisqu’on ne souhaite pas modifier les objets du module, seulement changer les références pour pointer vers de nouvelles variantes. Enfin, les fonctions anonymes ne peuvent pas être instrumentées, n’ayant de nom pour pouvoir les référencer.

Et surtout, with est une construction dépréciée du langage, et notamment interdite dans le « mode strict » du standard ECMASCript 5.1. Concrètement, ça veut dire qu’un module écrit dans ce mode strict ne peut pas être étendu avec with. C’est une nouvelle manifestation du compromis entre flexibilité et sûreté du code; le mode strict offre davantage de garanties pour le programmeur (en particulier, l’absence de with), et en échange il perd la possibilité d’appliquer la technique de ce chapitre.