Qui a créé la ou les idées des premières constructions de boucle?

53
while (1) {
      if (1+1==2) {
             print "Yes, you paid attention in Preschool!";
      } else {
             print "Wait... I thought 1+1=2";
      }
 }

En tant que développeur, nous devons tous utiliser des boucles très fréquemment. Nous savons que. Ce que je me demandais, c'est qui a pensé à l'idée d'avoir des boucles? Quelle langue a introduit les boucles? Quelle était la construction de la première boucle? Était-ce une whileboucle? Une forboucle? etc?

Dynamique
la source
22
Charles Babbage et Ada Lovelace, très probablement.
mcfinnigan
28
Il a été inventé dans les instructions de shampooing, rincer, faire mousser, répéter. :-)
Guy Sirton
13
@GuySirton, Ne sois pas stupide, c'est la récursion.
Mowwwalker
18
@ user838584 - s'il s'agissait d'une récursion, chacune repeatinvoquerait une autre repeat- vous ne finiriez jamais. Je pense que peut-être les femmes lisent les instructions de shampoing de cette façon, mais les hommes le lisent comme une itération et n'ont besoin que de quelques minutes pour se laver les cheveux.
Steve314
3
Un ordinateur sans boucles est une calculatrice.
starblue

Réponses:

102

Comme l'ont noté mouviciel et Emilio Garavaglia , le concept est antérieur à l'informatique. Cependant, la première instance de boucle logicielle a été la boucle utilisée par Ada Lovelace pour calculer les nombres de Bernoulli , comme indiqué dans la note G de sa traduction de l' esquisse du moteur d'analyse inventé par Charles Babbage , de LF Menabrea . Menabrea a noté très tôt la capacité du moteur analytique à boucler en boucle:

Ceci compris, au début de la série d’opérations que nous souhaitons exécuter, posons l’aiguille C sur la division 2, l’aiguille B sur la division 5 et l’aiguille A sur la division 9. Laissons la marteau du cadran C pour frapper; il frappera deux fois et en même temps l'aiguille B passera sur deux divisions. Ce dernier indiquera ensuite le nombre 7, qui succède au nombre 5 dans la colonne des premières différences. Si nous permettons maintenant au marteau du cadran B de frapper à son tour, il frappera sept fois, pendant lequel l'aiguille A avancera de sept divisions; ceux-ci ajoutés aux neuf déjà marqués par lui donneront le nombre 16, qui est le nombre carré consécutif à 9. Si nous reprenons maintenant ces opérations, en commençant par l'aiguille C, qui doit toujours être laissée sur la division 2,

Le mécanisme de bouclage du moteur analytique est directement hérité du métier à tisser mécanique de Joseph Marie Jacquard (1801), comme l'indique le mémoire de Menabrea:

On va maintenant se demander comment la machine peut de soi, et sans recourir à la main de l'homme, assumer les dispositions successives adaptées aux opérations. La solution de ce problème a été empruntée à l'appareil de Jacquard, utilisé pour la fabrication d'étoffes en brocart, de la manière suivante: -

