The Little Schemerを読み解く ~ Yコンビネータ

前置き

The Little Schemer(邦題は「Scheme手習い」)の中で最も難解だったのが、Yコンビネータの話しです。what is (define ...) という問いから始まります(ペーパーバック 4th EditionのP159)。

defineなしに再帰できるか?

length(defineによる定義)
(define length
  (lambda (lis) (cond
                 ((null? lis) 0)
                 (else (add1 (length (cdr lis)))))))

もしdefineが使えなかったら……

(lambda (lis) (cond
               ((null? lis) 0)
               (else (add1 (??? (cdr lis))))))

再帰呼び出しできません。ひとまず、???にはeternity(定義はP151)を使っておきます。

length0
(lambda (lis) (cond
               ((null? lis) 0)
               (else (add1 (eternity (cdr lis))))))

eternityは終わらない関数なので、決してcondのelse節へ入ってはいけません。つまり、これは空リスト専用のlength関数です。仮に、これをlength0と名付けましょう(defineが使えないので名前を付けることはできないのですが、後でこの名前は不要になります)。くどいようですが、長さが1以上のリストにlength0を適用すると、(eternity (cdr lis))が評価されてしまい万事休すです。

length0を使って、空リスト、または長さが1のリストに使えるlength関数を実装してみます。

length1
(lambda (lis) (cond
               ((null? lis) 0)
               (else (add1 (length0 (cdr lis))))))

これをlength1と名付けます。次は、長さが2以下のリストに使えるlength関数です。

length2
(lambda (lis) (cond
               ((null? lis) 0)
               (else (add1 (length1 (cdr lis))))))

length0、length1、length2の違いは、(cdr lis)に適用する関数の部分だけです。一部だけ違って、他はソックリ。こんな場合は、違う部分をパラメータ化して関数にするのが定石です。

λ
(lambda (len)
  (lambda (lis) (cond
                 ((null? lis) 0)
                 (else (add1 (len (cdr lis)))))))

この無名関数(以下、λと表記します)をeternityに適用すればlength0が手に入ります。それを空リストに適用すれば、0が返ってきます。

