Qu'est-ce que le programme Ada Lovelace a réellement fait?

L'épisode Microsoft Founding est l'un des plus célèbres de l'histoire de l'ordinateur. En 1975, Paul Allen s'est envolé pour Albuquerque pour montrer l'interprète BASIC que lui et Bill Gates ont écrit pour le micro-ordinateur Altair. Comme ils n'avaient pas d'ordinateur Altair en état de marche, ils ont testé leur interprète à l'aide d'un émulateur écrit par eux et fonctionnant sur le système informatique de Harvard. L'émulateur était basé uniquement sur les spécifications publiées du processeur Intel 8080. Quand Allen a finalement lancé l'interprète sur un véritable ordinateur Altair - devant la personne qui, espérait-il, achèterait son logiciel - il ne savait même pas si le programme fonctionnerait. Elle l'a mérité. Le mois suivant, Allen et Gates ont officiellement fondé la nouvelle société.

Plus de cent ans avant l'interprète de BASIC Allen et Gates, Ada Lovelace a écrit et publié un programme informatique. Elle a également écrit un programme pour un ordinateur, qu'elle ne connaissait que par la description. Mais son programme, contrairement à l'interpréteur BASIC, n'a jamais été exécuté car l'ordinateur pour lequel il a été écrit n'a jamais été construit.

Lovelace est souvent appelé le premier programme informatique au monde. Mais tout le monde n'est pas d'accord pour que cela s'appelle ainsi. L'héritage de Lovelace s'avère être l'un des sujets les plus brûlants de l'histoire de l'ordinateur. Walter Isaacson a écrit que le débat sur l'étendue et les mérites de ses contributions est de «peu d'importance académique». Inévitablement, le différend est alimenté par le fait que Lovelace était une femme. Les historiens ont cité toutes sortes de preuves pour prouver que les honneurs qui lui sont rendus sont conformes à l'affaire, ou, à l'inverse, immérités. Mais ils passent beaucoup moins de temps à expliquer les détails techniques de son travail publié, ce qui est dommage, car ce sont les détails techniques qui représentent la partie la plus intéressante de cette histoire. Qui ne serait pas intéressé de savoir comment le programme écrit en 1843 devrait fonctionner?

Honnêtement, le programme Lovelace est difficile à expliquer aux habitants. Mais ce sont les subtilités de son programme qui la rendent si remarquable. Elle mérite d'être appelée la première programmeuse, ou non, son programme a été enregistré avec une telle précision qui a dépassé tout ce qui était auparavant. Elle a soigneusement réfléchi aux opérations qui peuvent être combinées en groupes qui peuvent être répétées - inventant ainsi un cycle. Elle a réalisé à quel point il était important de garder une trace de l'état des variables changeantes, et a produit un enregistrement reflétant ces changements. En tant que programmeur, je suis étonné de voir à quel point le travail de Lovelace ressemble à l'expérience de l'écriture de logiciels aujourd'hui.

Examinons donc de plus près le programme Lovelace. Elle l'a conçu pour calculer les nombres de Bernoulli . Pour comprendre ce que c'est, il faut remonter quelques millénaires dans le passé, au début de l'un des plus anciens problèmes de mathématiques.

Somme des degrés

Les Pythagoriciens vivaient sur les rives de la mer Méditerranée et adoraient les nombres. L'un de leurs passe-temps était la fabrication de triangles de galets.



Une pierre, suivie d'une rangée de deux pierres, forment ensemble un triangle de trois pierres. Ajoutez une autre rangée de trois pierres pour former un triangle de six pierres. Cette procédure peut être poursuivie, en ajoutant chaque fois une ligne avec le nombre de pierres augmentant d'une unité. Un triangle de six rangées contient 21 pierres. Et combien de pierres seront dans le triangle de 423 rangées?

Les Pythagoriciens cherchaient un moyen de calculer la somme de la ligne suivante sans additionner:

1 + 2 + 3 + ⋯ + n

En fin de compte, ils ont réalisé que si vous placez deux triangles de même taille l'un à côté de l'autre afin qu'ils forment un rectangle, vous pouvez trouver l'aire du rectangle et la diviser en deux pour obtenir le nombre de pierres dans chacun des triangles:

