Kto stworzył idee pierwszych konstrukcji pętli?

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

Jako programista wszyscy musimy bardzo często używać pętli . Wiemy to. Zastanawiałem się, kto pomyślał o tym, żeby mieć pętle? W jakim języku wprowadzono pętle? Jaka była pierwsza konstrukcja pętli? Czy to była whilepętla? forPętla? itp?

Dynamiczny
źródło
22
Najprawdopodobniej Charles Babbage i Ada Lovelace.
mcfinnigan,
28
Został wynaleziony w instrukcjach szamponu, spłukać, spienić, powtórzyć. :-)
Guy Sirton
13
@ GuySirton, nie bądź głupi, to rekurencja.
mowwwalker
18
@ user838584 - gdyby to była rekurencja, każdy repeatprzywołałby inną repeat- nigdy byś nie skończył. Myślę, że kobiety mogą w ten sposób czytać instrukcje dotyczące szamponu, ale mężczyźni czytają je jako iterację i potrzebują tylko kilku minut na umycie włosów.
Steve314
3
Komputer bez pętli to kalkulator.
starblue

Odpowiedzi:

102

Jak zauważyli mouviciel i Emilio Garavaglia , koncepcja ta poprzedza przetwarzanie komputerowe. Jednak pierwszym wystąpieniem pętli programowej była pętla, którą Ada Lovelace wykorzystała do obliczenia liczb Bernoulliego , jak opisano w uwadze G jej tłumaczenia szkicu silnika analitycznego wynalezionego przez Charlesa Babbage'a przez LF Menabreę . Menabrea zauważyła, że ​​silnik analityczny zapętla się wcześnie:

Rozumiejąc to, na początku serii operacji, które chcemy wykonać, umieść igłę C w dziale 2, igłę B w dziale 5 i igłę A w dziale 9. Pozwólmy uderzenie młotem z tarczy C; uderzy dwa razy, a jednocześnie igła B przejdzie przez dwie dywizje. Ten ostatni wskaże następnie liczbę 7, która zastępuje liczbę 5 w kolumnie pierwszych różnic. Jeśli pozwolimy teraz, aby młot tarczy B uderzył z kolei, uderzy siedem razy, podczas których igła A przesunie się o siedem podziałów; te dodane do dziewięciu już przez nią oznaczonych dadzą liczbę 16, która jest liczbą kwadratową z rzędu na 9. Jeśli teraz wznowimy te operacje, zaczynając od igły C, która zawsze musi pozostać na polu 2,

Mechanizm zapętlenia silnika analitycznego jest bezpośrednio odziedziczony z mechanicznego krosna Josepha Marie Jacquarda (1801), jak zauważono w pamiętniku Menabrei:

Zostanie teraz zapytane, w jaki sposób maszyna może sama z siebie, i bez uciekania się do ręki człowieka, przyjmuje kolejne dyspozycje odpowiednie do operacji. Rozwiązanie tego problemu zostało zaczerpnięte z aparatu żakardowego, stosowanego do produkcji wyrobów brokatowych, w następujący sposób:

Dwa gatunki nici są zwykle rozróżniane w tkaninach; jeden to wątek osnowy lub wątek podłużny, drugi wątek luźny lub poprzeczny, który jest przenoszony przez przyrząd zwany promem i który przecina wzdłużną nić lub osnowę. Gdy wymagany jest materiał brokatowy, konieczne jest z kolei zapobieganie przechodzeniu niektórych wątków przez wątek, a to zgodnie z kolejnością, która jest określona przez naturę projektu, który ma być odtworzony. Wcześniej proces ten był długi i trudny i wymagano, aby robotnik, dbając o projekt, który miał skopiować, sam regulował ruchy, które miały podjąć wątki. Stąd wynikła wysoka cena tego opisu rzeczy, zwłaszcza jeśli do tkaniny wprowadzono nici o różnych kolorach. Aby uprościć tę produkcję, Jacquard opracował plan połączenia każdej grupy wątków, które miały działać razem, z wyraźną dźwignią należącą wyłącznie do tej grupy. Wszystkie te dźwignie kończą się prętami, które są połączone razem w jeden pakiet, mający zwykle postać równoległościanu z prostokątną podstawą. Pręty są cylindryczne i są oddzielone od siebie małymi odstępami. Proces podnoszenia nici jest zatem rozdzielony na proces przesuwania tych różnych ramion dźwigni w wymaganej kolejności. Aby to zrobić, pobierany jest prostokątny arkusz tektury, nieco większy niż część wiązki ramion dźwigni. Jeśli arkusz ten zostanie nałożony na podstawę pakietu, a następnie ruch postępowy zostanie przekazany do stołu kartonowego, ten ostatni przesunie się wraz ze wszystkimi prętami pakietu, i w konsekwencji wątki, które są połączone z każdym z nich. Gdyby jednak deskowanie zamiast być gładkie, zostało przebite otworami odpowiadającymi końcom dźwigni, które się z nim spotykają, wówczas, ponieważ każda z dźwigni przejdzie przez karton podczas ruchu tego ostatniego, wszystkie pozostaną na swoim miejsca. Widzimy zatem, że łatwo jest ustalić położenie otworów w tekturowym pudełku, że w danym momencie będzie pewna liczba dźwigni, a w konsekwencji paczek wątków, podniesionych, podczas gdy reszta pozostanie tam, gdzie byli. Zakładając, że proces ten jest sukcesywnie powtarzany zgodnie z prawem wskazanym przez wzorzec, który ma zostać wykonany, widzimy, że wzorzec ten można odtworzyć na materiale. W tym celu musimy jedynie skomponować serię kart zgodnie z wymaganym prawem, i układaj je kolejno w odpowiedniej kolejności; następnie, powodując ich przejście przez wielokątną belkę, która jest tak połączona, że ​​obraca nową twarz dla każdego pociągnięcia promu, która to twarz zostanie następnie skierowana równolegle do siebie na wiązkę ramion dźwigni, operacja podniesienia wątki będą regularnie wykonywane. Widzimy zatem, że tkanki brokatowe mogą być wytwarzane z precyzją i szybkością wcześniej trudną do uzyskania.

Krosno żakardowe to bardzo wczesne zastosowanie pętli w kontekście zamawiania maszyny w celu uzyskania powtarzalnego wyniku :

Ideą krosna żakardowego był system kart dziurkaczy i haczyków. Karty były bardzo grube i miały w nich dziurki prostokątne. Haki i igły używane do tkania były prowadzone przez te otwory w tekturze. Gdy haki zetknęły się z kartą, były trzymane w miejscu, chyba że napotkały jeden z dziurkowanych otworów. Następnie hak mógł przejść przez otwór z igłą wprowadzającą inny nić, tworząc w ten sposób pożądany wzór. Skomplikowane wzory zostały osiągnięte poprzez wiele kart ułożonych jedna za drugą i / lub używanych wielokrotnie.

Krosno żakardowe jest również rozpoznawane jako bardzo wczesna forma przechowywanego programu :

Jeśli impet leżący u podstaw rozwoju maszyn liczących omówionych do tej pory wynikał z obliczeń numerycznych, motywacja, która doprowadziła do najwcześniejszej formy „przechowywanego programu”, miała pochodzić z zupełnie innego źródła: przemysłu tekstylnego. Wcześniej widzieliśmy, że jednym z podstawowych aspektów systemów obliczeniowych jest koncepcja reprezentowania informacji i chociaż nie zrobiliśmy tego wprost, zastosowanie tego pomysłu można dostrzec we wszystkich artefaktach, które zbadaliśmy do tej pory: w rozwoju pisemnych reprezentacji wartości liczbowych i wynikających z nich podobieństw mechanicznych. Tak więc wyrównanie kamyków na ramce liczydła, zestawienie ruchomych skal na suwakach i konfiguracja zębatych kół zębatych na urządzeniach Schickarda, Pascala i Leibniza, są wszystkie przykłady technik reprezentacyjnych, które mają na celu uproszczenie złożonych procesów leżących u podstaw zadań arytmetycznych. Istnieją jednak kategorie informacji i ich reprezentacje, inne niż liczba, na podstawie których można wykonać procesy obliczeniowe. Technologia tkania opracowana przez Josepha-Marie Jacquarda w 1801 r. Ilustruje jeden przykład takiej kategorii.

Charles Babbage dostosował również procedurę przechowywania Jacquarda do silnika analitycznego , obecność lub brak dziury przekazał maszynie proste polecenie włączenia / wyłączenia:

Silnik analityczny ma wiele podstawowych funkcji, które można znaleźć we współczesnym komputerze cyfrowym. Programowano go za pomocą kart perforowanych, pomysł zapożyczony z krosna żakardowego używanego do tkania skomplikowanych wzorów na tekstyliach. Silnik miał „magazyn”, w którym można było przechowywać liczby i wyniki pośrednie, oraz oddzielny „młyn”, w którym przeprowadzono przetwarzanie arytmetyczne. Miał wewnętrzny repertuar czterech funkcji arytmetycznych i mógł wykonywać bezpośrednie mnożenie i dzielenie. Był również zdolny do funkcji, dla których mamy współczesne nazwy: rozgałęzienie warunkowe, zapętlenie (iteracja), mikroprogramowanie, przetwarzanie równoległe, iteracja, zatrzaskiwanie, odpytywanie i kształtowanie pulsu, między innymi, chociaż Babbage nigdzie nie używał tych terminów. Miał różne wyjścia, w tym wydruk na papierze, karty dziurkowane,

