計算モデル

ウィキペディア小見出し辞書

計算モデル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/26 20:47 UTC 版)

「共通中間言語」の記事における「計算モデル」の解説

CILはオブジェクト指向かつスタックベースである。これは、たいていのプログラミング言語同様、命令のパラメータと結果が、いくつかのレジスタや他のメモリ領域に保持されるのではなく、単一のスタック上に保持されることを意味する。 x86における加算命令のアセンブリコード例を挙げる。 add eax, edx ここで、eaxとedxは汎用レジスタであり、上記はeaxにedxの内容を加算代入している。 これに相当する中間言語 (IL) のコードは以下のように表せる。 ldloc.0ldloc.1addstloc.0 // a = a + b または a += b; ここで、スタック上に2つのローカル変数がプッシュされる。加算命令が呼び出された際にオペランドがポップされ結果がプッシュされる。残った値はその後ポップされ最初のローカル変数にストアされる。

計算モデル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/17 14:39 UTC 版)

「Javaバイトコード」の記事における「計算モデル」の解説

Java仮想マシン（の計算モデル）は、いわゆるスタックマシンである。例として、次のようなx86のコードを考える: mov eax, byte [ebp-4] mov edx, byte [ebp-8] add eax, edx mov ecx, eax 2つの値を加算して別の場所にその結果をコピーする。類似のJavaバイトコードは以下のようになる: 0 iload_1 1 iload_2 2 iadd 3 istore_3 ここで、加算される2つの値はスタックに積まれ、加算命令によりスタックから値が回収され、加算され、そして結果がスタックに戻される。それからストア命令がスタックのトップの値を変数の場所へ移動する。命令の前にある数は、メソッドの最初から各命令のオフセットを単に表しているだけである。このスタック指向モデルは、この言語のオブジェクト指向の側面にも及ぶ。例えば、"getName()" というメソッドの呼出しは以下のようになる: Method java.lang.String getName() 0 aload_0 // "this" オブジェクトが変数テーブルの場所0にストアされる。 1 getfield #5 // この命令はスタックのトップからオブジェクトをポップし、 // そのオブジェクトから指定されたフィールドを取得し、 // そしてスタックにそのフィールドをプッシュする。 // この例では、"name" フィールドがこのクラスの定数プールの5番目に対応する。 4 areturn // メソッドからスタックのトップのオブジェクトを返す。

計算モデル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/09 06:43 UTC 版)

「計算理論」の記事における「計算モデル」の解説

詳細は「計算モデル」を参照 ここでは例として、計算可能性がチューリングマシンと同等な計算モデル（「チャーチ＝チューリングのテーゼ」の記事を参照）のいくつかを示す。 ラムダ計算 計算を1つの初期ラムダ式（入力を分離したい場合は2つのラムダ式）と有限個のラムダ項で表す。各ラムダ項は前のラムダ項にβ簡約を適用したものである。 組合せ論理 ラムダ計算とよく似ているが、例えばラムダ計算では正規の形式ではない不動点演算子 Y は組合せ論理では正規に組み込まれているといった違いがある。 μ再帰関数 複数の自然数を引数として1つの自然数を返す関数であり、原始再帰関数に基づいて構築され、それにμ再帰を施したもの。 マルコフアルゴリズム 文字列に一種の文法規則を適用する文字列書き換え系。 レジスタマシン コンピュータを抽象化したもの。多くの場合、無限サイズの自然数を格納できるレジスタを持ち、命令数は非常に少ない。チューリングマシンと比較すると無限のメモリが欠けているが、レジスタが無限サイズの自然数を格納できるので、それで代替される。 P′′ （en:P′′）チューリングマシンと同様、無限長のテープに記号を記録するが、チューリングマシンにおける有限状態オートマトンに相当するものを、固定長でループの記述が可能な命令の列によって記述する。これを元に、命令セットを理論向けから実装向けに大幅にアレンジして設計されたプログラミング言語がBrainfuckである。 計算理論は、チューリングマシンより弱い（制限された）計算モデルを対象とすることもある。これらに関する理論を、「オートマトン(の)理論」と呼ぶことがある（この文脈では「オートマトン」とは、チューリングマシンより弱い（制限された）機械の総称である）。 正規表現は文字列パターンを指定するのによく使われる。また、それと等価な有限オートマトンは回路設計などに使われる。文脈自由文法はプログラミング言語の構文を定義するのに使われる。非決定性プッシュダウン・オートマトンは文脈自由文法と等価である。原始再帰関数は再帰関数のサブクラスを定義したものである。モデルが異なれば得意分野も異なる。 また、形式言語とその文法と、計算モデルとの間には対応する関係があり、計算可能性＝表現力について包含関係があることが知られている。チョムスキー階層及び形式言語の階層の記事を参照のこと。