タグ : アルゴリズム

Y-Combinator, lambda再帰, 不動点

Y-Combinatorが分かったような気がしたので、綴る。

そもそもY-Combinatrという単語に行き着いたのは、SICPの1章を進めてる間にフと「手続きに名前を与えないで、再帰ってできるかな?」という疑問からだった。

「lamda 再帰」でググってみるとlamda式による再帰呼び出し関数,再帰的な無名関数 – ヒビキノログがヒット。

その他いろんなページ(本当にいろんな)を参考にして、結局LoveRuby.Netさんの解説ページが自分の疑問からY-Combinatorに順序立てて解説されていて分かりやすかった。

前置きが長いけど

とりあえず、自分の理解のプロセスを綴る。

factを名無しで実装したい

分かりやすい例で、factorialから。

まず、普通に実装(再帰)

;;普通に実装
(define (fact n)
    (if (< n 2) 1
        (* n (fact (- n 1)))))

(fact 42)
;;gosh> 1405006117752879898543142606244511569936384000000000

;;lambdaで実装
(define fact
  (lambda (n)
    (if (< n 2) 1
        (* n (fact (- n 1))))))
(fact 42)
;;gosh> 1405006117752879898543142606244511569936384000000000

ここまでは、無問題。名前を使わずに再帰(自分自身を呼び出し)するには、引数として自分自身を受け取る必要がある。

さらにlambdaで包む

;;ここで、再帰先を引数で受け取る(自分自身)
(define fact
  (lambda (self)
    (lambda (n)
      (if (< n 2) 1 (* n ((self self) (- n 1)))))))

(fact fact)
;;gosh> #<closure (fact fact)>
((fact fact) 42)
;;gosh> 1405006117752879898543142606244511569936384000000000

ここまでの展開は、別に難しくないけど、上記のコードが実行されて再帰に展開されていく様子がどうもキチンと頭の中でイメージできない #容量不足?

((fact fact) 3)の展開を図にしてみた。

fact-fact

図で表す事で、上記の式が毎回(fact fact)を実行して再帰と同等に自己呼び出しを行なっている事がわかった。 #図の意味が分からんとかいうツッコミは無視

さらに、このコードからfactという名前を無くして実装をそのまま引数に渡すようにすれば、当初の目的「lambdaのみで再帰」は実現できている。

;;もう、この時点でlambda式のみで再起関数は達成できる
(((lambda (self)
    (lambda (n)
      (if (< n 2) 1 (* n ((self self) (- n 1))))))
  (lambda (self) ;;自分自身を引数に
    (lambda (n)
      (if (< n 2) 1 (* n ((self self) (- n 1)))))))
 42) ;;で、生成されたfactに値を渡して評価
;;gosh> 1405006117752879898543142606244511569936384000000000

ここからY-Combinator

導出したコードの、自分自身を2度適用する部分{(fact fact),(self self)}と、factorialを求める実装の部分は別々にlambdaで実装できる。

;;もっと抽象化する(適用部[Y Combinator]と計算部[fact]を分ける)。
(define Y-Combinator
  (lambda (f)
    ((lambda (proc) ;;factに渡すprocに自身を適用
      (f (lambda (arg) ((proc proc) arg))))
    (lambda (proc) ;;で、渡す
      (f (lambda (arg) ((proc proc) arg)))))))

(define fact ;;factの実装
  (lambda (f)
    (lambda (n)
      (if (< n 2) 1 ;;fは、Y-Combinator内で既に生成されたクロージャ
          (* n (f (- n 1)))))))

((Y-Combinator fact) 42)
;;gosh> 14050061177528798985431426062445115699363840000000

ここでは、説明しやすいようにY-Combinatorとfactを分けた上でdefineしているけど、実質lambdaのみで表現できている。

他の再帰関数も実装してみる

Y-Combinatorと再起関数の処理の実装を分けたため、実装をY-Combinatorに渡してやれば、lambdaのみであらゆる再帰手続きが表現可能。

;;ちなみに、可変長引数を扱うにはapplyでok
(define Y-Combinator
  (lambda (f)
    ((lambda (proc) ;;factに渡すprocに自身を適用
      (f (lambda (args-car . args-cdr)
           (apply (proc proc) args-car args-cdr))))
    (lambda (proc) ;;で、渡す
      (f (lambda (args-car . args-cdr)
           (apply (proc proc) args-car args-cdr)))))))

;;これで、任意個の引数をとる再起関数もlambdaのみで表現可能

