Barbara Liskov a consacré sa carrière à une difficulté qui accompagne
tous les grands logiciels : comment modifier une partie d’un système
sans devoir comprendre ni réécrire toutes les autres ? Sa réponse
passe par des interfaces précises, des représentations cachées et des
propriétés que les composants doivent continuer de respecter lorsqu’ils
évoluent.
Cette démarche a produit plusieurs contributions durables. Dans les
années 1970, Liskov et son équipe du MIT conçoivent CLU, premier
langage implanté à intégrer directement l’abstraction de données. Ses
travaux sur les hiérarchies de types conduisent ensuite au principe de
substitution qui porte son nom. Puis Argus, Viewstamped Replication et
ses recherches sur la tolérance aux fautes appliquent la même exigence
de raisonnement à des programmes répartis entre plusieurs machines.
Liskov n’a donc pas seulement ajouté des fonctionnalités à des langages.
Elle a contribué à définir une méthode : décrire ce qu’un composant
garantit, masquer la manière dont il le réalise et préserver ce contrat
lorsque le système grandit.
Du calcul scientifique à la question de la complexité logicielle
Née en 1939 à Los Angeles et élevée à San Francisco, Barbara Huberman
étudie les mathématiques à l’université de Californie à Berkeley. En
1961, elle rejoint la MITRE Corporation comme programmeuse.
L’informatique universitaire est encore jeune et la formation
spécialisée rare : elle apprend notamment Fortran dans le cadre de son
travail.
Elle poursuit ensuite des études d’informatique à Stanford sous la
direction de John McCarthy. Sa thèse, achevée en 1968, porte sur un
programme de jeu d’échecs. Liskov devient l’une des premières femmes aux
États-Unis à obtenir un doctorat délivré par un département
d’informatique, dans un milieu où les femmes restent très minoritaires.
De retour à MITRE, elle participe au système expérimental Venus. Ce
travail l’amène vers un problème plus général que l’écriture d’un
algorithme isolé. Le matériel possède des frontières visibles : des
composants sont reliés par des connexions définies. Dans un logiciel,
rien n’empêche au contraire une partie d’accéder aux détails d’une
autre. À mesure que le programme grandit, ces dépendances rendent chaque
changement risqué.
En rejoignant le MIT au début des années 1970, Liskov cherche donc des
contraintes intellectuelles et linguistiques capables de donner au
logiciel une modularité comparable.
L’abstraction de données : séparer le contrat de la représentation
Un type abstrait se définit par les opérations qu’il offre et par leurs
propriétés, non par la structure de données utilisée en interne. Une
pile, par exemple, peut exposer les opérations empiler, dépiler et
sommet. Le code client doit raisonner sur leur comportement sans
savoir si la pile repose sur un tableau, une liste chaînée ou une autre
représentation.
Cette séparation apporte trois bénéfices liés :
- le client manipule une interface plus petite que l’implémentation
complète ;
- l’auteur du module peut changer la représentation sans casser les
utilisateurs ;
- les propriétés du module peuvent être expliquées et vérifiées
indépendamment du reste du système.
La nouveauté n’est pas la simple idée de regrouper des sous-programmes.
Liskov donne une place centrale à la barrière d’abstraction : les
valeurs du type ne peuvent être construites et observées qu’au moyen des
opérations autorisées. L’implantation devient réellement cachée, au lieu
de rester une convention que n’importe quel appelant peut contourner.
Ce raisonnement paraît familier parce qu’il structure aujourd’hui les
classes, modules, bibliothèques et API. Au début des années 1970, il
faut encore montrer comment un langage peut le faire respecter et
comment un programmeur peut bâtir un système entier à partir de ces
unités.
CLU : inscrire l’abstraction dans le langage
À partir de 1973, le Programming Methodology Group du MIT transforme
cette idée en un langage expérimental : CLU, dont le nom vient de
cluster. Un cluster rassemble la représentation privée d’un type et
les opérations publiques qui permettent de le manipuler.
Liskov dirige le projet, mais CLU est une création collective. Alan
Snyder, Russell Atkinson, Craig Schaffert et d’autres étudiants et
chercheurs participent à la conception, au compilateur, à
l’environnement et à la documentation. Le projet sert à tester les idées
sur des programmes réels plutôt qu’à publier uniquement une notation
théorique.
CLU introduit ou combine plusieurs mécanismes qui influenceront les
langages ultérieurs :
- les types abstraits avec représentation cachée ;
- les types paramétrés, qui permettent par exemple de définir une
collection indépendamment du type de ses éléments ;
- les itérateurs, qui parcourent une structure sans révéler son
organisation interne ;
- une gestion structurée des exceptions ;
- une mémoire gérée automatiquement et des objets accessibles par
référence.
Le langage ne devient pas un produit industriel majeur. Dans les années
1970, diffuser un langage universitaire exige des portages, un soutien
durable et souvent l’adoption par une entreprise. Quelques centaines de
groupes l’utilisent, selon Liskov, mais son équipe privilégie finalement
de nouveaux sujets de recherche.
Son influence n’en est pas moins profonde. Des mécanismes devenus
courants dans Ada, C++,
Java, C# ou les langages modernes
reprennent, avec des syntaxes et des modèles différents, des problèmes
que CLU avait placés au centre de sa conception.
Du type abstrait au principe de substitution
Masquer une représentation ne suffit pas lorsque des types sont
organisés en hiérarchie. Si un programme attend un objet d’un type donné
et reçoit un objet d’un sous-type, ce remplacement doit-il toujours être
sûr ? Une simple ressemblance de méthodes ne garantit pas que leurs
comportements soient compatibles.
Liskov formule en 1987 une propriété de sous-typage comportemental,
développée ensuite avec Jeannette Wing. Dans sa forme pratique, le
principe de substitution de Liskov affirme qu’un objet d’un
sous-type doit pouvoir remplacer un objet du type de base sans rendre
faux ce que le programme client pouvait légitimement supposer.
Prenons un type Compte dont l’opération de retrait garantit qu’un
montant accepté sera déduit du solde. Un sous-type qui refuse
arbitrairement certains retraits pourtant autorisés par le contrat ne
constitue pas un remplacement correct, même s’il possède une méthode du
même nom. Il renforce une condition d’appel sur laquelle le client ne
comptait pas.
Le principe ne dit donc pas seulement « les sous-classes doivent avoir
la même interface ». Il impose de préserver le sens de cette interface :
ne pas exiger davantage de l’appelant, ne pas promettre moins en
résultat et maintenir les invariants annoncés.
Cette idée éclaire une limite fréquente de la programmation orientée
objet. L’héritage de code
peut être commode, mais une hiérarchie n’est robuste que si elle
représente une relation comportementale cohérente. Lorsque ce contrat ne
tient pas, la composition ou deux abstractions distinctes sont souvent
préférables.
Argus : maintenir les abstractions malgré les pannes
Après CLU, Liskov applique ses méthodes aux systèmes distribués. Dans un
programme exécuté sur plusieurs machines, une opération peut être
interrompue par une panne ou une coupure réseau. Certaines parties
peuvent continuer pendant que d’autres deviennent inaccessibles. Le
programmeur doit néanmoins préserver les données et éviter les résultats
partiellement appliqués.
Le langage Argus, développé au MIT à partir de la fin des années
1970, organise un système autour de guardians. Chaque guardian
encapsule un état et les opérations qui y accèdent, prolongeant la
logique des types abstraits dans un environnement distribué. Des actions
atomiques permettent de regrouper plusieurs modifications : elles
doivent réussir ensemble ou être annulées afin de ne pas laisser le
système dans un état incohérent.
Argus ne supprime pas la difficulté des pannes. Il donne au programmeur
des abstractions pour exprimer où se trouve l’état, quelles opérations
sont protégées et comment un calcul se rétablit. Cette démarche
préfigure les cadres modernes où transactions, services et réplication
doivent coopérer sans exposer chaque détail du réseau au code
applicatif.
Réplication, bases d’objets et tolérance aux fautes
Les recherches de Liskov dépassent ensuite les langages. Avec Brian Oki,
elle publie en 1988 Viewstamped Replication, un protocole qui
maintient plusieurs copies cohérentes d’un service. Une réplique
principale ordonne les opérations ; si elle tombe en panne, les autres
doivent choisir une nouvelle vue et continuer sans perdre les décisions
déjà validées.
Le protocole appartient à la famille des techniques de réplication de
machines à états qui sous-tendent aujourd’hui des services distribués à
haute disponibilité. Son importance vient de la précision avec laquelle
il relie ordre des opérations, changement de responsable et récupération
après panne.
Le projet Thor explore ensuite une base de données orientée objet
donnant un accès transactionnel à des objets persistants. Plus tard,
Liskov et Miguel Castro travaillent sur la tolérance aux fautes
byzantines, où certains nœuds peuvent se comporter de manière arbitraire
plutôt que simplement s’arrêter.
Ces sujets paraissent éloignés de CLU, mais ils prolongent la même
question. Un composant doit offrir une garantie compréhensible même
lorsque son implantation est complexe, distribuée et susceptible de
tomber en panne.
Une contribution collective devenue infrastructure intellectuelle
Liskov reçoit le prix Turing 2008 pour ses contributions aux fondements
pratiques et théoriques des langages et de la conception de systèmes.
Cette reconnaissance ne transforme pas ses projets en œuvres solitaires.
CLU dépend du Programming Methodology Group ; le principe de
substitution est approfondi avec Jeannette Wing ; Viewstamped
Replication est conçu avec Brian Oki ; Argus, Thor et les systèmes
tolérants aux fautes mobilisent de nombreux étudiants et collaborateurs.
Son rôle distinctif consiste à maintenir un fil directeur entre ces
travaux. Elle part d’un problème concret de construction logicielle,
formule l’abstraction nécessaire, l’incorpore dans un langage ou un
système, puis l’évalue par l’implantation.
Cette méthode explique pourquoi CLU reste important malgré sa diffusion
limitée. Un langage de recherche peut transformer l’informatique sans
devenir dominant : il rend des idées testables, révèle leurs limites et
fournit un vocabulaire que d’autres écosystèmes peuvent reprendre.
Pourquoi Barbara Liskov compte encore
Une grande partie du développement moderne repose sur des frontières :
API publiques, modules, services, types, contrats et protocoles. Ces
frontières permettent à plusieurs équipes de travailler séparément et à
une implantation d’évoluer sans imposer une réécriture générale.
Les travaux de Liskov rappellent toutefois qu’une frontière syntaxique
n’est pas suffisante. Un module utile doit cacher les bons détails. Un
sous-type doit préserver le comportement promis. Un service répliqué
doit maintenir ses garanties quand une machine disparaît. L’abstraction
n’est pas une façon d’ignorer la réalité ; c’est une façon de la
contenir derrière un contrat explicite.
Cette exigence relie les langages de programmation aux systèmes
distribués. Qu’il s’agisse d’une collection en mémoire ou d’un service
réparti dans plusieurs centres de données, la question reste la même :
sur quelles propriétés le reste du programme peut-il compter ?
Chronologie
- 1939 : naissance de Barbara Huberman à Los Angeles, en
Californie.
- 1961 : diplôme de mathématiques à l’université de Californie à
Berkeley, puis début comme programmeuse à MITRE.
- 1968 : doctorat en informatique à Stanford sous la direction de
John McCarthy.
- 1972 : arrivée au MIT, où elle développe ses travaux sur la
méthodologie de programmation.
- 1973 : lancement du projet CLU avec le Programming Methodology
Group.
- 1976 : publication d’une présentation majeure des mécanismes
d’abstraction de CLU.
- Années 1980 : développement d’Argus pour la programmation
distribuée et les actions atomiques.
- 1987 : formulation du principe de sous-typage comportemental qui
sera connu comme le principe de substitution de Liskov.
- 1988 : publication de Viewstamped Replication avec Brian Oki.
- 1994 : publication avec Jeannette Wing d’une formulation
approfondie du sous-typage comportemental.
- 2008 : attribution du prix Turing pour ses contributions aux
langages et à la conception de systèmes.
- 2018 : attribution de l’IEEE Computer Pioneer Award pour ses
travaux sur l’abstraction, CLU et Argus.
Questions fréquentes
Qu’a inventé Barbara Liskov ?
Elle a joué un rôle central dans la formulation de l’abstraction de
données, dirigé la création de CLU et formulé la propriété devenue le
principe de substitution de Liskov. Elle a également contribué à Argus,
Viewstamped Replication et plusieurs systèmes de stockage distribués.
Chacun de ces projets est le résultat d’un travail collectif qu’elle a
dirigé ou mené avec des collaborateurs.
Qu’est-ce qu’un type abstrait de données ?
C’est un type défini par les opérations et les propriétés qu’il
garantit, tandis que sa représentation interne reste cachée. Le code
client peut ainsi utiliser une pile, un ensemble ou une table sans
dépendre de la structure précise choisie pour les implanter.
Pourquoi CLU est-il important s’il a été peu utilisé ?
CLU a permis de tester dans un langage complet les types abstraits, les
itérateurs, les exceptions et les types paramétrés. Ces mécanismes ont
influencé la conception et les pratiques de langages ultérieurs, même si
CLU lui-même n’a pas obtenu une large diffusion commerciale.
Que dit exactement le principe de substitution de Liskov ?
Il exige qu’un objet d’un sous-type puisse remplacer un objet du type de
base sans violer les propriétés sur lesquelles le programme client
s’appuie. La compatibilité porte donc sur le comportement promis, pas
seulement sur les noms et signatures des méthodes.
Quel lien existe entre CLU et les systèmes distribués de Liskov ?
Les deux cherchent à contenir la complexité derrière des abstractions
explicites. CLU protège la représentation d’un type ; Argus et les
protocoles de réplication protègent les garanties d’un service malgré la
concurrence, la distribution et les pannes.
