PĘTLA (język programowania)

LOOP to prosty język rejestrów, który precyzyjnie oddaje prymitywne funkcje rekurencyjne . Język wywodzi się z modelu przeciw-maszyny . Podobnie jak liczniki, język LOOP zawiera zestaw jednego lub więcej nieograniczonych rejestrów , z których każdy może przechowywać jedną nieujemną liczbę całkowitą. Kilka instrukcji arytmetycznych (takich jak „ClearR”, „INCrement”, „DECrement”, „CoPY”, ...) działa na rejestrach. Jedyna przepływu sterowania to „ LOOP x DO … KONIEC' . Powoduje, że instrukcje w swoim zakresie są powtarzane x razy. (Zmiany zawartości rejestru x podczas wykonywania pętli nie wpływają na liczbę przebiegów.)

Historia

Język LOOP został sformułowany w artykule z 1967 roku przez Alberta R. Meyera i Dennisa M. Ritchiego . Pokazali zgodność między językiem LOOP a prymitywnymi funkcjami rekurencyjnymi .

Język ten był również tematem niepublikowanej rozprawy doktorskiej Ritchiego.

Zaprezentował go także Uwe Schöning wraz z GOTO i WHILE .

Filozofia projektowania i funkcje

W przeciwieństwie do programów GOTO i programów WHILE , programy LOOP zawsze kończą działanie . Dlatego zbiór funkcji obliczalnych przez programy LOOP jest właściwym podzbiorem funkcji obliczalnych (a zatem podzbiorem funkcji obliczalnych przez programy WHILE i GOTO).

Meyer i Ritchie udowodnili, że każda prymitywna funkcja rekurencyjna jest obliczalna metodą LOOP i odwrotnie.

Przykładem całkowitej obliczalnej funkcji, która nie jest obliczalna w LOOP, jest funkcja Ackermanna .

Definicja formalna

Składnia

Programy LOOP składają się z symboli LOOP , DO , END , := , + i ; jak również dowolną liczbę zmiennych i stałych. Programy LOOP mają następującą składnię w zmodyfikowanej formie Backusa – Naura :

Displaystyle {\ rozpocząć {tablica} {lrl} P &:: = & x_ {i}: = 0 \\&|& x_ {i}: = x_ {i} + 1\\&|&P;P\\&|&{\mathtt {LOOP}}\,x_{i}\,{\mathtt {DO}}\,P\,{\mathtt {END}}\end{ szyk}}}

Tutaj $x_ {1}, ... \}} są$ $są$ zmiennych i stałymi.

Semantyka

Jeśli P jest programem LOOP, P jest odpowiednikiem funkcji ${\ Displaystyle f: \ mathbb {N} ^ {k} \ rightarrow \ mathbb {N}}$ . Zmienne w programie LOOP odpowiadają argumentom funkcji ${\ displaystyle x_ {k}}$ ${1}}$ $x_$ do i są inicjowane przed wykonaniem programu odpowiednimi wartościami. Wszystkim pozostałym zmiennym nadawana jest wartość początkowa zero. Zmienna odpowiada wartości, którą przyjmuje po $podaniu$ wartości argumentów od $\$ $displaystyle x_ {1}}$ do ${k}}$ .

Oświadczenie o formie

 x _ja := 0

oznacza, że wartość zmiennej jest ustawiona na 0. ${\ displaystyle x_ {i}}$

Oświadczenie o formie

 x _ja := x _ja + 1

oznacza, że wartość zmiennej jest zwiększana o 1. ${\ displaystyle x_ {i}}$

Oświadczenie o formie

 P ₁ ;  P ₂

$displaystyle P_ {2}}$ sekwencyjne wykonywanie podprogramów i $\$ w tej kolejności

Oświadczenie o formie

   PĘTLA  x  DO  P  KONIEC

$wykonanie$ programu częściowego $ma$ razy , gdzie używana $jest$ wartość, którą na początku wykonywania instrukcji $,$ jeśli zmieni $się$ wartość nie wpłynie to na to, ile razy $wykonane$ pętli. Jeśli $to$ wartość zero, ${\ displaystyle P}$ nie jest wykonywany wewnątrz instrukcji LOOP . Pozwala to na rozgałęzienia w programach LOOP, gdzie warunkowe wykonanie częściowego programu zależy od tego, czy zmienna ma wartość zero, czy jeden.