1 + 2 + 3 + ⋯ + n = n (n + 1) / 2

Archimède a étudié un problème similaire. Il était intéressé par la séquence suivante:

1 ² +2 ² +3 ² + ⋯ + n ²

Il peut être imaginé comme une colonne de carrés de plus en plus grands (constitués de minuscules cubes), debout les uns sur les autres sous la forme d'une pyramide. Archimède voulait savoir s'il y avait un moyen facile de dire combien de cubes seraient nécessaires pour créer une pyramide avec, disons, 423 niveaux. Il a écrit une solution au problème, qui permet également une interprétation géométrique.



Trois pyramides peuvent être réalisées ensemble de manière à former un prisme rectangulaire, à une extrémité de laquelle se trouve une petite corniche d'un cube de hauteur. Ce rebord est un triangle obéissant aux mêmes règles que les triangles de pierre des Pythagoriciens. Par conséquent, le volume de la figure entière est donné par l'équation suivante:

3 (1 ² +2 ² +3 ² + ⋯ + n ² ) = (n + 1) n ² + (1 + 2 + 3 + ⋯ + n)

En substituant l'équation de Pythagore à la somme des n premiers entiers, et après avoir effectué quelques opérations algébriques, on obtient:

1 ² +2 ² +3 ² + ⋯ + n ² = n (n + 1) (2n + 1) / 6

En 499, le mathématicien et astronome indien Ariabhata a publié son travail, connu sous le nom d'Ariabhatia, qui donnait une formule pour calculer la somme des cubes:

1 ³ +2 ³ +3 ³ + ⋯ + n ³ = (1 + 2 + 3 + ⋯ + n) ²

La formule de la somme des n premiers entiers positifs au quatrième degré n'a été publiée que 500 ans plus tard.

À ce moment-là, vous pourriez avoir une question - existe-t-il une méthode universelle pour calculer la somme des n premiers entiers élevés à la puissance de k? Les mathématiciens étaient également intéressés par cela. Johan Faulhaber, un mathématicien allemand, légèrement avancé en numérologie, a pu dériver des formules pour la somme des nombres entiers jusqu'au 17e degré, en les publiant en 1631. Mais cela lui a pris de nombreuses années et il n'a pas donné de solution générale. Blaise Pascal a finalement trouvé une méthode généralisée en 1665, qui, cependant, dépendait du comptage de la somme des nombres entiers élevés aux degrés précédents. Par exemple, pour calculer la somme des n premiers entiers positifs élevés au 6e degré, vous devez d'abord apprendre à calculer la somme des n premiers entiers positifs élevés au 5e degré

Une solution généralisée plus pratique a été donnée dans un article publié à titre posthume par le mathématicien suisse Jacob Bernoulli , décédé en 1705. Bernoulli a commencé par dériver des formules pour calculer les sommes des n premiers entiers positifs élevés aux premier, deuxième, troisième et quatrième degrés. Il les a écrits sous forme de polynômes:

1 + 2 + 3 + ⋯ + n = 1 / 2n ² + 1 / 2n

1 ² +2 ² +3 ² + ⋯ + n ² = 1 / 3n ³ + 1 / 2n ² + 1 / 6n

1 ³ +2 ³ +3 ³ + ⋯ + n ³ = 1 / 4n ⁴ + 1 / 2n ³ + 1 / 4n ²

En utilisant le triangle de Pascal , Bernoulli s'est rendu compte que ces polynômes suivent un modèle prévisible. En fait, Bernoulli a divisé les coefficients de chaque terme en deux facteurs, dont l'un pouvait déterminer à l'aide du triangle de Pascal, et l'autre pour dériver d'une propriété intéressante par laquelle tous les coefficients du polynôme totalisaient un. Il n'était pas difficile de comprendre quel exposant mettre pour chaque membre, car ils suivaient également un modèle prévisible. Les facteurs de chaque coefficient, qui devaient être calculés selon la règle «la somme est égale à un», ont formé une séquence qui est devenue connue sous le nom de nombres de Bernoulli.

