λx. x K S K @はてな

このブログ内に記載された文章およびコードの著作権は,すべて Keisuke Nakano に帰属します.

λx. x K S K

この日記のタイトルになっているラムダ式「λx. x K S K」は, 「*1の一点基底」と呼ばれるコンビネータで, 全ての閉ラムダ式はこのコンビネータ X = λx. x K S K から構築することができる. このことは,S と K がそれぞれ X (X X) と X X X で表現できることから確認できる.

このような一点基底は多数知られている. ベーム*2による一点基底 X = λf. f (f S (K K K I)) K *3 を用いると, S と K をそれぞれ X (X X) と X X で表すことができる. また,バーレンドレヒト*4は,X = λf. f (f S (K K)) K という一点基底を提案しており, この X により,S と K はそれぞれ X (X X X) と X X X で表現できる. 現在のところ,フォッカー*5による X コンビネータ X = λf. f S (λx y z. x) がある意味で最も簡潔といわれており,S と K はそれぞれ X (X X) と X X で表現できる. なお,メレディス*6の一点基底 X = λa b c d. c d (a (λx. d)) はフォッカーのものより簡潔といえるかもしれないが,この X で S と K を表そうとすると,

S = V (X X X (X X) (X X X X (X X X X (V V)) (K (X X X X))))
K = X X X X (X X X X (X X X (X X)) (X X)) (X X)
ここで,V = X X X X (K (X X X X))
となり,一点基底が小さければいいというものでもない.

なお,brainfuck よりぶっ飛んでいる Iota(イオタ)という 2 命令言語があるが, この言語はロッサーの一点基底に似た X = λx. x S K に基づいている. この X により,S と K はそれぞれ X (X (X (X X))) と X (X (X X)) で表すことができる. Iota における 2 命令とは一点基底 i と関数適用の前置演算子 * なので, S と K はそれぞれ *i*i*i*ii と *i*i*ii で表される. ちなみに,この関数適用を後置演算子にすれば, クリス・オカサキ*7の「キーボードの P と A しか利かなくなっちゃった事件」での括弧のいらないコンビネータ式そのものになる.

*1:λx. x) K) S) K (= S)」ではなく 「λx. ((x K) S) K」と解釈される. この式は「ロッサー((John Barkley Rosser. チャーチ・ロッサーの定理や素数分布に関するロッサーの定理などが有名.

*2:Corrado Böhm.

*3:実際には,K K K I は K I でもよいが元の文献に倣っている.

*4:Henk Barendregt.

*5:Jeroen Fokker.

*6:Carew Meredith.

*7:Chris Okasaki.