Informatique

L'évolution des langages informatiques

Des nombres perforés sur un ruban aux langages qui protègent le programmeur contre lui-même : cinq planches pour comprendre comment l'on a appris à parler aux machines.

Un langage, c'est une échelle

Un processeur ne comprend que des nombres : chaque instruction est un code. Un langage de programmation est une manière plus commode, pour un être humain, d'écrire ces codes ; un programme de traduction, l'assembleur, le compilateur ou l'interpréteur, fait le reste. Toute l'histoire des langages consiste à monter les barreaux de cette échelle : s'éloigner de la machine pour se rapprocher de la pensée, sans rien perdre en exactitude.

La même opération, « ajouter n à s », écrite à chaque niveau. La flèche rouge descend comme le fait la traduction automatique, jusqu'aux bits que la machine exécute.

Planche 1

L'assembleur : des noms à la place des nombres

1947 – 1955

Les premiers programmes s'écrivaient directement en nombres, perforés sur un ruban de papier. Il fallait connaître par cœur le code de chaque opération et calculer à la main l'adresse de chaque case. Dès 1947, Kathleen Booth propose une notation symbolique, et Maurice Wilkes fait lire à l'EDSAC de Cambridge (1949) des instructions écrites en lettres. On écrit LOAD n plutôt que 112, et l'on nomme les endroits du programme par des étiquettes. Un programme traducteur, l'assembleur, remplace les noms par les nombres.

Programme

A48

B18

Source en assembleur. Colonnes de droite : l'adresse donnée par la première passe, puis le mot machine produit par la seconde (code d'opération × 100 + adresse).

Table des symboles

Chaque étiquette reçoit l'adresse de sa ligne pendant la première passe.

Codes des opérations

HALT	LOAD	STORE	ADD	SUB	JMP	JZ	JN
0	1	2	3	4	5	6	7

JZ saute si l'accumulateur est nul, JN s'il est négatif ; DATA réserve une case contenant un nombre.

Le ruban perforé produit : une colonne par mot machine, un trou par bit à 1 (poids fort en haut). La rangée de petits trous sert à entraîner le ruban.

Lignes par seconde3

Étape

—

Lignes / étiquettes

—

Références en avant (étiquette utilisée avant d'être définie)

—

Mots machine perforés

—

Résultat de l'exécution (instructions exécutées)

—

Résultat attendu (calcul direct)

—

Ce qu'il faut retenir. Pourquoi deux passes ? Parce qu'un programme utilise des étiquettes avant de les définir : à la ligne « JZ fin », l'assembleur ne sait pas encore où se trouve fin. La première passe ne fait que mesurer et nommer ; la seconde traduit. Le résultat est exactement le programme que l'on aurait écrit à la main, sans les erreurs de calcul d'adresse. Mais l'assembleur reste lié à une machine précise : chaque processeur a le sien, et le programme ne se transporte pas.

Planche 2

Le compilateur : écrire des formules, pas des instructions

1957 – 1960

En 1954, John Backus et son équipe chez IBM entreprennent un projet jugé irréaliste : traduire automatiquement des formules mathématiques en code machine aussi rapide que celui d'un programmeur expert. FORTRAN (FORmula TRANslation) sort en 1957. Son compilateur découpe la formule en jetons, la range dans un arbre syntaxique qui respecte la priorité des opérations, puis parcourt l'arbre pour produire les instructions. En 1960, le rapport ALGOL 60 décrit pour la première fois la grammaire d'un langage par des règles formelles, la notation de Backus et Naur.

Formule

ou tapez :

La grammaire utilisée (notation de Backus-Naur)

<expression> ::= <terme>
               | <expression> + <terme>
               | <expression> − <terme>
<terme>      ::= <facteur>
               | <terme> * <facteur>
               | <terme> / <facteur>
<facteur>    ::= <base> | <base> ^ <facteur>
<base>       ::= nombre | variable
               | ( <expression> ) | − <base>

Chaque règle devient une fonction du compilateur. La priorité de * sur + n'est écrite nulle part ailleurs : elle découle de l'emboîtement des règles.

L'arbre syntaxique construit par le compilateur. Pendant l'exécution, chaque nœud calculé affiche sa valeur en vert ; à droite, la pile de la machine.

Instructions par seconde2

Code produit pour une machine à pile

Jetons / nœuds / profondeur de l'arbre

—

Notation polonaise inverse (ordre du parcours)

—

Hauteur de pile maximale mesurée

—

Hauteur prévue par la règle d'Ershov

—

Résultat de la machine

—

Contrôle : évaluation récursive directe de l'arbre

—

Ce qu'il faut retenir. Le programmeur n'écrit plus « charger, ajouter, ranger » mais une formule ; c'est le compilateur qui choisit l'ordre des opérations. Comparez « a − b − c » (l'arbre penche à gauche : on soustrait de gauche à droite) et « 2 ^ 3 ^ 2 » (l'arbre penche à droite : 2⁹ = 512, et non 8² = 64) : la grammaire tranche ces ambiguïtés une fois pour toutes. La place mémoire nécessaire se prévoit sur l'arbre seul (règle d'Ershov, 1958 : une feuille demande 1 case, un nœud demande le maximum entre la hauteur de son fils gauche et celle de son fils droit plus un), et la mesure lui donne raison. Surtout, une même formule FORTRAN pouvait désormais être compilée pour des machines différentes : le programme devenait transportable.