Deux espèces de fils se distinguent généralement dans les étoffes tissées; l'un est le fil de chaîne ou le fil longitudinal, l'autre le fil de trame ou fil transversal, qui est acheminé par l'instrument appelé navette, et qui traverse le fil longitudinal ou la chaîne. Quand un tissu broché est requis, il est nécessaire d'empêcher certains fils de traverser la trame, et ce, selon une succession qui est déterminée par la nature du dessin à reproduire. Auparavant, ce processus était long et difficile et il était nécessaire que l'ouvrier, en s'occupant du dessin qu'il devait copier, règle lui-même les mouvements que devaient prendre les fils. De là le prix élevé de cette description des étoffes, surtout si des fils de différentes couleurs entraient dans l’étoffe. Pour simplifier cette fabrication, Jacquard a conçu le plan consistant à connecter chaque groupe de fils devant agir ensemble, avec un levier distinct appartenant exclusivement à ce groupe. Tous ces leviers se terminent par des tiges, réunies en un faisceau, se présentant généralement sous la forme d’un parallélépipède à base rectangulaire. Les tiges sont cylindriques et sont séparées les unes des autres par de petits intervalles. Le processus de remontée des fils se résout donc en un déplacement de ces différents bras de levier dans l’ordre requis. Pour ce faire, on prend une feuille de carton rectangulaire d'une taille légèrement supérieure à celle d'une section du faisceau de bras de levier. Si cette feuille est appliquée sur la base du paquet et qu'un mouvement d'avancement est ensuite communiqué au carton, ce dernier déplacera avec lui toutes les tiges du paquet, et par conséquent les fils qui sont connectés à chacun d'eux. Mais si le carton, au lieu d'être uni, était percé de trous correspondant aux extrémités des leviers qui le rencontraient, alors, chacun des leviers passant dans le carton lors du mouvement de ce dernier, ils resteraient tous dans leur position. des endroits. Nous voyons donc qu’il est facile de déterminer la position des trous dans le carton, qu’à un moment donné, il doit y avoir un certain nombre de leviers, et par conséquent de paquets de fils, levés, le reste restant où étaient. En supposant que ce processus soit répété successivement selon une loi indiquée par le motif à exécuter, nous percevons que ce motif peut être reproduit sur le support. Pour cela, il suffit de composer une série de cartes conformément à la loi requise, et organisez-les dans un ordre approprié, l'un après l'autre; puis, en les faisant passer sur un faisceau polygonal relié de manière à tourner une nouvelle face à chaque coup de la navette, cette face doit ensuite être poussée parallèlement à elle-même contre le faisceau de bras de levier, l'opération consistant à relever le les discussions seront effectuées régulièrement. Ainsi, nous voyons que les tissus brodés peuvent être fabriqués avec une précision et une rapidité autrefois difficiles à obtenir.

Le métier à tisser de Jacquard est une application très précoce d'une boucle dans le contexte de la commande d'une machine pour produire une sortie répétée :

L'idée derrière le métier à tisser Jacquard était un système de cartes perforées et de crochets. Les cartes étaient très épaisses et perforées de trous rectangulaires. Les crochets et les aiguilles utilisés dans le tissage étaient guidés par ces trous dans le carton. Lorsque les crochets sont entrés en contact avec la carte, ils ont été immobilisés à moins que celle-ci ne rencontre un des trous perforés. Ensuite, le crochet a pu passer à travers le trou avec une aiguille insérant un autre fil, formant ainsi le motif souhaité. Des motifs complexes ont été obtenus en disposant de nombreuses cartes disposées les unes après les autres et / ou utilisées à plusieurs reprises.

Le métier à tisser de Jacquard est également reconnu comme une forme très précoce d'un programme stocké :

Si l'essentiel du développement des machines à calculer dont il a été question jusqu'à présent était issu du calcul numérique, la motivation qui a conduit à la forme la plus ancienne de «programme stocké» devait provenir d'une source très différente: l'industrie textile. Nous avons vu précédemment que l'un des aspects fondamentaux des systèmes informatiques est le concept de représentation de l'information et, bien que nous ne l'ayons pas fait explicitement, l'application de cette idée peut être discernée dans tous les artefacts que nous avons examinés jusqu'à présent: dans le développement de représentations écrites pour les valeurs numériques et les parallèles mécaniques qui en découlent. Ainsi, l'alignement des cailloux sur un cadre de boulier, la juxtaposition d'échelles mobiles sur une règle à calcul et la configuration d'engrenages dentés sur les dispositifs de Schickard, Pascal et Leibniz, sont tous des exemples de techniques de représentation visant à simplifier les processus complexes sous-jacents aux tâches arithmétiques. Il existe cependant des catégories d'informations et leurs représentations, autres que le nombre, sur lesquelles des processus de calcul peuvent être effectués. La technologie de tissage développée par Joseph-Marie Jacquard en 1801 illustre un exemple d'une telle catégorie.

Charles Babbage a également adapté la procédure de stockage de Jacquard dans le moteur d'analyse . La présence ou l'absence d'un trou transmettait une simple commande marche-arrêt à la machine:

