Wer hat die Idee (n) der ersten Schleifenkonstrukte erstellt?

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

Als Entwickler müssen wir alle sehr häufig Schleifen verwenden. Wir wissen das. Was ich mich fragte, war, wer an die Idee dachte, Schleifen zu haben? Welche Sprache hat Schleifen eingeführt? Was war das erste Schleifenkonstrukt? War es eine whileSchleife? Eine forSchleife? usw?

Dynamisch
quelle
22
Wahrscheinlich Charles Babbage und Ada Lovelace.
McFinnigan
28
Es wurde in Shampoo-Anweisungen erfunden, ausspülen, aufschäumen, wiederholen. :-)
Guy Sirton
13
@GuySirton, sei nicht albern, das ist Rekursion.
Mowwwalker
18
@ user838584 - Wenn es eine Rekursion wäre, repeatwürde jede eine andere aufrufen repeat- Sie würden niemals fertig werden. Ich denke, vielleicht lesen Frauen Shampoo-Anweisungen auf diese Weise, aber Männer lesen sie als Iteration und brauchen nur ein paar Minuten, um sich die Haare zu waschen.
Steve314
3
Ein Computer ohne Schleifen ist ein Taschenrechner.
Starblue

Antworten:

102

Wie Mouviciel und Emilio Garavaglia feststellten, geht das Konzept dem Rechnen voraus . Die erste Instanz einer Softwareschleife war jedoch die Schleife Ada Lovelace , mit der Bernoulli-Zahlen berechnet wurden , wie in Anmerkung G ihrer Übersetzung der von Charles Babbage erfundenen Skizze der analytischen Maschine von LF Menabrea beschrieben . Die Schleifenfähigkeit der Analytical Engine wird von Menabrea früh erkannt:

Lassen Sie uns zu Beginn der Reihe von Operationen, die wir ausführen möchten, die Nadel C auf die Abteilung 2, die Nadel B auf die Abteilung 5 und die Nadel A auf die Abteilung 9 setzen Hammer des Zifferblatts C zum Schlagen; es schlägt zweimal und gleichzeitig überquert die Nadel B zwei Teilungen. Letzterer gibt dann die Zahl 7 an, die der Zahl 5 in der Spalte der ersten Unterschiede folgt. Wenn wir nun zulassen, dass der Hammer des Zifferblatts B seinerseits schlägt, schlägt er siebenmal, wobei die Nadel A sieben Teilstriche vorrückt; diese addieren sich zu den neun, die bereits durch sie markiert sind, und ergeben die Zahl 16, die das auf 9 folgende Quadrat darstellt. Wenn wir diese Operationen nun wieder beginnen, beginnen wir mit der Nadel C, die immer auf der Division 2 verbleiben soll.

Der Schleifenmechanismus der Analytical Engine ist direkt von Joseph Marie Jacquards mechanischem Webstuhl (1801) geerbt , wie in den Memoiren von Menabrea vermerkt:

Es wird nun gefragt, wie die Maschine von sich aus und ohne Rückgriff auf die Hand des Menschen die für die Operationen geeigneten aufeinanderfolgenden Dispositionen annehmen kann. Die Lösung dieses Problems wurde aus der Jacquard-Vorrichtung, die zur Herstellung von brokatierten Stoffen verwendet wird, auf folgende Weise übernommen:

