Histoire de l'informatique

L'informatique donne l'impression d'être née hier. Elle a pourtant une longue histoire, et cette histoire n'est pas un décor : les notions étudiées dans ce livre — les structures de données, la récursivité, la programmation objet, les bases de données, les réseaux — sont apparues à des dates précises, pour résoudre des problèmes précis, et portent encore la marque de ces problèmes.

Ce chapitre n'est donc ni une galerie de portraits ni une liste de dates à réciter. C'est le récit de quelques déplacements d'idées, où l'on posera chaque fois deux questions : quel problème cherchait-on à résoudre ? et qu'est-ce que la solution a rendu possible ?

Un fil traverse l'ensemble : le déplacement des rôles respectifs du logiciel et du matériel. Pendant des siècles, une machine ne sait faire que ce pour quoi elle a été construite ; en 1936, on comprend qu'une seule machine peut les imiter toutes ; en 1948, le programme entre dans la mémoire et devient une donnée comme les autres ; en 1969, il devient un produit que l'on vend ; depuis les années 2000, un service auquel on se connecte.

15.1 Introduction : lire l'histoire en informaticien

La frise ci-dessous donne les repères principaux. Ses trois bandes n'ont pas la même échelle : la première couvre deux millénaires, la deuxième un siècle et demi, la troisième un demi-siècle.

15.2 Avant l'ordinateur : l'algorithme, puis le calcul mécanique

15.2.1 Des algorithmes sans machine

Pendant des siècles, l'algorithme existe sans qu'aucune machine ne puisse l'exécuter : il est destiné à un être humain muni d'un papier et de patience.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b      # invariant : pgcd(a, b) ne change pas
    return a

print(pgcd(1071, 462))       # affiche 21

Deux autres héritages traversent l'histoire : le crible d'Ératosthène (IIIe siècle avant notre ère), et surtout la numération de position venue de l'Inde (Brahmagupta, 628), transmise par al-Khwârizmî puis diffusée en Europe par Fibonacci (Liber abaci, 1202). Sans elle, aucun calcul mécanique n'aurait été possible : c'est déjà une leçon d'informatique, celle du choix de la représentation des données.

15.2.2 Les premières machines à calculer (XVIIe siècle)

• 1623 — Wilhelm Schickard décrit à Kepler son « horloge à calculer », qui additionne et soustrait. L'unique exemplaire brûle avant d'avoir servi.
• 1642 — Blaise Pascal, âgé de dix-neuf ans, construit pour son père, collecteur d'impôts, la machine dite Pascaline ; une cinquantaine d'exemplaires seront fabriqués. C'est la première machine à calculer réellement diffusée.
• 1673 — Leibniz présente à la Royal Society une machine qui multiplie par additions répétées, grâce à un cylindre cannelé.
• 1703 — Leibniz publie son Explication de l'arithmétique binaire. Il ne construit aucune machine binaire : il faudra attendre Zuse, en 1941.

15.2.3 1804 : le métier Jacquard, ou le motif qui quitte la machine

Joseph-Marie Jacquard perfectionne en 1801-1804 un métier à tisser commandé par un ruban de cartes perforées, aboutissement des essais de Basile Bouchon (1725) et de Vaucanson (1745). Le motif tissé n'est plus fixé par la construction du métier : il est écrit sur les cartes. Changer de dessin, c'est changer de cartes, non de machine.

C'est le premier exemple de la séparation qui définira l'informatique : d'un côté une machine générale, de l'autre une description modifiable de ce qu'elle doit faire. Babbage s'en souviendra trente ans plus tard, Hollerith un demi-siècle après lui.

15.3 Le XIXe siècle : le programme, la logique et les données

15.3.1 Babbage : une machine qui suit un programme

Charles Babbage (1791-1871) part d'un problème concret : les tables numériques utilisées par les marins et les ingénieurs sont truffées d'erreurs de calcul et de copie. Sa réponse est d'automatiser le calcul et l'impression. En 1822, il propose la machine à différences, financée dès 1823 par le gouvernement britannique et jamais achevée — le Science Museum de Londres en a construit un exemplaire d'après ses plans : le mécanisme de calcul a fonctionné en 1991, l'imprimante en 2002. Puis, à partir de 1834, il conçoit une machine d'une tout autre ambition.

