LOOP（プログラミング言語）

LOOPは、原始的な再帰関数を正確に表現するシンプルなレジスタ言語です。^[1] この言語は、カウンタマシンモデルから派生したものです。カウンタマシンと同様に、 LOOP言語は、それぞれが1つの非負の整数を保持できる1つ以上の無制限のレジスタのセットで構成されています。いくつかの算術命令（「CleaR」、「INCrement」、「DECrement」、「CoPY」など）は、レジスタに対して動作します。唯一の制御フロー命令は、「LOOP x DO ... END」です。これにより、そのスコープ内の命令がx回繰り返されます。（ループの実行中にレジスタxの内容が変更されても、パスの回数には影響しません。）

LOOP言語は1967年の論文でAlbert R. MeyerとDennis M. Ritchieによって定式化されました。^[2] 彼らはLOOP言語と基本的な再帰関数との対応を示しました。

この言語はリッチーの未発表の博士論文のテーマでもあった。^{[3] [4]}

これは、 GOTOやWHILEとともにUwe Schöningによっても発表された。^[5]

GOTOプログラムやWHILEプログラムとは対照的に、LOOPプログラムは常に終了します。^[6]したがって、LOOPプログラムで計算可能な関数の集合は、計算可能な関数の適切な部分集合です（したがって、WHILEおよびGOTOプログラム関数で計算可能な関数の部分集合です）。^[7]

マイヤーとリッチーは、各原始再帰関数はループ計算可能であり、その逆も成り立つことを証明した。^{[2] [5]}

LOOP計算可能ではない全計算可能関数の例としては、アッカーマン関数がある。^[8]

LOOPLOOP プログラムは、記号DO、 、END、:=、+と、;任意の数の変数と定数で構成されます。LOOP プログラムは、修正バッカスナウア形式で次の構文を持ちます。

${\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{array}}}$

ここで、は変数名であり、は定数です。 ${\displaystyle Var:=\{x_{0},x_{1},...\}}$${\displaystyle c\in \mathbb {N} }$

Pが LOOP プログラムの場合、P は関数 と同等です。LOOP プログラム内の変数からは関数 の引数に対応し、プログラム実行前に適切な値で初期化されます。他のすべての変数には初期値 0 が与えられます。変数 は、からの引数値が与えられたときに が取る値に対応します。 ${\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}}$

次のような形式の声明

x i  := 0

変数の値が 0 に設定されていることを意味します。 ${\displaystyle x_{i}}$

次のような形式の声明

x i  := x i + 1

変数の値が 1 増加することを意味します。 ${\displaystyle x_{i}}$

次のような形式の声明

1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ;8 ;9 ;10 ;11 ;12 ;13 ;14 ;15 ;16 ;17 ;18 ;19 ;20 ;21 ;22 ;23 ;24 ;25 ; 26 ;27 ;28 ;30 ; 31 ;32 ;33 ;3

サブプログラムとをこの順序で順次実行することを表します。 ${\displaystyle P_{1}}$${\displaystyle P_{2}}$

次のような形式の声明

ループx終了 ​ ​