Bei gewebten Stoffen werden gewöhnlich zwei Arten von Fäden unterschieden; einer ist der Kettfaden oder Längsfaden, der andere der Schussfaden oder Querfaden, der von dem als Shuttle bezeichneten Instrument transportiert wird und der den Längsfaden oder die Kette kreuzt. Wenn ein brokatiertes Zeug benötigt wird, ist es wiederum erforderlich, zu verhindern, dass bestimmte Fäden den Schuss durchqueren, und dies in einer Reihenfolge, die durch die Art des zu reproduzierenden Designs bestimmt wird. Früher war dieser Prozess langwierig und schwierig, und es war erforderlich, dass der Arbeiter, indem er sich um den Entwurf kümmerte, den er kopieren sollte, selbst die Bewegungen regulierte, die die Fäden ausführen sollten. Daher entstand der hohe Preis dieser Stoffbeschreibung, insbesondere wenn Fäden verschiedener Farben in den Stoff eingingen. Um diese Herstellung zu vereinfachen, Jacquard entwarf den Plan, jede Gruppe von Fäden, die zusammenwirken sollten, mit einem bestimmten Hebel zu verbinden, der ausschließlich dieser Gruppe gehört. Alle diese Hebel enden in Stäben, die zu einem Bündel zusammengefasst sind und üblicherweise die Form eines Parallelepipeds mit einer rechteckigen Grundfläche haben. Die Stäbe sind zylindrisch und durch kleine Abstände voneinander getrennt. Der Vorgang des Anhebens der Fäden wird somit in den Vorgang des Bewegens dieser verschiedenen Hebelarme in der erforderlichen Reihenfolge aufgelöst. Zu diesem Zweck wird eine rechteckige Platte aus Pappe genommen, die etwas größer ist als ein Abschnitt des Hebelarmbündels. Wenn dieses Blatt auf die Basis des Bündels aufgebracht und dann eine Vorschubbewegung auf die Pappe übertragen wird, bewegt diese letztere alle Stangen des Bündels mit. und folglich die Fäden, die mit jedem von ihnen verbunden sind. Wenn jedoch die Pappe nicht glatt, sondern mit Löchern versehen wäre, die den Enden der Hebel entsprechen, die darauf treffen, dann blieben alle Hebel in ihrer Position, da jeder der Hebel während der Bewegung durch die Pappe geführt würde setzt. Wir sehen also, dass es leicht ist, die Position der Löcher in der Pappe zu bestimmen, dass zu jedem Zeitpunkt eine bestimmte Anzahl von Hebeln und folglich von Fadenpaketen angehoben werden muss, während der Rest dort verbleibt, wo sie sind wurden. Angenommen, dieser Vorgang wird nacheinander gemäß einem Gesetz wiederholt, das durch das auszuführende Muster angegeben wird, so nehmen wir an, dass dieses Muster auf dem Material reproduziert werden kann. Zu diesem Zweck müssen wir lediglich eine Reihe von Karten gemäß dem erforderlichen Gesetz zusammenstellen. und ordne sie in geeigneter Reihenfolge nacheinander an; dann, indem man sie über einen polygonalen Balken laufen läßt, der so verbunden ist, daß sie für jeden Hub des Shuttles eine neue Fläche drehen, die dann parallel zu sich selbst gegen das Bündel von Hebelarmen gedrückt wird, wird der Vorgang des Anhebens des Threads werden regelmäßig durchgeführt. So sehen wir, dass brokatierte Tissues mit einer Präzision und Schnelligkeit hergestellt werden können, die früher schwer zu bekommen waren.

Jacquard's Webstuhl ist eine sehr frühe Anwendung einer Schleife im Zusammenhang mit der Bestellung einer Maschine, um eine wiederholte Ausgabe zu erzeugen :

Die Idee hinter dem Jacquard-Webstuhl war ein System aus Lochkarten und Haken. Die Karten waren sehr dick und mit rechteckigen Löchern versehen. Die beim Weben verwendeten Haken und Nadeln wurden durch diese Löcher in der Pappe geführt. Wenn die Haken mit der Karte in Kontakt kamen, wurden sie stationär gehalten, sofern sie nicht auf eines der gestanzten Löcher stießen. Dann konnte der Haken mit einer Nadel, die einen anderen Faden einführte, durch das Loch gehen und so das gewünschte Muster bilden. Komplizierte Muster wurden erreicht, indem viele Karten hintereinander angeordnet und / oder wiederholt verwendet wurden.

Jacquards Webstuhl wird auch als eine sehr frühe Form eines gespeicherten Programms erkannt :