15.3.2 Ada Lovelace et le premier algorithme publié

Ada Lovelace (1815-1852) traduit en 1843 un article que l'ingénieur italien Luigi Menabrea avait consacré en 1842 à la machine analytique. Elle y ajoute sept notes, signées de ses initiales et plus longues que le texte traduit. La dernière, la note G, contient le déroulé complet du calcul des nombres de Bernoulli par la machine.

15.3.3 Boole, puis Hollerith : la logique et les données

George Boole publie en 1847 The Mathematical Analysis of Logic, puis en 1854 An Investigation of the Laws of Thought : le raisonnement logique obéit à des règles algébriques, sur des valeurs qui ne sont ni des longueurs ni des nombres, mais le vrai et le faux. Pendant quatre-vingts ans, son algèbre reste une curiosité de logicien ; elle deviendra en 1937 la théorie des circuits, c'est-à-dire l'électronique numérique tout entière.

Le recensement américain de 1880 avait demandé près de huit ans de dépouillement manuel. Herman Hollerith dépose en 1884 les brevets d'une machine à cartes perforées qui trie et compte automatiquement ; employée pour le recensement de 1890, elle donne le décompte de la population en quelques semaines et l'ensemble des résultats en deux à trois ans, sur un volume bien supérieur. La société qu'il fonde en 1896 fusionne en 1911 dans la Computing-Tabulating-Recording Company, rebaptisée IBM en 1924. Le traitement automatique des données de masse est né avant l'ordinateur — et, avec lui, la question de ses usages : ces mêmes machines serviront au meilleur comme au pire au cours du XXe siècle.

15.4 1936 : la machine universelle

En 1928, David Hilbert pose le problème de la décision : existe-t-il une procédure mécanique qui, pour tout énoncé mathématique, décide s'il est démontrable ? Répondre suppose de définir ce que « mécanique » veut dire. Deux réponses paraissent en 1936, et elles sont négatives : celle d'Alonzo Church en avril, par le lambda-calcul ; celle d'Alan Turing (1912-1954), soumise en mai sous le titre On Computable Numbers, with an Application to the Entscheidungsproblem et publiée dans les Proceedings of the London Mathematical Society en 1936-1937.

C'est l'acte de naissance conceptuel de l'ordinateur, douze ans avant le premier ordinateur. Une seule machine physique suffit, pourvu qu'on lui donne la description de celle que l'on veut imiter : cette description, c'est le programme. Le logiciel est né avant le matériel.

Claude Shannon (1916-2001) fait ensuite le lien manquant avec l'électricité. Dans son mémoire de master au MIT, soutenu en 1937 et publié en 1938 sous le titre A Symbolic Analysis of Relay and Switching Circuits, il montre que l'algèbre de Boole décrit exactement le comportement des circuits à relais : un circuit est une formule logique, et simplifier la formule, c'est économiser des composants. En 1948, son article A Mathematical Theory of Communication fonde la théorie de l'information — mesure de l'information, limites de la compression, correction des erreurs de transmission — et popularise le mot bit, proposé par son collègue John Tukey.

15.5 1936-1951 : les premières machines et le programme enregistré

15.5.1 Quatre critères pour comparer les machines de guerre

Entre 1938 et 1946, plusieurs équipes construisent, souvent sans se connaître, des machines très différentes. Les comparer suppose de fixer des critères.

Le Z3 de Konrad Zuse, achevé à Berlin en mai 1941, est la première machine programmable automatique en état de marche : binaire, à virgule flottante, commandée par un film perforé, mais dépourvue de saut conditionnel ; elle est détruite par un bombardement en 1943. Colossus, conçu par Tommy Flowers et opérationnel à Bletchley Park en février 1944, est électronique et reprogrammable par commutateurs, mais spécialisé dans la cryptanalyse ; son existence est restée secrète jusqu'aux années 1970, ce qui a longtemps faussé les récits. L'ENIAC d'Eckert et Mauchly, achevé fin 1945 et présenté au public le 15 février 1946, est électronique, décimal, universel — et programmé en déplaçant des fiches et des commutateurs. Sa programmation était assurée par six mathématiciennes longtemps oubliées des récits officiels : Kathleen McNulty, Frances Bilas, Betty Jean Jennings, Ruth Lichterman, Elizabeth Snyder et Marlyn Wescoff.