λでlength0を作り、使ってみる
gosh> (((lambda (len)
          (lambda (lis) (cond
                         ((null? lis) 0)
                         (else (add1 (len (cdr lis))))))) eternity) '())

0

方程式っぽく書いてみます。

  • length0 = eternityにλを適用したもの
  • length1 = length0にλを適用したもの
  • length2 = length1にλを適用したもの

つまり、

  • length0 = eternityにλを適用したもの
  • length1 = eternityにλを適用したものに、λを適用したもの
  • length2 = eternityにλを適用したものに、λを適用したものに、λを適用したもの

要するに、

  • length0 = eternityにλを1回適用したもの
  • length1 = eternityにλを2回適用したもの
  • length2 = eternityにλを3回適用したもの

ここで、「eternityに何かを1回適用する関数」を実装し、それをλに適用してみます。

length0(改訂)
((lambda (mk-length)              ;;eternityに
   (mk-length eternity))          ;;何か(mk-length)を1回適用する関数。
 (lambda (len)
   (lambda (lis) (cond
                  ((null? lis) 0)
                  (else (add1 (len (cdr lis))))))))

これは、すなはち、length0のことです。同様に、「eternityに何かを2回適用する関数」を実装し、それをλに適用すれば、length1になります。3回適用ならlength2です。

length2を使ってみる
gosh> (((lambda (mk-length)
          (mk-length (mk-length (mk-length eternity))))   ;;mk-lengthを3回適用。
        (lambda (len)
          (lambda (lis) (cond
                         ((null? lis) 0)
                         (else (add1 (len (cdr lis)))))))) '(a b))
2

すごいですね。length0もlength1も使わずに済みました。しかし、どんな長さのリストにも使えるlength関数には、まだ何か足りません。

eternityの役割

eternityにλをN回適用すれば、長さN-1以下のリストに使えるlength関数が手に入ることが分かりました。しかし、これを長さNのリストに適用するとどうなるでしょうか? 再帰ネストの底にあるeternityが(cdr lis)に適用されて永遠に返ってこないはずです。最初に書いた通り、eternityが評価されたら負けなのです。でも、このときの(cdr lis)は空リストなので、ほんのあと1回余分にλを適用できれば、無事Nが返ったはずです。これが第一ヒント。

ここで一旦、length0に戻りましょう。

length0(再掲)
((lambda (mk-length)
   (mk-length eternity))
 (lambda (len)                      ;;λ
   (lambda (lis) (cond
                  ((null? lis) 0)
                  (else (add1 (len (cdr lis))))))))

eternityの役割は何でしょうか? eternityは、仮引数lenの実引数です。そして、(len (cdr lis))は決して評価してはならないものです。評価できないなら、別にeternityじゃなくても、何でも良いですね。これが第二ヒントです。

eternityじゃなくても構わないなら、代わりにmk-lengthを使ってみましょう。

length0(変形1)
((lambda (mk-length)
   (mk-length mk-length))              ;;eternityの代わりにmk-length
 (lambda (len)
   (lambda (lis) (cond
                  ((null? lis) 0)
                  (else (add1 (len (cdr lis))))))))

これで、仮引数lenの実引数がmk-lengthになりました。そもそもmk-lengthはλです。このλを使えば、「あと1回余分にλを適用」することができます。つまり、(len (cdr lis))の部分を、((len eternity) (cdr lis))に代えます。ついでに仮引数名もlenからmk-lengthに変えてしまいましょう。

length0(変形2)
((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)              ;;新しいλ
   (lambda (lis) (cond
                  ((null? lis) 0)
                  (else (add1 ((mk-length eternity) (cdr lis))))))))

これなら、もし長さ1のリストに適用した場合でも、(mk-length eternity)のおかげで、再帰1回分、寿命が延びます。

gosh> (((lambda (mk-length)
          (mk-length mk-length))
        (lambda (mk-length)
          (lambda (lis) (cond
                         ((null? lis) 0)
                         (else (add1 ((mk-length eternity) (cdr lis)))))))) '(a))
1

しかし、依然として長さ2のリストには使えません。この壁を超えるには? 打開策を探るため、上記のコードの動作を分析してみます。

1行目の無名関数の引数はλなので、2行目の(mk-length mk-length)では、λをλに適用することになります。便宜上、これを(λ1 λ2)と書きましょう。そして、この結果を'(a)へ適用します。

((λ1 λ2) '(a))

(λ1 λ2)って何でしょうか? λ1の仮引数mk-lengthの実引数はλ2なので、(λ1 λ2)は、lisを引数に取る下記のような無名関数を返します。

(λ1 λ2)が返す無名関数
(lambda (lis) (cond
               ((null? lis) 0)
               (else (add1 ((λ2 eternity) (cdr lis))))))

これを'(a)に適用すると、'(a)は空リストではないのでelseに分岐し、(add1 ((λ2 eternity) (cdr '(a))))を評価します。

(λ2 eternity)ってなんでしょうか? λ1の仮引数mk-lengthの実引数はeternityなので、(λ2 eternity)は、lisを引数に取る下記のような無名関数を返します。

(λ2 eternity)が返す無名関数
(lambda (lis) (cond
               ((null? lis) 0)
               (else (add1 ((eternity eternity) (cdr lis))))))

これを(cdr '(a))に適用すると、(cdr '(a))は空リストなので0を返します。この0にadd1が適用され、結局、((λ1 λ2) '(a))の結果は1となります。もし、'(a)の代わりに'(a b)を使っていたら、最後もelseに分岐し、(eternity eternity)が評価されて永遠にサヨナラするところでした。

上記の2つの無名関数、つまり(λ1 λ2)が返す無名関数と(λ2 eternity)が返す無名関数を良く見比べて下さい。前者を例えば'(apple)に適用すると1が返りますが、後者を'(apple)に適用するとサヨナラです。この違いはどこから来るのか。答えは「eternityに何を適用するか」です。λを適用すれば延命され、eternityを適用するとジ・エンドなのです。もし、(eternity eternity)の左のeternityがλなら、後者の無名関数でも'(apple)の長さを返せます。

(eternity eternity)の左側のeternityは、どこから来たのか。それはλ2の実引数でした。では、λ2の実引数がeternityになるのはなぜか。λの定義の中で(mk-length eternity)しているためです。よって、これを(mk-length mk-length)に代えればOKです。適用される方の(つまり右側の)eternityまでλに代わってしまいますが、そもそもeternityは何でも良かった(上記の第二ヒント)ので問題ありません。

length(defineを使わない定義)
((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)              ;;λ
   (lambda (lis) (cond
                  ((null? lis) 0)
                  (else (add1 ((mk-length mk-length) (cdr lis))))))))

この定義なら、何度elseに入っても、その都度(λ λ)で延命されます。ついに万能のlengthが手に入りました(しかもdefineを使わずに)。

gosh> (((lambda (mk-length)
          (mk-length mk-length))
        (lambda (mk-length)
          (lambda (lis) (cond
                         ((null? lis) 0)
                         (else (add1 ((mk-length mk-length) (cdr lis)))))))) '(a b c d))
4

Yコンビネータ

最初に示した、defineを使ったlengthの定義と、最後に導出した、defineを使わないlengthの定義を比べてみます。

defineを使ったlengthと、defineを使わないlength
(define length
  (lambda (lis) (cond
                 ((null? lis) 0)
                 (else (add1 (length (cdr lis)))))))

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (lis) (cond
                  ((null? lis) 0)
                  (else (add1 ((mk-length mk-length) (cdr lis))))))))

最後の3行はソックリですね。(mk-length mk-length)の部分を引数でもらうことにして、その仮引数名をlengthとすれば…。

The Little Schemer P168より
((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)              ;;λ
   ((lambda (length)              ;;★
     (lambda (lis) (cond
                    ((null? lis) 0)
                    (else (add1 (length (cdr lis)))))))
   (mk-length mk-length))))

lisを仮引数とする無名関数の部分は、完全に同じになりました。ただし、これは実は失敗バージョンです。★印の無名関数を(mk-length mk-length)に適用するには、まず(mk-length mk-length)を、つまり(λ λ)を評価する必要があります。しかしλを評価するには、その定義の中の(mk-length mk-length)を評価する必要があり……。といった具合に循環してしまうのです。

そこで、★の実引数(mk-length mk-length)を、ひとひねりします。

The Little Schemer P171より
((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)              ;;λ
   ((lambda (length)              ;;★
     (lambda (lis) (cond
                    ((null? lis) 0)
                    (else (add1 (length (cdr lis)))))))
   (lambda (x) ((mk-length mk-length) x)))))

ここでは、何かへ(mk-length mk-length)を適用する無名関数を、仮引数lengthの実引数としています。よってこの無名関数を(cdr lis)へ適用することになり、そうすると(cdr lis)へ(mk-length mk-length)を適用する結果になります。

しかも、(mk-length mk-length)は無名関数のボディ内にあるので、★を適用する前に(mk-length mk-length)を評価する必要はありません。これが、失敗バージョンのような循環が起きない理由です。

最後に、★印の無名関数自体を引数として外へ(しかも一番外側へ)出します。つまり、lengthに特化した部分を、それ以外の部分と完全に分離するわけです。

lengthに特化した部分をパラメータ化
((lambda (le)                     ;;Y
  ((lambda (mk-length)
     (mk-length mk-length))
   (lambda (mk-length)
     (le (lambda (x) ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (lis) (cond
                  ((null? lis) 0)
                  (else (add1 (length (cdr lis))))))))

leを仮引数とする無名関数が、Yコンビネータです。仮引数leの実引数は、★印の無名関数になっています。

mk-lengthは単なる仮引数名なので、より抽象的なfに代えましょう。

Yコンビネータ
(lambda (le)
  ((lambda (f) (f f))
   (lambda (f)
     (le (lambda (x) ((f f) x))))))

Yコンビネータは、defineを使わずに再帰を生み出すことのできる関数です。

Last modified:2013/04/16 22:07:37
Keyword(s):
References:[FP: 関数型プログラミング] [The Little Schemerを読み解く ~ Schemeインタープリタ] [Yコンビネータ]
This page is frozen.