Warunkowe gałęzie silnika analitycznego w połączeniu z inspirowanymi żakardem pętlami mechanicznymi i procedurą przechowywania są zniechęcająco podobne (koncepcyjnie) do twojego przykładu, szczególnie jeśli dodamy drukarkę Babbage'a do print "...";części.

Oczywiście mechaniczne pętle wyprzedzają krosno Jacquarda, pierwszym znanym urządzeniem działającym w pętli jest mechanizm Antikythera (100 p.n.e.), a jeśli spojrzymy jeszcze głębiej w historię (i odważnie zaryzykujemy), zegary słoneczne są prawdopodobnie najstarszymi mechanizmami stworzonymi przez człowieka gdzie zrozumienie pętli jest oczywiste, podążając oczywiście za powtarzającym się wzorem orbit Słońca i innych ciał gwiezdnych.

Myślę jednak, że w kontekście obliczeń (i nie obliczania ani niczego innego) silnik analityczny i algorytm obliczania liczb Auli Bernoulli można przypisać do wprowadzenia pętli, dzieląc przynajmniej część uznania z krosnem Jacquarda, bezpośrednio dostosowując koncepcję z to.

Yannis
źródło
3
Przed krosnem żakardowym można znaleźć mechaniczne pętle w carillonach, takich jak ta w Brugii, gdzie dzwony są kontrolowane przez obrót cylindra .
mouviciel
6
@mouviciel Widzę twój potworny dzwonek i podnoszę ci mechanizm Antikythera. ; P
yannis
2
+1 za encyklopedyczną odpowiedź, w tym 2000-letni komputer!
mouviciel
2
ta piękna odpowiedź sprawiła, że ​​lubiłem pytanie. Nie tylko odpowiada na pytanie, ale stanowi przykład „jak odpowiedzieć na pytanie”. Dobra robota, drogi panie.
Chani
Zaakceptowałem tę odpowiedź, ponieważ była zarówno rozstrzygająca, encyklopedyczna, jak i po prostu niesamowita!
Dynamiczny
50

Pętle przed obliczeniami. Można je znaleźć w notacji muzycznej już od chorału gregoriańskiego:

powtórz znak

mouviciel
źródło
2
To może być świetna odpowiedź, jeśli dodano do niej nieco więcej szczegółów. Mimo to świetna robota.
Dynamiczny
Podaj więcej referencji (najwcześniejsza data, najwcześniejsza notacja muzyczna zawierająca konstrukcje pętli / powtarzania)
Skippy Fastol,
@SkippyFastol Jest w tym artykule: en.wikipedia.org/wiki/Repeat_sign#Other_notation
cwallenpoole
32

Pojęcie „zrób to ponownie” jest w pewnym sensie „prymitywne” dla ludzkiej percepcji. Możesz to powiedzieć dziecku, które właśnie opracowało minimalne rozumienie języka naturalnego.

W systemach dyskretnych pętle znajdują się we wszystkich skończonych maszynach stanowych, gdy przyznajesz, że możesz osiągnąć stan, w którym byłeś wcześniej .

Najprostsza pętla to cykl między dwoma stanami (zegar). Biorąc pod uwagę, że z tej liczby może wynikać większa liczba stanów, każda bardziej złożona maszyna jest konstruowana na „liczniku” zwiększanym przez zegar, który może „przeskoczyć” na niektóre flagi reprezentujące pewne operacje kombinacyjne. Jest to rdzeń maszyny Von Neumann, na której opiera się każdy komputer oparty na mikroprocesorze.

W kodzie maszynowym kodowany jest skok JP-Z-nnnn(gdzie Z jest flagą whpfer, na której opierasz swój warunek). W języku wyższego poziomu przekłada się to niemal natychmiast

if(z) goto x;

Pętla jest niczym więcej niż miejscem, w gotoktórym etykieta x poprzedza samą instrukcję goto.

Każdy inny preparat (do, do, while, itd.) Jest po prostu „cukier syntaktyczny”, aby lepiej oswoić się z dziką goto w bardzo typowych przypadków powtarzania aż coś się dzieje

