LOOP (programozási nyelv) - LOOP (programming language)

A LOOP egy egyszerű regiszternyelv, amely pontosan rögzíti a primitív rekurzív függvényeket . A nyelv a számlálógép modellből származik . A számlálógépekhez hasonlóan a LOOP nyelv egy vagy több korlátlan regisztert tartalmaz , amelyek mindegyike egyetlen nem negatív egész számot tartalmazhat. Néhány aritmetikai utasítás (például „CleaR”, „INCrement”, „DECrement”, „CoPY”, ...) működik a regisztereken. Az egyetlen vezérlési folyamat utasítás ' LOOP x DO ... END' . Ez azt eredményezi, hogy a hatókörébe tartozó utasításokat x -szer megismétlik. (Az x regiszter tartalmának a ciklus végrehajtása során bekövetkezett változásai nem befolyásolják az áthaladások számát.)

Történelem

A LOOP nyelvet 1967 -ben Albert R. Meyer és Dennis M. Ritchie fogalmazta meg . Megmutatták a LOOP nyelv és a primitív rekurzív függvények közötti megfelelést .

Ez a nyelv volt a témája Ritchie kiadatlan PhD dolgozatának.

Uwe Schöning is bemutatta , a GOTO és a WHILE mellett .

Tervezési filozófia és funkciók

A GOTO programokkal és a WHILE programokkal ellentétben a LOOP programok mindig leállnak . Ezért a LOOP programok által kiszámítható függvényhalmaz a számítható függvények megfelelő részhalmaza (és így a WHILE és GOTO programfüggvények által kiszámítható részhalmaz).

Meyer & Ritchie bebizonyította, hogy minden primitív rekurzív függvény LOOP-kalkulálható és fordítva.

Példa egy teljes számítható függvényre, amely nem LOOP számítható, az Ackermann függvény .

Formális meghatározás

Szintaxis

Loop-programok állnak a szimbólumokat LOOP, DO, END, :=, +és ;, valamint tetszőleges számú változók és konstansok. A LOOP programok a következő szintaxissal rendelkeznek módosított Backus – Naur formában :

${\ 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 {tömb}}}$

Itt vannak változónevek és konstansok. ${\ displaystyle Var: = \ {x_ {0}, x_ {1}, ... \}}$${\ displaystyle c \ in \ mathbb {N}}$

Szemantika

Ha P LOOP program, akkor P egy függvénynek felel meg . A változók segítségével a hurok Program megfelel az érveket a funkciót , és inicializálása előtt a program végrehajtása a megfelelő értékeket. Minden más változó nulla kezdeti értéket kap. A változó annak az értéknek felel meg, amely az argumentumértékek megadásától kezdve történik . ${\ 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}}$

Az űrlap nyilatkozata

xi := 0

azt jelenti, hogy a változó értéke 0 -ra van állítva. ${\ displaystyle x_ {i}}$

Az űrlap nyilatkozata

xi := xi + 1

azt jelenti, hogy a változó értéke 1 -gyel növekszik. ${\ displaystyle x_ {i}}$

Az űrlap nyilatkozata

P1; P2

képviseli a szekvenciális végrehajtását alprogramok és , ebben a sorrendben. ${\ displaystyle P_ {1}}$${\ displaystyle P_ {2}}$

Az űrlap nyilatkozata

LOOP x DO P END

a részprogram ismételt végrehajtását jelenti, összesen , ahol az utasítás végrehajtásának elején lévő értéket használjuk. Még ha megváltoztatja is a értékét , ez nem befolyásolja, hogy hányszor hajtódik végre a ciklusban. Ha értéke nulla, akkor nem hajtódik végre a LOOP utasításban. Ez lehetővé teszi az elágazásokat a LOOP programokban, ahol a részleges program feltételes végrehajtása attól függ, hogy egy változó értéke nulla vagy egy. ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle P}$

"Kényelmi utasítások" létrehozása

Az alap szintaxisból hozzon létre "kényelmi utasításokat". Ezek nem hagyományos értelemben vett szubrutinok, hanem az alap szintaxisból létrehozott és mnemonikus LOOP programok. Formai értelemben ezeknek a programoknak a használatához vagy (i) "ki kell terjeszteni" őket a kódba - ideiglenes vagy "segéd" változók használatát kell megkövetelniük, ezért ezt figyelembe kell venni, vagy (ii) meg kell tervezni a szintaxis a „beépített” utasításokkal.

