Le fonctionnement réel du programme d’Ada Lovelace (2018)

 (twobithistory.org)
2 points par GN⁺ 2024-12-17 | 1 commentaires | Partager sur WhatsApp
  • En 1843, Ada Lovelace publia une procédure de calcul des nombres de Bernoulli destinée à l’Analytical Engine, encore inachevée, ce qui la plaça au cœur du débat sur le « premier programme informatique »
  • Le tableau publié montre une étape d’une méthode visant à traiter toute la suite des nombres de Bernoulli, et la valeur que Lovelace appelait B7 correspond, en notation moderne, au huitième nombre de Bernoulli
  • Le programme de la Note G comprenait 25 opérations, des boucles imbriquées et même une notation pour suivre les valeurs des variables, ce qui le rendait bien plus élaboré que l’exemple sans répétition en 11 opérations de Menabrea
  • Lors de la traduction en C, il est apparu que la quatrième opération du tableau original, v5 / v4, aurait dû être v4 / v5 ; il s’agit probablement d’une erreur de composition, mais on peut y voir le plus ancien bug de l’histoire de l’informatique
  • Ce qui distingue Lovelace n’est pas tant le titre de « première programmeuse » que le fait d’avoir compris que la fabrication des cartes n’était pas une simple traduction d’expressions algébriques, mais une tâche de programmation que l’on pouvait bien ou mal réaliser

Le programme de 1843 qui n’a jamais pu être exécuté

  • Contrairement à l’anecdote fondatrice de Microsoft, le programme d’Ada Lovelace n’a jamais eu l’occasion d’être exécuté sur une vraie machine
    • Paul Allen et Bill Gates testèrent leur interpréteur BASIC, sans disposer d’un Altair, sur un émulateur fondé sur les spécifications de l’Intel 8080, puis le firent fonctionner sur un véritable Altair
    • Lovelace aussi écrivit un programme pour un ordinateur qui n’existait encore que sous forme de description, mais l’Analytical Engine ne fut jamais construit, si bien qu’il ne put pas être exécuté
  • Le programme de Lovelace est souvent présenté comme le premier programme informatique au monde, mais ce statut reste débattu
    • Les discussions sur l’étendue et la valeur de la contribution de Lovelace se poursuivent au point que Walter Isaacson les a qualifiées de « minor academic specialty »
    • La question importante ici n’est pas tant l’évaluation de la personne que de savoir comment le programme écrit en 1843 était conçu pour fonctionner
  • Le programme va au-delà d’une simple énumération de formules
    • Il organise des groupes d’opérations répétables, utilisant une structure équivalente à une boucle
    • Il introduit une notation permettant de suivre l’évolution de l’état des variables
    • Il présente des aspects qui ressemblent à l’expérience moderne de l’écriture logicielle

Les nombres de Bernoulli et le problème des sommes de puissances

  • Le programme de Lovelace était conçu pour calculer les nombres de Bernoulli
  • En arrière-plan des nombres de Bernoulli se trouve un vieux problème mathématique : le calcul des sommes de puissances
    • Les pythagoriciens cherchèrent une méthode pour calculer 1 + 2 + 3 + ... + n sans additionner directement les termes, et obtinrent la formule n(n+1)/2 en assemblant deux triangles pour former un rectangle
    • Archimède s’intéressa aux sommes de la forme 1² + 2² + 3² + ... + n² et laissa une solution interprétable géométriquement
    • Aryabhata publia en 499 l’Aryabhatiya, qui contenait notamment une formule pour la somme des cubes
  • Le problème plus général consistait à trouver une méthode pour calculer les sommes de la forme 1^k + 2^k + ... + n^k
    • Johann Faulhaber calcula et publia en 1631 des formules jusqu’à la puissance 17, mais ne donna pas de solution générale
    • Blaise Pascal élabora en 1665 une méthode générale, mais elle exigeait de connaître au préalable les méthodes de calcul de toutes les sommes de puissances inférieures
  • Jakob Bernoulli laissa une solution générale plus pratique
    • Il utilisa le triangle de Pascal pour repérer des motifs dans les coefficients des polynômes
    • Une partie des coefficients était obtenue grâce au triangle de Pascal, et le reste à partir de la propriété selon laquelle la somme des coefficients vaut toujours 1
    • Ce second facteur de coefficient est devenu la suite connue sous le nom de nombres de Bernoulli
  • La découverte de Bernoulli n’a pas rendu immédiatement trivial le calcul d’une somme de puissances arbitraire
    • Pour calculer la somme des puissances k, il fallait connaître les nombres de Bernoulli jusqu’au k-ième
    • Chaque nombre de Bernoulli se calcule à partir des précédents
    • Mais calculer une longue suite de nombres de Bernoulli restait bien plus simple que de dériver une par une les formules de chaque somme de puissances

