john7rv

ラムダ計算での再帰として
ここではYCombinatorのRacketでの実装を紹介します

Yコンビネータは名前のないラムダ関数に再帰をさせるためのテクニックです
再帰とは自分自身の関数を呼び出すことであり
呼び出すためには当然自分に名前がないといけないはずです

それにもかかわらず名前のないラムダ関数で再帰を実現させてしまう
魔法のようなテクニックです

あらかじめ言っておくと手続き型の言語ではYコンビネータは仕事などのプログラミングの実務的な面で
役に立つことはあまり無いかもしれません
大抵の言語ではループを使いたければ通常のループ関数を使えば良いだけですから。
もっともlispやschemeなどの関数型言語のような再帰と無名関数を
多用するプログラミングスタイルの言語では重要な価値があるでしょう
またYコンビネータはアカデミックな意味で価値があると言えるでしょう
ただしプログラミングでは直接的に役に立たなくても
教養として知っていることがプログラミングの書き方の技術の向上に間接的につながることは
あるかもしれません

ラムダ計算理論ではラムダ関数によって数学の様々な計算を
できなければいけません
その計算には当然再帰によるループも含まれます
なのでラムダ関数は実際に再帰もできなければいけません
ではそれをどのように具体的に実現したかを示したのがYコンビネータです

今回ここで説明のために書いたSchemeコードは
RacketSchemeのlazy(遅延評価)モード専用の実装です
おそらくGaucheなど他のSchemeではこのコードはそのままでは動かないはずです

Yコンビネータは
遅延評価のないプログラミング言語などでは
なんらかのエラーに引っかかってしまうことが多く
また型が厳格な言語でもやはりエラーになってしまいやすいようです
もちろんそのような厳格な言語でも
様々なテクニックや工夫を加えればYコンビネータを書くことができますが
そうするともともとの数式の形から離れてわかりにくくなってしまいます

Racket Schemeはコードを動作させるのにいくつかモードがあり
Racket Schemeのlazy（遅延評価）モードだと
ほぼ理論の数式に近い書き方ができるので今回はRacket Schemeを使いわせてもらいました
このページはYコンビネータを理解するのが目的なので
理論に近いコードで書けれる方がそれだけわかりやすくなるので良いのではないでしょうか

数式は次のとおりです

Y = λf.(λx.f(x x))(λx.f(x x))...数式

これに再帰させたい関数Gをかけます

YG = λf.(λx.f(x x))(λx.f(x x))G...再帰させる

Gはfに代入（B簡約）できます

YG = (λx.G(x x))(λx.G(x x))...B簡約(1)

右端のGは代入されたので消え、左端のλf.も代入されたので消えました

