Loading article…
スタック指向プログラミングは、スタック（または複数のスタック）に依存してデータを操作し、パラメータを渡します。いくつかのプログラミング言語、特にForth、RPL、およびPostScriptがこの説明に当てはまります。スタック指向プログラミング言語は 1 つ以上のスタック上で動作し、各スタックは異なる目的を果たします。他のプログラミング言語のプログラミング構造は、スタック指向システムで使用するために変更する必要があります。[1]ほとんどのスタック指向言語は、ポストフィックス記法または逆ポーランド記法で動作します。コマンドのすべての引数またはパラメータは、そのコマンドの前に記述されます。たとえば、ポストフィックス記法は、(プレフィックスまたはポーランド記法)、または(インフィックス記法)の代わりに記述されます。プログラミング言語Forth、Factor、RPL、PostScript、BibTeXスタイルの設計言語[2]、および多くのアセンブリ言語がこのパラダイムに適合します。
2, 3, multiplymultiply, 2, 32 multiply 3
スタックベースのアルゴリズムは、スタックからデータをポップし、スタックにデータをプッシュすることでデータを操作します。スタック操作演算子は、スタックがデータを操作する方法を制御します。ステートメントの効果を強調するために、ステートメントの前後のスタックの最上部を示すコメントがよく使用されます。これは、スタック効果図として知られています。PostScript は、変数、辞書、プロシージャ、いくつかの一般的なプロシージャ、および制御フロー ステートメントなど、追加の目的のために個別のスタックを使用します。言語モデルを分析すると、式とプログラムを簡単に解釈できます。
スタックベースのアルゴリズム
PostScript は、ポストフィックス スタック ベース言語の例です。この言語の式の例は次のとおりです 2 3 mul('mul' は乗算演算のコマンドです)。式を計算するには、スタックの方向がどのように機能するかを理解する必要があります。
スタックの向きは、次のコンベア ベルトの例えで表すことができます。コンベア ベルトの端 (入力)に、、、とマークされたプレート2が3順番mulに配置されます。コンベアの端 ( 2) にあるプレートは取り出すことができますが、端にあるプレートが取り外されるまで他のプレートにはアクセスできません。プレートはスタック内にのみ保管でき、スタックの上からのみ追加または削除でき、中央または下から追加または削除することはできません。空白のプレート (およびマーカー) を提供でき、プレートは永久に廃棄できます。
皿を取っ2てスタックに置き、次に皿を取っ3てスタックに置きます。次に、mul皿を取ります。これは実行する命令です。次に、スタックから一番上の 2 つの皿を取り出し、それらのラベル (2および3) を掛け合わせて、結果 ( 6) を新しい皿に書き込みます。2 つの古い皿 (2および3) と皿 を破棄しmul、新しい皿をスタックに置きます。コンベア上に皿がなくなると、計算の結果 ( 6) がスタックの一番上の皿に表示されます。
これは非常に単純な計算です。 のようなより複雑な計算が必要な場合はどうすればよいでしょう(2 + 3) × 11 + 1か。 最初に のように後置形式で記述すると、2 3 add 11 mul 1 addまったく同じ方法で計算を実行し、正しい結果を得ることができます。 計算の手順を次の表に示します。各列には、入力要素 (コンベアの端にあるプレート) と、その入力を処理した後のスタックの内容が表示されます。
すべての入力を処理した後、スタックには56答えである が含まれます。
このことから、スタックベースのプログラミング言語では、スタックの上から 1 つのデータを取り出す (ポップ) ことと、スタックの上からデータを戻す(プッシュ) ことの 1 つのデータ処理方法しかありません。従来の方法、または別のプログラミング言語で記述できる式は、接尾辞 (または接頭辞) 形式で記述できるため、スタック指向の言語で解釈できます。
スタック操作
スタックはスタック指向言語でデータを操作するための主要な手段であるため、そのような言語では、何らかのスタック操作演算子が提供されることがよくあります。一般的に提供される演算子にはdup、スタックの一番上の要素を複製するexch（またはswap）、スタックの一番上の要素を交換する（最初の要素が 2 番目になり、2 番目の要素が 1 番目になる）、rollスタック内またはスタックの一部の要素を循環的に並べ替えるpop（またはdrop）、スタックの一番上の要素を破棄する（push は暗黙的）、などがあります。これらは、手順を学習する上で重要になります。
スタック効果図
ステートメントの効果を理解しやすくするために、ステートメントの前後のスタックの最上部を示す短いコメントが使用されます。複数の項目がある場合、スタックの最上部は右端になります。この表記法は、コメントが括弧で囲まれる Forth 言語でよく使用されます。
( 前 -- 後 )
たとえば、基本的な Forth スタック演算子は次のように記述されます。
dup (a -- aa) drop (a --) swap (ab -- ba) over (ab -- aba) rot (abc -- bca)
以下の機能fibについて説明します。
嘘( n -- n' )
これは、ホーア論理における前提条件と事後条件に相当します。両方のコメントは、必ずしもスタックベースの言語のコンテキストではありませんが、 アサーションとして参照されることもあります。
PostScript スタック
PostScript やその他のスタック言語には、他の目的のための別のスタックがあります。
変数と辞書
さまざまな式の評価はすでに分析されています。変数の実装はどのプログラミング言語にとっても重要ですが、スタック指向の言語では、データと対話する方法が 1 つしかないため、特に重要です。
PostScript などのスタック指向言語で変数を実装する方法は、通常、キーと値のペアの辞書を保持する別の特殊なスタックを使用します。変数を作成するには、まずキー (変数名) を作成し、次にそれに値を関連付けます。PostScript では、名前データ オブジェクトの前に が付けられるため、たとえば数値 に関連付けることができる名前データ オブジェクトにも が付けられます。コマンドはであるため、
//x42definedef
/x 42 def
は、スタックの一番上にある辞書のx番号と名前を関連付けます。との間には違いがあります。前者は名前を表すデータ オブジェクトであり、で定義されているものを表します。
42/xxx/x
手順
スタックベースのプログラミング言語では、プロシージャはそれ自体がデータ オブジェクトとして扱われます。PostScript では、プロシージャは{との間に示されます}。
たとえば、PostScript構文では、
{ dup mul }
スタックの一番上にあるものを複製し、その結果を乗算する匿名の手順、つまり二乗手順を表します。
プロシージャは単純なデータ オブジェクトとして扱われるため、プロシージャ付きの名前を定義できます。プロシージャを取得すると、直接実行されます。
辞書は、定義を保存するだけでなく、スコープを制御する手段も提供します。
データ オブジェクトは最上位の辞書に格納されるため、予期しない機能が自然に発生します。辞書から定義を検索する場合、最上位の辞書がチェックされ、次に次の辞書がチェックされます。別の辞書で既に定義されているものと同じ名前のプロシージャが定義されている場合は、ローカルのプロシージャが呼び出されます。
いくつかの典型的な手順の解剖
プロシージャは多くの場合、引数を取ります。引数は、他のプログラミング言語とは異なり、プロシージャによって非常に特殊な方法で処理されます。
PostScript で フィボナッチ数列プログラムを調べるには:
/fib
{ dup dup 1 eq exch 0 eqまたはnot { dup 1 sub fib exch 2 sub fib add } if } def
スタック上で再帰定義が使用されます。フィボナッチ数関数は 1 つの引数を取ります。まず、1 か 0 かがテストされます。
プログラムの各主要ステップを分解し、スタックを反映して、次の計算を仮定しますfib(4) 。
スタック: 4
重複
スタック: 4 4
重複
スタック: 4 4 4
1等量
スタック: 4 4 偽
交換
スタック: 4 偽 4
0 等
スタック: 4 偽 偽
または
スタック: 4 偽
ない
スタック: 4 真
式が true と評価されるため、内部プロシージャが評価されます。
スタック: 4
重複
スタック: 4 4
1 サブ
スタック: 4 3
嘘
- (ここで再帰呼び出し)
スタック: 4 F(3)
交換
スタック: F(3) 4
2サブ
スタック: F(3) 2
嘘
- (ここで再帰呼び出し)
スタック: F(3) F(2)
追加
スタック: F(3)+F(2)
これは予想通りの結果です。
この手順では名前付き変数は使用せず、スタックのみを使用します。名前付き変数は、/a exch def構文を使用して作成できます。たとえば、{/n exch def n n mul}
は、名前付き変数を使用した平方化手続きですn。および が呼び出される/sq {/n exch def n n mul} defと仮定すると3 sq、手続きはsq次のように分析されます。
スタック: 3 /n
交換
スタック: /n 3
定義
スタック:空(定義済み)
ん
スタック: 3
ん
スタック: 3 3
マル
スタック: 9
これは予想通りの結果です。
制御とフロー
匿名の手続きが存在するため、フロー制御が自然に発生します。if -then-else文には、条件、条件が真の場合に実行される手続き、条件が偽の場合に実行される手続きの 3 つのデータが必要です。たとえば、PostScript では、
2 3 gt { (2は3より大きい) = } { (2は3より大きくない) = } ifelse
C ではほぼ同等の動作を実行します。
if ( 2 > 3 ) { printf ( "2 は 3 より大きい\n " ); } else { printf ( "2 は 3 より大きくない\n " ); }
ループやその他の構造も同様です。
言語モデルの分析
スタック指向言語で提供される単純なモデルにより、構文解析ではなく字句解析を行う必要があるため、式やプログラムを簡単に解釈し、理論的に評価する速度が大幅に速くなります。このようなプログラムの記述方法は、機械による解釈を容易にするため、PostScript はプリンタでの使用に適しています。ただし、PostScript プログラムの記述方法がやや人工的であることが、PostScript などのスタック指向言語を理解する上で最初の障壁となる可能性があります。
組み込み定義やその他の定義をオーバーライドしてシャドウイングする機能により、プログラムのデバッグが困難になり、この機能を無責任に使用すると予期しない動作が発生する可能性がありますが、一部の機能を大幅に簡素化できます。たとえば、PostScript を使用する場合、show pageカスタム演算子を定義したり、スタイルを生成するコードを繰り返したりする代わりに、特定のスタイルをページに適用するカスタム演算子で演算子をオーバーライドできます。
参照
参考文献
- ^ Luerweg, T. (2015). スタックベースのプログラミングパラダイム。プログラミング言語の概念–CoPL'15、33。
- ^ Oren Patashnik、BibTeX スタイルの設計(PDF)[リンク切れ ]