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

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


Y - コンビネータを SKI に変換してみた。Y - コンビネータの定義は次のようになる。

Y = λf.(λx.fxx)(λx.fxx)

手順は次のようになる。まず、lambda.hs を起動して、:load コマンドで設定ファイルを読み込み SKI コンビネータを使えるようにする。

C:\Users\****>runghc lambda.hs
lambda> :load
filename: defined.txt
lambda>

Y - コンビネータの body 部分は λx.fxx の自己言及になっているのでまず fxx を SKI コンビネータに変換したあと Yf = S(fxx)(fxx)f を作った。最後に (Yg) 3 で3の階乗を計算した。g は設定ファイルに記述した階乗のプログラム。

lambda> (f (x x)) ...... fxx を取り出す。
(f (x x))
lambda> (((K f) x) (((S I) I) x)) ...... f -> (K f) x, xx -> SIIx へ変形
(f (x x))
lambda> (((S (K f)) ((S I) I)) x) ...... S(Kf)(SII)x で x をくくりだす
(f (x x))
lambda> (((((K S) f) (K f)) ((S I) I)) x) ...... SKY -> (KSf)(Kf) に変形
(f (x x))
lambda> (((((S (K S)) K) f) ((S I) I)) x) ...... S(KS)Kf で f をくくりだす
(f (x x))
lambda> (((((S (K S)) K) f) ((K ((S I) I)) f)) x) ...... (S(KS)Kf)(K(SII)f) に変形
(f (x x))
lambda> ((((S ((S (K S)) K)) (K ((S I) I))) f) x) ...... S(S(KS)K)(K(SII)f で f をくくりだす
(f (x x))
lambda> (= M ((S ((S (K S)) K)) (K ((S I) I)))) ....... M = S(S(KS)K)(K(SII))
lambda> (= Ys ((S M) M))) ...... Ys = SMM
lambda> ((Ys g) 3) ...... (Ys g) 3 で factorial 3 を計算
(ls.(lz.(s (s (s (s (s (s z)))))))) ...... factorial 3 = 6

SKI - コンビネータでも自己言及関数のテストができた。

by tnomura9 | 2019-10-01 18:28 | Haskell | Comments(0)
<< Git とは何か ラムダ計算 SKI コンビネータ 3 >>