不動点演算子ふたたび

（追記：Ｙコンビネータって何に使うの？）

Yコンビネータ（Curryの不動点演算子）を説明するのがプチブーム（死語）らしいので、ふたたび挑戦。

まず、ふつーに再帰関数factをSchemeで定義してみる。

(define fact
  (lambda (n)
    (if (= n 0)
	1
	(* n (fact (- n 1))))))

この定義は、右辺にfact自身が出現するので、再帰的定義なのであった。ここから右辺にfactが出現しないようにするのが目標。とりあえず、factを関数の引数として外から受け取るようにしてみる。

(define make-fact
  (lambda (my-fact)
    (lambda (n)
      (if (= n 0)
	  1
	  (* n (my-fact (- n 1)))))))

これは( (make-fact fact) 10)みたく使えるが、make-factを呼び出す際にfactがいる。つまり、factの定義としては(define fact (make-fact fact) )となってしまう。これでは「右辺にfactが出現しないようにfactを定義する」という当初の目標を達成していない。

そこで、make-factが（factではなく）make-fact自身を引数として受け取るようにしてみる。

(define make-fact
  (lambda (my-make-fact)
    (lambda (n)
      (if (= n 0)
	  1
	  (* n ((my-make-fact my-make-fact) (- n 1)))))))

fact = (make-fact make-fact)となる予定なので、my-factが(my-make-fact my-make-fact)となったことに注意。これは( (make-fact make-fact) 10)みたく使える。言い換えると、

(define fact (make-fact make-fact))

と定義できる。

同様に、たとえばfibを定義してみると

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

となる。ただし、(my-make-fib my-make-fib)の部分が重複していて冗長なので、

(define make-fib
  (lambda (my-make-fib)
    (define (my-fib m) ((my-make-fib my-make-fib) m))
    (lambda (n)
      (if (<= n 1)
	  1
	  (+ (my-fib (- n 1))
	     (my-fib (- n 2)))))))

とローカル関数をdefineする。

以上の議論はfactやfibだけでなく、任意の再帰関数fについて通用するので、

(define make-f
  (lambda (my-make-f)
    (define (my-f x) ((my-make-f my-make-f) x))
    ...my-fを含む式...))
(define f (make-f make-f))

のように定義できる。ここで「my-fを含む式」を(F my-f)とおくと

(define make-f
  (lambda (my-make-f)
    (define (my-f x) ((my-make-f my-make-f) x))
    (F my-f)))
(define f (make-f make-f))

となる。

(define (my-f x) ...)

は

(define my-f (lambda (x) ...))

と等価だから、my-fをインライン展開すると

(define make-f
  (lambda (my-make-f)
    (F (lambda (x) ((my-make-f my-make-f) x)))))
(define f (make-f make-f))

となる。さらにmake-fもインライン展開すると

(define f
  ((lambda (my-make-f)
     (F (lambda (x) ((my-make-f my-make-f) x))))
   (lambda (my-make-f)
     (F (lambda (x) ((my-make-f my-make-f) x))))))

となる。最後に、Fも引数として受け取るようにすると

(define Y
  (lambda (F)
    ((lambda (my-make-f)
       (F (lambda (x) ((my-make-f my-make-f) x))))
     (lambda (my-make-f)
       (F (lambda (x) ((my-make-f my-make-f) x)))))))

となって(call-by-valueの)Yコンビネータができました。使い方は↓こんな感じ。

(define (Fact my-fact)
  (lambda (n)
    (if (= n 0)
	1
	(* n (my-fact (- n 1))))))
(define fact (Y Fact))
(define (Fib my-fib)
  (lambda (n)
    (if (<= n 1)
	1
	(+ (my-fib (- n 1))
	   (my-fib (- n 2))))))
(define fib (Y Fib))

実際に実行してみた（トリビア風に）。

> (fib 10)
89
> (fact 10)
3628800

型つき言語でも、ある種の再帰型(equi-recursive type)があれば同じです。たとえばocaml -rectypesなら

# let yy =
    fun ff ->
      (fun my_make_f ->
  	ff (fun x -> my_make_f my_make_f x))
      (fun my_make_f ->
  	ff (fun x -> my_make_f my_make_f x)) ;;
val yy : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
# let ffact my_fact =
    fun n ->
      if n = 0 then 1 else
      n * my_fact (n - 1) ;;
val ffact : (int -> int) -> int -> int = <fun>
# let fact = yy ffact ;;
val fact : int -> int = <fun>
# fact 10 ;;
- : int = 3628800
# let ffib my_fib =
    fun n ->
      if n <= 1 then 1 else
      my_fib (n - 1) + my_fib (n - 2) ;;
val ffib : (int -> int) -> int -> int = <fun>
# let fib = yy ffib ;;
val fib : int -> int = <fun>
# fib 10 ;;
- : int = 89

とか。

equi-recursive typeがないなら、ふつーのMLの再帰型(iso-recursive type)を使います。my_make_f my_make_fという自己適用が問題なので、「引数の型 = 関数自身の型」（返値の型は'a）となるように

type 'a t = T of ('a t -> 'a)

と定義して、

let yy =
  fun ff ->
    (fun (T my_make_f) ->
      ff (fun x -> my_make_f (T my_make_f) x))
    (T (fun (T my_make_f) ->
      ff (fun x -> my_make_f (T my_make_f) x)))

とすればOKです。

他にもTuringの不動点演算子とかあります。

ふー長かった。

P.S. 何箇所か不自然にスペースがあいているのは、( (とか) )がうまくエスケープできなかったせいです。ヘルプの通りにやったつもりなんですが、X(とかX)とか書いてもダメ…??

P.P.S. Schemeの処理系は大文字小文字を区別しないかもしれないので注意。上の例だけならno problemですが。

P.P.P.S. λ文字。「大文字小文字」で思い出したので。