Loading article…
スタック指向プログラミングは、 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 + 12 3 add 11 mul 1 add
すべての入力を処理した後、スタックには が含まれます56。これが答えです。
このことから、次のことが結論付けられます。スタックベースのプログラミング言語では、データを処理する方法は1つしかありません。それは、スタックの最上部からデータを1つ取り出し（ポップ） 、データをスタックの最上部に戻す（プッシュ）ことです。従来の方法で、あるいは他のプログラミング言語で記述できる式はすべて、後置（または前置）形式で記述でき、スタック指向言語による解釈が可能になります。
スタック指向言語ではスタックがデータ操作の主要な手段であるため、そのような言語ではスタック操作演算子が提供されることが多い。一般的に提供される演算子としてはdup、スタックの最上位要素を複製する`push`、スタックの最上位要素を交換する`push` exch（または`push`） 、スタック内またはスタックの一部で要素を循環的に入れ替える` push` 、スタックの最上位要素を破棄する`push`（`push`は暗黙的に実行される）、などがある。これらは手続きを研究する上で重要となる。swaprollpopdrop
ステートメントの効果を理解しやすくするために、ステートメントの前後のスタックの最上位を示す短いコメントが使用されています。スタックに複数の項目がある場合は、最上位が右端になります。この表記法は、コメントを括弧で囲むForth言語でよく用いられます。
（ビフォー・アフター）例えば、基本的なForthスタック演算子は以下のように説明されます。
重複( a -- aa )削除( a -- )交換( ab -- ba )上書き( ab -- aba )回転( abc -- bca )以下にそのfib機能について説明します。
フィブ（n - n'）これは、ホーア論理における事前条件と事後条件に相当します。どちらのコメントも、必ずしもスタックベースの言語の文脈ではありませんが、アサーションとして参照されることがあります。
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 or 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 false 交換 スタック: 4 false 4 0 eq スタック: 4 false false または スタック: 4 false ない スタック: 4 真
この式は真と評価されるため、内部の手続きが評価されます。
スタック: 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 sqsq
スタック: 3 /n 交換 スタック: /n 3 定義 スタック:空(定義済み) n スタック: 3 n スタック: 3 3 mul スタック: 9
これは予想通りの結果だ。
匿名手続きが存在するため、フロー制御は自然に発生する可能性があります。if -then-else文には、条件、条件が真の場合に実行される手続き、条件が偽の場合に実行される手続きの 3 つのデータが必要です。たとえば PostScript では、
2 3 gt { (2 は 3 より大きい) = } { (2 は 3 より大きくない) = } ifelseC言語ではほぼ同等の性能を発揮します。
if ( 2 > 3 ) { printf ( "2は3より大きい\n " ); } else { printf ( "2は3より大きくない\n " ); }ループやその他の構造も同様です。
スタック指向言語で提供されるシンプルなモデルにより、構文解析ではなく字句解析のみで済むため、式やプログラムの解釈が容易になり、理論的な評価もはるかに高速になります。このようなプログラムの記述方法は機械による解釈を容易にするため、PostScriptはプリンタでの利用に適しています。しかし、PostScriptプログラムのやや人工的な記述方法は、PostScriptのようなスタック指向言語を理解する上で最初の障壁となる可能性があります。
組み込み定義やその他の定義を上書きしてシャドウイングを行う機能は、プログラムのデバッグを困難にし、無責任な使用は予期せぬ動作を引き起こす可能性がありますが、一部の機能を大幅に簡素化できます。たとえば、PostScript では、showpageカスタム演算子を定義したり、スタイルを生成するためのコードを繰り返したりする代わりに、特定のスタイルをページに適用するカスタム演算子で演算子を上書きできます。