Tworzenie „wygodnych instrukcji”

Z podstawowej składni tworzy się „wygodne instrukcje”. Nie będą to podprogramy w konwencjonalnym sensie, ale raczej programy LOOP utworzone z podstawowej składni i wyposażone w mnemonik. W sensie formalnym, aby korzystać z tych programów, należy albo (i) „rozszerzyć” je w kodzie – będą one wymagały użycia zmiennych tymczasowych lub „pomocniczych”, więc trzeba to wziąć pod uwagę, albo (ii) zaprojektować składnia z instrukcjami „wbudowanymi”.

Przykład

Funkcja projekcji k-ary $Displaystyle U_ {i} ^ {k} (x_ {1},$ wyodrębnia i-tą współrzędną z uporządkowanej k-krotki.

$swoim$ Ritchie przyjęli zadanie stwierdzenie Jak pokazuje przykład, przypisanie można wyprowadzić z listy podstawowych instrukcji.

Aby utworzyć instrukcję $,$ użyj poniższego bloku kodu. ${\ Displaystyle x_ {j}: = \ operatorname {przypisać} (x_ {i})}$ = _równoważne

 x _j := 0; PĘTLA x  _i DO x _j := x _j + 1 KONIEC

Ponownie, wszystko to jest tylko dla wygody; nic z tego nie zwiększa wewnętrznej mocy modelu.

Przykładowe programy

Dodatek

Dodawanie jest rekurencyjnie definiowane jako:

{\ Displaystyle {\ rozpocząć {wyrównane} a + 0 & = a, & {\ textrm {(1)}} \\ a + S (b) & = S (a + b). & {\ textrm { (2)}}\end{wyrównane}}}

Tutaj S należy czytać jako „następca”.

W sekwencji hiperoperatora jest to funkcja ${\ displaystyle \ operatorname {H_ {1}}}$

${\ Displaystyle \ nazwa operatora {H_ {1}} (x_ {1}, x_ {2})}$ mogą być realizowane przez program LOOP ADD ( x ₁ , x ₂ )

 ₀₀ ₀₀ PĘTLA  x ₁ DO  x  := x  + 1  KONIEC  ;  PĘTLA  x ₂ DO  x  := x  + 1  KONIEC

Mnożenie

Mnożenie jest funkcją hiperoperacji ${\ displaystyle \ operatorname {H_ {2}}}$

${\ Displaystyle \ operatorname {H_ {2}} (x_ {1}, x_ {2})}$ mogą być realizowane przez program LOOP MULT ( x ₁ , x ₂ )

₀ ₀₀ x  := 0;  PĘTLA  x ₂ DO  x  := DODAJ( x ₁ , x  )  KONIEC

Program wykorzystuje program ADD() jako „instrukcję wygodną”. Rozwinięty program MULT jest programem LOOP z dwoma zagnieżdżonymi instrukcjami LOOP. ADD liczy się za jeden.

Więcej hiperoperatorów

Mając program LOOP dla funkcji hiperoperacji , można skonstruować program LOOP dla następnego poziomu. ${\ displaystyle \ operatorname {H_ {i}}}}$

${\ Displaystyle \ operatorname {H_ {3}} (x_ {1}, x_ {2})}$ (co oznacza potęgowanie ) może być realizowane przez program LOOP POWER ( x ₁ , x ₂ )

₀ ₀₀ x  := 1;  LOOP  x ₂ DO  x  := MULT( x ₁ , x  )  KONIEC

Rozwinięty program do potęgowania ma trzy zagnieżdżone instrukcje LOOP.

Poprzednik

Funkcja poprzednika jest zdefiniowana jako

{\ Displaystyle \ operatorname {pred} (n) = {\ rozpocząć {przypadki} 0 & {\ mbox {jeśli}} n = 0, \\ n-1& {\mbox{inaczej}}\end{przypadki}}}

.

${\ displaystyle pred (x_ {1})$ można obliczyć za pomocą następującego programu LOOP, który ustawia zmienną na $)$ .

 ₀ /* warunek wstępny: x2 = 0 */  LOOP  x ₁ DO  x  := x ₂ ; x  ₂ := x ₂ + 1  KONIEC