は、部分プログラムを合計 回繰り返し実行することを意味し、ステートメントの実行開始時の の値が使用されます。の値が変わっても、ループ内で が実行される回数には影響しません。 の値が 0 の場合、 はLOOPステートメント内で実行されません。これにより、変数の値が 0 か 1 かによって部分プログラムの条件付き実行が決まる LOOP プログラムでの 分岐が可能になります。${\displaystyle P}$${\displaystyle x}$${\displaystyle x}$${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$

基本構文から「便利な命令」を作成します。これらは従来の意味でのサブルーチンではなく、基本構文から作成され、ニーモニックが与えられた LOOP プログラムです。正式な意味では、これらのプログラムを使用するには、(i) コードに「展開」する必要があります。一時変数または「補助」変数の使用が必要になるため、これを考慮する必要があります。または、(ii) 命令を「組み込んだ」構文を設計する必要があります。

例

k 進射影関数は、順序付けられた k タプルから i 番目の座標を抽出します。 ${\displaystyle U_{i}^{k}(x_{1},...,x_{i},...,x_{k})=x_{i}}$

^{マイヤーとリッチーは、彼らの画期的な論文[2]}で、割り当てを基本ステートメントにしました。例が示すように、割り当ては基本ステートメントのリストから導き出すことができます。 ${\displaystyle x_{j}:=x_{i}}$

命令を作成するには、以下のコードブロックを使用します。 = _equiv${\displaystyle \operatorname {assign} }$${\displaystyle x_{j}:=\operatorname {assign} (x_{i})}$

xj  := 0 ;ループ
× iDO
  xj  := xj + 1です
終わり

繰り返しますが、これらはすべて便宜上のものであり、モデルの本質的な力を高めるものではありません。

加算は再帰的に次のように定義されます。

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

ここで、S は「後継者」と読みます。

ハイパー演算子シーケンスでは、関数${\displaystyle \operatorname {H_{1}} }$

${\displaystyle \operatorname {H_{1}} (x_{1},x_{2})}$_{ループプログラムADD( x 1} , x ₂ ) で実装できる。

ループx 1  DO 
  x 0  := x 0 + 1
 END ;
ループx 2  DO 
  x 0  := x 0 + 1
 END

掛け算は超演算関数である ${\displaystyle \operatorname {H_{2}} }$

${\displaystyle \operatorname {H_{2}} (x_{1},x_{2})}$_{ループプログラムMULT( x 1} , x ₂ ) で実装できる。

x 0  := 0;
ループx 2  DO 
  x 0  := ADD( x 1 , x 0 )
終了

このプログラムは、ADD() プログラムを「便利な命令」として使用します。拡張すると、MULT プログラムは 2 つのネストされた LOOP 命令を持つ LOOP プログラムになります。ADD は 1 つとしてカウントされます。

ハイパーオペレーション関数 のLOOPプログラムが与えられた場合、次のレベルのLOOPプログラムを構築することができる。 ${\displaystyle \operatorname {H_{i}} }$

${\displaystyle \operatorname {H_{3}} (x_{1},x_{2})}$例えば、 （指数を表す）は、LOOPプログラムPOWER( x ₁ , x ₂ ) によって実装できる。

x 0  := 1;
ループx 2  DO 
  x 0  := MULT( x 1 , x 0 )
終了

拡張された指数計算プログラムには、3 つのネストされた LOOP 命令があります。

先行関数は次のように定義される。

${\displaystyle \operatorname {pred} (n)={\begin{cases}0&{\mbox{if }}n=0,\\n-1&{\mbox{otherwise}}\end{cases}}}$。

この関数は、変数を に設定する次の LOOP プログラムによって計算できます。 ${\displaystyle x_{0}}$${\displaystyle pred(x_{1})}$

/* 前提条件: x2 = 0 */ 
LOOP x 1  DO 
  x 0  := x 2 ;
  x 2  := x 2 + 1
終了

拡大すると、これがプログラムです

/* 前提条件: x 2 = 0 */ 
LOOP x 1  DO 
  x 0  := 0;
   LOOP x 2  DO 
    x 0  := x 0 + 1
   END ;
  x 2  := x 2 + 1
終了

このプログラムは、他の LOOP プログラム内のサブルーチンとして使用できます。 LOOP 構文は、次のステートメントで拡張できます。これは、上記をサブルーチンとして呼び出すのと同じです。

x 0  := x 1 ∸ 1

注意: ここでも副作用に注意する必要があります。先行プログラムは変数 x _{2 を}変更しますが、この変数は他の場所で使用されている可能性があります。ステートメント x ₀  := x ₁ ∸ 1 を展開するには、変数 x _n、 x _n+1、 x _n+2 (n が十分に大きい場合) をそれぞれ 0、 x ₁、 0 に初期化し、これらの変数に対してコードを実行し、結果 (x _n ) を x ₀にコピーします。コンパイラはこれを実行できます。

上記の「加算」プログラムで、2 番目のループが x ₀を増分するのではなく減分する場合、プログラムは変数と の差 (0 でカットオフ) を計算します。 ${\displaystyle x_{1}}$${\displaystyle x_{2}}$

x 0  := x 1
ループx 2  DO 
  x 0  := x 0 ∸ 1
終了

前と同様に、次のステートメントを使用して LOOP 構文を拡張できます。

x 0  := x 1 ∸ x 2

_{if x 1} > x ₂ then P1 else P2の if-then-else ステートメント:

x n1  := x 1 ∸ x 2 ;
xn2 := 0  ;
x n3  := 1;
ループx n1  DO 
  x n2  := 1;
  x n3  := 0
 END ;
ループx n2  DO
  1 位
END ;
ループx n3  DO
  2位
終わり;

• μ再帰関数
• 原始再帰関数
• ブループとフロープ

• ループ、Goto、While
• プログラミングにおけるループの技術をマスターする: ステップバイステップのチュートリアル