マッカーシーの91関数

(define McCarthy-91-function
  (lambda (f)
    (lambda (n)
      (if (> n 100) (- n 10) (f (f (+ n 11)))))))

(map (Y-Combinator McCarthy-91-function) '(1 10 100 101 102))
;;gosh> (91 91 91 91 92)

Ackermann関数

;;ちょっと前に出てきたAckermann関数
(define Ackermann
  (lambda (f)
    (lambda (x y)
      (cond ((= y 0) 0)
            ((= x 0) (* 2 y))
            ((= y 1) 2)
            (else (f (- x 1)
                     (f x (- y 1))))))))

;;第一引数を固定したAckermann(curried-function)
(define curried-Ackermann
  (lambda (fix-arg)
      (lambda (arg)
        ((Y-Combinator Ackermann) fix-arg arg))))

(map (curried-Ackermann 1) '(1 2 3 4 5))
;;gosh> (2 4 8 16 32)
(map (curried-Ackermann 2) '(1 2 3 4))
;;gosh> (2 4 16 65536)
(map (curried-Ackermann 3) '(1 2 3))
;;gosh> (2 4 65536)

普通の再帰と時間を比べてみる

普通に名前を指定して呼び出す場合と違い、毎回自分自身を呼び出す手続きを生成(self self)して実行しているため、若干時間がかかる?

(time (begin (factorial 10000) #f))
;;gosh> ;(time (begin (factorial 10000) #t))
;;; real   0.726
;;; user   0.700
;;; sys    0.020
;;#t

(time (begin ((Y-Combinator fact) 10000) #f))
;;gosh> ;(time (begin ((Y-Combinator fact) 10000) #f))
;;; real   0.887
;;; user   0.860
;;; sys    0.020
;;#f

Memoize

Y-Cobinatorで関数を生成(self self)する段階で、引数-結果のペアをあらかじめ保存(ハッシュ)しておいて、引数から結果が分かる場合はハッシュから取り出すように実装する。 -> Memoize
これで、同じ呼び出しが何度も発生するfactのような関数は、効率が非常によくなる。
(関数呼び出しの増加が線形的に)

;;引数と結果のペアをハッシュに
(use util.list)
(define Y-Combinator-Memoiz
  (lambda (f)
    (define memo (make-hash-table 'equal?))
    ((lambda (proc)
       (f (lambda (_car . _cdr)
           (apply (proc proc) _car _cdr))))
     (lambda (proc) ;;で、渡す
      (f (lambda (_car . _cdr)
           (if (hash-table-get memo (apply list _car _cdr) #f)
               ()
               (hash-table-put! memo (apply list _car _cdr)
                               (apply (proc proc) _car _cdr)))
           (hash-table-get memo (apply list _car _cdr))))))))

(define fib
  (lambda (f)
    (lambda (n)
      (if (<= n 1) n
          (+ (f (- n 1)) (f (- n 2)))))))

引数と結果をハッシュに保存しておく事で、等価な関数呼び出しは2度目から省略される。

;;memoize効果
(time (begin ((Y-Combinator fib) 30) #t))
;;gosh> ;(time (begin ((Y-Combinator fib) 30) #t))
;;; real   4.272
;;; user   4.190
;;; sys    0.060
;;#t

(time (begin ((Y-Combinator-Memoiz fib) 30) #t))
;;gosh> ;(time (begin ((Y-Combinator-Memoiz fib) 30) #t))
;;; real   0.000
;;; user   0.000
;;; sys    0.000
;;#t
;;こんなのも計算できる(実時間で)。
(define big-num ((Y-Combinator-Memoiz fib) 10000))
;;gosh> ;(time (begin ((Y-Combinator-Memoiz fib) 100000) #t))
;;; real  29.190
;;; user   4.160
;;; sys    1.060
;;#t

不動点

Y-Combinatorを求める過程では意識しなかったけど、これは

と関数Fの不動点を求めていることと同等。ゆえに不動点オペレーターとも言うらしい。 #意識しないと分からなかった。

この不動点だとかなんだとかは、図で説明してくれてるおとうさんにもわかるYコンビネーター!が分かりやすいと思う。

まとめ

難しい事は図に表すと理解しやすい #場合もある
Y-Combinatorを調べているページを回っていると、他にも色々理解できない(できてない)トピックがちらほら。

  • カリー化
  • lambdaのみでif
  • 継続

うわー、知りたいことが多すぎる。

 
Better Tag Cloud