LOOP (programovací jazyk) - LOOP (programming language) - Wikipedia

SMYČKA je jazyk, který přesně zachycuje primitivní rekurzivní funkce.^[1]Jediné operace podporované v jazyce jsou přiřazení, přidání a opakování několikrát, které jsou opraveny před spuštěním provádění smyčky.

Jazyk LOOP byl představen v článku z roku 1967 autorem Albert R. Meyer a Dennis M. Ritchie. ^[2]Meyer a Ritchie ukázali shodu mezi jazykem LOOP a primitivní rekurzivní funkce.

Dennis M. Ritchie formuloval jazyk LOOP, který byl také tématem jeho nepublikovaného Ph.D. teze.^[3]^[4]

To bylo také předloženo Uwe Schöning, spolu s JÍT DO a ZATÍMCO.^[5]

Funkce

Každý primitivní rekurzivní funkce je LOOP-vypočítatelný a naopak.^[6]

Na rozdíl od JÍT DO programy a ZATÍMCO programy, LOOP programy vždy vypovědět.^[7] Proto je sada funkcí vypočítatelných programy LOOP správnou podmnožinou vypočítatelné funkce (a tedy podmnožina vypočítatelná programovými funkcemi WHILE a GOTO).^[8]

Příkladem celkové vypočítatelné funkce, kterou nelze vypočítat pomocí LOOP, je Ackermannova funkce.^[9]

Formální definice

Syntax

Programy LOOP se skládají ze symbolů SMYČKA, DĚLAT, KONEC, :=, +, - a ; stejně jako libovolný počet proměnných a konstant. Programy LOOP mají následující syntax v upraveném Backus – Naurova forma:

{ displaystyle { begin {array} {lrl} P & :: = & x_ {i}: = 0 & | & x_ {i}: = x_ {i} +1 & | & P; P & | & { mathtt {LOOP}} , x_ {i} , { mathtt {DO}} , P , { mathtt {END}} end {pole}}}

Tady, ${ displaystyle Var: = {x_ {0}, x_ {1}, ... }}$ jsou názvy proměnných a ${ displaystyle c in mathbb {N}}$ jsou konstanty.

Sémantika

Li P je program LOOP, P je ekvivalentní funkci ${ displaystyle f: mathbb {N} ^ {k} rightarrow mathbb {N}}$ . Proměnné ${ displaystyle x_ {1}}$ přes ${ displaystyle x_ {k}}$ v programu LOOP odpovídají argumentům funkce ${ displaystyle f}$ a jsou inicializovány před spuštěním programu s příslušnými hodnotami. Všechny ostatní proměnné mají počáteční hodnotu nula. Proměnná ${ displaystyle x_ {0}}$ odpovídá hodnotě, která ${ displaystyle f}$ bere při zadání hodnot argumentů z ${ displaystyle x_ {1}}$ přes ${ displaystyle x_ {k}}$ .

Prohlášení o formuláři

X_i := 0

znamená hodnotu proměnné ${ displaystyle x_ {i}}$ je nastavena na 0.

Prohlášení o formuláři

X_i : = x_i + 1

znamená hodnotu proměnné ${ displaystyle x_ {i}}$ je zvýšen o 1.

Prohlášení o formuláři

P₁; P₂

představuje postupné provádění podprogramů ${ displaystyle P_ {1}}$ a ${ displaystyle P_ {2}}$ v tomto pořadí.

Prohlášení o formuláři

LOOP x DO P KONEC

znamená opakované provádění dílčího programu ${ displaystyle P}$ celkem ${ displaystyle x}$ krát, kde hodnota, která ${ displaystyle x}$ má na začátku provádění příkazu použito. I kdyby ${ displaystyle P}$ změní hodnotu ${ displaystyle x}$ , neovlivní to, kolikrát ${ displaystyle P}$ se provádí ve smyčce. Li ${ displaystyle x}$ má tedy hodnotu nula ${ displaystyle P}$ není proveden uvnitř SMYČKA prohlášení. To umožňuje větve v programech LOOP, kde podmíněné provedení částečného programu závisí na tom, zda má proměnná hodnotu nula nebo jedna.

Ukázkové programy

Úkol

Následující program LOOP přiřadí hodnotu proměnné x_i do proměnné x_j.

X_j : = 0; LOOP x_i DO x_j : = x_j + 1END

Ve své seminární práci ^[10] Meyer a Ritchie zadali úkol ${ displaystyle x_ {j}: = x_ {i}}$ základní prohlášení. Jak ukazuje výše uvedený program, přiřazení je nadbytečné a lze jej odebrat ze seznamu základních příkazů. Může být použit jako podprogram v jiných programech LOOP. Syntaxi LOOP lze rozšířit pomocí následujícího příkazu, který odpovídá volání výše uvedeného jako podprogramu:

X_j : = x_i

Poznámka: Je třeba mít na paměti, že všechny proměnné jsou globální. Že nové tvrzení je ekvivalentní podprogramu to neznamená, že je podprogram. Normálně aktivační záznam brání všem vedlejším účinkům. V tomto případě však žádná jiná proměnná kromě x_j je ovlivněn, takže nedochází k vedlejším účinkům za předpokladu, že x_j, které v tomto okamžiku při provádění programu mohou obsahovat nenulovou hodnotu, je inicializováno na 0.

Projekce

Zvláštní případ přiřazovacího programu je program (používáme rozšířenou notaci):

X₀ : = x_i

Tento program počítá funkci k-aryho projekce ${ displaystyle U_ {i} ^ {k} (x_ {1}, ..., x_ {i}, ..., x_ {k}) = x_ {i}}$ , který extrahuje i-tu souřadnici z objednané k-n-tice.