Rozszerzony, to jest program

 ₀ ₀₀ /* warunek wstępny: x ₂ = 0 */  LOOP  x ₁ DO  x  := 0;  PĘTLA  x ₂ DO  x  := x  + 1  KONIEC  ; x  ₂ := x ₂ + 1  KONIEC

Ten program może być używany jako podprogram w innych programach LOOP. Składnię LOOP można rozszerzyć za pomocą następującej instrukcji, co jest równoznaczne z wywołaniem powyższej procedury jako podprogramu:

₀ x  := x ₁ ∸ 1

₀₀ Uwaga : Ponownie należy pamiętać o skutkach ubocznych. Poprzedni program zmienia zmienną x ₂ , która może być używana gdzie indziej. Aby rozwinąć instrukcję x := x ₁ ∸ 1, można zainicjalizować zmienne x _n , x _n+1 i x _n+2 (dla wystarczająco dużego n) odpowiednio na 0, x ₁ i 0, uruchomić na nich kod zmienne i skopiuj wynik (x _n ) do x . Kompilator może to zrobić.

Odejmowanie odcięte

₀ Jeśli w programie „dodawanie” nad drugą pętlą zmniejsza x zamiast zwiększać, program oblicza różnicę (odcięta na 0) zmiennych i ${\ displaystyle x_ {1}}$ i ${\ displaystyle x_ {2} }}$ .

₀
 ₀₀ x  := x ₁ PĘTLA  x ₂ DO  x  := x  ∸ 1  KONIEC

Podobnie jak poprzednio, możemy rozszerzyć składnię LOOP za pomocą instrukcji:

₀ x  := x ₁ ∸ x ₂

Jeśli to inaczej

Instrukcja if-then-else z if x ₁ > x ₂ then P1 else P2:

    x _n1 := x ₁ ∸ x ₂ ; x  _n2 := 0; x  _n3 := 1;  PĘTLA  x _n1 DO  x _n2 := 1; x  _n3 := 0  KONIEC  ;  PĘTLA  x _n2 DO  P1  KONIEC  ;  PĘTLA  x _n3 DO  P2  KONIEC  ;

Zobacz też

Uwagi i odniesienia

Bibliografia

