Schemer のための「すぐ理解できるYコンビネータ」

ラムダ計算の説明などによく登場するYコンビネータ(不動点コンビネータ)ですが、
「ラムダだけで再帰関数を定義できる」というのはわかってもYコンビネータを使った関数の定義は複雑ですし、
そもそもYコンビネータ自体の定義からしてどうなってるのかよくわからないので、少し難解です。

しかし、Schemer (Schemeプログラマ) 向けには簡単に理解できる説明があります。
Scheme でよく使う call-with というイディオムがありますが、これを使うことで
「Yコンビネータとは call-with-myself である」と言えるのです。

具体例で説明します。

階乗を計算する関数 fact を考えます。*1
fact は再帰で素直に定義すると以下のようになります。

(define (fact n)
  (if (zero? n)
      1
      (* n (fact (- n 1)))))

呼び出してみると、ちゃんと階乗を計算する関数になっています。

(fact 5)
;; => 120
(fact 6)
;; => 720

ここで、 define や letrec を使えない (一度束縛した環境への副作用が許可されない)
という制限を課した場合、fact をどのように定義したら良いでしょうか？

define を使えないとなると関数は lambda で定義することになるので、試しに書いてみると・・・

(lambda (n)
  (if (zero? n)
      1
      (* n (???? (- n 1)))))  ;; 定義できない

ちょっとむずかしいですね。
lambda で定義する関数は名前を持たないので、最後の ???? に書くべき名前が存在しません。

ここで、call-with-myselfという便利な関数を考えます。
call-with-myself は、これを使えばfactと同じ働きの関数を以下のように書くことができる、という関数です。

(call-with-myself
 (lambda (self)                   ;; (1)
   (lambda (n)                    ;; (2)
     (if (zero? n)
         1
         (* n (self (- n 1)))))))

ここで (2) は先ほどの書こうとして書けなかったlambdaとほぼ同じものです。
先ほどとは、 ???? としていた呼び出し箇所に self と書いてあるところが違います。
この self がどこから来たのかというと、call-with-myself に渡す関数 (1) の引数です。
このように call-with-myself を呼び出すことで、 self にこれから定義しようとしている
(2)の lambda 自身を束縛した状態で (2) を記述することができるわけです。

Scheme の call-with-current-continuation が「あとで実行される計算コンテキスト(継続)を取り出す」のに対し、
call-with-myself は「これから定義しようとしている関数を取り出している」とでも言えばよいでしょうか。

奇妙ですね。でも上のようにdefineやletrecが使えなければ役立つシチュエーションは確かにあります。

この便利な関数 call-with-myself は実際に定義することができて、それは以下のようになります。*2

(define call-with-myself
  (lambda (proc)
    ((lambda (f)
       (proc (lambda args
               (apply (f f) args))))
     (lambda (f)
       (proc (lambda args
               (apply (f f) args)))))))

実はこの call-with-myself こそがYコンビネータと呼ばれるものです。*3

call-with-myselfを使うと、他にも再帰が必要なシチュエーションにおいてdefineを使わずに書くことができます。
たとえば 0 〜 9 までの数をprintするには

((call-with-myself
  (lambda (loop)
    (lambda (i)
      (when (< i 10)
        (print i)
        (loop (+ i 1))))))
 0)

と書けます。なんだか named let みたいですね。
実際、シンプルな named let は call-with-myself を用いて

(define-syntax nlet
  (syntax-rules ()
    [(_ name ((var exp) ...) body ...)
     ((call-with-myself
       (lambda (name)
         (lambda (var ...)
           body ...)))
      exp ...)]))

というマクロで定義できます。呼び出してみると・・・

(nlet loop ((i 0))
            (when (< i 10)
              (print i)
              (loop (+ i 1))))
0
1
2
3
4
5
6
7
8
9

ちゃんと動くようです。

マクロが出てきたところで、 call-with-myself を書くときの定型句をマクロでなんとかしてみます。

(define-syntax nlambda
  (syntax-rules ()
    [(_ name (arg ...) body ...)
     (call-with-myself
      (lambda (name)
        (lambda (arg ...)
          body ...)))]))

nlambda を使うと fact 相当の関数が

(nlambda fact (n)
  (if (zero? n)
      1
      (* n (fact (- n 1)))))

と書けます。ずいぶんスッキリ書けるようになりました。

**

さて、call-with-myself, つまりYコンビネータについていろいろ見てきましたが、
Scheme では本来 define や letrec が使えるので、
再帰関数を定義するときにわざわざYコンビネータを使う必要はありません。
ただ「lambdaすごい！ lambda万能！」と言うためには、Yコンビネータを理解しておいたほうが、わかってるフリができるかもしれませんｗ

**

会社の読書会で「アンダースタンディング・コンピュテーション」を読んでいるのですが、
Yコンビネータのところで盛り上がったので、自分なりに理解した内容をまとめるためにこの記事を書いてみました。
ツッコミなどあればお待ちしております。

以下注釈です。

*1 Scheme では関数のことを手続きと言いますが、ここでは関数で統一します。

*2 「call-with-myselfの定義にdefine使ってるじゃないか」と思うかもしれませんが、
本文ではわかりやすさのために call-with-myself という名前をつけているだけです。
call-with-myself の実体は上に書いてあるとおりの単なるlambdaなので、factと同じ関数も

((lambda (proc)
   ((lambda (f)
      (proc (lambda args
              (apply (f f) args))))
    (lambda (f)
      (proc (lambda args
              (apply (f f) args))))))
 (lambda (self) ;; (1)
   (lambda (n)  ;; (2)
     (if (zero? n)
         1
         (* n (self (- n 1)))))))

と書くことができます。
呼び出してみると、

(((lambda (proc)
    ((lambda (f)
       (proc (lambda args
               (apply (f f) args))))
     (lambda (f)
       (proc (lambda args
               (apply (f f) args))))))
  (lambda (self)
    (lambda (n)
      (if (zero? n)
          1
          (* n (self (- n 1)))))))
 5)
;; => 120

(((lambda (proc)
    ((lambda (f)
       (proc (lambda args
               (apply (f f) args))))
     (lambda (f)
       (proc (lambda args
               (apply (f f) args))))))
  (lambda (self)
    (lambda (n)
      (if (zero? n)
          1
          (* n (self (- n 1)))))))
 6)
;; => 720

ちゃんと動いてますね。

*3 正確にはこれはZコンビネータです。
Schemeの評価モデルではYコンビネータを実行すると無限ループに陥るので、
procにわたす引数をlambdaでくるんだZコンビネータを使います。

また、普通Zコンビネータ(やYコンビネータ)はカリー化された関数を扱うので、

(lambda (proc)
  ((lambda (f)
     (proc (lambda (arg)
             ((f f) arg))))
   (lambda (f)
     (proc (lambda (arg)
             ((f f) arg))))))

のように定義しますが、
ここでは再帰関数として、つまり call-with-myself 内で定義する関数として複数の引数をとる関数を直接定義できるように、

(lambda (proc)
  ((lambda (f)
     (proc (lambda args
             (apply (f f) args))))
   (lambda (f)
     (proc (lambda args
             (apply (f f) args))))))

としています。