Předchůdce

Funkce předchůdce je definována jako

{ displaystyle operatorname {pred} (n) = { začátek {případů} 0 & { mbox {if}} n = 0, n-1 & { mbox {jinak}} konec {případů}}}

.

Tuto funkci lze vypočítat následujícím programem LOOP, který nastavuje proměnnou ${ displaystyle x_ {0}}$ na ${ displaystyle pred (x_ {1})}$ .

/ * předpoklad: x₂ = 0 * / LOOP x₁ DO x₀ : = 0; LOOP x₂ DO x₀ : = x₀ + 1 KONEC; X₂ : = x₂ + 1END

Tento program lze použít jako podprogram v jiných programech LOOP. Syntaxi LOOP lze rozšířit pomocí následujícího příkazu, který odpovídá volání výše uvedeného jako podprogramu:

X₀ : = x₁ ∸ 1

Poznámka: Opět je třeba si uvědomit vedlejší účinky. Program předchůdce mění proměnnou x₂, které by se mohly používat jinde. Chcete-li rozšířit příkaz x₀ : = x₁ ∸ 1, lze inicializovat proměnné x_n, X_{n + 1} a x_{n + 2} (pro dostatečně velké n) na 0, x₁ a 0, spustit kód na těchto proměnných a zkopírovat výsledek (x_n) až x₀. Kompilátor to může udělat.

Přidání

V následujícím programu proměnná ${ displaystyle x_ {0}}$ je nastaven na součet proměnných ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$ .

LOOP x₁ DO x₀ : = x₀ + 1END; LOOP x₂ DO x₀ : = x₀ + 1END

Tento program lze použít jako podprogram v jiných programech LOOP. Syntaxi LOOP lze rozšířit pomocí následujícího příkazu, který odpovídá volání výše uvedeného jako podprogramu:

X₀ : = x₁ + x₂

Mezní odčítání

Pokud je v programu „sčítání“ nad druhou smyčkou decrement x₀ namísto přírůstku program vypočítá rozdíl (odříznutý v 0) proměnných ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$ .

X₀ : = x₁LOOP x₂ DO x₀ : = x₀ ∸ 1END

Stejně jako dříve můžeme rozšířit syntaxi LOOP pomocí příkazu:

X₀ : = x₁ ∸ x₂

Násobení

Následující program LOOP nastavuje hodnotu proměnné ${ displaystyle x_ {0}}$ k součinu proměnných ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$ .

LOOP x₁ DO x₀ : = x₀ + x₂KONEC

Tento multiplikační program používá syntaxi zavedenou podprogramem přidání z předchozího příkladu. Násobení se zde provádí přidáním hodnoty ${ displaystyle x_ {2}}$ celkem ${ displaystyle x_ {1}}$ časy ukládání výsledků do ${ displaystyle x_ {0}}$ .

Jestliže pak jinak

Příkaz if-then-else s if x₁ > x₂ pak P1 else P2:

X_n1 : = x₁ ∸ x₂;X_n2 : = 0; x_n3 : = 1; LOOP x_n1 DO x_n2 : = 1; X_n3 : = 0END; LOOP x_n2 DO P1END; LOOP x_n3 DO P2END;

Viz také

Poznámky a odkazy

^ Herbert Enderton (2012). Teorie vypočítatelnosti. Akademický tisk.
^ Meyer, Albert R.; Ritchie, Dennis M. (1967). Složitost smyčkových programů. ACM '67: Sborník příspěvků z 22. národní konference v roce 1967. doi:10.1145/800196.806014.
^ „Objevování ztracené disertační práce Dennise Ritchieho“. CHM. 2020-06-19. Citováno 2020-07-14.
^ "Struktura programu a návrh výpočetní složitosti | 102790971 | Muzeum počítačové historie". www.computerhistory.org. Citováno 2020-07-14.
^ Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 105. ISBN 978-3-8274-1824-1. DNB 986529222.
^ Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 105. ISBN 978-3-8274-1824-1. DNB 986529222.
^ Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 93. ISBN 978-3-8274-1824-1. DNB 986529222.
^ Schöning, Uwe (2001). Theoretische Informatik-kurz gefasst (4. vyd.). London: Oxford University Press. str. 122. ISBN 3-8274-1099-1.
^ Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 112. ISBN 978-3-8274-1824-1. DNB 986529222.
^ Meyer & Ritchie: Složitost smyčkových programů, ACM 1967

externí odkazy

Loop, Goto & While

[1] Herbert Enderton (2012). Teorie vypočítatelnosti. Akademický tisk.

[2] Meyer, Albert R.; Ritchie, Dennis M. (1967). Složitost smyčkových programů. ACM '67: Sborník příspěvků z 22. národní konference v roce 1967. doi:10.1145/800196.806014.

[3] „Objevování ztracené disertační práce Dennise Ritchieho“. CHM. 2020-06-19. Citováno 2020-07-14.

[4] "Struktura programu a návrh výpočetní složitosti | 102790971 | Muzeum počítačové historie". www.computerhistory.org. Citováno 2020-07-14.

[5] Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 105. ISBN 978-3-8274-1824-1. DNB 986529222.

[6] Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 105. ISBN 978-3-8274-1824-1. DNB 986529222.

[7] Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 93. ISBN 978-3-8274-1824-1. DNB 986529222.

[8] Schöning, Uwe (2001). Theoretische Informatik-kurz gefasst (4. vyd.). London: Oxford University Press. str. 122. ISBN 3-8274-1099-1.

[9] Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. str. 112. ISBN 978-3-8274-1824-1. DNB 986529222.

[10] Meyer & Ritchie: Složitost smyčkových programů, ACM 1967

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]