Scheme手習い 第９章 ……もう一度、もう一度、もう一度、……（その４）

Yコンビネータについて習います。こんなものどうやって考えつくのか全く不思議ですが、手順を踏むと導き出せる事を実体験出来ます。

ノート：

Yコンビネータ

defineはここでは要するに関数に名前を付ける機能。『defineがなかったら』関数に名前が付けられない。名前が付いていない関数はlambdaで定義した結果を一回は呼べるけど、二度と呼べない。とすると一度呼ばれた関数から二度目に自分自身を呼び出す事が出来ない。なので再帰が出来ない事になる。

define以外にlambdaで定義した関数に名前を付ける方法は仮引数がある。引数として関数を受け取り、その関数を適用する時にもう一度引数としてその関数を渡してあげれば、その先でもまた同じ関数を適用する事は出来る。

まず、元の関数lengthから始める。defineは使えないからlambdaから始めて、lengthを呼べないから取り敢えず埋め草としてeternityを呼ぶ事にする。確かに空リストに対しては０を返すけど、空じゃなかったらeternityに入ってしまい返って来ない。

取り敢えず要素が一つあるリストに対して１と返す様にするには１回再帰しなければならないが、再帰は出来ないので、再帰の代わりにeternigyの部分に２回目の呼び出しに相当する部分を展開してしまう。もう１回eternityの部分に展開すると要素２個までサポート出来る。けどこれを永遠に繰り返す訳にもいかない。

関数の定義に繰り返し・重複がある場合には共通の関数を作って、異なる部分は引数として与えて新しい関数を作る、と言うのが関数を抽象化するの意味。

まずはlengthに相当する関数を引数として受け、リストを引数にその長さを返す関数を返す関数として定義する。defineで名前は付けられないけど、引数として関数を貰えば名前を付けられると。確かに元のlength相当の関数は簡単に定義出来る。ただこの関数に引数として何を渡せば良いのか。ここでも取り敢えず埋め草としてeternityを渡してlength0相当の関数を得ている。

実際に評価してみる。空リストには０を返すが、lengthはeternityなのでelseに入るとそのまま無限ループとなる。

> (((lambda (length)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (length (cdr l)))))))
 eternity) '())
0
> 

確かに空リストに対しては0を返す。

前回同様、eternityの部分にlength0相当の関数を展開してあげればlength≦1相当の関数が得られる。lengthが二回出てきてしまうので引数名をfとgと使い分けて分かりやすくしてある。

同様にもう１回eternityの部分に展開するとlength≦2相当が得られる。今度は引数は全てlengthに戻されている。

実際に評価してみる。

> (((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))) '(a b))
2
> 

まだ繰り返しが発生するので、更にもう一段関数の抽象化を進める。

もう一度length0に相当する関数を作って返す関数に立ち返る。length0は

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

eternityに相当する関数を引数で受け取り、上記の関数を返す関数は

(lambda (f)
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (f (cdr l)))))))

eternityにこの関数を適用すればlength0相当の関数が返る。
fは本来再帰するlengthに相当するので、lengthと言う名前にする。ここで上記の関数を引数として受け取り、eternityに適用してlength0相当の関数を返す関数を考える。関数を受け取りeternityに適用するだけの関数を考えると：

(lambda (g)
  (g eternity))

このgはいずれeternityに適用してlength0相当の関数を作るので、mk-lengthと言う名前にする。この関数を先の関数に適用するとlength0が返る。

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

実際に評価してみる。

> (((lambda (mk-length)
      (mk-length eternity))
    (lambda (length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 (length (cdr l))))))))
   '())
0
> 

上記の(else (add1 (length (cdr l))))のlengthの部分に、length0相当の関数、即ち(mk-length eternity)が当てはめられればlength≦1相当の関数となる。それにはmk-lengthを(mk-length eternity)に適用すれば良い。

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

更に(mk-length (mk-length eternity))にmk-lengthを適用するとlength≦2相当の関数となる。でもこれでは結局また繰り返しが出て来てしまうのだが,

ここで発想の転換。

eternityに辿り着いてしまうのは次に適用すべき関数が足りなくなってしまった事を意味する。と言う事は基底部に入らずに再帰しなければならなくなった時点で次に呼び出すべき関数を生成すれば良いと言える。

もう一度length0相当の定義に戻って

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

ここではlengthは直接呼べる関数をイメージしていたが、関数を返す関数でも良く、(cdr l)にその返って来た関数を適用すると考えても良い。『関数lengthを返す関数』はmk-lengthに他ならないので、lengthにmk-lengthが渡る様に

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