La découverte de Bernoulli ne signifiait pas que la somme des n premiers entiers positifs élevés à une puissance quelconque pouvait désormais être calculée de manière triviale. Pour calculer la somme des n premiers entiers positifs élevés à la puissance de k, il a fallu connaître tous les nombres de Bernoulli jusqu'au kième. Et chaque nombre de Bernoulli ne pouvait être calculé qu'en connaissant tous les précédents. Mais calculer une longue séquence de nombres de Bernoulli était incomparablement plus facile que de compter chaque somme de nombres élevée à une puissance, la découverte de Bernoulli a donc été une grande percée pour les mathématiques.

Babbage

Charles Babbage est né en 1791, près de cent ans après la mort de Bernoulli. J'ai toujours eu une telle idée de lui qu'il a développé, mais n'a pas construit, un ordinateur mécanique. Mais je n'ai jamais vraiment compris comment cet ordinateur était censé fonctionner. Il s'est avéré que les idées de base sont assez faciles à comprendre. Le programme Lovelace était censé fonctionner sur l'une des machines Babbage, nous devons donc prendre une autre petite digression et parler du fonctionnement de ces machines.

Babbage est venu avec deux ordinateurs mécaniques distincts. Le premier s'appelait une machine à différence . Avant l'invention des calculatrices de poche, les gens comptaient sur les logarithmes pour calculer le produit des grands nombres. Les grandes tables logarithmiques ne sont fondamentalement pas si difficiles à compiler, mais le nombre de calculs requis pour les compiler a conduit au fait qu'au moment de Babbage, elles contenaient souvent des erreurs. Agacé par cela, Babbage a décidé de créer une machine capable de créer mécaniquement des tables de logarithme sans faire d'erreurs.

La machine de différence n'était pas un ordinateur, car elle ne pouvait qu'additionner et soustraire. Elle a utilisé la méthode inventée par le mathématicien français Gaspard de Prony , qui a brisé le processus de construction d'une table en petites étapes. Ces étapes ne nécessitaient que l'addition et la soustraction, ce qui signifiait qu'une petite armée de personnes sans compétences mathématiques pouvait être utilisée pour construire la table. La méthode de Proni, connue sous le nom de méthode des différences divisées , pourrait être utilisée pour compiler un tableau pour tout polynôme. Et les polynômes pourraient déjà être utilisés pour le calcul approximatif des fonctions logarithmiques et trigonométriques.

Pour imaginer comment ce processus a fonctionné, considérons la fonction polynomiale simple suivante:

y = x ² +1

La méthode de différence fractionnée trouve la différence entre les valeurs y successives pour différentes valeurs x. Ensuite, il y a les différences entre ces différences, puis, éventuellement, les différences entre les dernières différences, jusqu'à ce qu'une différence constante apparaisse. Cette différence peut ensuite être utilisée pour obtenir la valeur polynomiale suivante par addition.

Puisque le polynôme indiqué n'a que le deuxième degré, nous pouvons trouver la différence constante après seulement deux colonnes de différences:

x	y	Diff 1	Diff 2
1	2
2	5	3
3	10	5	2
4	17	7	2
5	?	?	2
...	...	...	...

Maintenant, sachant que la différence constante est de 2, nous pouvons trouver la valeur de y lorsque x est 5, en utilisant une addition. En ajoutant 2 et 7, la dernière valeur de la colonne Diff 1, nous obtenons 9. En ajoutant 9 et 17, la dernière valeur de la colonne y, nous obtenons 26 - notre réponse.

La machine de différence Babbage pour chaque colonne de différence de la table avait sa propre colonne physique avec des engrenages. Chaque engrenage représentait une position décimale et la colonne entière représentait un nombre décimal. La machine de différence avait huit colonnes avec des engrenages, de sorte qu'elle pouvait compiler des tableaux polynomiaux jusqu'au septième degré. Les colonnes ont été initialement définies sur des valeurs qui coïncident avec la première ligne du tableau des différences, calculées à l'avance. L'opérateur a ensuite dû faire tourner le vilebrequin, ce qui a provoqué une différence constante autour de la machine lorsque les valeurs stockées dans chacune des colonnes ont été ajoutées aux éléments suivants.

