EWD：置換プロセス

こんにちは、Habr！ Edsger Dijkstraによる記事Substitution Processes （1962）の翻訳を紹介します。 パラグラフへの分割はオリジナルではありません。

はじめに

マシンは（その構造によって）言語を決定します。つまり、独自の入力言語です。逆に、言語のセマンティック定義は、それを理解できるマシンを定義します。 言い換えれば、機械と言語は同じコインの両面です。 このようなメダルについて説明します。 私はあなたの意見では、私の会話の主題のこれらの2つの側面のどちらが最も重要であるかについてあなたに決定を任せます。 私があなたにアウトラインを与えるつもりの言語は、人にとって容認できないほど難しいです、そして、私が説明しようとしている機械は、ひどく非効率的です。



したがって、私の精神構造が存在する権利を持っている場合、その正当性は他の性質に見出す必要があります。 あなたは私の車、私の意見と判断、少なくともその並外れたシンプルさと優雅さ、それがまったく異なる（一見した）動作を実行する方法の均一性にそれらを見つけることができます。 私の言語の正当化は、明確で一貫した解釈と実行される操作のプログラムでの明示的な指示に起因する、その明確さと異常に高いあいまいさです。通常、すべての操作が暗示されます（そして、これからいくつかの誤解が生じます）。 誰かが望めば、彼は私の車と言語が教育目的で発明されたと考えることができます。



説明を始める前に、2つの意図的な省略について警告したいと思います。 私が紹介するシステムは、多くの「隣接する可能性」の中から慎重に選択した結果です。 私は自分の選択を説明しません。言及されていない選択肢を意識的に残します。 言い換えれば、少なくともある意味では、システムを「ローカル最適」として導入することは控えます。 これは私の見解の信頼性を低下させるので、私は個人的にこの省略を後悔していますが、簡潔にするためにそのような説明をスキップする必要があります。



気にしないもう1つの質問は、従来のマシンを使用してこのシステムを実装する方法の質問です。 どんなに失礼であっても、これを実現できるかどうかという質問をすることもできます（そして、私がやっていることを愚かではないことを確認するために、私は自分でやった）。 これが可能だということを私の言葉で伝えてください。 この可能性を最も疑わしいリスナーに納得させることができる程度まで、実装方法を開発しました。 しかし、この実装に関する詳細な情報を表示するつもりはありません。なぜなら、言及された場合、基本から注意をそらすようなarbitrary意的な決定を多く含める必要があったからです。 特に、メモリ割り当ての問題は変更されません。

数字と算術

私の機械は、私が言葉と呼ぶ情報の単位を制御します（そして制御可能です）。 一般性を失うことなく、有限の数の異なる単語に制限することができ、各単語は同じビット数で表されます。



マシンは、数字、演算子、変数、区切り文字など、さまざまな種類の単語を区別します。 ここで、最初の「単語番号」と「単語演算子」に注目します。



2つの数値の加算や乗算などの通常の算術演算には、入力として2つの数値ワードが含まれ、出力として1つのワード（数値）も含まれます。 数値と数値ワード（たとえば、ビットから取得）を一致させるルールは、算術デバイスの操作で具体化されます。これは、入力と出力の両方に同じルールが適用される通常のプロパティを持ちます：算術デバイスの出力を再入力できます仕事の次の段階で彼。 算術デバイスの特性は時間的に一定であると想定しているため、数値語には「固定された意味」があると言えます。 数値ワードの固定解釈は、算術デバイスの定数プロパティに関連付けられているため、演算子ワード（「 +



」、「 -



」、「 *



」、「 /



」など）によって基本的な算術演算を示すことは驚くことではありません。修正済みとみなすこともできます。



マシンは、主に一連の単語で構成されるプログラムを実行しています。 現在、私は算術式の計算を必要とするプログラムの部分に自分自身を制限します。



通常、次のように記述される式を考えます。

  5 + 39 / (7 + 2 * 3) - 6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