Topór, Paweł (1966). „Iteracja względnej rekurencji pierwotnej”. Mathematische Annalen . 167 : 53–55. doi : 10.1007/BF01361215 . S2CID 119730846 .
Topór, Paweł (1970). „Iteracja pierwotnej rekurencji” . Dziennik logiki symbolicznej . 35 (3): 253–255. doi : 10.1002/malq.19650110310 .
Calude, Cristian (1988). Teorie złożoności obliczeniowej . Roczniki matematyki dyskretnej . Tom. 35. Wydawnictwo Północnej Holandii . ISBN 9780080867755 .
Czerniawski, Jan Karol (1976). „Proste programy realizują dokładnie formuły Presburgera” . SIAM Journal o informatyce . 5 (4): 666–677. doi : 10.1137/0205045 .
Czerniawski, Jan Karol; Kamin, Samuel Noe (1979). „Kompletna i spójna aksjomatyka Hoare'a dla prostego języka programowania”. Stowarzyszenie Maszyn Komputerowych . 26 (1): 119–128. doi : 10.1145/322108.322120 . S2CID 13062959 .
Constable, Robert L.; Borodin, Allan B (1972). „Podrekurencyjne języki programowania, część I: Wydajność i struktura programu”. Dziennik ACM . 19 (3): 526–568. doi : 10.1145/321707.321721 . S2CID 42474303 .
Crolard, Tristan; Lacas, Samuel; Valarcher, Pierre (2006). „O sile wyrazu języka pętli” . Nordic Journal of Computing . 13 : 46–57.
Crolard, Tristan; Polonowski, Emmanuel; Valarcher, Pierre (2009). „Rozszerzenie języka pętli o zmienne proceduralne wyższego rzędu” (PDF) . Transakcje ACM w logice obliczeniowej . 10 (4): 1–37. doi : 10.1145/1555746.1555750 . S2CID 1367078 .
Enderton, Herbert (2012). Teoria obliczalności . Prasa akademicka. doi : 10.1145/1555746.1555750 .
Fachini, Emanuela; Maggiolo-Schettini, Andrea (1979). „Hierarchia prymitywnych funkcji sekwencji rekurencyjnych” . RAIRO - Informatique Théorique - Informatyka teoretyczna . 13 (1): 49–67. doi : 10.1051/ita/1979130100491 .
Fachini, Emanuela; Maggiolo-Schettini, Andrea (1982). „Porównywanie hierarchii prymitywnych funkcji sekwencji rekurencyjnych”. Zeitschrift für mathematische Logik und Grundlagen der Mathematik . 28 (27–32): 431–445. doi : 10.1002/malq.19820282705 .
Goetze, Bernhard; Nehrlich, Werner (1980). „Struktura programów pętli i hierarchie podrekurencyjne” . Zeitschrift für mathematische Logik und Grundlagen der Mathematik . 26 (14-18): 255-278. doi : 10.1002/malq.19800261407 .
Ibarra, Oscar H.; Leininger, Brian S. (1981). „Charakterystyki funkcji Presburgera”. SIAM Journal o informatyce . 10 (1): 22–39. doi : 10.1137/0210003 .
Ibarra, Oscar H.; Rosier, Louis E. (1983). „Proste języki programowania i ograniczone klasy maszyn Turinga” . Informatyka teoretyczna . 26 (1–2): 197–220. doi : 10.1016/0304-3975(83)90085-3 .
Kfoury, AJ; Moll, Robert N.; Arbib, Michael A. (1982). Programistyczne podejście do obliczalności . Springer, Nowy Jork, NY. doi : 10.1007/978-1-4612-5749-3 . ISBN 978-1-4612-5751-6 .
Machtey, Michael (1972). „Języki z rozszerzoną pętlą i klasy funkcji obliczeniowych” . Journal of Computer and System Sciences . 6 (6): 603–624. doi : 10.1016/S0022-0000(72)80032-1 .
Planeta Matematyka. „prymitywna rekurencyjna funkcja o wartościach wektorowych” . Źródło 2021-08-21 .
Matos, Armando B. (2014-11-03). „Zamknięta forma prymitywnych funkcji rekurencyjnych: od programów imperatywnych, przez wyrażenia matematyczne, po programy funkcyjne” (PDF) . Źródło 2021-08-20 .
Matos, Armando B. (2015). „Efektywność prymitywnych funkcji rekurencyjnych: widok programisty” . Informatyka teoretyczna . 594 : 65–81. doi : 10.1016/j.tcs.2015.04.022 .
Meyer, Albert R .; Ritchie, Dennis MacAlistair (1967). Złożoność programów pętli . ACM '67: Materiały z 22. konferencji krajowej w 1967 r. doi : 10.1145/800196.806014 .
Minsky, Marvin Lee (1967). Obliczenia: maszyny skończone i nieskończone . Sala Prentice'a. doi : 10.1017/S0008439500029350 . S2CID 227917578 .
Ritchie, Dennis MacAlistair (1967). Struktura programu i złożoność obliczeniowa (wersja robocza) (PDF) .
Ritchie, Robert Wells (listopad 1965). „Klasy funkcji rekurencyjnych oparte na funkcji Ackermanna” . Pacific Journal of Mathematics . 15 (3): 1027–1044. doi : 10.2140/pjm.1965.15.1027 .
Schöning, Uwe (2001). Theoretische Informatik-kurz gefasst (4 wyd.). Londyn: Oxford University Press. ISBN 3-8274-1099-1 .
Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 wyd.). Londyn: Oxford University Press. ISBN 978-3-8274-1824-1 . DNB 986529222 .
Tsichritzis, Dennis C (1970). „Problem równoważności prostych programów”. Dziennik ACM . 17 (4): 729–738. doi : 10.1145/321607.321621 . S2CID 16066171 .
Tsichritzis, Dennis C (1971). „Uwaga na temat porównania hierarchii podrekurencyjnych”. Listy dotyczące przetwarzania informacji . 1 (2): 42–44. doi : 10.1016/0020-0190(71)90002-0 .

Linki zewnętrzne

Pętla, Goto i Podczas