Les deux machines à calculer de Babbage

  • Charles Babbage conçut deux types de calculateurs mécaniques
    • Le premier était la Difference Engine
    • Le second, connu aujourd’hui comme un ordinateur mécanique, était l’Analytical Engine
  • La Difference Engine n’était pas un ordinateur, mais une machine effectuant uniquement des additions et des soustractions
    • Babbage était frustré par les nombreuses erreurs présentes dans les tables de logarithmes de l’époque, et voulut les produire mécaniquement
    • La méthode des différences divisées de Gaspard de Prony découpait le processus de production des tables de logarithmes en petites étapes ne nécessitant que des additions et des soustractions
    • Les polynômes peuvent être utilisés pour approximer les fonctions logarithmiques et trigonométriques
  • La Difference Engine faisait correspondre chaque colonne d’une table de différences à une colonne physique de roues dentées
    • Chaque roue dentée représentait un chiffre décimal, et une colonne entière représentait un nombre décimal
    • Elle comportait 8 colonnes, ce qui permettait de tabuler des polynômes jusqu’au degré 7
    • L’opérateur réglait les valeurs initiales, puis tournait une manivelle afin que les différences constantes se propagent vers la colonne suivante
  • Babbage construisit et démontra une partie de la Difference Engine, mais ne parvint pas à achever la machine complète
    • Il ne trouva pas de fabricant capable de produire le nombre nécessaire de roues dentées avec une précision suffisante
    • Une Difference Engine fonctionnelle ne fut construite que dans les années 1990, une fois l’usinage de précision devenu possible
  • L’Analytical Engine fut imaginée comme une machine bien plus puissante et flexible
    • Elle devait utiliser des colonnes de roues dentées similaires à celles de la Difference Engine, mais en compter des centaines, voire davantage
    • Elle pouvait être programmée au moyen de cartes perforées, comme le Jacquard Loom
    • Elle pouvait effectuer non seulement des additions et des soustractions, mais aussi des multiplications et des divisions
    • Une partie appelée « mill » se reconfigurait selon l’opération, lisait les opérandes dans les colonnes de stockage et inscrivait le résultat dans une autre colonne

