Y Combinator応用

Scheme

特に応用はないのかなあと思っていたんだけど、全然そんなこともないようです。
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
ということで、上記サイトを参考にY Combinatorをメモ化して、再帰関数のメモ化を手軽にできるようにしてみる。

関数のメモ化

(define (memoize func)
  (let* ((cache (make-hash-table 'equal?))
	 (getCache (cut hash-table-get cache <> #f))
	 (setCache! (lambda (key value) (hash-table-put! cache key value) value)))
    (lambda args
      (cond [(getCache args) => values]
	    [else (setCache! args (apply func args))]))))

という関数を作って好きな関数を引数に渡すと、メモ化された関数が返値として得らまする。ただ再帰関数では、関数の中でそのまま自分自身を呼び出してしまうと、メモ化されないという問題があります。
それを解決しようとすると、再帰関数に手を入れる必要が出てきます。そこでY Combinaterにメモ化機能を組み込むと、再帰関数側では何も考えずに、メモ化することができるようになります。

Y Combinator

U Combinatorというものがあって、次のように定義されるらしい。

(define (U proc)
  (proc proc))

引数として与えられた関数をそれ自身を引数として呼び出すこいつが何物かあんまりわかっていないのですが、これを使うと、Y Combinatorの定義が簡単になるようです。

(define (Y proc)
  (U (lambda (p) (proc (lambda args (apply (p p) args))))))

Y コンビネータのメモ化

ここでYコンビネータのメモ化をかんがえると、procが次呼び出す関数、すなわちprocの引数に渡されている(lambda args (apply (p p) args))をメモ化すればいいということがわかります。
先ほどのmemoize関数のコードをほぼ流用すると、メモ化されたY Combinatorは次のように書くことができます。

(define (memoizeY proc)
  (let* ((cache (make-hash-table 'equal?))
	 (getCache (cut hash-table-get cache <> #f))
	 (setCache! (lambda (key val)
		      (hash-table-put! cache key val)
		      val))
	 (memoize (lambda (proc) (lambda args
				   (cond [(getCache args) => values]
					 [else (setCache! args (apply proc args))])))))
    (U (lambda (p) (proc (memoize (lambda args (apply (p p) args))))))))

ということでこいつが上手く動いているのかをフィボナッチ関数を使って確認してみる。再帰と言えばフィボナッチ、フィボナッチといえば再帰。

(define (fib proc)
  (lambda (i)
    (case i
      ((0 1) i)
      (else (+ (proc (- i 1)) (proc (- i 2)))))))

(time ((memoizeY fib) 1000))

;(time ((memoizeY fib) 1000))
; real   0.009
; user   0.015
; sys    0.000

ちゃんと動いてます。というわけで手軽に再帰関数がメモ化できるようになりました。よい応用例が思いつきませんが、なかなか便利なような気がします。

メモ化機能を切り離す

先ほどのメモ化Y Combinatorをじーっと眺めていると、メモ化の機能はprocが引数として受け取る関数に適用されているだけということがわかります。
つまり、procが受け取った引数に対してメモ化をしてくれれば、特別なメモ化されたY Combinatorを用意しなくても良いと言うことがわかります。

Schemeにはcomposeという関数合成を行う関数があるようです。これは複数の関数を引数にとり、それらを合成した関数を作成します。

(define (compose F G)
  (lambda (arg) (F (G arg))))

こんな感じですね。多分。

Y Combinatorの引数は、関数を引数にとって関数を返す高階関数なので、この高階関数に別の機能をもった関数（この場合はメモ化）を高階関数をcomposeを使って合成すると、あらびっくりメモ化再帰が実現できてしまうという寸法です。

(define (make-memoizer)
  (let* ((cache (make-hash-table 'equal?))
	 (getCache (cut hash-table-get cache <> #f))
	 (setCache! (lambda (key value) (hash-table-put! cache key value) value)))
    (lambda (func)
      (lambda args
	(cond [(getCache args) => values]
	      [else (setCache! args (apply func args))])))))

(time ((Y (compose fib (make-memoizer))) 1000))

;(time ((Y (compose fib (make-memoizer))) 1000))
; real   0.012
; user   0.016
; sys    0.000

うまくいっているようですね。なぜ先ほどのmemoizeをそのまま使わなかったかというと、先ほどのmemoizeでは呼ばれるたびに新しいcacheが作成され、メモ化が正常に行われないためです。解決するには、memoizeの外にcacheがある必要がありますが、cacheをグローバルに置くのも気持ち悪いなーということで、memoizeを生成するmake-memoizerという関数を作りました。

これでフィボナッチ数列を求めるコードと、再帰のコードと、メモ化のコードが綺麗に分離することができました。
合成する関数はメモ化に限らないので、好きな機能を組み込むことができます。上記の参考サイトでは、途中経過のプリント、自動分散化、投機実行など面白そうなことをやっています。ご参照ください。

感想

とくに先があるとは思っていなかったのですが、こうやってみるとY Combinatorも色々面白いんですねえ。ただY Combinatorを使うと末尾再帰されない気もするので、適用する問題を選ばなければならない気もします。

Y Combinater

Scheme

そういや昔Y Combinaterについて瞬間最大風速的にいろんな人が言及していたことがあったけど、あのときは興味もないしよくわからないしでスルーしていたんですが、Schemeの勉強を始めたんだし、まじめに考えてみようと思いました。
結果的にわかったような気分ですが、なんか一番大事なキモを置き忘れているようで微妙にモヤモヤが。あと、再帰と高階関数になじんでいないときついですね、これ。

とりあえずまとめておく。間違っていたら誰か教えて欲しい...

参考にしたサイト

Y Combinator
Yコンビネータを読み解こう - ボクノス

何がしたいか

定番ですが階乗を再帰で書くと次のようになります。

(define (fact i)
  (if (= i 1)
      i
      (* (fact - i 1))))

しかしこれはfactの定義の中にfactが出ているという自己言及の構造になっているので、λ計算で表現することができない。じゃあどうやって自分の名前を使わずに再帰関数を定義しようかというのが、問題です。

継続渡しで

うーん、とりあえず定義の中からfactをなくすということで、継続渡しスタイルにしてみよう。

(define (fact i proc)
  (if (= i 1)
      i
      (* i (proc (- i 1) proc))))

呼び出し側はこれでも良いけど、

(fact 4 fact)

一応適当な関数を作って、くくりだしておこう。

(define (l proc)
  (lambda (i) (proc i proc)))

(print ((l fact) 4)) => 24

やった！ 計算できた！

fact-makerを使って

で終わるとY Combinatorの出番がなくなってしまうので、参考にしたサイトに従って、factが次に呼び出す関数procを引数に、factを生成する高階関数fact-makerを定義する。

(define (fact-maker proc)
  (lambda (i) (if (= i 1)
		  i
		  (* i (proc (- i 1))))))

このfact-makerを使うと、factは次のように定義できる。

(define fact (lambda ()fact-maker fact))

(lambdaで囲っているのは、fact定義時に(fact-maker fact)が評価されると無限ループに陥るため)

つまり

fact = (fact-maker fact)

これを無限に展開し続けると

fact = (fact-maker (fact-maker fact)) = (fact-maker (fact-maker (fact-maker fact))) = ... = (fact-maker (fact-maker (fact-maker (fact-maker .......)))) = ...

という形の再帰構造になる。でもこのままだと、factの定義からfactを消すためには、fact-makerを自身に無限に適用し続けないといけない。
ここでもし、関数を引数にとり、(Y p) = (p (Y p))となる関数Yがあるとする。するとこのYをfact-makerに適用すると、

(Y fact-maker) = (fact-maker (Y fact-maker)) = (fact-maker (fact-maker (Y fact-maker))) = ... = (fact-maker (fact-maker (fact-maker (fact-maker ......))))

というように展開される。
これは、上記のfactの定義と同じになる！

つまり

fact = (fact-maker (Y fact-maker)) = (Y fact-maker)

となる。
この関数を引数にとる再帰的な関数YをY Combinatorと呼ぶらしい。

Y Combinatorの導出

さて、では(Y p) = (p (Y p))という関数はなんだろう。というのをこの定義から導き出す方法がわかんなかったので、参考サイトを参考に作ってみよう。

factも面倒くさいので、単純に無限に自分を呼び出し続ける関数recを考える。評価すると無限ループします。試していないけど、末尾最適化されるので、永遠にループし続けるはず。

(define (rec i)
  (rec i))

(rec 10) ;=> 無限ループになるはず

;1.fact-makerと同じスタイルにする。
(define (rec-maker proc)
  (lambda (i) ((proc proc) i)))

((rec-maker rec-maker) 10) ;=> 無限ループになるはず

;2.(proc proc) => (lambda (arg) ((proc proc) arg))に変形。
(define (rec-maker proc)
  (lambda (i) ((lambda (arg) ((proc proc) arg)) i))

((rec-maker rec-maker) 10) ;=> 無限ループになるはず

;3.(lambda (arg) ((proc proc) arg)) を fact0の外にくくり出す。
;元のrec-makerをrec0に変名。
(define (rec0 proc)
  (lambda (i) (proc i))

(define (rec-maker proc)
   (rec0 (lambda (arg) ((proc proc) arg))))

;4.(rec-maker rec-maker) は次のように展開される。
((lambda (proc) (rec0 (lambda (arg) ((proc proc) arg))))
 (lambda (proc) (rec0 (lambda (arg) ((proc proc) arg)))))

;5.proc と rec0をくくりだして名前をつける。
(define Y
 (lambda (f)
  ((lambda (proc)
   (f (lambda (arg) ((proc proc) arg))))
  ((lambda (proc)
   (f (lambda (arg) ((proc proc) arg))))))))
 
((Y rec) 10) ;=> 無限ループになるはず

実行しても無限ループになるから試していません！ 括弧の対応も間違っているかも。素直にfactでやればよかった。

わかりやすいようにしてみる。（これは意味的には変わらないですが、実行順序の関係で無限ループになる）

(define (Y f)
 ((lambda (p) (f (p p))) (lambda (p) (f (p p)))))

展開すると、たしかに(Y p) = (p (Y p))となる。

(Y f) => ((lambda (p) (f (p p))) (lambda (p) (f (p p))))) => (f ((lambda (p) (f (p p))))) (lambda (p) (f (p p))))))) => (f (Y f))

(p p)がキモですね。こいつが自分自身を複製するおかげで、無限に展開し続けられます。
任意の長さの引数をつけるように、applyをつかうようにしておく。

 (define (Y proc) ((lambda (p) (proc (lambda args (apply (p p) args))))
 		  (lambda (p) (proc (lambda args (apply (p p) args))))))

使用例

factばかり計算させるのもY Combinatorに申し訳ないので、foldを定義してみる。

(define (my-fold proc init lst)
  ((Y (lambda (self) (lambda (proc init lst)
		       (if (null? lst)
			   init
			   (self proc (proc (car lst) init) (cdr lst)))))) proc init lst))
			   
(print (my-fold + 0 '(1 2 3 4))) ;=> 10

おー、動いてる動いてる。というわけで好きな再帰関数が自分の名前を使わずに定義できるようになりました。
まだ調べていないけどletrecのマクロ定義とかも似たようなことしているんじゃないかと思ってます。

感想

実用的にはあんまり必要ないんでしょうけど、なかなか頭の体操になって面白かったです。正確な理解かどうかは自信はないですが。高階関数はなかなか面白いですね。本当は学生時代に勉強したはずなんですけどね... ちゃんと理解していなかったから試験終了と同時に忘れたんだろうなあ。

というわけで学生時代にざるですくってほとんどこぼれていった知識を、気が向いたらまた掬い直したいなあと思いました。

情報源

Scheme

WindowsへのGaucheのインストール方法

僕はCygwinにGaucheを入れて使ってます。
考えすぎると頭がかゆくなる Meadow + cygwin + gauche でwindowsにおける快適なscheme実行環境を構築
が非常に参考になりました。書いていることそのままやればインストールできます。

プログラミング言語Gauche

オライリーの本も買いましたが、開くのが面倒くさいときはこっち見てます。構成が違うのと、それぞれ記述があったりなかったりするように見えます。
http://karetta.jp/book-cover/gauche-hacks

Gauche ユーザリファレンス

Gaucheのユーザリファレンス。よくわからないときはこれを見ます。非常に簡潔な記述なので、僕は読んでもやっぱりわかんなかったりします。
Gauche Users’ Reference: Top

Practical Scheme

Gaucheの作者、川合氏のサイト。掲載されている文書を読むと、Lispを学ぶ欲求がわいてきます。
http://practical-scheme.net/index-j.html

OnLisp

Lispのマクロすごいよ！ という本。CommonLispよくわからないんですが、継続周りはSchemeの説明があったので参考になりました。
http://www.komaba.utmc.or.jp/~flatline/onlispjhtml/

Structure and Interpretation of Computer Programs(SICP)

有名な教科書。読んでません。日本語訳は質が悪い＆高いと評判なので、ただで読める英語版はいいですね。
http://mitpress.mit.edu/sicp/full-text/book/book.html

ほかに見つけたら足していこう。

■

そういえばはてなダイアリーってエントリー単位じゃなくて日にち単位で書き込むんだったか。ダイアリーと言うだけのことはあるけど、違和感すごいある。あとアメリカから&ホテルの回線細いからかもしれないけど、遅い。

Scheme

Scheme

勉強がてらSchemeをはじめました。
関数型言語をちゃんと勉強しないとなーと思ってHaskelを始めたけど全然全く意味がわからない上に、特にやりたいことが見つからず挫折したのが三年前。Scalaがずいぶんはやっているらしい、よし、やってみるかと思って手を出したけどやっぱりHaskelと同様に挫折したのが半年前。そして最近Emacsテクニックバイブルを参考にEmacsを設定してみたらこれまで使っていたEmacsは何だったんだというぐらい便利になったので、自分でもカスタマイズをちゃんとできるようになりたいという欲求が高まったんだけど、Emacs-Lispがさっぱりわからないという現実に打ちのめされ、よし勉強するかときめたはいいがいまいちしっくりくる本がなくてどうしようと悩んだ結果、そうだCommonLispとかSchemeとかなら本も色々ありそうだ、といことでとりあえず言語仕様がコンパクトでわかりやすいという噂のSchemeで勉強だと決めて本を探したところ、「プログラミング言語Gauche」というのがわかりやすくて実用的でよいという評判だったので、買って勉強を始めたという次第。
いまのところ結構楽しいので、ログを残そうと思って昔一瞬だけ使ったはてダをリサイクルしました。