15.5.2 Juin 1945 : le rapport sur l'EDVAC

Le 30 juin 1945 circule un document intitulé First Draft of a Report on the EDVAC, signé du seul nom de John von Neumann. Il décrit une machine dont le programme, codé en nombres, est rangé dans la même mémoire que les données.

Les premières exécutions suivent de peu. Le 21 juin 1948, à Manchester, la Small-Scale Experimental Machine, surnommée Baby, exécute le premier programme jamais rangé en mémoire — la recherche du plus grand diviseur propre d'un nombre, en cinquante-deux minutes. C'est la date que retient le programme officiel pour la naissance de l'ordinateur. Le 6 mai 1949, à Cambridge, l'EDSAC de Maurice Wilkes devient la première machine à programme enregistré d'usage régulier. Puis le commerce commence : le Z4 de Zuse est loué à l'École polytechnique fédérale de Zurich en 1950, le Ferranti Mark 1 est livré en février 1951, et l'UNIVAC I au bureau du recensement des États-Unis le 31 mars 1951.

15.6 Le matériel : du tube au circuit intégré

15.6.1 Le transistor, le circuit intégré, le microprocesseur

Les tubes à vide de l'ENIAC consomment, chauffent et grillent. Aux Bell Labs, le 16 décembre 1947, John Bardeen et Walter Brattain obtiennent une amplification avec un dispositif à pointes de germanium ; la démonstration à la direction a lieu le 23 décembre. William Shockley conçoit en janvier 1948 le transistor à jonction, seul industrialisable, réalisé en 1951. Les trois reçoivent le prix Nobel de physique en 1956.

Assembler les transistors un par un devient vite le facteur limitant. Deux ingénieurs résolvent le problème presque simultanément : Jack Kilby (Texas Instruments) fait fonctionner le 12 septembre 1958 un circuit complet gravé dans un seul bloc de germanium, avec des fils soudés à la main ; Robert Noyce (Fairchild) conçoit en janvier 1959 un circuit en silicium dont les connexions sont déposées par le procédé planar, seul compatible avec la production de masse. Les deux sociétés se sont disputé les brevets avant de signer une licence croisée en 1966 ; la paternité est aujourd'hui partagée, et Kilby a reçu le prix Nobel en 2000. L'exemple est instructif : entre l'idée et le procédé industrialisable, c'est souvent le second qui change le monde.

Douze ans après le circuit de Noyce, en novembre 1971, Intel annonce le 4004, premier microprocesseur commercialisé : un processeur complet sur une puce, 2 300 transistors, 4 bits, conçu par Federico Faggin, Ted Hoff, Stanley Mazor et Masatoshi Shima pour une calculatrice japonaise. Là encore l'antériorité est discutée : le calculateur MP944 du chasseur F-14 (1970) est resté classifié jusqu'en 1998, et le circuit AL1 de Four-Phase Systems date de 1969.

15.6.2 La loi de Moore

15.7 Le logiciel : des langages, un métier, une industrie

15.7.1 Ne plus écrire en binaire

Sur les premières machines, programmer signifie écrire des nombres. Trois étages de traduction apparaissent en quinze ans. Vers 1949-1951, l'assembleur remplace les codes numériques par des mnémoniques et les adresses par des étiquettes ; à Cambridge, David Wheeler invente le mécanisme d'appel de sous-programme qui porte son nom, et la bibliothèque de code réutilisable est née. En 1952, Grace Hopper (1906-1992) réalise l'A-0, souvent présenté comme le premier compilateur — le terme est à nuancer, car l'A-0 assemblait des sous-programmes plutôt qu'il ne traduisait un langage ; son travail suivant, FLOW-MATIC (1955-1959), utilise en revanche des instructions en anglais. En avril 1957, l'équipe de John Backus chez IBM livre le premier compilateur FORTRAN, commencé en 1954 : le pari — produire un code machine aussi efficace que celui d'un humain — était jugé perdu d'avance ; il est gagné, et le langage de haut niveau s'impose.