L’article de Menabrea et les notes de Lovelace

  • Babbage rencontra à Turin l’ingénieur italien Luigi Menabrea, futur Premier ministre, et Menabrea publia en 1842 un article en français expliquant les possibilités de l’Analytical Engine
  • Lovelace traduisit en anglais l’article de Menabrea en 1843
    • Lovelace rencontra Babbage pour la première fois en 1833, à l’âge de 17 ans, et fut fascinée par sa Difference Engine
    • Elle avait reçu une solide formation mathématique dès l’enfance et continua à étudier les mathématiques auprès d’Augustus de Morgan après son mariage et la naissance de ses trois enfants
  • L’article de Menabrea abordait brièvement le fonctionnement de la Difference Engine et la supériorité de l’Analytical Engine
    • L’Analytical Engine y était présentée comme une machine capable de multiplier deux nombres de 20 chiffres en 3 minutes
    • Il prenait pour exemples un système simple d’équations linéaires et le développement du produit de deux binômes, en utilisant des « diagrams of development »
    • Ces tableaux étaient eux aussi des programmes au même sens que celui de Lovelace, mais il s’agissait d’exemples simples, sans branchement ni répétition
  • La traduction de Lovelace était accompagnée de notes plus longues que le texte original, et c’est là que ses principales contributions apparaissent
    • La Note A examine longuement la possibilité que l’Analytical Engine soit une machine capable d’exécuter n’importe quelle opération mathématique
    • Elle estime que la machine pourrait agir non seulement sur des nombres, mais aussi sur des objets dont les relations fondamentales mutuelles peuvent être exprimées par la science abstraite des opérations
    • Elle mentionne par exemple qu’elle pourrait un jour composer de la musique
  • La Note G est célèbre pour deux raisons
    • L’argument de Lovelace selon lequel on ne peut pas dire que l’Analytical Engine « pense » fut plus tard appelé par Alan Turing « Lady Lovelace’s Objection »
    • Elle y inclut aussi un programme de calcul des nombres de Bernoulli afin de montrer que la machine pouvait traiter des problèmes très complexes

La structure réelle du programme de la Note G

  • Le tableau complet de Lovelace est un « diagram of development » étendu ; l’image originale est visible ici
  • Le programme ressemble à une liste d’opérations spécifiées avec des symboles mathématiques ordinaires
    • Babbage ou Lovelace ne semblent pas être allés jusqu’à créer quelque chose comme un jeu d’opcodes pour l’Analytical Engine
  • Lovelace expliquait une méthode pour calculer toute la suite des nombres de Bernoulli jusqu’à une certaine limite, mais le programme présenté sous forme de tableau en illustre une seule étape
    • La valeur calculée est celle que Lovelace appelait B7
    • En notation mathématique moderne, il s’agit du huitième nombre de Bernoulli
    • La formule est de la forme B7 = -1(A0 + B1A1 + B3A3 + B5A5)
  • Chaque terme de cette formule représente un coefficient d’un polynôme de somme de puissances particulier
    • La puissance concernée est 8, et c’est dans la formule de la somme des puissances huitièmes des entiers positifs qu’apparaît pour la première fois le huitième nombre de Bernoulli
    • B1 à B7 sont différents nombres de Bernoulli selon l’indexation de Lovelace
    • A0 à A5 sont les facteurs de coefficients que Bernoulli pouvait calculer avec le triangle de Pascal
    • Le programme de Lovelace utilise n = 4
  • Une traduction en C est disponible sous forme de gist
    • Elle calcule d’abord A0 et B1A1
    • Elle entre ensuite dans une boucle répétée deux fois pour calculer B3A3 et B5A5
    • Après le calcul de chaque produit, celui-ci est ajouté aux précédents afin d’obtenir la somme totale à la fin

Boucles, état des variables et vieux bug

  • La traduction en C met bien en évidence le caractère visionnaire du programme de Lovelace
    • Le programme original ne comportait pas exactement de boucle while, mais Lovelace créait des groupes d’opérations et indiquait en note quand les répéter
    • La traduction en C contient deux boucles while, dont l’une est imbriquée dans l’autre
    • Dans l’original comme dans la traduction en C, v10 se comporte comme une variable compteur décrémentée à chaque répétition
  • Le tableau de Lovelace permet de suivre les changements d’état plus facilement que celui de Menabrea
    • Il contient une colonne intitulée « Indication of change in the value on any Variable »
    • Chaque variable y reçoit un indice en exposant pour indiquer les valeurs successives qu’elle prend pendant l’exécution du programme
    • L’exposant 2 signifie la deuxième valeur assignée depuis le début du programme
  • Une fois transcrit en C et exécuté, le programme donna d’abord un résultat incorrect, et la cause ne venait pas du code de traduction, mais du tableau original
    • Le « diagram of development » de Lovelace indique la quatrième opération comme v5 / v4
    • L’ordre correct est v4 / v5
    • Il s’agissait probablement non pas d’une erreur du programme conçu par Lovelace, mais d’une erreur de composition
  • Jim Randall a lui aussi traduit le programme de Lovelace en Python et a signalé le même bug de division ainsi que deux autres problèmes
  • Le bug mineur du programme original rejoint l’interprétation selon laquelle Lovelace essayait d’écrire quelque chose de proche d’un véritable programme, et non une simple démonstration