Emilio Garavaglia
źródło
4

Koncepcja zapętlenia jest jedną z rzeczy, które odróżniają pełnowymiarowy komputer od prostej maszyny obliczeniowej. Jeśli system nie obsługuje zapętlania, oznacza to, że nie jest on kompletny, a zatem nie jest komputerem.

Pierwszym kompletnym projektem Turinga był silnik analityczny Babbage'a , więc musiał mieć koncepcję zapętlenia. Istnieją jednak systemy, które mają pętlę, ale Turing nie jest kompletny (ponieważ pomijają coś innego). Praca Babbage'a jest jednak prawdopodobnie dobrym punktem wyjścia.

GordonM
źródło
6
Rachunek lambda nie ma pętli (i żadnych warunków ani skoków), ale jest kompletny. Rekurencja jest tak samo potężna jak iteracja.
3
możesz przepisać dowolną pętlę na funkcję rekurencyjną i wyeliminować pętle
maniak zapadkowy
5
Artykuł w Wikipedii na temat pętli opisuje rekurencję jako sposób wyrażenia pętli, a nie całkowicie niepowiązaną koncepcję. en.wikipedia.org/wiki/Program_loop#Loops Jeśli chodzi o procesory nieposiadające pętli, dysponują narzędziami niezbędnymi do ich wdrożenia (przeskakując na
dowolny
8
Dokładnie, rekurencja może być używana do wyrażania pętli. Jest to zupełnie inna koncepcja, mimo że są dla siebie izomorficzne. Kubek do kawy nie jest pączkiem tylko dlatego, że rzekomo mylą go topolodzy.
4
To prawda, ale każdy system z funkcją Turing musi mieć możliwość wyrażenia koncepcji wielokrotnego wykonywania tej samej sekwencji, mechanizmem może być rekurencja lub przeskakiwanie wstecz na liście instrukcji lub cokolwiek innego, co osiąga ten sam efekt. Jeśli system nie zapewnia żadnego sposobu na powtórzenie zestawu instrukcji (poza fizycznym powtórzeniem instrukcji z listy), nie może to być zakończenie Turinga. Silnik analityczny był całkowicie Turinga, więc musi implementować zapętlanie w takiej czy innej formie.
GordonM,
3

Zakładając, że masz na myśli współczesne tekstowe języki programowania komputerów.

Algol60 ma „FOR”, „DO”, „UNTIL” i „WHILE”, tak było przed 1960 rokiem.

Retro Computing Muzeum posiada kilka języków sprzed 1960.

Kvikkalkul , język z lat 50. do programowania szwedzkich okrętów nuklearnych ma tylko GOTO. (Jednak Kvikkalkul jest prawie na pewno mistyfikacją z lat 90., a nie prawdziwym językiem historycznym.)

Plankalkül Konrada Zuse jest najwcześniejszy, jaki udało mi się znaleźć. Ma konstrukcję „für”.

Chad Brewbaker
źródło
Plankalkül był zasadniczo niepublikowany do niedawna, a Kvikkalkul od dawna mówi się, że to mistyfikacja. W tym świetle pewnie należy się podziękować Johnowi Backusowi i zespołowi FORTRAN , który miał działający kompilator w terenie w 1957 r., Z DOpętlami.
Ross Patterson
2

Praca zarówno Liebniza, jak i Newtona zawiera algorytmy z konstruktami pętli. Liebniz zbudował kalkulator mechaniczny i spekulował (podobnie jak Lovelace lata później) o maszynie do wykonywania bardziej zaawansowanych analiz. Jego notatki na temat tych pomysłów są szkicowe, ale opisują uporządkowaną logikę za pomocą pętli.

Jednak idea powtarzania sekwencji i liczenia kontrolowanych pętli, a także to, co nazywamy pętlami, omawia się w pracy człowieka, dla którego algorytmy są nazwane: Muhammad ibn Musa al-Khwarizmi z IX wieku. Jego druga książka, al-Kitab al-mukhtasar fi hisab al-jabr wa'l-muqabala (الكتاب المختصر في حساب الجبر والمقابلة) (Kompendium na temat obliczania poprzez ukończenie i wyważenie) była znana Newtonowi, Liebnizowi, Babbage, Lovelace .

Oczywiście al-Khwarizmi polegał częściowo na starożytnych Grekach. W pewnym momencie prawdopodobnie wracamy do wersji płukania, piany, powtórzenia Adama i Ewy.

Więcej informacji na temat Al-Khwārizmī i jego pracy można znaleźć:

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

Chuck Herbert
źródło