LOOP (język programowania) - LOOP (programming language)

LOOP jest prostym językiem rejestru, który precyzyjnie wychwytuje prymitywne funkcje rekurencyjne . Język wywodzi się z modelu przeciw-maszyny . Podobnie jak liczniki, język LOOP zawiera zbiór jednego lub więcej nieograniczonych rejestrów , z których każdy może zawierać jedną nieujemną liczbę całkowitą. Kilka instrukcji arytmetycznych (takich jak 'Clear', 'INCrement', 'DECrement', 'CoPY', ...) działa na rejestrach. Jedyną instrukcją przepływu sterowania jest ' LOOP x DO ... END' . Powoduje to, że instrukcje w swoim zakresie są powtarzane x razy. (Zmiany zawartości rejestru x podczas wykonywania pętli nie wpływają na liczbę przejść.)

Historia

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

Język był także tematem niepublikowanej pracy doktorskiej Ritchiego.

Zaprezentował ją również 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ą się . Dlatego zbiór funkcji obliczanych przez programy LOOP jest właściwym podzbiorem funkcji obliczalnych (a zatem podzbiorem funkcji obliczalnych przez funkcje programu WHILE i GOTO).

Meyer i Ritchie udowodnili, że każda prymitywna funkcja rekurencyjna jest obliczalna w pętli i na odwrót.

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

Formalna definicja

Składnia

Pętlowych programów składa 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 postaci Backusa–Naura :

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

Tutaj są nazwy zmiennych i są stałymi. ${\displaystyle Var:=\{x_{0},x_{1},...\}}$${\ Displaystyle c \ w \ mathbb {N}}$

Semantyka

Jeśli P jest programem LOOP, P jest odpowiednikiem funkcji . Zmienne through w programie LOOP odpowiadają argumentom funkcji i są inicjowane przed wykonaniem programu z odpowiednimi wartościami. Wszystkie inne zmienne mają początkową wartość zero. Zmienna odpowiada wartości, która przyjmuje wartości argumentów od do . ${\ Displaystyle f: \ mathbb {N} ^ {k} \ rightarrow \ mathbb {N}}$${\displaystyle x_{1}}$${\displaystyle x_{k}}$${\displaystyle f}$${\displaystyle x_{0}}$${\displaystyle f}$${\displaystyle x_{1}}$${\displaystyle x_{k}}$

Oświadczenie o formie

xi := 0

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

Oświadczenie o formie

xi := xi + 1

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

Oświadczenie o formie

P1; P2

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

Oświadczenie o formie

LOOP x DO P END

oznacza powtarzające się wykonanie częściowego programu w sumie razy, gdzie używana jest wartość, która ma na początku wykonania instrukcji. Nawet jeśli zmieni wartość , nie wpłynie to na to, ile razy zostanie wykonane w pętli. Jeśli ma wartość zero, to nie jest wykonywane 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. ${\displaystyle P}$${\displaystyle x}$${\displaystyle x}$${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$

Tworzenie „dogodnych instrukcji”

Z podstawowej składni tworzymy „wygodne instrukcje”. Nie będą to podprogramy w konwencjonalnym znaczeniu, ale raczej programy typu LOOP utworzone z podstawowej składni i opatrzone mnemonikiem. W sensie formalnym, aby korzystać z tych programów, należy albo (i) „rozszerzyć” je do kodu – będą 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 wyodrębnia i-tą współrzędną z uporządkowanej k-krotki. ${\ Displaystyle U_ {i} ^ {k} (x_ {1}, ..., x_ {i}, ..., x_ {k}) = x_ {i}}$

W swoim przełomowym artykule Meyer i Ritchie uczynili zadanie podstawowym stwierdzeniem. Jak pokazuje przykład, przypisanie można wyprowadzić z listy podstawowych stwierdzeń. ${\ Displaystyle x_ {j}: = x_ {i}}$

Aby utworzyć instrukcję, użyj poniższego bloku kodu. Zwróć uwagę na użycie powyższej wskazówki: ${\displaystyle \operatorname {przypisać}}$

${\ Displaystyle x_ {j}: = \ nazwa operatora {przypisać} (x_ {i})}$= _ekwiwalent

xj := 0;
LOOP xi DO
  xj := xj + 1
END

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 {\ zacząć {wyrównany} a + 0 i = a {\ textrm {(1)}} \ \ a + S (b) i = S (a + b). & {\ textrm {(2) }}\end{wyrównany}}}$

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

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

${\ Displaystyle \ operatorname {H_ {1}} (x_ {1}, x_ {2})}$może być zaimplementowany przez program LOOP ADD( x ₁ , x ₂ )

LOOP x1 DO
  x0 := x0 + 1
END;
LOOP x2 DO
  x0 := x0 + 1
END

Mnożenie

Mnożenie to funkcja hiperoperacji ${\displaystyle \operatorname {H_{2}}}$

${\ Displaystyle \ Operatorname {H_ {2}} (x_ {1}, x_ {2})}$może być realizowany przez program LOOP MULT( x ₁ , x ₂ )

x0 := 0;
LOOP x2 DO
  x0 := ADD( x1, x0)
END

Program używa programu ADD() jako "instrukcji wygodnej". Rozszerzony program MULT jest programem LOOP z dwoma zagnieżdżonymi instrukcjami LOOP. DODAJ 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})}$na przykład (co oznacza potęgowanie ) można zaimplementować za pomocą programu LOOP POWER( x ₁ , x ₂ )

x0 := 1;
LOOP x2 DO
  x0 := MULT( x1, x0 )
END

Rozszerzony program potęgowania ma trzy zagnieżdżone instrukcje LOOP.

Poprzednik

Poprzednia funkcja jest zdefiniowana jako

${\ Displaystyle \ operatorname {pred} (n) = {\ zacząć {przypadki} 0 i {\ mbox {jeśli}} n = 0, \ \ n-1 i {\ mbox {inaczej}} \ koniec {przypadki}}}$.

Ta funkcja może być obliczona przez następujący program LOOP, który ustawia zmienną na . ${\displaystyle x_{0}}$${\displaystyle pred(x_{1})}$

/* precondition: x2 = 0 */
LOOP x1 DO
  x0 := x2;
  x2 := x2 + 1
END

Rozszerzony, to jest program

/* precondition: x2 = 0 */
LOOP x1 DO
  x0 := 0;
  LOOP x2 DO
    x0 := x0 + 1
  END;
  x2 := x2 + 1
END

Ten program może być używany jako podprogram w innych programach LOOP. Składnia LOOP może być rozszerzona o następującą instrukcję, równoważną wywołaniu powyższego jako podprogramu:

x0 := x1 ∸ 1

Uwaga : Znowu trzeba pamiętać o efektach 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, uruchom kod na te zmienne i skopiuj wynik (x _n ) do x ₀ . Kompilator może to zrobić.

Odejmowanie odcięcia

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

x0 := x1
LOOP x2 DO
  x0 := x0 ∸ 1
END

Tak jak wcześniej możemy rozszerzyć składnię LOOP o instrukcję:

x0 := x1 ∸ x2

Jeśli to inaczej

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

xn1 := x1 ∸ x2;
xn2 := 0;
xn3 := 1;
LOOP xn1 DO
  xn2 := 1;
  xn3 := 0
END;
LOOP xn2 DO
  P1
END;
LOOP xn3 DO
  P2
END;

Zobacz też

• funkcja rekurencyjna μ
• prymitywna funkcja rekurencyjna
• BlooP i FlooP

Uwagi i referencje

Bibliografia

Zewnętrzne linki

• Pętla, Goto & While