Planche 3

Lisp et la récursivité : une fonction qui s'appelle elle-même

1958

En 1958, John McCarthy crée Lisp au MIT pour l'intelligence artificielle. Lisp traite les programmes comme des listes, et surtout il rend naturelle la récursivité : une fonction peut se définir à partir d'elle-même, comme en mathématiques. Exemple : la suite de Fibonacci, où chaque terme est la somme des deux précédents. L'ordinateur garde la trace des appels en cours sur une pile d'appels.

(defun fib (n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

Vitesse4

L'arbre des appels se dessine dans l'ordre où l'ordinateur les fait. Les appels en cours, empilés, sont en rouge ; un appel terminé affiche sa valeur en vert ; un appel servi par la mémoire est grisé. À droite, la pile d'appels.

Appels effectués

—

Nombre d'appels prévu

—

Hauteur de pile actuelle / maximale

—

Résultat fib(n)

—

Contrôle par une boucle simple

—

fib(30) sans mémoire : appels comptés ici, et 2F(31) − 1

—

fib(30) avec mémoire : appels comptés

—

Ce qu'il faut retenir. Le programme récursif est la traduction mot pour mot de la définition mathématique, ce qui le rend clair et sûr. Mais l'arbre montre son défaut : fib(3) est recalculé plusieurs fois, et le nombre d'appels, 2F(n+1) − 1, croît aussi vite que la suite elle-même (plus de deux millions et demi d'appels pour n = 30). La mémoïsation, qui range chaque résultat pour ne plus le recalculer, ramène ce nombre à 2n − 1. La hauteur de pile, elle, ne dépasse jamais n. Lisp a apporté bien d'autres idées reprises partout : le ramasse-miettes qui libère la mémoire inutile, les fonctions passées en arguments, l'interpréteur interactif. Ses descendants, ML, Haskell, OCaml (né à l'INRIA), forment la famille des langages fonctionnels.

Planche 4

Les types : quand le langage protège le programmeur

1970 – 1996

Dans la mémoire, tout n'est que bits : rien ne distingue un entier d'un nombre à virgule ou d'une lettre. Un type dit au langage comment interpréter ces bits, et donc ce qu'on a le droit d'en faire. Pascal (Niklaus Wirth, 1970) puis Ada (Jean Ichbiah, 1980) vérifient strictement les types ; C (Dennis Ritchie, 1972) laisse au programmeur plus de liberté et plus de responsabilité. Deux accidents célèbres montrent ce qui se joue.

Un entier signé sur 16 bits ne peut valoir que de −32 768 à 32 767. Le 4 juin 1996, 37 secondes après son décollage, la fusée Ariane 5 (vol 501) se désintègre. Un programme repris d'Ariane 4 convertissait une vitesse horizontale, stockée sur 64 bits, en entier sur 16 bits. Sur la trajectoire plus rapide d'Ariane 5, la valeur dépassa 32 767. Le logiciel, écrit en Ada, détecta bien le débordement et leva une exception ; mais celle-ci n'était pas traitée, et les deux centrales inertielles s'arrêtèrent l'une après l'autre.

Valeur à convertir20 000

Les 65 536 valeurs d'un entier de 16 bits forment un cercle : après 32 767 vient −32 768. L'aiguille rouge montre où tombe la valeur réelle (bleu) si on la range sans vérification.

Valeur réelle

—

Rangée sans vérification sur 16 bits (calcul modulo 65 536)

—

Contrôle : conversion faite par le navigateur (Int16Array)

—

Langage qui vérifie (comme Ada)

—

La plupart des nombres décimaux n'ont pas d'écriture binaire finie : 0,1 en binaire vaut 0,000110011001100… sans fin. L'ordinateur en range une approximation. En 1991, à Dhahran, une batterie de missiles Patriot comptait le temps en dixièmes de seconde dans un registre de 24 bits ; 0,1 y était tronqué. Après 100 heures de fonctionnement, l'erreur accumulée faussa le suivi d'un missile Scud, qui ne fut pas intercepté et tua 28 soldats.

Nombre d'additions de 0,1100 000

Heures de fonctionnement du Patriot100

Écart entre la somme de N fois 0,1 et la valeur exacte N/10, en échelle logarithmique. Bleu : addition ordinaire (nombres de 64 bits). Vert : sommation compensée de Kahan (1965). Rouge : le compteur du Patriot (24 bits tronqués).

0,1 tel qu'il est réellement rangé (64 bits)

—

0,1 + 0,2 calculé par la machine

—

Écart de la somme ordinaire

—

Écart de la somme compensée de Kahan

—

Erreur du Patriot à chaque dixième de seconde

—

Dérive de l'horloge et décalage du Scud (1 676 m/s)

—

Ce qu'il faut retenir. Un type n'est pas une simple étiquette : il fixe ce que la machine peut représenter. Un langage strictement typé refuse de mélanger un texte et un nombre, et peut détecter un débordement ; encore faut-il que le programme prévoie quoi faire alors. Les nombres à virgule, eux, sont presque toujours faux d'un rien, et un rien multiplié par des millions d'opérations devient une seconde entière. Les langages récents, Rust (2015) en tête, vont plus loin : leur système de types interdit dès la compilation des familles entières d'erreurs de mémoire.

Planche 5 · signature

L'arbre généalogique des langages

1957 – 2016

Aucun langage ne naît de rien : chacun emprunte à ses prédécesseurs une syntaxe, une idée, une manière de penser. On classe souvent les langages en grandes familles, les paradigmes : impératif (une suite d'ordres qui modifient la mémoire), objet (des objets qui s'envoient des messages), fonctionnel (des fonctions qui se composent), logique (des faits et des règles dont la machine déduit les conséquences), et les langages de script, souples et interprétés.

Année2017

Langage

Chaque langage est placé à son année de naissance, dans la bande de sa famille principale ; une flèche relie un langage à ceux qu'il a influencés. Touchez un langage : ses ancêtres s'allument en rouge, ses descendants en bleu.

Langages présents / influences

—

Ancêtres du langage choisi

—

Descendants du langage choisi

—

Plus longue lignée d'influences (calculée sur le graphe)

—

Voici l'algorithme d'Euclide, le plus ancien algorithme connu (vers −300), qui calcule le plus grand commun diviseur de deux entiers, écrit dans onze langages de familles différentes. Choisissez-en un : il s'écrit sous vos yeux.

Langage

Nombre de caractères (espaces non comptés) de chaque version. Le langage choisi est en rouge.

Lignes / caractères / symboles de la version choisie

—

Rapport entre la version la plus longue et la plus courte

—

La version JavaScript, exécutée par votre navigateur sur 1 000 couples au hasard

—

Ce qu'il faut retenir. ALGOL 60, presque oublié aujourd'hui, est l'ancêtre de la plus grande partie de l'arbre : Pascal, C, puis C++, Java, C#, Go et Rust en descendent. Les idées circulent entre les familles : l'objet vient de Simula (1967), la fonction comme valeur vient de Lisp, et des langages « impératifs » comme Python, Rust ou Swift empruntent aujourd'hui beaucoup aux langages fonctionnels. Écrire la même chose dans onze langages montre que l'algorithme d'Euclide, lui, n'a pas changé depuis vingt-trois siècles : ce qui évolue, c'est la façon de le dire à la machine, plus ou moins concise, plus ou moins sûre. Prolog (Alain Colmerauer, Marseille, 1972), Ada (Jean Ichbiah) et OCaml (INRIA) rappellent la part française de cette histoire.

Frise des jalons

En résumé

Nommer

L'assembleur remplace les nombres par des noms et calcule les adresses : premier barreau de l'échelle, encore lié à une machine.

Compiler

FORTRAN et ALGOL traduisent des formules à partir d'une grammaire : le programme devient lisible et transportable d'une machine à l'autre.

Abstraire

Lisp, Simula et leurs héritiers apportent la récursivité, les fonctions comme valeurs, les objets : on décrit le problème plus que la machine.

Protéger

Les types détectent les erreurs avant qu'elles ne coûtent cher ; les langages récents en font une garantie dès la compilation.

Pour aller plus loin

Gilles Dowek, Les Principes des langages de programmation, Éditions de l'École polytechnique, 2008.
Donald Knuth et Luis Trabb Pardo, « The early development of programming languages », 1976, repris dans A History of Computing in the Twentieth Century, Academic Press, 1980.
Jean Sammet, Programming Languages: History and Fundamentals, Prentice-Hall, 1969.
Les actes des conférences History of Programming Languages (HOPL, ACM, 1978, 1993, 2007, 2020), où les créateurs racontent eux-mêmes la naissance de leur langage.
Jacques-Louis Lions (dir.), Ariane 5, échec du vol 501, rapport de la commission d'enquête, 1996.
General Accounting Office, Patriot Missile Defense: Software Problem Led to System Failure at Dhahran, rapport GAO/IMTEC-92-26, 1992.

L'arbre généalogique retient, pour chaque langage, ses influences les plus souvent citées par ses auteurs ; il en simplifie forcément beaucoup. Rust est placé à 2010, année de sa présentation publique (version 1.0 en 2015), parce qu'il a influencé Swift (2014).