制御テーブル

制御テーブルは、制御フローを制御したり、プログラム制御で主要な役割を果たすテーブルです。制御テーブルの構造や内容については厳格な規則はありません。制御テーブルの限定的な属性は、プロセッサまたはインタープリタによる「実行」を通じて何らかの方法で制御フローを指示できることです。このようなテーブルの設計は、テーブル駆動設計と呼ばれることもあります^{[1] [2]} (ただし、これは通常、直接実行時テーブルではなく、外部テーブルから自動的にコードを生成することを指します)。場合によっては、制御テーブルは有限状態マシンベースのオートマトンベースのプログラミングの特定の実装である場合があります。制御テーブルに複数の階層レベルがある場合、それらはUML 状態マシンと同等の方法で動作することがあります^[3]

制御テーブルには、条件式や関数 参照に相当するものが埋め込まれていることが多く、通常は連想リスト内の相対的な列位置によって示されます。制御テーブルを使用すると、同様の構造やプログラム ステートメントを何度もプログラミングする必要性が減ります。ほとんどのテーブルは 2 次元であるため、プログラム コードの 1 次元よりも表示や更新が簡単です。

場合によっては、プログラマー以外の人が制御テーブルのコンテンツを管理するよう割り当てられることがあります。たとえば、ユーザーが入力した検索フレーズに特定のフレーズが含まれている場合、検索ユーザーの移動先を制御するテーブルに URL (Web アドレス) を割り当てることができます。フレーズに「スカート」が含まれている場合、テーブルはユーザーをスカートの製品カタログ ページである「www.shopping.example/catalogs/skirts」にルーティングできます (この例の URL は実際には機能しません)。このようなテーブルは、プログラマーの代わりにマーケティング担当者が管理する場合があります。

• 入力値の変換:
  • 後の分岐やポインタ検索のためのインデックス
  • プログラム名、相対サブルーチン番号、プログラムラベル、またはプログラムオフセット、制御フローを変更する
• 状態遷移の制御変数を使用してイベント駆動型プログラミングでメインループを制御する
• オンライントランザクション処理アプリケーションのプログラムサイクルの制御

• インタプリタによって処理される仮想マシンの仮想命令として機能する

バイトコードに似ているが、通常はテーブル構造自体によって暗示される操作を伴う

テーブルは、固定長または可変長の複数の次元を持つことができ、通常はコンピュータ プラットフォーム間で移植可能で、インタープリタの変更のみが必要であり、アルゴリズム自体は変更する必要はありません。アルゴリズムのロジックは、基本的にテーブルの構造と内容に組み込まれています。テーブルの構造は、マルチマップ連想配列に似ている場合があり、データ値 (またはデータ値の組み合わせ) を 1 つ以上の実行される関数にマップできます。

おそらく最も単純な実装では、制御テーブルは、生データ値を配列のインデックスとして直接使用するか、事前にデータに対して何らかの基本的な演算を実行することにより、生データ値を対応するサブルーチンのオフセット、インデックス、またはポインターに直接変換するための 1 次元テーブルになることがあります。これは、定数時間で実現できます(連想配列の一般的なルックアップテーブルを使用した線形検索やバイナリ検索は不要)。ほとんどのアーキテクチャでは、比較やループなしで、2 つまたは 3 つのマシン命令で実行できます。この手法は、「トリビアル ハッシュ関数」と呼ばれ、分岐テーブルに特に使用される場合は「ダブル ディスパッチ」と呼ばれます。これを実現するには、データのすべての可能な値の範囲が小さい必要があります (たとえば、範囲が16 進数の '00' ～ 'FF' であるASCIIまたはEBCDIC文字値など)。実際の範囲がこれより小さいことが保証されている場合は、配列を 256 バイト未満に切り捨てることができます)。

1次元配列を使用して、生のASCII値（A、D、M、S）を新しいサブルーチンインデックス（1、4、3、2）に定数時間で変換するテーブル

(この例では、範囲内のギャップは「..」として表示され、「次の行までのすべての 16 進値」を意味します。最初の 2 列は配列の一部ではありません)

オートマトンベースのプログラミングと疑似会話型トランザクション処理では、異なるプログラム状態の数が少ない場合、「密なシーケンス」制御変数を使用して、メイン プログラム ループのフロー全体を効率的に指示できます。

2 バイトの生データ値には、すべての入力可能性を処理するために、最小65,536 バイトのテーブル サイズが必要ですが、256 種類の出力値のみが許可されます。ただし、この直接変換手法では、ヒューリスティックと十分な高速アクセス メモリが使用できる場合、(相対) サブルーチン ポインタへの検証と変換が非常に高速になります。

分岐テーブルは、直前のインデックス付き分岐によって分岐したときにプログラム ラベルへの多方向分岐を実行する、連続したマシン コード 分岐/ジャンプ命令の 1 次元「配列」です。これは、入力範囲が小さく、密で、ギャップがほとんどない場合 (前の配列の例で作成されたように)、 switch ステートメントを実行するために最適化コンパイラによって生成されることがあります [1]。

複数の同等のステートメントと比較すると、If分岐命令は非常にコンパクトですが、分岐オペコードと条件コード マスクが分岐オフセットとともに繰り返されるため、依然としていくらかの冗長性があります。プログラム ラベルへのオフセットのみを含む制御テーブルを構築してこの冗長性を克服することができます (少なくともアセンブリ言語では)。しかも、従来の分岐テーブルと比較すると、 実行時間のオーバーヘッドはわずかです。