1948  en machine     : 1 20   3 21   2 22    (des nombres, rien d'autre)
1951  en assembleur  : CHARGE X ; AJOUTE Y ; RANGE Z
1957  en FORTRAN     : Z = X + Y
1991  en Python      : z = x + y

15.7.2 1958-1967 : les idées qui structurent encore ce livre

• LISP (John McCarthy, 1958, article publié en avril 1960) : les listes, les fonctions manipulées comme des données, la récursivité comme principe de construction, et le ramasse-miettes qui libère automatiquement la mémoire.
• COBOL (comité CODASYL, 1959-1960, à partir de FLOW-MATIC) : les traitements de gestion, des instructions en anglais, et une longévité stupéfiante — il fait encore tourner des systèmes bancaires.
• ALGOL 60 (rapport de 1960) : les blocs, la portée des variables, la récursivité autorisée, et une manière rigoureuse de décrire une grammaire, la forme de Backus-Naur. Peu utilisé industriellement, il est l'ancêtre commun de Pascal, C, Java et Python.
• Simula 67 (Ole-Johan Dahl et Kristen Nygaard, Oslo, 1967) : écrit pour simuler des files d'attente, il invente pour cela la classe, l'objet et l'héritage. Toute la programmation objet de ce livre vient de là ; ses auteurs recevront le prix Turing en 2001.

En 1969, aux Bell Labs, Ken Thompson et Dennis Ritchie écrivent Unix sur une machine mise au rebut ; Ritchie crée en 1972 le langage C, et Unix est réécrit en C dès 1973. Pour la première fois, un système d'exploitation devient portable : toutes les familles de systèmes actuelles, sauf Windows, descendent de là. En 1989, Guido van Rossum commence Python au CWI d'Amsterdam, en héritier du langage d'enseignement ABC ; la version 0.9.0 paraît en février 1991, la 2.0 en 2000, la 3.0 en 2008. Le même mois d'août 1991, Linus Torvalds annonce le noyau Linux.

15.7.3 L'évolution des rôles du logiciel et du matériel

Le 23 juin 1969, IBM annonce qu'il facturera désormais séparément les machines, les logiciels et les services. Ce « dégroupage » crée du jour au lendemain un marché : le logiciel devient un produit que l'on vend, et une industrie naît. Quatorze ans plus tard, le 27 septembre 1983, Richard Stallman annonce le projet GNU, qui vise un système complet librement modifiable et redistribuable ; la licence GPL formalise ces libertés en 1989, et le noyau Linux (1991, placé sous GPL l'année suivante) lui apporte la pièce manquante.

15.8 Les données et les réseaux

15.8.1 1970 : le modèle relationnel

Jusque-là, interroger une base de données suppose de savoir comment les enregistrements sont rangés sur le disque. En juin 1970, Edgar Frank Codd, chercheur chez IBM, publie A Relational Model of Data for Large Shared Data Banks : les données sont des relations — des tables — et on les interroge par une algèbre, sans rien savoir de leur stockage. Le projet System R d'IBM (1974-1979) en fait un système réel et invente au passage le langage SEQUEL, devenu SQL ; Oracle commercialise sa version 2 en 1979 ; SQL est normalisé en 1986-1987. Cette indépendance entre la description logique des données et leur rangement physique est l'idée qui structure les chapitres consacrés aux bases de données.

15.8.2 1969-1993 : d'ARPANET au Web

L'idée fondatrice des réseaux est la commutation de paquets : découper les messages en morceaux acheminés indépendamment, au lieu de réserver un circuit d'un bout à l'autre. Elle est proposée séparément par Paul Baran (RAND, 1960-1964) et Donald Davies (Royaume-Uni, 1965-1966, à qui l'on doit le mot paquet), sur des bases théoriques développées par Leonard Kleinrock — dont la part exacte est, elle aussi, discutée.

• 29 octobre 1969 — Premier message échangé sur ARPANET, entre l'université de Californie à Los Angeles et l'institut de recherche de Stanford. Le système tombe en panne après les deux premières lettres du mot login.
• Mai 1974 — Vinton Cerf et Robert Kahn publient le protocole qui deviendra TCP/IP.
• 1^er janvier 1983 — ARPANET bascule d'un seul coup vers TCP/IP : c'est la date de naissance technique d'Internet, un réseau de réseaux qui n'appartient à personne. Le système de noms de domaines suit en 1983-1984.
• Mars 1989 — Tim Berners-Lee, informaticien au CERN, propose une organisation hypertexte des documents du laboratoire. Fin 1990, avec Robert Cailliau, il écrit le premier serveur et le premier navigateur ; la première page est en ligne le 20 décembre 1990. Le 30 avril 1993, le CERN place le logiciel dans le domaine public, décision sans laquelle le Web serait sans doute resté un produit parmi d'autres.

L'ordinateur personnel avait entre-temps déplacé le calcul vers l'utilisateur : le Micral N de François Gernelle (janvier 1973, France) et l'Altair 8800 (1975) se disputent le titre de premier micro-ordinateur, avant l'Apple II (1977), l'IBM PC (12 août 1981) et le Macintosh (24 janvier 1984), dont l'interface graphique doit tout au Xerox Alto (1973) et à la démonstration de Douglas Engelbart du 9 décembre 1968 — souris, hypertexte et travail collaboratif réunis en une heure et demie. Depuis, le mouvement s'est inversé : avec les services en ligne (Amazon Web Services, 2006) et le téléphone intelligent (iPhone en 2007, Android en 2008), calcul et données repartent vers de grands centres, et la machine de l'utilisateur redevient un terminal — un retour partiel au temps partagé des années 1960, dont le système CTSS du MIT (1961) fut le premier exemple.

15.9 Repères pour les autres notions du livre

Le programme officiel demande que ces repères soient « construits au fur et à mesure de la présentation des concepts ». Voici, notion par notion, d'où viennent celles que ce livre enseigne.

15.10 Bilan

Ce chapitre a suivi une seule histoire, celle d'une séparation progressive entre la machine et ce qu'elle fait.

• Les algorithmes précèdent les machines de deux mille ans : Euclide vers 300 avant notre ère, al-Khwârizmî vers 820. Les machines à calculer du XVIIe siècle (Schickard 1623, Pascal 1642, Leibniz 1673) calculent, mais n'exécutent aucun programme.
• Le programme naît au XIXe siècle : les cartes de Jacquard (1804), la machine analytique de Babbage (1834), la note G de Lovelace (1843). Boole (1854) fait de la logique un calcul, Hollerith (1890) mécanise le traitement des données de masse.
• 1936 est l'année charnière : Turing et Church définissent le calculable, la machine universelle et l'indécidable — douze ans avant le premier ordinateur. Shannon (1937 et 1948) relie logique, circuits et information.
• 1948 est la date des premiers ordinateurs au sens du programme officiel : le Baby de Manchester exécute un programme rangé en mémoire, selon le plan donné en 1945 par le rapport sur l'EDVAC.
• Le matériel progresse ensuite exponentiellement : transistor (1947-1948), circuit intégré (1958-1959), microprocesseur (1971), avec la loi de Moore comme feuille de route — jusqu'à la fin de la course à la fréquence, vers 2005, qui impose les processeurs à plusieurs cœurs.
• Le logiciel change quatre fois de statut : contenu dans le matériel, puis donnée en mémoire, puis produit vendu (1969), puis service en réseau (depuis 2000).
• Les autres rubriques du programme ont chacune leur date : Simula 67 pour les objets, Codd 1970 pour le relationnel, 1969-1983 pour Internet, 1989-1993 pour le Web.

Deux réflexes valent d'être conservés au-delà de ce chapitre. Le premier : devant une affirmation historique, demander selon quel critère — « le premier ordinateur » ne veut rien dire sans définition. Le second : devant une technique, chercher quel problème elle résolvait. Les cartes perforées ont disparu, mais la ligne de $80$ caractères est restée ; et l'architecture décrite en 1945 gouverne encore la machine sur laquelle ce texte est lu.