Babbage a réussi à construire une petite partie de la machine à différences et à l'utiliser pour démontrer ses idées lors de fêtes. Mais même après avoir dépensé tellement d'argent qu'ils auraient suffi pour construire deux grands navires de guerre, il n'a pas pu terminer sa voiture. Au début du XVIIIe siècle, Babbage n'a trouvé personne qui puisse lui produire la bonne quantité de matériel avec la bonne précision. La version de travail de la machine de différence n'a été construite que dans les années 1990, après l'avènement des machines de haute précision.


En conséquence, Babbage s'est désintéressé de la machine de différence, réalisant que vous pouvez créer une machine beaucoup plus puissante et flexible. Sa « machine analytique » est aujourd'hui connue sous le nom d'ordinateur mécanique de Babbage. La machine analytique était basée sur les mêmes colonnes d'engrenages que la différence, mais si cette dernière n'avait que huit colonnes, celle analytique devrait en avoir plusieurs centaines. Une machine analytique pourrait être programmée avec des cartes perforées, comme un métier à tisser jacquard , et elle pourrait se diviser et se multiplier, pas seulement additionner et soustraire. Pour effectuer l'une de ces opérations, une partie de la machine appelée «usine» se reconstruirait dans la configuration souhaitée, lirait les opérandes d'autres colonnes utilisées pour stocker les données, puis écrirait le résultat dans d'autres colonnes.

Babbage l'a appelé une machine analytique parce qu'il était assez puissant pour faire quelque chose qui ressemble à la matanalyse. La machine de différence pourrait produire des tables polynomiales, mais la machine analytique pourrait calculer, par exemple, les coefficients de multiplication polynomiale d'une autre expression. C'était une machine incroyable, mais le gouvernement britannique a pris la sage décision de rejeter la demande de financement. Babbage s'est donc rendu à l'étranger, en Italie, pour essayer d'y trouver du soutien.

Notes du traducteur

À Turin, Babbage a rencontré un ingénieur italien et futur Premier ministre Luigi Federico Menabrea. Il a persuadé Menabrea d'écrire un aperçu des capacités de la machine analytique. En 1842, Menabrea publie un ouvrage sur ce sujet en français. L'année suivante, Lovelace a publié une traduction du travail de Menabrea en anglais.

Lovelace, alors connue sous le nom d'Ada Byron, a rencontré Babbage lors d'une fête en 1833, à l'âge de 17 ans et il avait 41 ans. Lovelace a été frappé par la machine à différence Babbage. Mais elle a pu comprendre comment cela fonctionne, car dans son enfance, elle a été activement enseignée les mathématiques. Sa mère, Anabella Milbank, a décidé que la base mathématique solide de l'éducation de sa fille la découragerait de la nature sauvage et romantique que possédait son père, Lord Byron , un célèbre poète. Après s'être rencontrés en 1833, Lovelace et Babbage sont restés dans le cercle social général et ont souvent correspondu.

Ada Byron épousa William King en 1835. King devint plus tard comte de Lovelace, après quoi Ada devint comtesse de Lovelace. Et même après avoir donné naissance à trois enfants, elle a continué à étudier les mathématiques, prenant comme professeur Augustus de Morgan, qui a découvert les lois de Morgan . Lovelace a immédiatement reconnu le potentiel de la machine analytique et a facilement accepté de travailler avec lui pour faire avancer cette idée. Son amie l'a invitée à traduire le travail de Menabrea pour un public anglais.

Le document contenait une brève description du fonctionnement d'une machine à différence, puis il a été montré dans quelle mesure la machine analytique la dépasserait. La machine analytique était censée être si puissante qu'elle pourrait "résulter de la multiplication de deux nombres, chacun composé de vingt caractères, en seulement trois minutes". Menabrea a donné d'autres exemples de la possibilité d'une machine, démontrant comment elle résoudrait un simple système d'équations linéaires et décomposerait le résultat de la multiplication de deux binômes. Dans les deux cas, Menabrea a présenté ce que Lovelace a appelé des «graphiques de développement» décrivant la séquence d'opérations nécessaires pour calculer la bonne réponse. Il s'agissait de programmes, au même titre que le programme Lovelace était un programme, et ils ont été publiés un an avant ses travaux. Mais, comme nous le verrons, les programmes de Menabrea n'étaient que des exemples de possibles. Tous étaient triviaux dans le sens où ils ne nécessitaient aucune ramification ou cycle.