Példa

A k-ary vetítési függvény kivonja az i-edik koordinátát egy rendezett k-sorból. ${\ displaystyle U_ {i}^{k} (x_ {1}, ..., x_ {i}, ..., x_ {k}) = x_ {i}}$

Meyer & Ritchie alapdokumentumukban alapvető kijelentéssé tették a feladatot . Ahogy a példa is mutatja, a hozzárendelés az alapvető állítások listájából származtatható. ${\ displaystyle x_ {j}: = x_ {i}}$

Az utasítás létrehozásához használja az alábbi kódblokkot. Figyelje meg a fent említett tipp használatát: ${\ displaystyle \ operatornév {hozzárendelés}}$

${\ displaystyle x_ {j}: = \ operatornév {hozzárendelés} (x_ {i})}$= _ekv

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

Mindez megint csak a kényelem kedvéért; ezek egyike sem növeli a modell belső erejét.

Példa programok

Kiegészítés

Amellett van rekurzívan definiáljuk:

${\ displaystyle {\ begin {aligned} a+0 & = a, & {\ textrm {(1)}} \\ a+S (b) & = S (a+b). & {\ textrm {(2) }} \ end {aligned}}}$

Itt S -t "utódként" kell értelmezni.

A hiperoperatív szekvenciában ez a függvény${\ displaystyle \ operatornév {H_ {1}}}$

${\ displaystyle \ operatornév {H_ {1}} (x_ {1}, x_ {2})}$az ADD LOOP programmal valósítható meg (x ₁ , x ₂ )

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

Szorzás

A szorzás a hiperműveleti függvény ${\ displaystyle \ operatornév {H_ {2}}}$

${\ displaystyle \ operatornév {H_ {2}} (x_ {1}, x_ {2})}$a MULT LOOP programmal valósítható meg (x ₁ , x ₂ )

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

A program az ADD () programot használja "kényelmi utasításként". Bővítve a MULT program egy LOOP program, két beágyazott LOOP utasítással. Az ADD egynek számít.

Több hiperoperátor

Ha egy hiperoperációs funkcióhoz LOOP programot adunk , akkor LOOP programot készíthetünk a következő szintre ${\ displaystyle \ operatornév {H_ {i}}}$

${\ displaystyle \ operatornév {H_ {3}} (x_ {1}, x_ {2})}$például (ami a hatványozást jelenti ) a LOOP POWER (x ₁ , x ₂ ) programmal valósítható meg

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

A kiterjesztett hatványozó program három egymásba ágyazott LOOP utasítást tartalmaz.

Előző

Az előd funkciót úgy definiáljuk

${\ displaystyle \ operatornév {pred} (n) = {\ begin {case} 0 & {\ mbox {if}} n = 0, \\ n-1 & {\ mbox {egyébként}} \ end {case}}}$.

Ezt a függvényt a következő LOOP program számíthatja ki, amely a változót erre állítja . ${\ displaystyle x_ {0}}$${\ displaystyle pred (x_ {1})}$

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

Bővítve, ez a program

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

Ez a program alprogramként használható más LOOP programokban. A LOOP szintaxis a következő utasítással bővíthető, ami megegyezik a fentiek alprogramként való meghívásával:

x0 := x1 ∸ 1

Megjegyzés : Ismét figyelembe kell venni a mellékhatásokat. Az elődprogram megváltoztatja az x ₂ változót , amely máshol is használatban lehet. Bővíteni a nyilatkozatot x ₀  : = x ₁ ∸ 1, lehetett inicializálni az x _n , x _{n + 1} , és x _{n + 2} (egy elég nagy n) 0, x ₁ és 0, illetve, futtatja a kódot ezeket a változókat, és másolja az eredményt (x _n ) x _{0 -ba} . Ezt egy fordító is megteheti.

Kivágás levonása

Ha a második ciklus feletti „összeadás” programban a növekmény helyett x ₀ -ra csökken , akkor a program kiszámítja a változók ( és 0 -nál levágott) különbségét és . ${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$

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

Mint korábban, a LOOP szintaxist kibővíthetjük a következő kijelentéssel:

x0 := x1 ∸ x2

Ha máskor

If-then-else utasítás, ha x ₁ > x _2, majd 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;

Lásd még

• μ-rekurzív függvény
• primitív rekurzív funkció
• BlooP és FlooP

Jegyzetek és hivatkozások

Bibliográfia

Külső linkek

• Loop, Goto & While