Les limites du titre de première programmeuse

  • Dire que Lovelace a écrit ou publié le « premier programme » n’est pas entièrement exact
    • Menabrea avait publié des « diagrams of development » un an avant la traduction de Lovelace
    • Babbage avait lui aussi écrit plus de vingt programmes non publiés
    • Selon ce que l’on considère comme un programme, la question reste discutable
  • Le programme publié par Lovelace était largement en avance sur ce qui avait été publié auparavant
    • Le plus long programme présenté par Menabrea comptait 11 opérations
    • Les exemples de Menabrea ne comportaient ni boucle ni branchement
    • Le programme de Lovelace comprend 25 opérations et des boucles imbriquées, donc une structure de branchement
  • Menabrea estimait qu’une fois la machine achevée, la difficulté se réduirait à la confection des cartes, et que celles-ci n’étant qu’une traduction d’expressions algébriques, il serait facile de confier l’exécution à un opérateur au moyen d’une notation simple
  • Babbage et Menabrea se concentraient surtout sur l’application de l’Analytical Engine aux problèmes de calcul mathématique qui les intéressaient
  • Lovelace pensait que l’Analytical Engine pouvait faire bien plus que ce que Babbage ou Menabrea imaginaient, et elle comprit que la « confection des cartes » n’était pas une simple tâche accessoire, mais une tâche de programmation que l’on pouvait bien ou mal accomplir

À lire aussi