Lovelace a ajouté quelques notes à sa traduction de l'œuvre de Menabrea, et au total, elles se sont révélées plus longues que l'œuvre originale. C'est là qu'elle a apporté sa principale contribution à l'informatique. Dans la note A, que Lovelace a faite à la description initiale de la machine analytique, elle a expliqué en détail, et parfois de manière lyrique, que cette machine serait capable d'effectuer des opérations mathématiques arbitraires. Elle prévoyait qu'une telle machine ne se limiterait pas à travailler avec des nombres et serait capable de traiter tous les objets "dont l'interaction fondamentale mutuelle peut être exprimée par la science abstraite des opérations, et qui peuvent être adaptés aux enregistrements opérationnels et au mécanisme de la machine". Elle a ajouté qu'un jour une telle machine pourra, par exemple, composer de la musique. Une telle prédiction était d'autant plus remarquable que Menabrea lui-même considérait cette machine comme un simple outil d'automatisation de «calculs longs et ennuyeux» qui libérerait les capacités intellectuelles de brillants scientifiques pour des recherches plus avancées. La prévoyance miraculeuse de Lovelace, comme le montre la note A, est l'une des principales raisons pour lesquelles nous l'honorons aujourd'hui.

Une autre note célèbre est la note de G. Lovelace, commençant par déclarer que, malgré ses capacités impressionnantes, la machine analytique ne peut pas être «pensée». C'est cette note de bas de page qu'Alan Turing appellera plus tard «l'objection d'Ada Lovelace». Cependant, poursuit Lovelace, la voiture est capable de choses incroyables. Pour démontrer sa capacité à gérer des problèmes plus complexes, Lovelace a proposé son programme de calcul des nombres de Bernoulli.

Son texte intégral, sous la forme d'un «tableau de développement» étendu, dont le format décrit par Lovelace dans la note D, peut être consulté ici . Il s'agit essentiellement d'une liste d'opérations indiquées par des symboles mathématiques. Il ne semble pas que Babbage ou Lovelace soient allés jusqu'à développer un ensemble de codes de fonctionnement pour la machine analytique.

Bien que Lovelace ait décrit une méthode pour calculer une séquence complète de nombres de Bernoulli jusqu'à une certaine limite, son programme n'a montré qu'une seule étape dans ce processus. Elle a compté le nombre qu'elle a nommé B7, connu des mathématiciens modernes comme le huitième nombre de Bernoulli. Par conséquent, son programme a résolu l'équation suivante:

B7 = −1 (A ₀ + B ₁ A ₁ + B ₃ A ₃ + B ₅ A ₅ )

Ici, chaque terme représente un coefficient dans une formule polynomiale pour la somme d'entiers élevés à un certain degré. Nous parlons ici de la huitième puissance, puisque le huitième nombre de Bernoulli apparaît pour la première fois dans la formule de la somme des entiers positifs élevés à la huitième puissance. Les nombres B et A représentent deux types de facteurs découverts par Bernoulli. Les numéros B1 à B7 sont les différents numéros de Bernoulli numérotés selon Lovelace. Les nombres A0 à A5 sont des multiplicateurs des coefficients que Bernoulli pourrait calculer en utilisant le triangle Pascal. Les valeurs de A0, A1 et A3 sont indiquées ci-dessous. Ici n désigne l'indice d'un nombre de Bernoulli dans une séquence de nombres impairs de Bernoulli commençant par le premier. Dans le programme Lovelace, n = 4.

A ₀ = −1 / 2⋅ (2n - 1) / (2n + 1)

A ₁= 2n / 2

A ₃ = 2n (2n - 1) (2n - 2) / (2⋅3⋅4)

A ₅ = 2n (2n - 1) (2n - 2) (2n - 3) (2n - 4) / (2⋅3⋅4⋅5⋅6)

J'ai traduit le programme Lovelace en C , et donc ce sera probablement plus facile à lire. Tout d'abord, son programme calcule A ₀ et le résultat de la multiplication B ₁ A ₁ . Commence alors le cycle, répété deux fois, pour calculer B ₃ A ₃ et B ₅ A ₅ , car ils sont lus de la même manière. Après avoir compté chaque multiplication, le résultat est ajouté aux précédents, donc à la fin du programme, le montant total est obtenu.