通常の接尾辞表記（「逆ポーランド表記」とも呼ばれる）では、これにより、次の数字と演算子のシーケンスが生成されます（このシーケンスの隣接する要素は、紙で読みやすいようにスペースで区切られます）

  5 39 7 2 3 * + / + 6 -
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このような式を順番に計算するために特別に設計されたよく知られたメカニズムがあります-これは私が「スタック」と呼ぶことを好むものです。 （このデバイスは多くの人々によって独立して発明され、一般化されたため、「プッシュダウンリスト」、「ネストストア」、「セラー」、「後入れ先出し」など、さまざまな名前で知られるようになりました。など）上記の数字と演算子のシーケンスをプログラムの一部を表す単語の行と見なす場合、マシンはこの行を単語ごとに左から右に読み取ります。 数字の単語が見つかった場合、この数字（つまり、この数字の単語のコピー）がスタックの一番上に追加され、演算子の単語と一致した場合、対応する操作がスタックの一番上で実行されます。 次の図では、線はスタックの最上部の連続した状態を示しており、頂点自体は線の右側にあります。

  ... 5 ... 5 39 ... 5 39 7 ... 5 39 7 2 ... 5 39 7 2 3 ... 5 39 7 6 ... 5 39 13 ... 5 3 ... 8 ... 8 6 ... 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プログラムのこの小さな部分を実行した最終的な結果は、式の値がスタックに追加されたことです。

計算と置換

上記の例が明確に示すように、マシンはプログラムテキストを単語ごとにスタックの最上部にコピーすることから開始します。 遅かれ早かれ、これを中断する必要があります。そうしないと、マシンは単なるコピー機になります。 前述のシステムでは、コピー処理はプログラムテキスト内の任意の演算子の出現によって中断されます。 したがって、演算子の機能は2つあります。まず、操作を実行する必要があるため、コピーを中断する必要があることを示し、次に、この操作を定義します。 これら2つの完全に異なる関数を分離することを提案します。これ以降、算術演算子は基本的に数値の処理と同じ方法で処理されます。つまり、演算子語もスタックにコピーされます。 コピープロセスが中断されるたびに、この瞬間から導入され、「 E



」で示される特別な単語を挿入することにより、プログラムでこれを明示的に示します（「評価」から-計算）。 これで私のマシンは次のようになります：プログラムテキストを単語ごとに左から右に読み取ります。「読み取り」とは次のことを意味します。読み取った単語が「 E



」に等しくない場合、そのコピーはスタックに追加されます。がコピーされ、代わりに、（最初に）スタックの最上位ワードで示される操作が実行されます。



これらの規則に従って、前の例の式の計算を処方するプログラムは、次の単語の行で構成されます。

  5 39 7 2 3 * E + E / E + E 6 - E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プログラムテキストのこの部分の制御下で（つまり、この単語の行が「マシンで読み取られる」とき）、スタックの最上部は次の行に示すように順次変更されます。

  ... 5 ... 5 39 ... 5 39 7 ... 5 39 7 2 ... 5 39 7 2 3 ... 5 39 7 2 3 * ... 5 39 7 6 ... 5 39 7 6 + ... 5 39 13 ... 5 39 13 / ... 5 3 ... 5 3 + ... 8 ... 8 6 ... 8 6 – ... 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記のように、マシンはプログラムテキスト内の単語「 E



」を読み取ると、スタックのトップワードで示される操作を実行します。 「 E



」という単語を読んだ直後に、スタックの最上位の単語が実際には演算子の単語であるようなプログラムに限定します（たとえば、数値の単語ではありません）。 さらに、演算子のすぐ後ろにある単語がこの演算子によって提示された要件に対応する場合に限定します。 （たとえば、上記の2項算術演算の場合、演算子の直後の2つの単語は数字でなければなりません。）



つまり、算術演算のオペランドが式である場合、演算を実行する前にこの式の代わりに数値を代入します。 これは、本質的に算術演算が数値オペランドでのみ定義されるという条件を満たすものです。

変数を使用した計算

式または部分式を「置換」としてその数値で置き換えることを検討し、これらの置換をいつ実行するかを明示的に示しますが、これは不要です-「 3 + 4



」はいつ実行するかに関係なく、常に「 7