より一般的には、制御テーブルは真理値表、または印刷された決定テーブル(または複数のレベルの決定テーブルのツリー) の実行可能 (「バイナリ」) 実装として考えることができます。制御テーブルには (多くの場合は暗黙の)命題と、1 つ以上の関連する「アクション」が含まれます。これらのアクションは通常、 「インタープリタ」プログラムによって呼び出される汎用またはカスタム ビルドのサブルーチンによって実行されます。この場合のインタープリタは、実質的に仮想マシンとして機能し、制御テーブル エントリを「実行」して、インタープリタの基礎となるコードよりも 高いレベルの抽象化を提供します。

制御テーブルは、言語に依存するswitch ステートメントと同様の方法で構築できますが、入力値の組み合わせをテストする (ブール形式のAND / OR条件を使用) ことや、複数のサブルーチンを呼び出す(単一の値セットと「分岐」プログラム ラベルではなく) 可能性が追加されています。(いずれにしても、switch ステートメント構造は、高水準言語 ( HLL ) では使用できないか、実装が混乱を招く可能性があります。これに対して、制御テーブルの概念には、固有の言語依存性はありませんが、それでも、選択したプログラミング言語で使用可能なデータ定義機能に応じて、異なる方法で実装される可能性があります。)

制御テーブルは、本質的には、従来のプログラムの「本質」を具体化したものであって、プログラミング言語の構文とプラットフォームに依存するコンポーネント (IF/THEN DO..、FOR..、DO WHILE..、SWITCH、GOTO、CALL など) を取り除いて、変数 (input1 など)、値 (「A」、「S」、「M」、「D」など)、およびサブルーチン ID (「Add」、「subtract、..」または #1、#2 など) に「凝縮」したものです。テーブル自体の構造は、通常、関連する (デフォルトの) 論理操作 (「等しいかどうかのテスト」、サブルーチンの実行と「次の操作」、またはデフォルトのシーケンスに従うことなど) を意味します(他のプログラミング パラダイムで要求されるように、プログラム ステートメント内で明示的に記述されるのではなく)。

多次元制御テーブルには通常、最低限、値とアクションのペアが含まれ、さらに、入力データまたは出力データの場所、サイズ、形式、処理の前または後にデータ変換(またはその他の実行時処理のニュアンス) が必要かどうか (関数自体に暗黙的に含まれていない場合) などの演算子と型情報が含まれる場合があります。テーブルには、「行」内の他の値に応じて、実行される汎用またはカスタマイズされたプリミティブまたはサブルーチンへのインデックスや相対または絶対ポインタが含まれる場合と含まれない場合があります。

以下に示す表は、特定の入力が指定されていないため、「input1」にのみ適用されます。

構造によって暗示される条件と行動

(この値とアクションの並列ペアリングは、イベント駆動型プログラミングの構成要素、つまり「イベント検出」と「イベント処理」と類似していますが、イベント自体の 非同期性は (必ずしも) ありません)

制御テーブル内にエンコードできる値の種類は、使用するコンピュータ言語に大きく依存します。アセンブリ言語は、 (アクション用) 直接実行可能なマシン コードのオプションを含む、最も広い範囲のデータ型を提供します。通常、制御テーブルには、入力の一致する可能性のある各クラスの値と、対応するアクション サブルーチンへのポインターが含まれます。一部の言語では、ポインターを(直接) サポートしていないと主張していますが、代わりに、テーブル エントリの値によって制御される条件付き実行を実行するための「相対サブルーチン番号」を表すために使用できるインデックスをサポートできます (例: ギャップなしで設計された最適化されたSWITCHステートメントで使用するため (つまり、多方向分岐) )。

各列の上にコメントを配置すると（または埋め込まれたテキスト ドキュメントでも）、決定表を「人間が読める」ものにすることができます。これは、決定表を「凝縮」（エンコード）した後でも、元のプログラム仕様とほぼ一致します。特に、コーディングを開始する前に、各固有のアクションを列挙した印刷された決定表が作成されている場合はなおさらです。表のエントリには、実行時統計を収集して「実行中」または後で最適化するためのカウンターをオプションで含めることもできます。

制御テーブルは、静的ストレージ、フラット ファイルなどの補助ストレージ、またはデータベースに格納できます。また、プログラムの初期化時にパラメータ (それ自体がテーブルに格納されている場合もあります) から部分的にまたは全体的に動的に構築することもできます。効率を最大化するには、インタープリタがテーブルの使用を開始するときに、テーブルがメモリに常駐している必要があります。

インタープリタは、高級言語を含む任意の適切なプログラミング言語で記述できます。適切に設計された汎用インタープリタと、適切に選択された汎用サブルーチンのセット (最も一般的に発生するプリミティブを処理できる) を組み合わせると、新しいカスタム サブルーチンに対してのみ、従来のコーディングを追加で必要とします (制御テーブル自体の指定に加えて)。インタープリタは、オプションで、完全なアプリケーション プログラムの明確に定義されたセクション (メイン制御ループなど) にのみ適用され、その他の「条件の少ない」セクション (プログラムの初期化、終了など) には適用されません。

インタープリタは過度に複雑である必要はなく、コンパイラ作成者のような高度な知識を持つプログラマによって作成される必要もなく、他のアプリケーション プログラムと同じように作成できます。ただし、通常は効率性を考慮して設計されます。インタープリタの主な機能は、テーブル エントリを一連の「命令」として「実行」することです。制御テーブル エントリを解析する必要はありません。したがって、これらのエントリは可能な限り「実行準備完了」になるように設計する必要があります。つまり、適切な列の変数を、すでにコンパイルされたインタープリタの汎用コードに「プラグイン」するだけで済みます。プログラム命令は、理論上は無限に拡張可能であり、インタープリタにのみ意味のあるテーブル内の値 (任意である可能性あり) を構成します。インタープリタの制御フローは、通常、各テーブル行を順次処理することによって行われますが、テーブル エントリ内の特定のアクションによって変更されることもあります。

したがって、これらの任意の値は、データまたは関数ポインタへの直接インデックスとして使用できる値を選択することで、効率性を考慮して設計できます。特定のプラットフォーム/言語では、分岐テーブル値を使用して命令パスの長さを最小限に抑えるように特別に設計することも、 JITコンパイラなどの一部のケースでは、直接実行可能なマシン コード「スニペット」(またはそれらへのポインタ) で構成することもできます。

サブルーチンは、インタープリタ自体と同じ言語、またはサポートされている他のプログラム言語でコーディングできます (適切な言語間の「呼び出し」リンク メカニズムが存在する場合)。インタープリタやサブルーチンの言語の選択は、通常、さまざまなプラットフォーム間での移植性の必要性によって決まります。制御テーブルの移植性を高めるために、インタープリタには複数のバージョンがある場合があります。インタープリタがこの構造をサポートしている場合、従属制御テーブル ポインターは、オプションで「アクション」列のサブルーチン ポインターの代わりに使用できます。これは、従来の構造化プログラム構造を模倣して、より低い論理レベルへの条件付き「ドロップ」を表します。

一見すると、制御テーブルを使用すると、プログラムのオーバーヘッドがかなり増えるように見えます。制御テーブルでは、ネイティブのプログラミング言語ステートメントが実行される前にインタープリタ プロセスが必要になるためです。ただし、常にそうであるとは限りません。実行可能なコーディングをテーブルで表現されたロジックから分離 (または「カプセル化」) することで、最も効率的に機能を実行するようにターゲットを絞りやすくなります。これは、スプレッドシートアプリケーションで最も顕著に表れます。スプレッドシート アプリケーションでは、基盤となるスプレッドシート ソフトウェアが複雑な論理「数式」を可能な限り効率的な方法で透過的に変換し、結果を表示します。

以下の例は、追加の抽象化層を大幅に補うだけでなく、非効率的で保守性が低く、長くなる可能性のあるコードを改善する可能性のある潜在的なパフォーマンス向上を示すために部分的に選択されています。示されている例は「低レベル」アセンブリ言語とC 言語のものですが、どちらの場合も、制御テーブル アプローチを実装するために必要なコード行数は非常に少なく、それでも、冗長な従来のプログラム言語構造と比較して、定数時間のパフォーマンスが大幅に向上し、ソース コードの繰り返しが減り、明瞭性が向上することがわかります。この記事のテーブルと多方向分岐の効率に関するDonald Knuthの引用も参照してください。

以下の例は任意ですが(わかりやすくするために 1 つの入力のみに基づいています)、通常のプログラム ステートメントの代わりにテーブルを使用することで制御フローがどのように実現されるかを示すことを目的としています。この手法は、列の数を増やすか、複数のテーブル エントリ (オプションの and/or 演算子を使用) を使用することで、複数の入力を処理するように簡単に拡張できることは明らかです。同様に、(階層的な)「リンクされた」制御テーブルを使用することで、構造化プログラミングを実現できます (オプションでインデントを使用して従属制御テーブルを強調表示できます)。

「CT1」は、単純なルックアップ テーブルである制御テーブルの例です。最初の列は、テストされる入力値 (暗黙の「IF input1 = x」による) を表し、TRUE の場合、対応する 2 番目の列 (「アクション」) には、呼び出し(またはSWITCHステートメントに似たジャンプ) によって実行されるサブルーチン アドレスが含まれます。これは、実質的に、戻り値のある多方向分岐(「動的ディスパッチ」の形式)です。最後のエントリは、一致が見つからない場合のデフォルト ケースです。

CT1

データ構造内のポインタを他のデータ値とともにサポートするプログラミング言語の場合、上記の表 (CT1) を使用して、表の一致する値に従って適切なサブルーチンに制御フローを誘導できます(他のことを示す列がない場合、この単純なケースでは等しいと想定されます)。

IBM/360 (最大 16Mb アドレス範囲) またはZ/Architectureのアセンブリ言語の例

この最初の例では、コーディング時に検索を最適化する試みは行われず、代わりに単純な線形検索手法が使用されています。これは、概念を説明し、ソース行数が少ないことを示すためだけです。256 種類の入力値すべてを処理するには、約 265 行のソース コード (主に 1 行のテーブル エントリ) が必要になりますが、複数の「比較と分岐」には通常約 512 行のソース行が必要です (バイナリのサイズも約半分になり、各テーブル エントリに必要なのは 4 バイトのみで、一連の「比較即時」/分岐命令に必要な約 8 バイトは不要です (入力変数が大きいほど、節約効果はさらに大きくなります)。

  *  -  -  -  -  -  -  -  -  -  通訳者  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - *
           LM R14,R0,=A(4,CT1,N) R14=4、R15 --> テーブル、R0 = テーブル内のエントリ数 (N) を設定します。
  TRY CLC INPUT1,0(R15) ********* テーブルエントリに値が見つかりましたか?
           BEアクション * loop * YES、テーブルからサブルーチンへのレジスタポインタをロード
           AR R15,R14 * * いいえ、R14 (=4) を追加して CT1 の次のエントリを指します。
           BCT R0,TRY ********* カウントが尽きるまで戻り、その後ドロップスルーします
  デフォルトのアクション...テーブル内の値が一致しない場合は、別の処理を実行します
           LA R1​​5,4(R15) はデフォルトエントリを指します (テーブル終了点以降)
  アクション L R15,0(R15) は、R15のポインタをR15に取得します。R15のポインタは、
           BALR R14,R15 サブルーチンを実行する（「CALL」して戻る）
           B END このプログラムを終了します
  * ------------------ 制御テーブル -----------------------------------------*
  * | この列の許容される EBCDIC または ASCII 値は、変数 'input1' に対して '=' でテストされます。
  * | | この列は適切なサブルーチンの3バイトアドレスです
  * 10 ...
  CT1       DC C'A',AL3(ADD) 制御テーブルの開始 (エントリ長4バイト)
           DC C'S'、AL3(減算)
           DC C'M'、AL3(乗算)
           DC C'D'、AL3(除算)
  N EQU (*-CT1)/4 テーブル内の有効なエントリの数 (合計長 / エントリ長)
           DC C'?',AL3(DEFAULT) デフォルトエントリ – ドロップスルーですべてキャッチするために使用されます
  INPUT1 DS C入力変数はこの変数にあります
  * ------------------ サブルーチン ------------------------------------------*
  ADD CSECTサブルーチン#1（ここでは別のCSECTとして示されていますが、
  . またはインラインコード)
  . 追加する指示
           BR R14 リターン
  SUBTRACT CSECT サブルーチン #2
  . 減算する命令
           BR R14 リターン
  などなど

上記の例のインタープリタのパフォーマンスを向上させる

上記の例で選択を行うと、平均命令パス長(サブルーチン コードを除く) は '4n/2 +3' ですが、256 バイトの変換テーブルを最初に使用して生の EBCDIC データから CT1 への直接インデックスを作成すると、 n = 1 ～ 64 の場合、比較なしのパス長 '5' で定数時間に 簡単に短縮できます。n = 6 の場合、これは 3 つの連続した比較および分岐命令に相当します。ただし、n<=64 の場合、平均すると、複数の比較を使用する場合よりも約 13倍少ない命令数になります。n=1 ～ 256 の場合、平均すると、1 つの追加命令が必要になるため (インデックスを 4 倍にするため)、使用する命令数は約 42倍少なくなります。${\displaystyle O(1)\,}$

改良されたインタープリター(平均して上記の例よりも最大26 倍少ない命令が実行され 、n = 1 ～ 64、多重比較を使用する場合よりも最大 13 倍少なくなります)。

64 個の異なる入力値を処理するには、約 85 行 (またはそれ以下) のソース コード (主に 1 行のテーブル エントリ) が必要ですが、複数の「比較と分岐」には約 128 行が必要です ( 2 番目のインデックスを抽出するために 256 バイトの追加のテーブルが必要であるにもかかわらず、バイナリのサイズもほぼ半分になります)。

  *  -  -  -  -  -  -  -  -  -  通訳者  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - *
           SR R14、R14 ********* R14=0 に設定
  CALC IC R14,INPUT1 * calc * EBCDICバイトをR14の下位ビット（24～31）に格納する
           IC R14,CT1X(R14) * * EBCDIC値をテーブル'CT1X'のインデックスとして使用して新しいインデックスを取得します
  FOUND L R15,CT1(R14) ********* インデックス(0,4,8など)を使用してサブルーチンへのポインタを取得します
           BALR R14,R15 サブルーチンを実行します（「CALL」して戻るかデフォルトに戻ります）
           B END このプログラムを終了します
  * --------------- 追加変換テーブル (EBCDIC --> ポインタテーブル INDEX) 256 バイト----*
  CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 16バイトのx'00の12個の同一セット
  * X'00 – x'BF' を表す
           DC AL1(00, 04 ,00,00, 16 ,00,00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF'
           DC AL1(00,00,00,00, 12,00,00,00,00,00,00,00,00,00,00,00 ) ..x'D0' – X'DF'
           DC AL1(00,00, 08,00,00,00,00,00,00,00,00,00,00,00,00,00 ) ..x'E0' – X'EF'
           DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF'
  * アセンブラを使用すると、インデックス値を自動的に計算し、値をよりユーザーフレンドリーにすることができます。
  * (例えば、「04」は上記の表CT1Xの記号式「PADD-CT1」に置き換えることができます)
  * CT1 を修正 (インデックス = 00、単一次元、完全な 31 ビット アドレスの場合のデフォルト アクションを追加)
  CT1       DC A(DEFAULT) インデックス =00 制御テーブルの開始 (4 バイトのアドレス定数)
  パッドDCA(追加) =04
  PSUB DC A(減算) =08
  PMUL DC A(乗算) =12
  PDIV DC A(除算) =16
  * 残りのコードは最初の例と同じです

さらに改良されたインタープリター(平均して最初の例に比べて実行される命令が最大21 倍少なくなり (n>=64 の場合) 、多重比較を使用する場合に比べて最大 42倍少なくなります)。

256 種類の異なる入力値を処理するには、約 280 行以下のソース コード (主に 1 行のテーブル エントリ) が必要ですが、複数の「比較と分岐」には約 512 行が必要です (バイナリのサイズもほぼ半分になります)。

  *  -  -  -  -  -  -  -  -  -  通訳者  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - *
           SR R14、R14 ********* R14=0 に設定
  CALC IC R14,INPUT1 * calc * EBCDICバイトをR14の下位ビット（24～31）に格納する
           IC R14,CT1X(R14) * * EBCDIC値をテーブル'CT1X'のインデックスとして使用して新しいインデックスを取得します
           SLL R14,2 * *  インデックスを4倍する（追加命令）
  FOUND L R15,CT1(R14) ********* インデックス(0,4,8など)を使用してサブルーチンへのポインタを取得します
           BALR R14,R15 サブルーチンを実行します（「CALL」して戻るかデフォルトに戻ります）
           B END このプログラムを終了します
  * --------------- 追加変換テーブル (EBCDIC --> ポインタテーブル INDEX) 256 バイト----*
  CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 16バイトのx'00'の同一セット12個
  * X'00 – x'BF' を表す
           DC AL1(00, 01,00,00 , 04,00,00,00,00,00,00,00,00,00,00,00,00 ) ..x'C0' – X'CF'
           DC AL1(00,00,00,00, 03,00,00,00,00,00,00,00,00,00,00,00 ) ..x'D0' – X'DF'
           DC AL1(00,00, 02 ,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF'
           DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF'
  * アセンブラを使用すると、インデックス値を自動的に計算し、値をよりユーザーフレンドリーにすることができます。
  * (例えば、「01」は上記の表CT1Xの記号表現「PADD-CT1/4」に置き換えることができます)
  * CT1 を修正しました (インデックスは 0、4、8、12、16 ではなく 0、1、2、3、4 に基づいており、256 のすべてのバリエーションを許可しています)
  CT1       DC A(DEFAULT) インデックス =00 制御テーブルの開始 (4 バイトのアドレス定数)
  パッドDCA(追加) =01
  PSUB DC A(減算) =02
  PMUL DC A(乗算) =03
  PDIV DC A(除算) =04
  * 残りのコードは2番目の例と同じです

C 言語の例 このCの例では2 つのテーブルを使用します。最初のテーブル (CT1) は、入力 (x) を照合してインデックスを取得するための単純な線形検索の1 次元ルックアップ テーブルであり、2 番目の関連テーブル (CT1p) は、ジャンプ先のラベルのアドレスのテーブルです。

 static const char CT1 [] = { "A" , "S" , "M" , "D" }; /* 許可された入力値 */ static const void * CT1p [] = { && Add , && Subtract , && Multiply , && Divide , && Default }; /* デフォルトに移動するラベル */ for ( int i = 0 ; i < sizeof ( CT1 ); i ++ ) /* ASCII 値をループ */ { if ( x == CT1 [ i ]) goto * CT1p [ i ]; } /* 見つかった --> 適切なラベル */ goto * CT1p [ i + 1 ]; /* 見つからない --> デフォルトのラベル */                                                      
                      
               
              
                             

256 バイトのテーブルを使用して、生の ASCII 値 (x) を密な連続インデックス値に直接変換し、CT1p から分岐アドレスを直接検索する場合 (つまり、バイト幅の配列を使用した「インデックス マッピング」)、これをより効率的にすることができます。その後、x のすべての可能な値に対して定数時間で実行されます (CT1p にラベルではなく関数名が含まれている場合、ジャンプは動的関数呼び出しに置き換えられ、スイッチのような goto がなくなりますが、関数のハウスキーピングの追加コストによってパフォーマンスが低下します)。

 static const void * CT1p [] = { &&デフォルト、&&加算、&&減算、&&乗算、&&除算}; /* 以下の 256 バイトのテーブルは、対応する ASCII 位置 (A、S、M、D) に値 (1、2、3、4) を保持し、その他はすべて 0x00 に設定されます */ static const char CT1x [] = { '\x00' , '\x00 ' , '\x00' , '\x00' , '\x00' , '\ x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\ x00 ' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、' \x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、'\x00' 、' \ x00 ' 、 '\x00 ' 、'\x00 ' 、 '\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、 ' \x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、 '\x00 ' 、' \x00' 、'\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、'\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、'\x00' 、' \x00' 、 '\x00' 、'\x00' 、'\x00' 、 '\x00' 、'\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、'\x00' 、 '\x00' 、'\x01' 、'\x00' 、'\x00' 、'\x04' 、'\x00' 、'\x00' 、'\x00' 、         
 
    
                            
                            
                            
                            
                     '\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、'\x03' 、'\x00' 、'\x00' 、'\x00' 、' \x00' 、'\x00' 、'\x02' 、'\x00' 、'\x00' 、 '\x00' 、 ' \ x00 ' 、'\ x00' 、'\x00' 、 '\x00' 、 ' \ x00' 、' \x00' 、'\x00' 、'\x00' 、 '\x00 ' 、'\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、' \x00' 、 '\x00' 、 '\x00' 、 ' \x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、 '\ x00' 、 '\x00' 、'\x00' 、 '\x00' 、 '\x00' 、 '\ x00' 、 '\x00' 、'\x00 ' 、 '\x00' 、 '\x00' 、 ' \x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\ x00 ' 、'\ x00 ' 、' \x00' 、'\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、 '\ x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、'\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 ' \x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、'\x00' 、 '\x00' 、 '\x00' 、'\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、'\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00 ' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、'\x00' 、 '\x00' 、'\x00'       
                            
                            
                            
                            
                            
               、' \ x00 ' ...​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 、' \ x00 ' ...​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​'\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、'\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 ' \x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、 '\x00' 、'\x00' 、 '\x00' 、 '\x00' 、'\x00' 、'\x00' 、 '\ x00 ' 、'\x00' 、'\x00' 、 '\x00' 、'\x00' 、'\x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、'\x00' 、'\x00' 、 '\x00' 、 '\x00' 、'\x00' 、             
                            
                            
                            
                            
                          '\x00' , '\x00' , '\x00' }; /* 次のコードは、入力文字 (x) の値に関係なく、一定時間で実行されます */ i = CT1x ( x ); /* 最初に ASCII 値をインデックスとして使用して、テーブル CT1x から正しいサブルーチン インデックスを抽出します */ goto * CT1p [ i ]; /* インデックスに対応するラベルに移動します (0=デフォルト、1=追加、2=減算など) - CT1p を参照してください */  
 
               
            

次の例は、データ構造内のポインタ定義をサポートしていないが、サブルーチンへのインデックス付き分岐をサポートしている言語で、同様の効果を実現する方法を示しています。サブルーチンは、サブルーチン ポインタの ( 0 ベースの) 配列内に格納されています。テーブル (CT2) は、ポインタ配列 (CT2P) へのインデックス (2 番目の列から) を抽出するために使用されます。ポインタ配列がサポートされていない場合は、SWITCH ステートメントまたは同等のステートメントを使用して、制御フローを一連のプログラム ラベル (例: case0、case1、case2、case3、case4) の 1 つに変更し、入力を直接処理するか、適切なサブルーチン (デフォルト、加算、減算、乗算、除算など) への呼び出し (戻り値付き) を実行して処理します。

CT2

上記の例のように、テーブル検索を実際に使用せずに、潜在的なASCII入力値 (A、S、M、D または不明) をポインター配列インデックスに非常に効率的に変換できますが、ここでは最初の例との一貫性を保つためにテーブルとして示されています。

CT2Pポインタ配列

多次元制御テーブルを構築 (つまりカスタマイズ) すると、上記の例よりも「複雑」になり、複数の入力に対して複数の条件をテストしたり、一致基準に基づいて複数の「アクション」を実行したりできるようになります。「アクション」には、別の従属制御テーブルへのポインターを含めることができます。以下の簡単な例では、暗黙の「OR」条件が追加の列として組み込まれています (小文字の入力を処理するためですが、この例では、小文字ごとに大文字と同じサブルーチン識別子を指定する追加のエントリを用意するだけで、同様に処理できます)。各入力の実際の実行時イベントが発生したときにそれをカウントするための追加の列も含まれています。

CT3

制御テーブル エントリは、手続き型言語の条件文に非常に似ていますが、重要な点は、実際の (言語依存の) 条件文 (つまり、命令) が存在しないことです (汎用コードは物理的にはテーブル エントリを処理するインタープリタ内にあり、テーブル自体には存在しません。テーブル自体には、単にその構造と値を介してプログラム ロジックが具体化されています)。

このようなテーブルでは、一連の類似したテーブル エントリによってロジック全体が定義されるため、テーブル エントリ番号またはポインターは、従来のプログラムのプログラム カウンターの代わりとなり、テーブル エントリで指定される「アクション」でリセットされることがあります。以下の例 (CT4) は、前のテーブルを拡張して「次の」エントリ (および/または「フロー変更」(ジャンプ) サブルーチン)を含めると、ループが作成される様子を示しています (この例は、実際にはこのような制御テーブルを作成する最も効率的な方法ではありませんが、上記の最初の例から段階的に「進化」していく様子を示すことで、追加の列を使用して動作を変更する方法を示しています)。5 番目の列は、1 つのテーブル エントリで複数のアクションを開始できることを示しています。この場合は、各エントリの通常の処理後に実行されるアクションです(「-」値は「条件なし」または「アクションなし」を意味します)。

構造化プログラミングまたは「Goto レス」コード(「 DO WHILE」または「for loop 」構造と同等のものを組み込んだもの) も、適切に設計され「インデント」された制御テーブル構造で対応できます。

CT4 (入力1を読み取って処理し、'E'に遭遇するまで繰り返す完全な「プログラム」)

CT4Pポインタ配列

電気通信料金の専門分野（特定の通話の料金を決定すること）では、 テーブル駆動型料金設定技術は、市場の力によってルールが頻繁に変更される可能性があるアプリケーションで制御テーブルを使用する例です。料金を決定するテーブルは、多くの場合、プログラマー以外の人によって突然変更される可能性があります。^{[4] [5]}

アルゴリズムがインタープリターに事前に組み込まれていない場合 (したがって、テーブルに保持されている式の実行時解釈がさらに必要になる場合)、テーブル駆動型評価ではなく「ルールベースの評価」と呼ばれます (したがって、オーバーヘッドが大幅に増加します)。

スプレッドシートデータシートは、2 次元の制御テーブルと考えることができます。このテーブルでは、空でないセルは、基礎となるスプレッドシート プログラム (インタープリタ) のデータを表します。数式を含むセルは、通常、等号で始まり、インタープリタ内の制御フローを変更することで、参照されている他のセルの処理を指示する特殊なタイプのデータ入力を指定します。基礎となるインタープリタからの数式の外部化により、スプレッドシートと、上記の「ルール ベースの評価」の例の両方が、プログラマー以外の人が制御テーブルを使用するわかりやすい例として明確に識別されます。

制御テーブル手法が特定のプログラミング パラダイムに属すると言えるのであれば、最も近い類似点はオートマトン ベースのプログラミングまたは「リフレクティブ」 (メタプログラミングの形式。テーブル エントリはインタープリタの動作を「変更」すると言えるため) でしょう。ただし、インタープリタ自体とサブルーチンは、利用可能なパラダイムのいずれか、またはそれらの組み合わせを使用してプログラムできます。テーブル自体は、基本的にコンパイルする必要もなく、外部ソースから読み取ることができる「生データ」値のコレクションです (ただし、効率を上げるためにメモリ ポインタを直接使用する特定のプラットフォーム依存の実装は除きます)。

多次元制御テーブルは、仮想マシン上で動作するバイトコードと概念的に類似しています。つまり、実際の実行には、通常、プラットフォーム依存の「インタープリタ」プログラムが必要です (これは、テーブルの内容によって条件付きで大きく決まります)。また、プラットフォームに依存しない共通の中間「命令セット」を作成するという目的において、最近の共通中間言語(CIL) と概念的に類似しています (ただし、CIL とは異なり、他の言語の共通リソースとして使用することを意図していません)。Pコードも同様ですが、1966 年にまで遡る初期の実装であると考えられます。

多次元制御テーブルを使用してプログラム フローを決定する場合、通常の「ハードウェア」プログラム カウンター機能は、最初の (または次の) テーブル エントリへのポインターか、そのインデックスのいずれかを使用して効果的にシミュレートされます。命令の「フェッチ」には、そのテーブル エントリ内のデータのデコードが含まれます。エントリ内のデータのすべてまたは一部を最初にコピーする必要はありません。ポインターを使用できるプログラミング言語には、コンテンツへのアクセスと、実行後に次のテーブル エントリを指すようにカウンターを進めることの両方で、オーバーヘッドが少ないという 2 つの利点があります。次の「命令」アドレス (つまり、テーブル エントリ) の計算は、各テーブル エントリのオプションの追加アクションとして実行することもでき、どの段階でも ループやジャンプ命令を実行できます。

インタープリタ プログラムは、オプションで各ステージでプログラム カウンター (および命令の種類に応じたその他の関連詳細) を保存し、デバッグ、ホット スポット検出、コード カバレッジ分析、パフォーマンス分析のために実際のプログラム フローの完全または部分的なトレースを記録することができます(上記の例 CT3 および CT4 を参照)。

• 明確さ –情報表はどこにでもあり、一般の人々でもほとんどが本質的に理解できます（特に製品ガイドの障害診断表）。
• 移植性 – 100% 言語に依存しない設計が可能（インタープリタを除くプラットフォームに依存しない）
• 柔軟性 -プリミティブまたはサブルーチンを透過的に実行し、問題に合わせてカスタム設計できる機能
• 簡潔さ – 表は通常、条件/アクションのペアを並べて表示します（通常のプラットフォーム/言語実装の依存関係なし）。その結果、
  • バイナリファイル– 命令の重複が少なくなり、サイズが小さくなります
  • ソースファイル – 複数の条件文を削除することでサイズが縮小されました
  • プログラムの読み込み（またはダウンロード）速度の向上
• 保守性 – テーブルを使用すると、複数の比較に比べて保守に必要なソース行の数が少なくなることが多い
• 参照の局所性 - コンパクトなテーブル構造により、テーブルがキャッシュ内に残る
• コードの再利用 - 「インタープリタ」は通常、再利用可能です。多くの場合、まったく同じテクニックを使用して新しいプログラミング タスクに簡単に適応でき、実質的に、テーブル定義によって制御される、試行錯誤されたサブルーチンの標準ライブラリになりながら、「有機的に」成長することができます。
• 効率– システム全体の最適化が可能です。インタープリタのパフォーマンスが向上すると、通常、それを使用するすべてのアプリケーションも向上します (上記の「CT1」の例を参照)。
• 拡張可能 – インタープリタを拡張するだけで新しい「命令」を追加できる
• インタプリタはアプリケーションプログラムのように記述できる

オプション:-

• インタープリタは、テーブル自体に収集された実行時メトリックを使用して、内省的かつ「自己最適化」を行うことができます (CT3 および CT4 を参照 - エントリは降順で定期的にソートできます)。インタープリタは、実行時に収集されたメトリック (配列のサイズ、値の範囲、ソート済みまたは未ソートなど) から、最も効率的な検索手法を動的に選択することもできます。
• 動的ディスパッチ- 一般的な関数は事前にロードし、あまり一般的でない関数は最初の遭遇時にのみフェッチしてメモリ使用量を削減できます。これを実現するために、テーブル内メモ化を使用できます。
• インタプリタにはデバッグ、トレース、監視機能が組み込まれており、テストモードまたは「ライブ」モードに応じて自由にオンまたはオフに切り替えることができます。
• 制御テーブルは、（ユーザー入力またはパラメータに基づいて）オンザフライで構築され、その後、（コードを文字通り構築することなく）インタープリタによって実行されます。

• トレーニングの必要性 – アプリケーションプログラマーは通常、汎用的なソリューションを作成するためのトレーニングを受けていない

以下は、前述した 1 次元テーブルではなく、多次元テーブルでの使用に主に適用されます。

• オーバーヘッド– 仮想命令を「解釈」する必要があることによる間接レベルの追加により、いくらか増加します(ただし、通常は、効率的な直接変換、検索、および条件付きテスト技術を最大限に活用する適切に設計された汎用インタープリタによって、相殺される以上の効果が得られます。これらの技術は、他の方法では利用されない可能性があります)
• 複雑な式は、比較の目的でデータテーブルエントリに直接使用できるとは限りません。

(ただし、これらの「中間値」は、サブルーチン内で事前に計算され、その値は条件テーブルエントリで参照されます。または、サブルーチンは完全な複雑な条件テストを（無条件の「アクション」として）実行し、その結果として真理フラグを設定することで、次のテーブルエントリでテストできます。構造化プログラム定理を参照してください)

マルチウェイ分岐は重要なプログラミング手法ですが、多くの場合、非効率的な if テストのシーケンスに置き換えられています。Peter Naur は最近、プログラム フローを制御するためのテーブルの使用は、ほとんど忘れ去られてきたコンピューター サイエンスの基本的な考え方であると考えていると私に書きました。しかし、彼は、この考え方がいつ再発見されるかは、いつか明らかになるだろうと期待しています。これは、私が研究したすべての優れたコンパイラの効率の鍵です。

— ドナルド・クヌース、『go to 文による構造化プログラミング』

インタープリタ言語で書かれたプログラムには、別の見方もあります。それは、次から次へと続くサブルーチン呼び出しの連続とみなすことができます。そのようなプログラムは、実際にはサブルーチン呼び出しの長いシーケンスに展開される可能性があり、逆に、そのようなシーケンスは通常、簡単に解釈できるコード化された形式にまとめることができます。インタープリタ技術の利点は、表現が簡潔であること、マシンに依存しないこと、診断能力が向上することです。インタープリタは、コード自体の解釈と適切なルーチンへの分岐に費やす時間が無視できるほど少ないように記述できることがよくあります。

— ドナルド・クヌース『コンピュータプログラミングの芸術』第1巻、1997年、202ページ

プログラムを表現するために必要なスペースは、一般的な操作シーケンスをコンパクトに表現するインタープリタを使用することで削減できることが多い。典型的な例としては、複雑なプロトコルや語彙形式を小さなテーブルにエンコードするための有限状態マシンの使用が挙げられる。

— ジョン・ベントレー、効率的なプログラムを書く

ジャンプテーブルは、範囲テストを省略できる場合に特に効率的です。たとえば、制御値が列挙型（または文字）の場合、小さな固定範囲の値しか含めることができず、ジャンプテーブルがすべての可能な値を処理できるほど大きい場合は、範囲テストは不要です。

—  David.A. SPULER、静的探索問題としてのマルチウェイ分岐ステートメントのコンパイラコード生成

プログラムは、人間が読むために書かれる必要があり、機械が実行するために書かれるのは当然のことです。

—  「コンピュータプログラムの構造と解釈」、初版序文、アベルソン＆サスマン

フローチャートを見せて、表を隠せば、私は困惑し続けるでしょう。表を見せれば、フローチャートは必要なくなります。明らかになります。

—  「人月の神話：ソフトウェアエンジニアリングに関するエッセイ」フレッド・ブルックス

• オートマトンベースのプログラミング
• データベース中心のアーキテクチャ
• データ駆動型テスト
• 決定表
• 有限状態機械
• キーワード駆動型テスト
• ポインタ（コンピュータプログラミング）
• スイッチ文–単一の入力変数に応じて、複数のプログラムラベルの1つに分岐する多方向分岐
• スレッドコード
• トークンスレッド

• 意思決定テーブルに基づく方法論
• ドナルド・クヌース著「go to ステートメントによる構造化プログラミング」
• 静的探索問題としての多方向分岐文のコンパイラコード生成 1I994、David A. Spuler 著

• Windows PowerShell の switch ステートメントは、標準の switch ステートメントの拡張について説明します (制御テーブルに類似した機能を提供します)。
• ポインタを使用した「C」言語の制御テーブルの例、Christopher Sawtell 著、1993 年、オークランド大学コンピュータ サイエンス学部
• テーブル駆動設計 2016年6月10日にWayback Machineにアーカイブされた、DataKineticsのWayne Cunneyworthによる
• 要件から表、コード、テストまで George Brooke 著
• 曖昧な決定表の使用とコンピュータプログラムへの変換に関するコメント、PJH King と RG Johnson、ロンドン大学、ロンドン、英国
• PJH キングによる限定エントリー決定表の曖昧さ
• PJH King によるルール マスク技術による決定表のコンピュータ プログラムへの変換
• マルチウェイ分岐コード生成のスーパーオプティマイザ分析 Archived 27 February 2012 at the Wayback Machine section 3.9, page 16 index マッピング
• C/C++ での関数ポインタ配列によるジャンプ テーブル Jones, Nigel. 「関数へのポインタ配列 [2]」Embedded Systems Programming、1999 年 5 月。
• 2009 年 12 月のこの記事のページビュー統計

• 有限ステートマシンによるソフトウェアのモデリング - 実践的なアプローチ
• 一般的なコンピュータプログラミングアプリケーションのための有限状態表 1988 年 1 月 Mark Leininger 著
• MSDN:トリガーベースのイベント処理
• c2.com のコントロール テーブル