Loading article…
コンピュータ科学において、抽象マシンは、コンピュータシステムがどのように機能するかを詳細かつ正確に分析できる理論モデルです。[ 1 ]入力を受け取り、定義済みのルールに基づいて出力を生成するという点で、数学関数に似ています。抽象マシンは、ハードウェアに依存しずに正しく動作することが期待される点で、リテラルマシンとは異なります。[ 2 ]抽象マシンは、プログラムの段階的な実行を可能にするため「マシン」であり、実際の（ハードウェア）マシンの多くの側面を無視するため「抽象的」です。[ 3 ]典型的な抽象マシンは、入力、出力、および前者を後者に変換するために使用される許容される操作のセットによる定義で構成されます。これらは、純粋に理論的な理由だけでなく、現実世界のコンピュータシステムのモデルとしても使用できます。[ 2 ]計算理論では、抽象マシンは、計算可能性に関する思考実験やアルゴリズムの複雑さの分析によく使用されます。[ 3 ]抽象機械のこのような使用は、有限状態機械、ミーリー機械、プッシュダウンオートマトン、チューリング機械など、計算複雑性理論の分野において基本的である。[ 4 ]
抽象マシンは、特定の瞬間に同時に実行できる操作の数に基づいて、通常、決定論的抽象マシンと非決定論的抽象マシンの 2 つのタイプに分類されます。[ 2 ]決定論的抽象マシンは、特定の初期状態または条件が常に同じ出力を生成するシステムです。入力が出力に変換される方法にランダム性や変動はありません。[ 5 ]対照的に、非決定論的抽象マシンは、異なる実行で同じ入力に対してさまざまな出力を提供できます。[ 2 ]反復回数に関係なく同じ入力に対して同じ結果を与える決定論的アルゴリズムとは異なり、非決定論的アルゴリズムはさまざまなパスをたどって異なる出力に到達します。[ 6 ]非決定論的アルゴリズムは、決定論的アプローチを使用して正確な解を導出することが困難またはコストがかかる場合に、近似解を得るのに役立ちます。[ 7 ]
例えば、チューリングマシンは、コンピュータサイエンスにおける最も基本的な抽象マシンの一つです。 [ 2 ]これらのマシンは、任意の長さのテープ（記号列）に対して操作を実行します。その命令は、記号の変更と、マシンのポインタが現在指している記号の変更の両方を可能にします。例えば、基本的なチューリングマシンは、「記号を 1 に変換してから右に移動」という単一の命令を持つことができ、このマシンは 1 の列のみを生成します。[ 8 ]この基本的なチューリングマシンは決定論的ですが、同じ入力に対して複数のアクションを実行できる非決定論的なチューリングマシンも構築できます。[ 2 ]
抽象マシンの物理的実装（ハードウェア）の場合、プログラミング言語の命令を実行するために何らかの物理デバイス（機械的または電子的）が使用されます。しかし、抽象マシンは、抽象マシンと基盤となる物理デバイスの間のレベルで、ソフトウェアまたはファームウェアで実装することもできます。 [ 9 ]
抽象マシンは、直感的には、物理的なコンピュータの概念を抽象化したものです。 [ 13 ]実際の実行には、アルゴリズムをプログラミング言語が提供する構成要素を使用して適切に形式化する必要があります。これは、実行されるアルゴリズムがプログラミング言語の命令を使用して表現されなければならないことを意味します。[ 3 ]プログラミング言語の構文により、命令と呼ばれる有限個の構成要素を使用してプログラムを構築できます。ほとんどの抽象マシンは、プログラムストアと状態を共有しており、多くの場合、スタックとレジスタが含まれます。[ 9 ] [ 14 ]デジタルコンピュータでは、スタックは、（初期値がロードされた後）正の整数のみをカウントできるアドレスレジスタを備えたメモリユニットです。スタックのアドレスレジスタは、その値が常にスタックの最上位項目を参照するため、スタックポインタとして知られています。 [ 15 ]プログラムは一連の命令で構成され、スタックポインタは次に実行される命令を示します。命令が完了すると、スタックポインタが進みます。この抽象マシンの基本的な制御メカニズムは、実行ループとしても知られています。[ 3 ]つまり、プログラミング言語の抽象マシンとは、そのプログラミング言語で書かれたプログラムを格納および実行できるデータ構造とアルゴリズムの集合のことである。コンパイルのための中間言語ステップを提供することで、プログラミング言語の高レベルと実際のマシンの低レベルとの間のギャップを埋める。抽象マシンの命令は、特定のソース言語またはソース言語のセットの操作を実装するために必要な固有の操作に適応している。[ 9 ]
1950年代後半、Association for Computing Machinery (ACM)やその他の関連団体は、Conway のマシンなど、Universal Computer Oriented Language (UNCOL)に関する多くの提案を開発した。UNCOL の概念は優れているが、生成されるコードのパフォーマンスが低いため、広く使用されていない。 1990年代後半にJava 仮想マシンが開発されたにもかかわらず、コンピューティングの多くの分野でそのパフォーマンスは引き続き問題となる。Algolオブジェクト コード(1964)、P4 マシン (1976)、UCSD P マシン(1977)、Forth (1970) は、この種の成功した抽象マシンの例である。[ 3 ]
オブジェクト指向プログラミング言語の抽象マシンは、多くの場合スタックベースであり、オブジェクトのフィールドとメソッドへの特別なアクセス命令を備えています。これらのマシンでは、メモリ管理は多くの場合、ガベージコレクタ（プログラミング言語に組み込まれたメモリ回復機能）によって暗黙的に実行されます。 [ 16 ] Smalltalk-80（1980年）、Self（1989年）、Java（1994年）は、この実装の例です。[ 3 ]
文字列処理言語は、数値ではなく文字列の処理に重点を置いたコンピュータ言語です。文字列処理言語は、コマンドシェル、プログラミングツール、マクロプロセッサ、スクリプト言語の形で数十年にわたって存在してきました。[ 17 ]適切な抽象マシンを使用することには、実行速度の向上と移植性の向上という2つの利点があります。Snobol4とML /Iは、抽象マシンを使用してマシンの独立性を獲得した初期の文字列処理言語の注目すべき例です。[ 3 ]
SECD マシン(1964 年) や Cardelli の関数型抽象マシン (1983 年)など、関数型言語用の初期の抽象マシンでは、厳密な評価 (イージー評価または値渡し評価とも呼ばれる) が定義されており[ 3 ]、関数引数は呼び出し前に正確に 1 回評価されます。最近では、G マシン (1984 年)、Krivine マシン(1985 年)、Three Instruction Machine (1986 年) など、遅延評価 (または必要に応じた呼び出し) [ 18 ]に関する研究が主流となっており、関数引数は必要な場合にのみ最大 1 回評価されます。その理由の 1 つは、厳密な評価の効果的な実装が今ではよく理解されているため、抽象マシンの必要性が減ったことです[ 3 ] 。
述語論理（一階述語論理）は、論理プログラミング言語の基礎です。最もよく知られている論理プログラミング言語はPrologです。Prologのルールは、普遍量化「ホーン節」と呼ばれる統一された形式で記述され、これは目的の証明を発見しようとする計算を開始することを意味します。Prologプログラムコンパイルの事実上の標準となっているWarren Abstract Machine WAM (1983) [ 3 ]は、ほとんどの研究の対象となっています。WAM は、バックトラッキング (探索アルゴリズム) をサポートするために、データ統合命令や制御フロー命令などの特殊目的命令を提供します。[ 19 ]
一般的な抽象マシンは、メモリとインタプリタで構成されています。メモリはデータとプログラムを格納するために使用され、インタプリタはプログラムに含まれる命令を実行するコンポーネントです。[ 9 ]
インタープリタは、解釈する言語に固有の操作を実行する必要があります。ただし、言語の多様性を考慮すると、すべてのインタープリタに共通する操作のカテゴリと「実行メカニズム」を特定することは考えられます。インタープリタの操作とそれに付随するデータ構造は、次のカテゴリに分類されます。[ 9 ] [ 20 ]
抽象マシンには、文字列や整数などのプリミティブデータ型を操作するための操作が含まれていなければなりません。[ 9 ]例えば、整数は、物理的な抽象マシンと多くのプログラミング言語で使用される抽象マシンの両方において、ほぼ普遍的に基本データ型とみなされています。マシンは、加算や乗算などの必要な算術演算を単一のタイムステップ内で実行します。 [ 21 ]
「シーケンス制御」のための操作と構造により、プログラム命令の実行フローを制御できます。特定の条件が満たされると、プログラムの通常の逐次実行を変更する必要が生じます。[ 9 ]そのため、インタプリタは、データ操作に使用される操作（たとえば、次に実行する命令のアドレスを更新する操作）とは異なる操作によって変更されるデータ構造（次に実行する命令のアドレスを格納するために使用されるものなど）を使用します。[ 22 ]
データ転送操作は、オペランドとデータがメモリからインタプリタへ、またはその逆方向にどのように転送されるかを制御するために使用されます。これらの操作は、ストアと、ストアからのオペランドの取得順序を扱います。[ 9 ]
メモリ管理とは、データやアプリケーションを割り当てるためにメモリ内で実行される操作のことです。抽象マシンでは、データやプログラムは無期限に保持できますが、プログラミング言語の場合は、より複雑なメカニズムを使用してメモリを割り当てたり解放したりできます。[ 9 ]
抽象マシン階層はよく用いられ、各マシンは直下のレベルの機能を利用し、直上のレベルを満たすために独自の機能を追加します。最も基本的なレベルには、物理的な電子デバイスで構成されたハードウェアコンピュータを追加できます。このレベルの上に、抽象マイクロプログラムマシンレベルを導入することができます。オペレーティングシステムによって提供される抽象マシンは、マシン語で記述されたプログラムによって実装され、直上（ファームウェアレベルがない場合はハードウェアの直上）に位置します。一方で、オペレーティングシステムは、物理マシンでは利用できない高レベルのプリミティブ（たとえば、ファイルを操作するプリミティブ）を提供することで、物理マシンの機能を拡張します。ホストマシンは、オペレーティングシステムによって提供される抽象マシンで構成され、その上にJava仮想マシンとそのバイトコード言語などの中間マシンを使用して高レベルプログラミング言語が実装されます。抽象マシンによって高レベル言語（たとえばJava）に提供されるレベルは、通常、階層の最終レベルではありません。この段階で、追加サービスをまとめて提供する 1 つ以上のアプリケーションが導入されることがあります。たとえば、「Web マシン」レベルを追加して、Web 通信を処理するために必要な機能 (通信プロトコルやHTML コードの表示) を実装できます。「Web サービス」レベルはその上に位置し、相互作用プロトコルと関連するプロセスの動作の両方の観点から、Web サービスが通信するために必要な機能を提供します。このレベルでは、Web サービスに基づくいわゆる「ビジネス プロセス」の動作を規定するまったく新しい言語が開発されることがあります (ビジネス プロセス実行言語の例)。最後に、最も高いレベル (たとえば、 E コマース) には、非常に特殊で限定された機能を持つ専用アプリケーションが存在します。[ 9 ]