The King's Museum

ソフトウェアエンジニアのブログ。

Scheme 手習い(9)~ Y コンビネータ~

第9章:…… もう一度、もう一度、もう一度、……(続き)

第9章の最後は Y コンビネータについて。 リストの要素数を数える length を題材にして Y コンビネータを学ぶ。

length

リストの要素数を数えるなんの変哲もない関数 length を定義する。

(define (length l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))]))

length を define を使わずに定義できるだろうか?

define がなければ、関数名を定義できないので定義内で自身を参照できない。 これでは再帰ができないので length は定義できなくなってしまう。

でも、方法はある。それが Y コンビネータだ。 順を追って考えよう。

length-0, length-1, ..., length-n

まずは空リストの要素数を数えることができる関数を定義しよう。 ここで重要なのは define を使わず、lambda だけを使うことだ。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1 (eternity (cdr l)))]))

空リスト以外だと無限ループするが、これで空リストの要素数は数えられるようになった。 これを length-0 と呼ぶことにする。

では、次に要素 1 以下のリストを数えられる関数を定義してみる。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1 (length-0 (cdr l)))]))

define がないのだから length-0 は参照できない。 そこで、length-0 の定義をそのまま lambda を使った表記に置き換えることにする。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1
                ((lambda (l)
                  (cond [(null? l) 0]
                        [else (add1 (eternity (cdr l)))]))
                 (cdr l)))]))

これを length-1 と呼ぼう。

同じようにしていけば length-2、length-3、...、length-n を定義できるはずだ。

ただ、見ての通りどんどん関数定義が長くなってしまう。 このままでは length は定義できない。

mk-length

そこで共通のパターンを抽象化して、同じ関数定義を繰り返し書かなくてもよいようにしたい。 さきほどの length-n の次の部分を共通化することを考える。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1 (length (cdr l)))]))

定義内の length はどこにも存在しないため、このままでは参照できない。 そこで引数として length を外から与えられるようにする。

(lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))

こうすれば length-n を定義できる。 例えば length-0 を作りたいなら eternity を渡せばよい。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 eternity) ; = length0

length-1 なら次のように length-0 を与えれば良い。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 length-0)

ただ、ここでも length-0 は参照できないので lambda を使った表記に置き換える必要がある。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 ((lambda (length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 (length (cdr l)))])))
   eternity)) ; = length1

さらに length-2 は次のようになる。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 ((lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))])))
  ((lambda (length)
     (lambda (l)
       (cond [(null? l) 0]
             [else (add1 (length (cdr l)))])))
   eternity)))

ここまでの変形で同じような部分が連続するようになった。

共通する部分 (lambda (length) ... が何をしているかといえば、「外から次の再帰呼び出しの関数を受け取り length 関数を生成する」という処理だ。

(lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
; => これに名前を付けたい

そこでこの関数に make length を意味する mk-length という名前を付けることにする。

名前を付けるにはどうしたらよいか。 lambda を用いて引数としてさきほどの関数を与え、引数に mk-length と名前をつけることにする。

そうすると length-0 は次のようになる。

((lambda (mk-length)
   (mk-length eternity))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

length-1 は次のようになる。

((lambda (mk-length)
   (mk-length
     (mk-length eternity)))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

length-2 は次のとおり。

((lambda (mk-length)
   (mk-length 
     (mk-length
       (mk-length eternity))))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

ここまでの変形でだいぶシンプルになった。念のため実行してみる。

(((lambda (mk-length)
    (mk-length 
      (mk-length
        (mk-length eternity))))
  (lambda (length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 (length (cdr l)))]))))
  '(1 2)) ; => 2

ただしく実行することができた。 しかし、まだ要素数が多くなるほど関数定義も増えてしまう点に変わりはなく、このままでは length は定義できない。

(mk-length mk-length)

今のままでは mk-length を何度も書かないと length を定義できない。 あともう少し、関数を変形すればこれを回避することができる。

まず、eternity について。 eternity は無限ループする関数なので、呼び出した時点で処理は終了しなくなる。 どうせ、eternity を呼んでしまったらそこで終わりなのだから、eternity ではなく何か別の関数、たとえば mk-length 自体を渡すように変更してみる。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

こうすると mk-length には length ではなく、mk-length が渡ってくるようになる。 そこで引数名を length から mk-length に変更する。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (mk-length (cdr l)))]))))