Wenn die bisher diskutierten Impulse für einen Großteil der Entwicklung von Rechenmaschinen aus numerischen Berechnungen stammten, war die Motivation, die zur frühesten Form von "gespeichertem Programm" führte, eine ganz andere: die Textilindustrie. Wir haben bereits früher gesehen, dass einer der grundlegenden Aspekte von Rechensystemen das Konzept der Darstellung von Informationen ist, und obwohl wir dies nicht explizit getan haben, kann die Anwendung dieser Idee in allen bisher untersuchten Artefakten festgestellt werden: bei der Entwicklung schriftlicher Darstellungen für numerische Werte und der daraus resultierenden mechanischen Parallelen. So die Ausrichtung von Kieselsteinen auf einem Abakusrahmen, das Nebeneinander von beweglichen Skalen auf einem Rechenschieber und die Konfiguration von Zahnrädern auf den Geräten von Schickard, Pascal und Leibniz, All dies sind Beispiele für Darstellungstechniken, die die komplexen Prozesse vereinfachen sollen, die arithmetischen Aufgaben zugrunde liegen. Es gibt jedoch andere Informationskategorien und Darstellungen davon als die Anzahl, an denen Rechenprozesse ausgeführt werden können. Die von Joseph-Marie Jacquard 1801 entwickelte Webtechnik veranschaulicht ein Beispiel für eine solche Kategorie.

Charles Babbage hat auch Jacquards Speicherverfahren in der Analytical Engine angepasst. Das Vorhandensein oder Fehlen eines Lochs hat der Maschine einen einfachen Ein- / Ausschaltbefehl übermittelt:

Die Analytical Engine verfügt über viele wesentliche Funktionen, die im modernen Digitalcomputer zu finden sind. Es war mit Lochkarten programmierbar, eine Idee, die dem Jacquard-Webstuhl entlehnt war, mit dem komplexe Muster in Textilien gewebt wurden. Die Engine hatte einen "Speicher", in dem Zahlen und Zwischenergebnisse gespeichert werden konnten, und eine separate "Mühle", in der die arithmetische Verarbeitung durchgeführt wurde. Es verfügte über ein internes Repertoire der vier Rechenfunktionen und konnte eine direkte Multiplikation und Division durchführen. Es war auch zu Funktionen fähig, für die wir moderne Namen haben: Bedingte Verzweigung, Schleifen (Iteration), Mikroprogrammierung, Parallelverarbeitung, Iteration, Latching, Polling und Pulsformung, obwohl Babbage diese Begriffe nirgends benutzte. Es hatte eine Vielzahl von Ausgaben, einschließlich Ausdruck, Lochkarten,

Die bedingten Verzweigungen der Analytical Engine in Kombination mit den von Jacquard inspirierten mechanischen Schleifen und der Aufbewahrungsprozedur ähneln (konzeptionell) beängstigend Ihrem Beispiel, insbesondere wenn wir den Babbage-Drucker für die print "...";Teile in den Mix aufnehmen .

Offensichtlich sind mechanische Schleifen älter als Jacquard's Webstuhl. Das erste bekannte Gerät, das in Schleifenform arbeitet, ist der Antikythera-Mechanismus (100 v. Chr.). Wenn wir uns die Geschichte noch genauer ansehen (und uns fürchterlich vom Thema abwenden), sind Sonnenuhren wahrscheinlich die ältesten von Menschen hergestellten Mechanismen wo ein Verständnis von Schleifen offensichtlich ist, folgt dies natürlich dem sich wiederholenden Muster der Umlaufbahnen der Sonne und anderer Sternkörper.

Ich denke jedoch, dass im Zusammenhang mit dem Rechnen (und nicht dem Berechnen oder etwas anderem) der Berechnungsalgorithmus für die Bernoulli-Zahlen von Analytical Engine und Ada für die Einführung von Schleifen gutgeschrieben werden kann, wobei zumindest ein Teil des Kredits mit Jacquards Webstuhl geteilt wird, nachdem das Konzept direkt von übernommen wurde es.

