|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ コンビネータ ： [こんびねーた] (n) combinator, (n) combinator ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計算 ： [けいさん] 1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast
SKIコンビネータ計算は型無しラムダ計算を単純化した、ひとつの計算モデルである。このモデルは、ある種のプログラミング言語と考えることができるが、人間によるソースコードの記述には適さない（難解プログラミング言語には時折採用される）。その代わり、このモデルは非常に単純なチューリング完全な言語であるため、アルゴリズムの数学理論においては重要である。また関数型言語を実行する抽象機械のモデルとして使っている例もある〔D. A. Turner ''A new implementation technique for applicative languages''〕。 ラムダ計算におけるあらゆる演算は、SKIにおいて3つの定数記号S, KおよびI（これらを''コンビネータ''と呼ぶ）および変数記号によって表現できる。2引数の関数適用演算のみを持つ形式言語の構文木と考えれば、定数記号と変数記号を葉とする二分木と捉えることもできる。 実際には、 I はモデルを簡単にするために導入されたものであり、SKIシステムを展開するにはSとKの2つで十分である。 == 素朴な説明 == 非形式的には、またプログラミング言語のジャーゴンとして、木 (''xy'') は“関数” ''x'' に“引数” ''y''を適用したものと考えられる。評価されるとき（すなわち関数に引数を“適用”するとき）、木は“値を返す”、すなわち別の木に変形する。当然“関数”も“引数”も“値”もそれぞれ葉もしくは二分木である。簡単のために関数適用は左結合であるものとし、無駄な括弧は省略するのが普通である。このようにしても曖昧性はない。 評価演算は次のように定義される： （''x''、''y'' および ''z'' は任意の式とする） I(Identity combinator) は引数を返す： : I''x'' = ''x'' K(Constant (独Konstant) combinator) に''x''だけを適用した場合、任意の引数に対して''x''を返す1引数の定数関数 K''x''を得る： : K''xy'' = ''x'' S(Substitution combinator) は3つの引数を取って、1つ目の引数に3つ目の引数を適用し、その結果に2つ目の引数に3つ目の引数を適用した結果を適用する。簡単に： : S''xyz'' = ''xz''(''yz'') 計算の例： SKSK は S-規則によって KK(SK) に評価される。次に KK(SK) は K-規則によって K に評価される。これ以上適用できないので、ここで計算は終了する。 任意の木 ''x'' および ''y'' について、 SK''xy'' はいつでも ''y'' と評価されることがわかる。すなわち SK''x'' と I は“関数として同値”（外延的同値）であると考えられる。任意の式のすべての I の出現を (SKK) や (SKS) あるいは (SK) に置き換えることができ、結果の式は元の式と外延的に同値である。すなわち I は 糖衣構文にすぎない。 実は、ただ1つのコンビネータを用いて完全な体系を定義することも可能である。1つの例としてChris Bakerによるιコンビネータがある。定義は次の通り： : ι''x'' = ''x''SK --> 計算の例： SKSK は S-規則によって KK(SK) に評価される。次に KK(SK) は K-規則によって K に評価される。これ以上適用できないので、ここで計算は終了する。 任意の木 ''x'' および ''y'' について、 SK''xy'' はいつでも ''y'' と評価されることがわかる。すなわち SK''x'' と I は“関数として同値”（外延的同値）であると考えられる。任意の式のすべての I の出現を (SKK) や (SKS) あるいは (SK) に置き換えることができ、結果の式は元の式と外延的に同値である。すなわち I は 糖衣構文にすぎない。 実は、ただ1つのコンビネータを用いて完全な体系を定義することも可能である。1つの例としてChris Bakerによるιコンビネータがある。定義は次の通り： : ι''x'' = ''x''SK 実は、ただ1つのコンビネータを用いて完全な体系を定義することも可能である。1つの例としてChris Bakerによるιコンビネータがある。定義は次の通り： : ι''x'' = ''x''SK 'SK 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「SKIコンビネータ計算」の詳細全文を読む スポンサード リンク
|