」に等しくなります追加。



ただし、変数が（定数とは対照的に）作用するようになると、状況は急激に変化します。 （以下では、変数を小さい文字で指定し、「



」などの「特別な単語」などの大文字を予約します。これについては後で説明します。）式の値を計算する必要があるとします。

  x + 4
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

変数



値が3の瞬間。これは、上記の式では、計算時の数値を「



」の代わりに置き換える必要があることを意味します。 その後のみ、算術置換を実行できます（「 3 + 4



」を「 7



」に置き換えます）。 「 x



」に依存するもの（つまり、表現「 x + 4



」）から、「 x



」への将来の変更に依存しない結果（つまり、「 7



」）を取得します。 x



置換を実行するときの値に。 変数「 x



」の「スナップショット」を作成しました。 明らかに、変数「 x



」（時間とともに変化します！）のスナップショットをいつ作成するかを明示的に示すことに固執します。



この明示的な指示のメカニズムがすでに導入されているので、今、私たちは労働の最初の成果を収穫します。 式を評価するためのプログラムの一部：

  x + 4
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

現在、次の形式があります。

  x E 4 + E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、上記の仮定に従って、スタックの状態のシーケンスは次のとおりです。

  ... x ... 3 ... 3 4 ... 3 4 + ... 7
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私たちのマシンは、他のいくつかの定式化で「変数x



値が3



である」という事実を説明するために提供します。すなわち、プログラム実行プロセスの状態は、スタックの最上位ワードが「 x



」の瞬間に「 E



この上位ワードを数値ワード「 3



」に置き換えます。 したがって、スタックの最上位にある変数はこの変数の演算子と見なされ、計算プロセスでは、その時点でのプログラム実行プロセスの状態に依存する何かに置き換えられます。 このような「演算子変数」は、その直後のスタックのワードに特別な要件を設定せずに実行されます。 （演算子と変数の類似性は、次の例でさらに強調されます。）

中間コンピューティング

プログラムのテキストで読み取られたすべての単語がスタックに追加されますが、単語「 E



」は例外です。これは、マシンに強制的に置換を実行させます。 以下で説明する理由により、「 E



」という単語をスタックに追加できるようにしたいと考えています。 ただし、この拡張機能のフレームワークは既に存在します。 単語「 P



」（「延期」から延期）で示される特別な演算子を導入します。これは、固定置換による計算の過程で実行されます。つまり、単語「



」に置き換えられます。 次の例で「 P



」演算子の使用方法を説明します。



この例では、「 x



」、「 y



」、および「 plinus



」という名前の3つの変数があります（「プラス-マイナス」-プラスまたはマイナスから）。 プログラム実行プロセスの状態は、「 plinus E



」を読み取るとスタックの先頭に「 +



」という単語が生成されると仮定します。 テキストを読むとき：

  x PE y PE plinus EPE
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スタックの最上部には一連の状態があります。

  ... x ... x P ... x E ... x E y ... x E y P ... x E y E ... x E y E plinus ... x E y E + ... x E y E + P ... x E y E + E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、スタックの最上部には、プログラムの一部として読み取られたときに式「 x + y



」を評価する単語の文字列が含まれます。 変数「 plinus



」の値が「 -



」の場合、式「 x - y



」（つまり、プログラムの一部としてこの式を評価する単語の文字列）を生成します。



我々が行ったのは、式「 x plinus y



」の中間評価であり、その結果もまた式です。 前の例では、最後のスタックアクションは常に1つの数値を残していました。 数値は式の些細な例です。したがって、数値だけでなく、中間結果の形式でのより一般的な式の生成は、通常の慣行の明らかな継続です。

変数の変更

これまで、スタックの最上部での単語の生成について説明しましたが、これらの単語を使用して何をするかについては説明していません。 さらに、この変数に関して、プログラム実行プロセスは、この変数の計算が以前に定義された置換をもたらすような状態にある可能性があることを示唆しましたが、この置換自体の定義については以前に言及していません。 これらの2つのスペースは、代入演算子を導入することで埋められます。



「 x := 3