yannis
quelle
3
Vor Jacquards Webstuhl befinden sich in Glockenspielen mechanische Schleifen, wie in Brügge, bei denen die Glocken durch die Drehung eines Zylinders gesteuert werden .
mouviciel
6
@mouviciel Ich sehe deine Glockenmonstrosität und ich hebe dir einen Antikythera-Mechanismus auf. ; P
yannis
2
+1 für Ihre enzyklopädische Antwort, einschließlich eines 2000 Jahre alten Computers!
mouviciel
2
Diese schöne Antwort ließ mich die Frage am liebsten stellen. Es beantwortet nicht nur die Frage, sondern ist auch ein Beispiel dafür, wie man eine Frage beantwortet. Gute Arbeit, mein Herr.
Chani
Akzeptierte diese Antwort, weil sie sowohl schlüssig, enzyklopädisch als auch einfach nur fantastisch war!
Dynamische
50

Schleifen vor dem Computing. Sie finden sie in Notenschrift schon beim Gregorianischen Gesang:

Wiederholungszeichen

mouviciel
quelle
2
Dies kann eine gute Antwort sein, wenn etwas mehr Details hinzugefügt wurden. Trotzdem gute Arbeit.
Dynamische
Bitte geben Sie weitere Referenzen an (frühestes Datum, früheste musikalische Notation für Feature-Loop / Repeat-Konstrukte)
Skippy Fastol
@SkippyFastol Es ist in diesem Artikel: en.wikipedia.org/wiki/Repeat_sign#Other_notation
cwallenpoole
32

Der Begriff "Mach es noch einmal" ist irgendwie "primitiv" für die menschliche Wahrnehmung. Sie können dies einem Kind erzählen, das gerade ein minimales Verständnis der natürlichen Sprache erarbeitet hat.

In diskreten Systemen finden sich in allen Zustandsautomaten Schleifen, wenn Sie zugeben, dass Sie einen Zustand erreichen können, den Sie schon einmal hatten .

Die einfachste Schleife ist der Zyklus zwischen zwei Zuständen (eine Uhr). Angesichts der Tatsache, dass eine höhere Anzahl von Zuständen aus einer Zählung resultieren kann, wird jede komplexere Maschine auf einen "Zähler" aufgebaut, der durch einen Takt inkrementiert wird, der auf bestimmte Flags, die bestimmte kombinatorische Operationen darstellen, "springen" kann. Dies ist der Kern einer Von Neumann-Maschine, auf der jeder mikroprozessorbasierte Computer basiert.

Im Maschinencode ist ein Sprung codiert JP-Z-nnnn(wobei Z die Basis Ihrer Bedingung ist). In einer höheren Sprache wird dies fast sofort übersetzt

if(z) goto x;

Eine Schleife ist nichts anderes als ein gotoPunkt, an dem das x-Label vor der goto-Anweisung steht.

Jede andere Formulierung (für, do, while usw.) ist nur "syntaktischer Zucker", um das wilde Goto in den sehr häufigen Fällen des Wiederholens besser zu domestizieren , bis etwas passiert

Emilio Garavaglia
quelle
4

Das Konzept des Loopings ist eines der Merkmale, die einen vollwertigen Computer von einer einfachen Rechenmaschine unterscheiden. Wenn ein System keine Schleifen unterstützt, ist es nicht vollständig und daher kein Computer.

Das erste vollständige Design von Turing war die Analytical Engine von Babbage. Es musste also ein Looping-Konzept gegeben haben. Es gibt jedoch Systeme mit Schleifen, die jedoch nicht vollständig sind (weil sie etwas anderes auslassen). Babbages Arbeit ist jedoch wahrscheinlich ein guter Ausgangspunkt.