Le moteur d'analyse comporte de nombreuses fonctionnalités essentielles que l'on retrouve dans les ordinateurs numériques modernes. Il était programmable à l’aide de cartes perforées, une idée empruntée au métier à tisser Jacquard utilisé pour le tissage de motifs complexes dans les textiles. Le moteur avait un «magasin» où les nombres et les résultats intermédiaires pouvaient être conservés, et un «moulin» séparé où le traitement arithmétique était effectué. Il avait un répertoire interne des quatre fonctions arithmétiques et pouvait effectuer une multiplication et une division directes. Il était également capable de fonctions pour lesquelles nous avons des noms modernes: branchement conditionnel, boucle (itération), microprogrammation, traitement parallèle, itération, verrouillage, interrogation et mise en forme d'impulsions, entre autres, bien que Babbage n'ait jamais utilisé ces termes. Il avait une variété de sorties, y compris une impression papier, des cartes perforées,

Les branches conditionnelles du moteur analytique combinées aux boucles mécaniques inspirées par Jacquard et à la procédure de stockage sont extrêmement similaires (conceptuellement) à votre exemple, en particulier si nous ajoutons l’imprimante de Babbage au mélange, pour les print "...";pièces.

Les boucles mécaniques sont bien antérieures au métier à tisser de Jacquard, le premier dispositif connu fonctionnant en boucle étant le mécanisme d'Anticythère (100 BCE), et si nous regardons plus loin dans l'histoire (et nous aventurons horriblement hors sujet), les cadrans solaires sont probablement les plus anciens mécanismes fabriqués par l'homme où la compréhension des boucles est évidente, en suivant bien sûr le motif de répétition des orbites du soleil et des autres corps stellaires.

Cependant, je pense que dans le contexte de l'informatique (et non de calcul ou autre chose), le moteur d'analyse et l'algorithme de calcul des nombres de Bernoulli d'Ada peuvent être crédités pour l'introduction de boucles, partageant au moins une partie du crédit avec le métier de Jacquard, ayant directement adapté le concept de il.

Yannis
la source
3
Avant le métier à tisser de Jacquard, vous pouvez trouver des boucles mécaniques dans les carillons, comme celui de Bruges, où les cloches sont contrôlées par la rotation d'un cylindre .
mouviciel
6
@mouviciel Je vois votre cloche monstruosité et je vous élève un mécanisme d'Anticythère. ; P
yannis
2
+1 pour votre réponse encyclopédique, y compris un ordinateur à 2000 ans!
mouviciel
2
cette belle réponse m'a fait préférer la question. Cela répond non seulement à la question, mais constitue un exemple de "comment répondre à une question". Bon travail, cher monsieur.
Chani
Accepté cette réponse car elle était à la fois concluante, encyclopédique et tout simplement géniale!
Dynamic
50

Les boucles précèdent l'informatique. Vous pouvez les trouver en notation musicale dès le chant grégorien:

répéter le signe

mouviciel
la source
2
Cela peut être une excellente réponse si un peu plus de détails y ont été ajoutés. Encore un excellent travail.
Dynamic
Veuillez donner plus de références (la date la plus ancienne, la notation musicale la plus ancienne pour présenter les constructions en boucle / répétées)
Skippy Fastol
@SkippyFastol C'est dans cet article: en.wikipedia.org/wiki/Repeat_sign#Other_notation
cwallenpoole
32

Le concept de "refaire" est en quelque sorte "primitif" pour la perception humaine. Vous pouvez le dire à un enfant qui vient d’élaborer une compréhension minimale du langage naturel.

Dans les systèmes discrets, on trouve des boucles dans toutes les machines à états finis lorsque vous admettez que vous pouvez atteindre un état que vous avez déjà été .

La boucle la plus simple est le cycle entre deux états (une horloge). Etant donné qu'un nombre d'états plus élevé peut en résulter, chaque machine plus complexe est construite sur un "compteur" incrémenté par une horloge qui peut "sauter" sur certains drapeaux représentant certaines opérations combinatoires. C’est le cœur d’une machine Von Neumann sur laquelle est basé chaque ordinateur à microprocesseur.

Dans le code machine, un saut est codé JP-Z-nnnn(où Z est le drapeau de base qui détermine votre condition). Dans les langues de niveau supérieur, cela se traduit presque immédiatement en

if(z) goto x;

Une boucle n'est rien de plus qu'un point gotooù l'étiquette x précède l'instruction goto elle-même.

Toute autre formulation (pour, fait, tout, etc.) est juste un "sucre syntaxique" pour mieux domestiquer le goto sauvage dans les cas très fréquents de répétition jusqu'à ce que quelque chose se produise