と定義を変更する。もやはlengthは『リストの長さを返す関数』ではなく『length関数を返す関数』なので、その名前もmk-lengthに代えたのが本の定義。全部mk-lengthになってしまい若干目眩がする。

でもここはまだ完成していない。mk-lengthは引数をひとつ取るので（mk-lengthは上記の定義で(lambda (length)…)で作られる関数だから引数lengthを取る）最後にmk-lengthを呼ぶ所で引数の関数を与えなければならない。本では今回も埋め草としてeternityを充てている。

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l))))))))
   '(apple))
1
> 

但し、これでは２回目に適用したmk-lengthの引数mk-length（元の(lembda (length)…の部分）がeternityとなってしまい、リストの長さが２の時にはeternityを適用してしまう。なのでここでもmk-lengthを引数としてあげれば常に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))))))))
   '(apple orange peach pear pine))
5
> 

おぉ、動いた。

上記の形で動作する事は分かったが元のlengthの関数とは少し違う形になってしまった。次のステップとして、必要な関数を作り続ける部分とリストの長さを計算する部分に分離する事を考える。length関数に相当する部分の(mk-length mk-length)を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))))
   l)

この定義を評価するには、まず最初の(lambda (mk-length) …)に適用するためにその引数を評価する。(lambda (mk-length) ( (lambda (length) …)))を評価すると内側の( (lambda (length) …))が(mk-length mk-length)の部分に展開される。次はまた最初の(lambda (mk-length) …)に渡すために(lambda (mk-length) ( (lambda (length) …))))を評価して( (lambda (length) …)))を渡して、再び(mk-length mk-length)の部分が展開される。となっていつまでたってもlに適用すべき関数が確定しない。

問題は(lambda (length)…)に(mk-length mk-length)を渡そうとする時、渡す前に(mk-length mk-length)を評価（展開）してしまう所にある。『mk-lengthをその引数に適用する時に関数を返そうとする』と言うのがその事を意味していると思われる。なので引数として渡すときには評価されず、実際に必要になった時に始めて評価されて関数を生成する様にする必要がある。

そこでlength相当の関数を返す(mk-length mk-length)の部分をもう１段lambdaで包む。こうすると引数として渡す段階ではlambdaが評価されてlengthとしては(mk-length mk-length)を定義とする関数が渡され、その関数定義の中のelseに入った段階で始めて(mk-length mk-length)が評価される事になる。本ではこの事を一旦括りだす前にlambdaで包んで引数として(cdr l)をxで受けて(mk-length mk-length)を適用する形にしてから括りだす操作をしている。

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((lambda (x) ((mk-length mk-length) x)) (cdr l))))))))
   '(a b c))
3
> (((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)))))
   '(a b c))
3
> 

『名前をその値で置き換える』は「名前＝仮引数」を「その値＝実引数」で「置き換える＝展開する」と解釈。『値を取り出してそれに名前をつけています』は関数定義の中にある内容（値）の一部をlambdaを使って定義の外に括り出して引数として名前を付けると解釈。

ここで更に変形。リストの長さを計算する部分を更にまたlambdaで包んで外に出して、その部分だけを最後（と言っても長さを計算するリストの前）に引数として渡す形に変形する。即ち一番外側からlambdaで包んでその引数leの部分に長さを計算する関数を渡す。

> (((lambda (le)
      ((lambda (mk-length)
         (mk-length mk-length))
       (lambda (mk-length)
         (le (lambda (x) ((mk-length mk-length) x))))))
    (lambda (length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 (length (cdr l))))))))
   '(a b c))
3
> 

ちゃんと動く。

実際には何を取り戻したのでしょう。

元の関数mk-lengthを取り出しました。

元の関数はlengthではないかと思うが、良く分からない。

lengthの計算部分は完全に外に出てmk-lengthと言う名前は適切ではないので、単にfと書き換えるとYコンビネータとなる。

Yコンビネータを言葉で表現するのは困難。

> ((Y (lambda (length)
        (lambda (l)
          (cond ((null? l) 0)
                (else (add1 (length (cdr l))))))))
   '(a b c))
3
> 

(Y Y)は、引数のYをYに適用する。即ち再び(Y Y)を呼び出す事になるので無限に再帰する。

これを一体どう使うのかあまりピントは来ないが、理論的根拠になる事以外に多少の使い道はあるらしい。