この時点では mk-length に (cdr l) を渡してしまっている。 mk-length は関数を引数に受け取る関数なので、mk-length を渡す必要がある。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 ((mk-length mk-length) (cdr l)))]))))

(mk-length mk-length) は length を生成する呼び出しであり length 関数を返してくれる。 mk-length 関数に自分自身(mk-length)を渡すようにしたおかげで、再帰してリストを数える length が定義できるようになった。

これで define を使わずに length を定義できた。

(((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 ((mk-length mk-length) (cdr l)))]))))
 '(1 2 3 4)) ; => 4

これで一応、「define を使わずに length を定義する」という目的は達成することができた。

Y コンビネータ

ここまで define を使わずに length を定義できた。 さて、これを一般化して length に限らず、任意の再帰関数を define を使わずに定義できるか考えてみよう。

任意の再帰関数を定義するためには「再帰を行うための関数部分」と「再帰関数自体の定義部分」に分けることを目標とする。

さきほどの length から一つずつ関数を変形していこう。

((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 ((mk-length mk-length) (cdr l)))]))))

(add1 ...) の中にある (mk-length mk-length) は、length を生成する関数呼び出しになっている。 そこで、この関数を呼び出した結果を length という名前をつけて扱うことにする。

例によって、lambda の引数を使って、length という名前を付けることにする。

((lambda (mk-length)
  (mk-length mk-length))
 (lambda (mk-length)
    ((lambda (length)
       (lambda (l)
         (cond [(null? l) 0]
               [else (add1 (length (cdr l)))])))
     (mk-length mk-length))))

(mk-length mk-length) を事前に評価し、length という名前の引数に渡す形に変えた。 しかし、この定義では定義を評価しようとすると無限ループしてしまう。 引数の (mk-length mk-length) を評価する段階で、無限に展開しようとしてしまうためだ。

(mk-length mk-length) は必要な時に一度だけ評価されるようにしたい。 そこで、遅延評価されるように lambda を使って (mk-length mk-length) を呼び出せるようにする。

((lambda (mk-length)
  (mk-length mk-length))
 (lambda (mk-length)
    ((lambda (length)
       (lambda (l)
         (cond [(null? l) 0]
               [else (add1 (length (cdr l)))])))
     (lambda (x) ((mk-length mk-length) x)))))

これで無限ループすることなく length が定義できた。あともう少しだ。

次に、内部のまさに length 特有の処理を定義している部分を le という引数名にして、一番外側にくくり出す。

(lambda (le)
  ;; 再帰を行うための関数部分
  ((lambda (mk-length)
     (mk-length mk-length))
   (lambda (mk-length)
     (le (lambda (x) ((mk-length mk-length) x)))))
  ;; 再帰関数自体の定義部分。le という名前になる
  (lambda (length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 (length (cdr l)))]))))

これで「再帰を行うための関数部分」の部分と「再帰関数自体の定義部分」に分けることができた。

一般的にこの「再帰を行うための関数部分」を 適用順 Y コンビネータ と呼ぶ。 引数を mk-length のような名前ではなく、より一般的な f とすると次のようになる。

(define Y
  (lambda (le)
    ((lambda (f)
       (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

ついによく見かける Y コンビネータにたどり着いた。

これを使って階乗 fact は次のように定義できる。

(define fact
   (Y (lambda (f)
        (lambda (n)
          (cond [(= n 1) 1]
                [else (* n (f (- n 1)))])))))
(fac 5) ; => 120

どうやら正しく Y コンビネータを定義できたようだ。

ずいぶんと長くなってしまったが、一応 Y コンビネータについて理解した。 一通り書いてあることは理解したつもりだけど、本質的に理解できてはいないなという感じ。 もっと深い理解にたどり着くためにはもっと努力が必要なようだ。

これで Scheme 手習いもあと1章を残すのみとなった。

(c) The King's Museum