Emilio Garavaglia
la source
4

Le concept de bouclage est l’un des éléments qui distinguent un ordinateur complet d’une simple calculatrice. Si un système ne prend pas en charge la mise en boucle, il n'est pas complet et n'est donc pas un ordinateur.

La première conception complète de Turing était le moteur analytique de Babbage , qui devait donc avoir un concept de boucle. Cependant, il existe des systèmes qui fonctionnent en boucle mais qui ne sont pas complets (parce qu'ils omettent autre chose). Le travail de Babbage est probablement un bon point de départ.

GordonM
la source
6
Le lambda calcul n'a pas de boucles (et pas de conditions ou de sauts), pourtant il est complet. La récursion est aussi puissante que l'itération.
3
vous pouvez réécrire n'importe quelle boucle sur une fonction récursive et éliminer les boucles
freaket freak
5
L'article de Wikipédia sur les boucles décrit la récursivité comme un moyen d'exprimer une boucle plutôt que comme un concept totalement indépendant. en.wikipedia.org/wiki/Program_loop#Loops Quant aux CPU n'ayant pas de boucles, ils disposent des outils nécessaires pour les implémenter (passer à une adresse mémoire arbitraire)
GordonM
8
Justement, la récursivité peut être utilisée pour exprimer des boucles. Il est un concept tout à fait différent, même si elles sont isomorphes. Une tasse de café n'est pas un beignet simplement parce que les topologues les confondraient.
4
Certes, mais tout système complet doit avoir un moyen d’exprimer le concept d’exécution de la même séquence plusieurs fois. Le mécanisme peut être une récursion, un saut en arrière dans la liste d’instructions ou tout autre résultat produisant le même effet. Si un système ne fournit aucun moyen de répéter un ensemble d'instructions (autre que de répéter physiquement les instructions de la liste), la tâche ne peut pas être complète. Le moteur analytique étant complet, il doit donc implémenter la mise en boucle sous une forme ou une autre.
GordonM
3

Supposons que vous parliez de langages de programmation informatiques modernes.

Algol60 a "POUR", "DO", "UNTIL" et "WHILE", donc c'était avant 1960.

Le musée du calcul rétro comprend quelques langues avant 1960.

Kvikkalkul , le langage des années 50 pour la programmation des sous-marins nucléaires suédois, n'a que le GOTO. (Cependant, le kvikkalkul est presque certainement un canular des années 90, pas un vrai langage historique.)

Plankalkül de Konrad Zuse est le premier que j'ai trouvé. Il a une construction "für".

Chad Brewbaker
la source
Plankalkül était essentiellement inédit jusqu'à récemment, et on dit depuis longtemps que Kvikkalkul est un canular. Dans cette optique, il faut probablement remercier John Backus et l’ équipe de FORTRAN , qui avait un compilateur en service sur le terrain en 1957, avec des DOboucles.
Ross Patterson
2

Le travail de Liebniz et de Newton contient des algorithmes avec des constructions en boucle. Liebniz a construit une calculatrice mécanique et a spéculé (comme Lovelace l’a fait des années plus tard) sur une machine permettant d’effectuer des analyses plus sophistiquées. Ses notes sur ces idées sont sommaires, mais elles décrivent une logique structurée avec des boucles.

Cependant, l'idée de séquences de répétition et de comptage de boucles contrôlées, ainsi que ce que nous appellerions des boucles tandis que sont décrites dans le travail de l'homme pour qui les algorithmes sont nommés: Muhammad ibn Musa al-Khwarizmi du IXe siècle. Son deuxième livre, al-Kitab al-Mukhtasar fi hisab al-jabr wa'l-muqabala (Un Compendium sur le calcul par complément et équilibrant) était connu de Newton, Liebniz, Babout, Aventure, Aventure, .

Bien entendu, al-Khwarizmi s'est en partie fié aux Grecs de l'Antiquité. À un moment donné, nous reviendrons probablement à la version d'Adam et Eve qui dit «rincez, mousse, répétez».

Pour en savoir plus sur Al-Khwārizmī et son travail, voir:

http://www-groups.dcs.st-andrews.ac.uk/history/Mathematicians/Al-Khwarizmi.html

Chuck Herbert
la source