De toute évidence, la traduction en C ne peut pas être une reproduction exacte du programme Lovelace. Il déclare des variables sur la pile et les variables Lovelace ressemblaient plus à des registres. Mais il rend plus évident la partie la plus prophétique du programme Lovelace. Un programme C a deux boucles while, l'une dans l'autre. Le programme Lovelace n'avait pas de boucles while, mais il regroupait les opérations et décrivait dans une note pourquoi elles devaient être répétées. La variable v10 du programme d'origine et traduite en C fonctionne comme un compteur, diminuant à chaque passage du cycle - une conception similaire est familière à chaque programmeur. En général, en plus de l'abondance de variables avec des noms obscurs, un programme C ne semble pas inconnu.

Il convient également de noter que la traduction du programme Lovelace en C n'a pas été très difficile, grâce à un détail dans son diagramme. Contrairement aux tableaux de Menabrea, son tableau comporte une colonne «signe d'un changement dans la valeur d'une variable», ce qui facilite beaucoup le suivi du changement d'état. Elle ajoute un exposant à chaque variable pour indiquer les valeurs successives qui y sont stockées. L'index 2, par exemple, signifie que la valeur utilisée est la deuxième valeur affectée à la variable depuis le début du programme.

Premier programmeur?

Après avoir traduit le programme Lovelace en C, j'ai pu l'exécuter sur l'ordinateur. À ma grande déception, le résultat était incorrect. Après avoir recherché des erreurs, j'ai finalement réalisé que le problème ne venait pas de mon code - le bug était contenu dans le programme d'origine!

Dans le «tableau de développement», Lovelace écrit dans la quatrième opération v5 / v4. Mais la v4 / v5 sera correcte. Cette erreur peut apparaître à l'impression, mais pas à Lovelace. D'une manière ou d'une autre, il s'agit du plus ancien bug informatique. J'ai été surpris d'avoir passé une dizaine de minutes à chercher le tout premier bug de l'histoire.

Jim Randall, un autre blogueur qui a traduit le programme Lovelace en PythonA également noté ce bogue de division et deux autres problèmes. Quelles sont les petites erreurs du programme Ada Lovelace publié? Il est possible qu'elle essayait d'écrire non seulement une démonstration, mais un vrai programme. Après tout, vous ne pouvez pas écrire autre chose que des programmes de jouets, en évitant les erreurs?

Un article de Wikipedia indique que Lovelace a été le premier à publier un «programme compliqué». C'est peut-être précisément ainsi qu'il vaut la peine d'en percevoir les réalisations. Menabrea, dans son travail, a publié des «graphiques de développement» un an avant la publication de la traduction de Lovelace. Babbage a également écrit plus de vingt programmes qui n'ont jamais été publiés. Par conséquent, il n'est pas tout à fait correct d'écrire que Lovelace a écrit ou publié le premier programme, bien que l'on puisse toujours discuter de ce qui constitue un programme. Et pourtant, le programme Lovelace est bien en avance sur tout ce qui a été publié avant lui. Dans le programme le plus long, Menabrea a eu 11 opérations et il n'y avait ni boucles ni branches. Le programme Lovelace comportait 25 opérations et une boucle imbriquée (et donc une ramification). Menabrea à la fin de son travail a écrit ce qui suit:

Après la construction de la machine, la fabrication de cartes posera des difficultés; mais comme il ne s'agit que d'une traduction de formules algébriques, au moyen d'une notation simple, il sera assez simple de déléguer leur exécution à un travailleur.

Ni Babbage ni Menabrea n'étaient particulièrement intéressés à appliquer la machine analytique à des problèmes qui allaient au-delà des problèmes mathématiques qui ont inspiré Babbage à créer des ordinateurs. Lovelace s'est rendu compte que la machine analytique était capable de bien plus que Babbage et Menabrea auraient pu imaginer. Lovelace s'est également rendu compte que «faire des cartes» ne serait pas un travail mécanique, et que cela pourrait être mal ou bien fait. Il est difficile d'évaluer cela sans comprendre son programme à partir de la note G et sans voir à quel point elle a pris soin de le développer. Mais, après avoir fait cela, vous pouvez convenir que Lovelace, même sans être le tout premier programmeur, a été le premier programmeur à mériter ce nom.