GordonM
quelle
6
Der Lambda-Kalkül hat keine Schleifen (und keine Bedingungen oder Sprünge), aber er ist vollkommen. Rekursion ist genauso mächtig wie Iteration.
3
Sie können jede Schleife in eine rekursive Funktion umschreiben und Schleifen eliminieren
Ratschenfreak
5
Der Wikipedia-Artikel über Schleifen beschreibt die Rekursion als Ausdruck einer Schleife und nicht als völlig verwandtes Konzept. en.wikipedia.org/wiki/Program_loop#Loops CPUs, die keine Schleifen haben, verfügen über die erforderlichen Tools, um diese zu implementieren (Springen zu einer beliebigen Speicheradresse)
GordonM
8
Genau genommen kann Rekursion verwendet werden, um Schleifen auszudrücken . Es ist ein ganz anderes Konzept, obwohl sie zueinander isomorph sind. Eine Kaffeetasse ist kein Donut, nur weil Topologen sie angeblich verwirren.
4
Es ist wahr, aber jedes System mit vollständigem Aufbau muss das Konzept der mehrfachen Ausführung derselben Sequenz zum Ausdruck bringen können. Der Mechanismus kann eine Rekursion sein oder in der Anweisungsliste rückwärts springen oder alles andere, was den gleichen Effekt erzielt. Wenn ein System keine Möglichkeit bietet, einen Befehlssatz zu wiederholen (außer die Anweisungen in der Liste physisch zu wiederholen), kann Turing nicht vollständig sein. Die Analytical Engine war Turing-vollständig, daher muss sie die Schleifen in der einen oder anderen Form implementieren.
GordonM
3

Angenommen, Sie meinen moderne Text-Computerprogrammiersprachen.

Algol60 hat "FOR", "DO", "UNTIL" und "WHILE", also war es vor 1960.

Das Retro Computing Museum hat vor 1960 einige Sprachen.

Kvikkalkul , die Programmiersprache für schwedische Atom- U-Boote aus den 50er Jahren, hat nur GOTO. (Kvikkalkul ist jedoch mit ziemlicher Sicherheit ein Schwindel aus den 90er Jahren, keine echte historische Sprache.)

Der Plankalkül von Konrad Zuse ist der früheste, den ich finden konnte. Es hat ein "für" -Konstrukt.

Chad Brewbaker
quelle
Plankalkül war bis vor kurzem im Wesentlichen unveröffentlicht, und Kvikkalkul wird seit langem als Scherz gehandelt. In diesem Licht muss das Verdienst wahrscheinlich John Backus und dem FORTRAN- Team gelten, das 1957 einen laufenden Compiler mit DOLoops auf dem Feld hatte .
Ross Patterson
2

Die Arbeit von Liebniz und Newton enthält Algorithmen mit Schleifenkonstrukten. Liebniz baute einen mechanischen Taschenrechner und spekulierte (wie Lovelace es Jahre später tat) über eine Maschine, um komplexere Analysen durchzuführen. Seine Notizen zu diesen Ideen sind flüchtig, aber sie beschreiben strukturierte Logik mit Schleifen.

Die Idee von Wiederholungssequenzen und zählungsgesteuerten Schleifen sowie das, was wir als while-Schleifen bezeichnen würden, werden jedoch in der Arbeit des Mannes diskutiert, für den die Algorithmen benannt wurden: Muhammad ibn Musa al-Khwarizmi aus dem 9. Jahrhundert. Sein zweites Buch, al-Kitab al-Mukhtasar fi hisab al-Jabr wa'l-Mukhtasar fi hisab al-Jabr wa'l-Mukhtasar fi hisab al-Jabr wa'l-Mukhtasar fi hisab .

Natürlich stützte sich al-Khwarizmi teilweise auf die alten Griechen. Irgendwann kehren wir wahrscheinlich zu Adams und Evas Version von Spülen, Schäumen, Wiederholen zurück.

Weitere Informationen über Al-Khwārizmī und seine Arbeit finden Sie unter:

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

Chuck Herbert
quelle