右側の(λx.G(x x)を左側の(λx.G(x x)のxにそれぞれ代入（B簡約）できます
左側の(λx.G(x x)のλx.は代入されたので消えます

YG = G(λx.G(x x))(λx.G(x x))...B簡約(2)

B簡約(2)の(λx.G(x x))(λx.G(x x))の部分は
B簡約(1)の右辺と同じです 　#　YG = (λx.G(x x))(λx.G(x x))...B簡約(1)
なのでこれをわかりやすく書き直せば

YG = G(YG)

となります
YG=B
とすると
B=G(B)
となり
BはG関数のFixedPointとなります

これで変換は完了ですが
しかし(λx.G(x x))(λx.G(x x))
の構造は残ったままなのです
なので再帰関数Gが内部で止まらない限り
また右の(λx.G(x x))を左の(λx.G(x x)のxに代入（B簡約）できるわけです
つまり何回代入変換しようとも

(λx.G(x x))(λx.G(x x))

というYコンビネータの構造は変わらず保持されるので
永遠に再帰できるようになります
（もっとも今回はGの累乗計算内部に指定回数で止まる制限を加えてるので指定回数でストップさせれます）

これを繰り返していけば

YG = G(G(G(G(G(G(G(YG)))))))

となりGだけが増えていき再帰になるようになります

しかし先行評価ではなく遅延評価であると
必要な計算のみを行うので
Yコンビネータは永遠の無限ループにはならないのです
その実際のコードは後ろで載せます

ここからはRacket Schemeのコードで書き説明します
Racketのlazyモード専用です
YはYコンビネータ
Gはこれは再帰させたいlambdaで書かれた関数です
今回のプログラムでは累乗計算を書いています

#lang lazy

(define Y (lambda (f) ((lambda (x) (f (x x)))
                       (lambda (x) (f (x x))))))
                           
(define G                         
 　　(lambda (f2) (lambda (n) (if (= n 0) 1 (* n (f2 (- n 1)))))))

となり
10回累乗させるとすれば

((Y G) 10)
>>3628800

となります
これで完成ですが
上記のB簡約(1)(2)の部分もコード化してみます

Gをfに代入します

 (define YG  ((lambda (x) (G (x x)))
              (lambda (x) (G (x x)))))

(YG 10)
>>3628800

右側の(λx.G(x x)を左側の(λx.G(x x)のxに代入（B簡約）

(define GYG  (G
              ((lambda (x) (G (x x)))
               (lambda (x) (G (x x)))))
)
(GYG 10)
>>3628800

ここのコードの動作を解説すると
B簡約(1)の

 (define YG  ((lambda (x) (G (x x)))  　・・・(FirstLambda  FL)
              (lambda (x) (G (x x)))))　・・・(SecondLambda SL)

最初の行の(lambda (x) (G (x x)))をFirstLambda 省略形FLと名付け
2つ目の行の(lambda (x) (G (x x)))をSecondLambda 省略形SLと名付けるとします
最初の行FLのxに
2つ目の行の(lambda (x) (G (x x)))つまりSLをそのまま代入するのです

(lambda (SL) (G (SL SL)))

ということになり
代入したのでlambdaも消して

(G (SL SL))

となります
SLを(lambda (x) (G (x x)))に戻せば

(G ((lambda (x) (G (x x))) (lambda (x) (G (x x)))))

となるわけです
これを行に分けて書けば

(G 
   ((lambda (x) (G (x x))) 
    (lambda (x) (G (x x)))))

となりGだけ増えてあとは元の形と同じになります

そして上のB簡約(1)とB簡約(2)を見てください
Scheme上で
(YG 10)
としたものも
(GYG 10)
としたものも
答えは同じ

>>3628800

になっています
つまり
YG = GYG
です
YGをBで表せば
B = GB
でありGにはどんな関数でも入れることができるので
YCombinatorによるFixed Point Theoryとなります

(define GGYG  (G(G
              ((lambda (x) (G (x x)))
               (lambda (x) (G (x x))))))
  )
(GGYG 10)
>>3628800 

(注意)
ちなみに今回はYとGという関数を作っていますがこれはわかりやすくするためで
全てを完全にラムダ関数だけで書くこともできます
あとRacketSchemeは大文字と小文字を区別します

先程も書きましたが
Yコンビネータそのものは先行評価では無限ループになりますが
遅延評価ではそうはなりません

#lang lazy

(define Y (lambda (f) ((lambda (x) (f (x x)))
                       (lambda (x) (f (x x))))))
(define G                         
 　　(lambda (f2) (lambda (n) (+ n 5))))

((Y G) 10)
>>15

これは累乗計算を１回だけのただの加算計算に変えたものですが
無限ループにならずに計算を一度だけして正確に計算できています
遅延評価であれば
必要な計算だけを終えてプログラムは無限ループにならずにそこで止まるのです
遅延評価モードでは無限を有限で扱えるということです

(lambda (x) (f (x x)))

の

(f (x x)))

ではxは関数として動作すると同時に引数(オブジェクト)としても存在します
つまり関数と変数を違う型として処理する型付きプログラミング言語でこれをそのまま書けば
たいてい型チェックでエラーになってしまうでしょう
もちろんキャストしたり関数もオブジェクトとして書くなどいろいろな工夫を凝らすことで書ける場合も多くあります
Schemeでは関数もデータもリスト構造をしておりスムーズに書けるのでここで説明に使わせてもらいました

Yコンビネータが再帰を増やしていく原理を簡単に言えば

Z関数（引数A 引数A）

という２つの引数を取り
後ろのAを前のAに代入するZという関数を考えます

Z(A,A) -> Z(A(A)） #これは引数が１個の関数の場合です

例えば引数が１個のf(B)を代入すると考えます

Z(f(B), f(B))

そして後ろのf(B)を前のf(B)に代入すると

Z(f(f(B)))

で終わりです

しかし
Z関数の自分自身の右半分を左半分に引数として渡すと

Z(Z(A,A),Z(A,A))

それを繰り返すと

Z(Z(Z(A,A),Z(A,A)))

対角関数は引数を２倍に増やした後
後ろの引数を前の引数に代入して
引数の数を減らし元の構造に戻します


自分自身の関数は同じ構造の２つの引数を持ってるので
構造は変わらずにZだけが増えていくんですね

これは面白い

これはおそらくdiagonal functionを使った証明と
同じ構造をしています
同じ構造に同じ構造を代入するところは
なんとなくフラクタルにも似ています

しかし対角関数の再帰と
通常の関数の再帰は何が違うのだろうか
おそらく変わらないのだろうが
自然はただの再帰は認めない
我々は関数に名前をつけれるから
再帰をできるのであり
自然は無名関数のように（水素原子に差をつけれないように）
なっているので
対角関数を使って再帰をするしかないのではないだろうか