1 commentaires

 
GN⁺ 2024-12-17
Commentaires Hacker News

  • Le véritable signe d’un programme non trivial, c’est qu’il ne fonctionne pas du premier coup
    Il est frappant de voir que, après avoir été frustré par l’absence de techniques de fabrication de précision de masse permettant de construire l’appareil simple de Babbage, il a conçu un nouveau système plus complexe d’un ordre de grandeur et est même allé jusqu’en Italie à la recherche de capacités de fabrication plus avancées

    • J’ai déjà eu un employé comme ça
      Quand quelque chose le bloquait, il commençait par fabriquer ses propres outils, et une fois, parce qu’il n’aimait pas les polices intégrées à une très petite taille de points, il a créé sa propre police
      C’était le meilleur ingénieur que j’aie connu, mais il fallait constamment veiller à ce qu’il ne s’enfonce pas dans un terrier de lapin
    • +1 pour l’histoire Babbage/Lovelace, mais même si ces deux faits sont vrais séparément, il est difficile d’y voir la “meilleure voie” choisie par Babbage parce qu’il manquait d’usinage de précision, menant à un système plus complexe et à un voyage en Italie
      Tim Robinson a aussi dit que « si le Meccano des années 1920 avait existé cent ans plus tôt, Babbage aurait complètement réussi », et à ses yeux il ressemblait davantage à un profil logiciel jeté sur du matériel à cause d’idées en avance sur ce qui était réalisable
      Au-delà de son manque de sens des affaires et de la planification de projet, qui l’empêchait de réduire le périmètre ou de renoncer à la précision sur 10 chiffres, il continuait à avoir de meilleures idées et à les poursuivre, tombant sans cesse dans des terriers de lapin, et comme il avait déjà reçu plusieurs prix très jeune rien qu’avec sa proposition de Difference Engine, il lui a probablement été difficile d’abandonner même des décennies plus tard
      Son implication avec le gouvernement constitue aussi un autre grand axe tragique. Les aristocrates méprisaient et se méfiaient du gouvernement et de la politique, les classes inférieures s’en méfiaient parce qu’il ne leur avait guère apporté d’aide, mais Babbage, issu de cette classe moyenne idéale pour développer une vision patriotique de l’État, semblait penser qu’il offrait ses inventions à la « nation » et que le gouvernement devait le récompenser
      Il n’a pas réussi à achever la Difference Engine, mais il a demandé au gouvernement si des fonds supplémentaires pourraient permettre de réaliser la meilleure Analytical Engine, et le gouvernement a tergiversé pendant 20 ans. Même quand l’État a proposé de lui rendre son invention, il a refusé
      Sous l’effet de ses nombreux prix, il semble aussi s’être attaché à son identité d’« homme intelligent », et il existe une anecdote selon laquelle il aurait refusé de participer avec Faraday à l’évaluation d’un prix, au motif qu’il devait en être l’unique juge. Ce genre d’attitude a aussi pu l’orienter davantage vers des idées de génie grandioses mais irréalistes que vers une exécution pratique
      The Thrilling Adventures of Lovelace and Babbage de Sydney Padua semble être un livre extrêmement bien documenté ; je n’ai pas pu lire une grande partie du texte principal, mais j’ai lu les annexes en détail, et je le recommande
    • L’idée qu’« un programme non trivial ne fonctionne pas du premier coup » est fausse

  • Article vraiment formidable. J’ai été impressionné, dès l’introduction, par le fait que Lovelace réfléchissait profondément à la manière d’organiser les opérations en groupes répétables, inventant ainsi la boucle, et qu’elle ait compris l’importance de suivre l’état quand une variable change, en créant une notation pour représenter ce changement
    Du point de vue d’un programmeur, il est étonnant de voir à quel point ce que faisait Lovelace ressemble à l’expérience moderne de l’écriture logicielle, et l’explication selon laquelle elle l’avait conçu pour calculer les nombres de Bernoulli entre suffisamment dans le détail pour faire comprendre ce qu’elle accomplissait
    Si elle vivait aujourd’hui, on l’imaginerait au bout du couloir en train de s’acharner sur un problème en Rust, avec probablement une forte préférence pour les langages à typage statique

    • Quelle que soit la reconnaissance qu’Ada mérite pour ses techniques de programmation, ce qui ressort toujours le plus, c’est sa capacité à voir la vue d’ensemble du calcul
      Le point essentiel est qu’elle a compris que l’Analytical Engine pouvait agir non seulement sur des nombres, mais aussi sur d’autres objets, pourvu qu’ils puissent être exprimés en termes des relations de la science abstraite des opérations ; par exemple, si les relations fondamentales de l’harmonie et de la composition musicale pouvaient être exprimées de cette façon, la machine pourrait produire une musique élaborée de n’importe quel degré de complexité et de longueur
      En 1842, un siècle avant l’apparition des premiers ordinateurs réellement programmables, tirer une telle idée d’une simple description d’un prototype d’ordinateur mécanique relève d’un hacking remarquable
    • La notation destinée à suivre l’état quand les variables changent m’a particulièrement marqué parce qu’elle ressemble beaucoup à la forme d’affectation unique statique
      https://en.wikipedia.org/wiki/Static_single-assignment_form#Benefits
      C’est encore aujourd’hui proche des techniques modernes, et elle l’avait donc déjà il y a 180 ans

  • Il est intéressant de lire que Paul Allen et Bill Gates ont testé leur interpréteur BASIC pour l’Altair, sans véritable Altair, sur un ordinateur de Harvard à l’aide d’un émulateur construit uniquement à partir des spécifications de l’Intel 8080, et qu’au premier lancement devant un vrai Altair, tout a fonctionné correctement
    Dans ce cas, les véritables héros cachés ici ne seraient-ils pas les ingénieurs d’Intel, qui ont rédigé des spécifications assez précises pour qu’un logiciel tournant sur un émulateur écrit à partir de celles-ci fonctionne ensuite sans problème sur le vrai matériel ?

    • En 1976, pour mon premier travail commercial en programmation, j’ai modifié un émulateur 8008 écrit en Fortran pour qu’il fonctionne comme un émulateur 8080 sur un mini-ordinateur Data General
      L’objectif était de permettre à un autre programmeur, qui écrivait un firmware 8080 pour un traceur, de déboguer son code, et si je me souviens bien, le code source de cet émulateur venait de quelque chose appelé l’INTERP/8 8008 d’Intel. À lire divers textes en ligne, il semble qu’Allen et Gates l’aient aussi utilisé

  • À mon avis, la partie la plus formidable réside dans le vrai travail contenu dans les « notes » qu’elle a ajoutées à la traduction
    Référence : https://upload.wikimedia.org/wikipedia/commons/c/cf/Diagram_for_the_computation_of_Bernoulli_numbers.jpg
    Et aussi https://en.wikipedia.org/wiki/Note_G
    L’article renvoie également à cette ressource qui transpose son travail en Python : https://enigmaticcode.wordpress.com/tag/bernoulli-numbers/

    • La moitié de l’article parle de Note A et de Note G

  • En voyant que le passage du programme de Lovelace en C ne paraît pas si étrange, à part le fait qu’il déborde de variables aux noms inutiles, je me suis dit que l’auteur n’avait clairement jamais rencontré mes collègues

    • Ça m’a rappelé un partenaire de projet en cours de programmation au lycée qui donnait à ses variables les mots les plus grossiers et obscènes qui lui passaient par la tête
      Je n’étais pas particulièrement conservateur, mais il ne se souvenait évidemment jamais à quoi servait la variable butts, et il n’a jamais compris pourquoi son propre code continuait à le perdre
    • Ou alors il n’a jamais travaillé avec des mathématiciens, physiciens ou ingénieurs qui programment. Dès que j’ai lu cette phrase, j’ai pensé : « un quant typique »
      Mon père, ingénieur chimiste, a appris à programmer en FORTRAN, où à l’époque les noms de variables devaient faire une lettre et jusqu’à deux chiffres. Plus tard, il a appris le Basic, mais son code restait mentalement du FORTRAN, donc cette habitude lui est restée
      Au début, je pensais que c’était juste lui, mais bien plus tard, en travaillant à Wall St, j’ai vu exactement la même chose chez des quants qui recopiaient du code de Numerical Recipes, même en C

  • C’est amusant de voir, dans la manière dont Menabrea considérait l’Analytical Engine avant tout comme un outil permettant d’automatiser des « calculs longs et arides » afin que de grands scientifiques puissent consacrer leur capacité intellectuelle à une pensée de plus haut niveau, à quel point le discours sur l’automatisation dure depuis longtemps
    On dit exactement la même chose aujourd’hui à propos des LLM

    • Au fond, la différence essentielle entre l’ordinateur comme outil et l’ordinateur comme appareil de consommation, n’est-ce pas justement l’automatisation des « calculs longs et arides » ?

  • Je me demande si quelqu’un a créé une machine virtuelle à partir du jeu d’instructions de Babbage et y a exécuté le programme d’Ada

  • Cela avait déjà été discuté à l’époque où cet article a été publié
    What Did Ada Lovelace’s Program Actually Do? - https://news.ycombinator.com/item?id=17797003 - août 2018, 52 commentaires

  • Petite digression, mais je me suis demandé comment les gens l’appelaient à l’époque
    Son nom était Augusta Ada King et elle était comtesse de Lovelace ; je me demande s’il était déjà courant à l’époque d’abréger un titre nobiliaire pour en faire une sorte de nom de famille, ou si c’est un usage plus récent

    • Pour le détenteur du titre, le comte de Lovelace, il existait en général une manière de l’appeler simplement par le nom du lieu
      Après que William King-Noel est devenu Earl of Lovelace, on l’appelait « Lovelace », et elle aurait sans doute été appelée « Lady Lovelace » dans le monde mondain, et « Countess of Lovelace » dans un contexte officiel

  • Très bon article. C’est l’explication la plus claire que j’aie lue jusqu’ici sur le caractère novateur d’Ada, en quel sens, et pourquoi elle mérite d’être reconnue