人気ブログランキング | 話題のタグを見る

ラムダ計算 SKI コンビネータ


コンビネータとはラムダ式の body の変数が全て束縛変数となるラムダ式(関数)のことだ。例えば λx.x は引数の値をそのまま返す恒等関数だが、ラムダ抽象された変数は x で body の部分の変数も x しかない。

lambda> ((lx.x) a)
a

このようなコンビネータには名前がつけられているものがある。上の恒等関数にも名前がつけられており I (Identity combinator) コンビネータと呼ばれる。

I = λx.x

ラムダ計算機で検証すると次のようになる。

lambda> (= I (lx.x))
lambda> (I a)
a

また、K コンビネータ (Constrant combinator) は2つの引数を持ち、第一の引数を渡すと、引数1個の関数になる。この関数は引数にどのような値を与えても最初に与えられた第1引数の値を返す。このため定数関数と呼ばれている。

K = λxy.x

ラムダ計算機では次のようになる。

lambda> (= K (lx.(ly.x)))
lambda> ((K a) x)
a

S コンビネータ (Substitution Combinator) は構造が複雑で、第3引数に第1引数を関数適用したものを、第3引数に第2引数を関数適用したものに関数適用する。

S = λxyz.(xz)(yz)

ラムダ計算機では次のようになるが、あまり有り難みがわからない。

lambda> (= S (lx.(ly.(lz.((x z) (y z))))))
lambda> (((S x) y) z)
((x z) (y z))

実は、この SKI コンビネータには特別な性質がある。この3つを組み合わせると、ラムダ抽象を使わずにどのようなラムダ式でも記述できるのだ。そこで、それを検証してみることにする。

先ず、恒等関数だが、これは I コンビネータそのものだ。

lambda> I
(lx.x)
lambda> (I a)
a

また、K コンビネータは論理式の true そのものだ。

lambda> K
(lx.(ly.x))
lambda> ((K a) b)
a

そこで K コンビネータを I コンビネータに関数適用すると、それは false になる。

lambda> (K I)
(ly.(lx.x))
lambda> (((K I) a) b)
b

true と false ができたので、条件分岐を作ってみたいが、ラムダ抽象を使わずにどうやって作ればいいのだろうか。条件分岐は引数が c x y の3つなので I コンビネータや K コンビネータでは役不足だ。それで、S コンビネータを使うことを考えてみる。作りたいラムダ式は次のようなものだ、

λcab.cab

このラムダ式の body の部分を取り出すとこれは ((c a) b) である。これは変数 a を変数 b と c に順に関数適用していることを示している。

lambda> ((c a) b)
((c a) b)

そこで I コンビネータを c に関数適用すると次のようになる。

lambda> (((I c) a) b)
((c a) b)

すなわち I コンビネータが条件分岐を表す関数である。I = λx.x なので I は引数を一つしか取らないが、(I a) の値は関数なので引数を取れる。したがって、I は結果的に3つの引数を取ることが可能なのだ。これがラムダ式が高階関数であることの威力だ。

lambda> I
(lx.x)
lambda> (I true)
(lx.(ly.x))
lambda> (((I true) a) b)
a

Ω - コンビネータ λ.(x x) は最も単純な自己言及関数だが、これも SKI コンビネータで表現できる。Ω - コンビネータの body の部分を次のように等価なラムダ式に置き換えていけばいい。

lambda> (x x)
(x x)
lambda> ((I x) (I x))
(x x)
lambda> (((S I) I) x)
(x x)

したがって、Ω = SII である。

ラムダ式を SKI コンビネータで表すと、束縛変数が表に出てこない。ラムダ抽象を使わずに関数適用のみでラムダ式を記述することができるからだ。スタックにプッシュしたデータをやり取りする場合のように、束縛変数の名前が不要になってしまう。すなわち、α変換に関して考慮しなくて良くなる。コンビネータにはこのようにプログラミングのフレームワークを変える性質もあるようだ。そうして、この SKI コンビネータはラムダ記法と同じ様にチューリング機械と同等の表現力がある「チューリング完全」らしい。

SKI コンビネータのうち I コンビネータは次のように SKK で定義できるので、理論的には S コンビネータと K コンビネータだけで全ての関数が表現できる。しかし、上の例でも分かるように I コンビネータを利用したほうが使いやすい。

lambda> ((S K) K)
(lz.z)
lambda> (((S K) K) hello)
hello


by tnomura9 | 2019-09-28 22:21 | Haskell | Comments(0)
<< ラムダ計算 SKI コンビネータ 2 ラムダ計算 括弧の対応 >>