B,Cコンビネータとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > B,Cコンビネータの意味・解説 

B,Cコンビネータ

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

コンビネータ論理」の記事における「B,Cコンビネータ」の解説

SとKに加え、モイセイ・シェインフィンケリ(ロシア語版英語版)の論文ではBとCと呼ばれる、以下のような簡約をするコンビネータ含めた。 (C f x y) = (f y x) (B f g x) = (f (g x)) 彼は、どのようにしてSとKだけを用いてこれらを表現できるかを説明した。これらのコンビネータ述語論理ラムダ計算コンビネータ式にする際に非常に有用である。これらはハスケル・カリーと、だいぶ後に計算機における用法関連付けたデビッド・ターナーによって使われた。これらを使って、以下のように変換ルール拡張できる。 T[x] => x T[(E₁ E₂)] => (T[E₁] T[E₂]) T[λx.E] => (K T[E]) (if x is not free in E) T[λx.x] => I T[λx.λy.E] => T[λx.T[λy.E]] (if x is free in E) T[λx.(E₁ E₂)] => (S T[λx.E₁] T[λx.E₂]) (if x is free in both E₁ and E₂) T[λx.(E₁ E₂)] => (C T[λx.E₁] T[E₂]) (if x is free in E₁ but not E₂) T[λx.(E₁ E₂)] => (B T[E₁] T[λx.E₂]) (if x is free in E₂ but not E₁) BとCコンビネータを使うと、λx.λy.(y x)の変換このようになる。 T[λx.λy.(y x)] = T[λx.T[λy.(y x)]] = T[λx.(C T[λy.y] x)] (by rule 7) = T[λx.(C I x)] = (C I) (η-reduction) = C*(traditional canonical notation : X* = X I) = I'(traditional canonical notation: X' = C X) 確かに、(C I x y)は(y x)に簡約される。 (C I x y) = (I y x) = (y x) その動機は、BとCは限定されたSであるということである。Sは値を取り両方のアプリカンドを置き換えて適用を行う一方。Cはアプリカンドのみ、Bは引数のみを置き換える。そのコンビネータのための近代的な名前は、ハスケル・カリー1930年博士論文による(B,C,K,Wシステム参照)。モイセイ・シェインフィンケリ(ロシア語版英語版)のもとの論文では、今S, K, I, B,Cと呼んでいるものはそれぞれS, C, I, Z, Tと呼ばれていた。新し変換規則によるコンビネータサイズ短縮はBとCを用いなくても、この論文の節3.2のように達成できる

※この「B,Cコンビネータ」の解説は、「コンビネータ論理」の解説の一部です。
「B,Cコンビネータ」を含む「コンビネータ論理」の記事については、「コンビネータ論理」の概要を参照ください。

ウィキペディア小見出し辞書の「B,Cコンビネータ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「B,Cコンビネータ」の関連用語

B,Cコンビネータのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



B,Cコンビネータのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのコンビネータ論理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS