combinator
コンビネータとは自由変数を含まないλ項のことをいいますが、Yコンビネータ以外あまり取り上げられていない気がするのですが、これも100年に1度の金融危機の影響かとか、WBC楽しみですねだとか、そういえば今年雪祭り行けなかったんですよとか、最近携帯変えましたとか色々あるのですが、自分の練習もかねて、そんなコンビネータ達と戯れたいと思います。
沢山ある！
Y以外にも広く知られている（？）コンビネータはいっぱいあるようですが、その中からいくつか。
- I ≡ λx.x
- K ≡ (λx.(λy.x)) //以下、簡単に λx y.x と書きます
- F ≡ λx y.y
- M ≡ λx.xx
- S ≡ λx y z.xz(yz)
- B ≡ λx y z.x(yz)
- C ≡ λx y z.xzy
- L ≡ λx y.x(yy)
- Y ≡ (λx.xx)(λx.xx) (SLL)
（当てるアルファベットが違うのはたまに見かけますが、大体こんな感じ）
true, false, if を表現してみる
TRUE = λx y.x (K)
FALSE = λx y.y (KI,F)
IF = λx y z.xyz
falseがなぜ空気いらない（Kuuki Iranai）なのか少し補足。
KI => (λx.(λy.x))I
=> (λy.I)
Iは(λx.x)なので、
=> (λy.(λx.x)).
これを簡単に書くと λy x.x となります。 F コンビネータと一緒！
これらをF#(OCaml)で書いてみる。
> let K x y = x;; val K : 'a -> 'b -> 'a > let I x = x;; (* id関数とほぼ同じ *) val I : 'a -> 'a > let IF x y z = x y z;; val IF : ('a -> 'b -> 'c) -> 'a -> 'b -> 'c (* テスト用関数。"foo"の時に真を返して、そうでなければ偽。 *) > let isFoo = function - | "foo" -> K - | otherwise -> (K I) ;; val isFoo : string -> ('a -> 'a -> 'a) > IF (isFoo "bar") "true!" "false...";; val it : string = "false..." > IF (isFoo "foo") "true!" "false...";; val it : string = "true!"
Y!
先に挙げたコンビネータのうち、Yは少しややこしいのでここでそれを。
不動点オペレータ(fixed-point operator)などとも呼ばれるY氏。
これを以下のように定義してみる。
fixf = (λx.f(xx))(λx.f(xx))
燃えさかる赤いλ式に、クールなブルーλ式を渡してみると・・・
=> f( (λx.f(xx))(λx.f(xx)) )
となるのが分かります。
ん？下線部分どこかで見たことあるような・・・？*1
なんとfixの定義！
=> f( fixf )
これが、 f(f(f(fixf))) などと括弧いいことになっていくわけです。
fix式は関数fの引数として渡されるわけだから、それを評価するかどうかはfが決めます。なので、書いた瞬間コンソールに無限に文字列が表示される、といったことにはなりません。
色々な言語で・・・
色々な言語を勉強中なのであれこれ書いてみます。（実はこれがメインだったりする）
意外なことに、まずSmalltalkで！(Dolphin Smalltalk)
SとYを定義してみた。
| S | S := [:x :y :z | x value: z value: (y value: z)]. ^ S value: [:x :y | x*y] value: [:x | x+10] value: 10. "=> 200" | Y | Y := [ :f | [:x | f value: [:a | (x value: x) value: a]] value: [:x | f value: [:a | (x value: x) value: a]] ]. ^ ( Y value: [:f | [:n | (n > 1) ifTrue: [n * (f value: (n-1))] ifFalse: [1]]] ) value: 5 "=>120"
何とか動いた〜。
お次はLisp。
Common Lispでやると爽やかじゃなくなるので、まずSchemeから。
> (define fix (lambda (f) ((lambda (x) (f (lambda (arg) ((x x) arg)))) (lambda (x) (f (lambda (arg) ((x x) arg)))) ))) ;; こっちの方がまだ見やすい・・・？ > (define (Y f) (let ((e (lambda (x) (f (lambda (y) ((x x) y)))))) (e e) ))
> (define foo (fix (lambda (f) (lambda (n) (if (= n 0) '() (cons n (f (- n 1))) ))))) > (foo 10) (10 9 8 7 6 5 4 3 2 1)
爽やかでしたね。仕方ないので次はCommon Lispで書いてみることに
CL-USER> (setq Y (symbol-macrolet ((e #'(lambda (x) (funcall f #'(lambda (&rest args) (apply (funcall x x) args) ))))) #'(lambda (f) (funcall e e)) )) CL-USER> (setq fn #'(lambda (f) #'(lambda (x acc) (if (< x 1) acc (funcall f (1- x) (cons x acc)) )))) CL-USER> (funcall (funcall Y fn) 10 nil) (1 2 3 4 5 6 7 8 9 10)
こっちは、&rest と apply を使うことで複数個の引数を使えるようにした。
ちなみにCommon Lispのlabelsや、Schemeのletrecは不動点オペレータとして見ることもできる。
お次はHaskell。
Prelude> let y f = let x = f x in x Prelude> y (\f n -> if n>1 then n * f (n - 1) else 1) 5 120
遅延評価すごい！ let x = f x とかシビれる。
勝手にカリー化してくれるので複数の引数にも対応できます。
そんなHaskellには標準で不動点オペレータが用意されているのでした。
Prelude> :m Control.Monad.Fix Prelude Control.Monad.Fix> :t fix fix :: (a -> a) -> a Prelude Control.Monad.Fix> fix (\f n -> if n>1 then n * f (n - 1) else 1) 5 120
最後に、Ocaml.
以前こんなの見つけたのですが、自分自身まだ良く理解してないので貼っておいて勉強します・・・。
type使えば何とかできるんじゃないかな？と漠然と思っていたけど、想像と全然違った。。
type 'a recc = { out : 'a recc -> 'a } let inn y = { out = y } let out z = z.out let y f = (fun x a -> f (out x x) a) (inn (fun x a -> f (out x x) a))Fixed-point combinator - Wikipedia
あと、いげ太さんの日記にもメモがあるので、あわせて読みたい。
結論
長々書いておいて結局何が言いたかったかというと、
KYは空気読めないのではなく、KコンビネータとYコンビネーｔ（ｒｙ
若い女の子の間ではλ計算とか当たり前らしい・・・！
僕自身初心者なので変なところとかあるかも。。そんな時はご指摘なんて頂けると嬉しいです。
*1:式の部分をリンクかと思って何気なくマウスオーバーした人はコメント欄にて懺悔すること
