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を使うと末尾再帰されない気もするので、適用する問題を選ばなければならない気もします。