」のように1つの単語に意味を割り当てるには、プログラムに次のように記述できます。

  3 x := E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スタック状態のトップになります：

  ... 3 ... 3 x ... 3 x :=
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

割り当て演算子「 :=



」の実行中、マシンはその直後の単語を調べます。 割り当てを適用する必要がある変数でなければなりません。 次の単語がこの変数に割り当てられ（これについては以下で詳しく説明します）、スタックの最上部にある3つの単語（現在処理中）がスタックから削除されます。 次の割り当て（つまり、変数 " x



"の新しい割り当て）まで、この変数を計算すると、スタックのトップワードがワード " 3



"に置き換えられます。

文字列の割り当て

これは、左側と右側の位置まで、 ALGOL 60



使用される割り当てステートメントに近いものです。 ただし、1つの単語のみから値を割り当てるだけでは十分ではないため、単語の文字列から値を割り当てる必要があるため、割り当てられた値がスタックに引き込まれる深さを示すことができるはずです。 これを行う最も簡単な方法は、スタックにマーカーを挿入することです。たとえば、割り当てられた値の最後の単語の後に特別な単語「



」（「Terminal」から-end）を挿入します。 さらに、別の割り当て演算子「 :-



」を導入します（前の段落で示した「単語割り当て」とは対照的に、「行割り当て」と呼ばれます）。 このステートメントの実行中に、マシンはスタックの上部を下方向に調べます。 最初の単語（「 :-



」演算子のすぐ下）は、値を割り当てる必要がある変数でなければなりません。 その後、マシンは、特別なマーカー「



」に遭遇するまで単語ごとの調査を続けます。この方法で送信された単語は、割り当てられた値として認識される行を一緒に形成します。



「



」をスタックに追加する最も簡単な方法は、「



」という単語を、スタックが読み込まれるプログラム内の目的の場所に単に挿入することです。 ただし、これは行いません。 後で説明する理由により、この単語を含まないプログラムの制御下で、スタックの一番上に「



」を生成する機能が必要です。 スタックの上部に「 E



」を作成できるのと同じトリックでこれを行うことができます。 単語「 S



」で示される新しい演算子を導入します（たとえば、「セパレータ」から-セパレータ、または単に「 S



」がアルファベットの「 T



」に先行するため）、実行中に単語「 T



」に置き換えられ、ルールを確立します。これが単語「



」をスタックに追加する唯一の方法であること。



これらすべてを使用して、代入演算子「 x := 3



」の代替表記法、つまり：

  SE 3 x :- E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スタックの上部の状態のシーケンスを与える：

  ... S ... T ... T 3 ... T 3 x ... T 3 x :-
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この結果は、単語「 :=



」の割り当てを使用した以前のフォームと同等です。

中間コンピューティングを行に保存する

この例では、より強力な代入を使用しましょう。これは、以前の代入の1つを拡張したものです。つまり、式「 x plinus y



」の中間評価を記述するx plinus y



です。 この中間計算の結果は、変数「 x



」および「 y



」に依存する式であり、この式を「 z



」と呼びたいとします。 これを行うには、プログラムに書き込みます。

  SE x PE y PE plinus EPE z :- E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この行の最後の「 E



」ステートメントが実行されると、スタックの最上部は次のようになります（「 plinus



」の値に関する同じ仮定の下）。

  ... T x E y E + E z :-
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このステートメントの実行後、上記の単語はスタックから削除され、単語「 T



」も含まれます。 後続の割り当ての前に、変数「 z



」の計算は、それに割り当てられた文字列の実行（「読み取り」）を意味します。 変数「 z



」の計算中、マシンはこの行の最初のワードにアクセスできる必要があります。 ただし、この行を読み始めるときには、この行の最後の単語がどこにあるかを知る必要もあります。 割り当て演算子は、エンドマーカーを再度追加することでこれを考慮し、この目的のために同じ単語「



」を使用できると仮定します。 変数「 z



」の計算中、プログラムに割り当てられた行は、終了マーカー「 T



