人気ブログランキング |

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


ラムダ記法の関数を SKI コンビネータで表すのは機械的にできる。次の3つのルールを機械的に適用していくだけだ。

1)λx.M = M ... λ抽象は外して良い
2)((x z) (y z)) = (S x y) z ..... (x z) (y z) の形の関数適用は変数 z をくくり出せる。
3)x = I x ..... 変数 x だけの項は (I x) の形に変えることができる。
4)a = (K a) x ..... 項 a は (Ka) x の形に変えることできる。このとき、(K a) を関数適用する x は任意の項を使うことができる。

このルールに従って、前回も紹介した、

λxyz.x(yz)

を SKI コンビネータで置き換えてみると、次のようになる。

lambda> (lx.(ly.(lz.(x (y z)))))
(lx.(ly.(lz.(x (y z)))))
lambda> (x (y z)) ...... ルール1)を使ってラムダ抽象を除去して body だけにする。
(x (y z))
lambda> (((K x) z) (y z)) ..... ルール4)を使って x --> (K x) z にする。
(x (y z))
lambda> (((S (K x)) y) z) ..... ルール2)を使って z をくくりだす。
(x (y z))
lambda> (((((K S) x) (K x)) y) z) .... ルール4)を使って S -> (K S) x にする。
(x (y z))
lambda> (((((S (K S)) K) x) y) z) ..... ルール2)を使って x をくくりだす。
(x (y z))
lambda> (= M ((S (K S)) K)) .... 求めるコンビネータは S(KS)K である。
lambda> (((M x) y) z)
(x (y z))

ラムダ記法の関数は、atom か、関数抽象か、関数適用のどれかで記述されているので上のルールを適用していけば、どのようなラムダ項も SKI コンビネータで記述することができる(はずだ)。

しかし、上のルールは変数が1回しか現れないときは機械的に適用できるが、(x (x x)) の様に同じ変数が何回も現れる場合は適用できるのだろうか。

lambda> (x (x x))
(x (x x))
lambda> (x ((I x) (I x)))
(x (x x))
lambda> (x (((S I) I) x))
(x (x x))
lambda> ((I x) (((S I) I) x))
(x (x x))
lambda> (((S I) ((S I) I)) x)
(x (x x))
lambda> ((S I) ((S I) I))
(lz.(z (z z)))

問題ないようだ。

by tnomura9 | 2019-09-30 18:54 | Haskell | Comments(0)
<< ラムダ計算 SKI コンビネータ 4 ラムダ計算機 設定ファイル >>