」が見つかるまでプログラムの一部によって左から右に読み取られます。 最新の割り当てに関する新しい状況を簡単に提示できます。

  z → x E y E + ET
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

同様に、以前の割り当て：

  3 x := E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

  SE 3 x :- E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次のように提示される状況に貢献します。

  x → 3 T
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この配置の最も顕著な側面の1つは、「数字」と「指示」の通常の区別が完全になくなったことです。 変数の値はプログラムの一部として定義され、この変数の計算はプログラムのこの部分の実行を意味します。

現在の開発に関する注記

課題と測定値の二重性について

さらに、割り当てと一方でテキストを読むこととの間の特定の形式の二重性に注意を喚起したいと思います。 マシンがプログラムテキストを読み取ると、スタックの最上部はそのプログラムテキストの制御下で埋められます。 割り当てでは、スタックのコンテンツの制御下で「読み取り可能なテキスト」が作成されます。 二重性は、アクセシビリティ要件の観点からも説明できます。 スタック上の単語は、トップダウン方向でのみアクセス可能にする必要があります。 ただし、割り当て演算子がスタックの先頭を読み取り可能なテキストに変換する場合、後続の単語は他の方向で使用可能になります。



最後に、スタックは「匿名の中間結果」用に予約されていますが、読み取られるテキストは、原則として、少なくとも常に「名前付き」です。変数に割り当てることで作成するためです。

再帰について

気配りのある読者は、変数の値の表示に加えて、マシンにさらに2つの変更を暗黙的に導入したことに気付きました。



1つ目は、プログラムテキスト内の単語「



」の出現と、それに対する機械の「即時反応」です。これは比較的単純です。 私たちの理解では、テキストで読まれた単語「



」はスタックの一番上にコピーされません！ 代わりに、問題の変数のこの計算を引き起こした「 E



」ステートメントの直前の変数ワードまで、マシンに読み取りを続行させます。 言い換えれば、それは閉じられたルーチンの終わりで「 return



」のように振る舞います。



しかし、変数の計算には他の変数（それ自体を含む）の計算が必要な場合があります。変数の計算の実際的な定義は基本的に再帰的であり、再帰的定義に必要なメカニズムは...別のスタックです！ この2番目のスタックは、匿名スタックと呼ばれる最初のスタックとは対照的に、「アクティベーションスタック」と呼ばれます。 アクティベーションスタックの機能の1つは、読み取りプロセスを制御することです。 変数の計算が開始されると、アクティベーションスタックがいっぱいになり、対応する単語「



」が読み取られると、以前のサイズまで減少します。 （マシン構造の通常の用語では、アクティベーションスタックにはオーダーカウンター値のスタックが含まれ、その最上位要素は定義上現在のオーダーカウンターです。同じ用語では、古い要素は戻りアドレスを含むスタックのように機能します）



発言。 2つのスタックを1つにまとめることもできます。 , . , , , .

, , : . (« x



», « y



», « plinus



» . .) , «». «» , . «», ALGOL 60



, , .



, , , . , , . .



« », : ( ). : , .

, , , .



(: , ) . (, «», , ALGOL 60



.) « L0



», « L1



», « L2



» . .



, . , .



« E



» , - (, « L2



»), . , ( ) . . , , .

. « x



», « y



» « complus



» ( «complex-plus» — ) :

  x → 10 23 T
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

  y → 5 -2 T
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

  complus → L0 E := E L1 E := E L2 E := E L1 EE + E L1 EE L0 EE + E T
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

:

  SE x E y E complus E z :- E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

, « z



»:

  z → 15 21 T
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

, , .



ALGOL



: «complus» — , . . , « », , , .

. , « plus



» « +



». :

  SE + PE plus :- E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

:

  plus → + ET
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

:

  x E y E plus E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

  x E y E + E
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

. , .

おわりに

, . « goto



», . , . -, , -, : , .



. , , — , , , , .



, , , , . — , ALGOL 60



. , , , , . , , , ( ALGOL 60



) . : ( ) , , . , .



, , , . ; « ». , , , , , .



, , ( , ), . « ALGOL 60



» , , , , , .

, . , , , : ( ) .