the why of y
Richard P. Gabriel
Lucid, Inc. および Stanford University
導入
Y がどのように動作し、誰がそれを思いついたのか疑問に思ったことはありますか? ?Scheme の熟練プログラマが公衆の面前で Y を賞賛して、あなたが Lisp の弱者のように感じたことはありますか? この文書では、Y がどのように動作するかだけでなく、どのように発明されたかを説明します。関数が引数として渡され適用される際に理解しやすいため、Scheme の記法を使用します。最後に、Scheme コードの一部について Common Lisp の同等物を示します。
Y の目的は、特別な組み込み手段なしに自己参照プログラムを書くメカニズムを提供することです。Scheme には、グローバル関数定義や letrec を含む、このようなプログラムを書くための複数のメカニズムがあります。以下は Scheme で階乗関数を書く一つの方法です:
(define fact
(lambda (n)
(if (< n 2)
1
(* n (fact (- n 1))))))
これが機能するのは、グローバル変数 fact がその値を lambda 式の値に設定されているためです。関数本体内の変数 fact が評価されて、どの関数を呼び出すかを決定する際、その値はグローバル変数から見つかります。ある意味で、関数名としてグローバル変数を使用することは不快です。なぜなら、グローバルで脆弱なリソース—グローバル変数空間—に依存しているからです。
Scheme の自己参照形式 letrec は通常、副作用を使用して実装されます。副作用のないプログラミング言語とプログラムについて推論する方が容易です。したがって、副作用を使用せずに再帰関数を書く能力を確立することは理論的に興味深いです。
以下は letrec を使用するプログラムです:
(letrec ((f (lambda (n)
(if (< n 2)
1
(* n (f (- n 1)))))))
(f 10))
このプログラムは 10! を計算します。lambda 式内の f への参照は、letrec によって確立された f の束縛を指します。
let と set! を使用して letrec を実装できます:
(letrec ((f (lambda ...))) ...)
これは以下と等価です:
(let ((f <undefined>))
(set! f (lambda ...))
...)
lambda 式の本体内の f へのすべての参照は、lambda 式の値を参照します。
Y とは何か
Y は、再帰的または自己参照的関数を記述するものと見なせる関数を取り、その再帰関数を実装する別の関数を返す関数です。以下は Y を使用して 10! を計算する方法です:
(let ((f (Y (lambda (h)
(lambda (n)
(if (< n 2)
1
(* n (h (- n 1)))))))))
(f 10))
Y への引数として渡される関数は、関数を引数として取り、定義したい階乗関数のように見える関数を返すものです。つまり、Y に渡される関数は (lambda (h) ...) です。この関数の本体は階乗関数のように見えますが、階乗関数への再帰呼び出しを期待する箇所で、代わりに h が呼び出されます。Y は h の値として適切な値が供給されるよう配置します。
Y は関数に対する 適用的順序不動点演算子 (applicative-order fixed-point operator for functionals) と呼ばれます。階乗の例でこれが何を意味するか見てみましょう。Y* が真の数学的階乗関数であるとします(おそらくプラトンの天界にある)。F を以下の関数とします:
F = (lambda (h)
(lambda (n)
(if (< n 2)
1
(* n (h (- n 1))))))
すると ((F f*) n) = (f* n) となります。つまり、f* は F の不動点です: F は(ある意味で)f* を f* 自身に写像します。Y は以下の性質を満たします: ((F (Y F)) x) = ((Y F) x)。これは Y の非常に重要な性質です。もう一つの重要な性質は、関数に対する最小の定義された不動点が一意であることです。したがって (Y F) と f* はある意味で同じです。
適用的順序の Y は古典的な Y (コンビネータ)とは異なります。一部のテキストでは、我々が Y と呼ぶものは Z と呼ばれます。
導出方法
私の計画は、まず Y を導出することです。これは Y を理解する良い方法です。次に階乗の場合にそれが正しいことを証明します。その後、一般的な証明がどのように進むか想像できるでしょう。また ((F (Y F)) x) = ((Y F) x) を示します。一意性の性質はここで扱うには少し難しすぎます。すべての証明は非形式的で、詳細を省略します。最後に、Scheme と Common Lisp の両方で Y の拡張をいくつか検討します。
Y を導出するために、再帰関数の例である階乗から始めます。導出では、3つの技法を使用します:
- Scheme の自己参照プリミティブを使用しないために追加の引数を渡す
- 自己参照パラメータの操作と通常のパラメータの操作を分離するために、複数パラメータ関数をネストした単一パラメータ関数に変換する
- 抽象化を通じて関数を導入する
すべてのコード例では、整数を参照するために変数 n と m を、未知だが区別されない引数を参照するために変数 x を、関数を参照するために変数 f, g, h, q, r を使用します。
階乗関数の基本形式は以下です:
(lambda (n)
(if (< n 2)
1
(* n (h (- n 1)))))
変数 h は、再帰呼び出しが行われたときに呼び出したい関数、つまり階乗関数自体を参照する必要があります。h が正しい関数を直接参照する方法がないため、引数として渡しましょう:
(lambda (h n)
(if (< n 2)
1
(* n (h h (- n 1)))))
h への再帰呼び出しでは、最初の引数も h になります。なぜなら、再帰状況で使用する正しい関数を後の関数呼び出しに渡したいからです。
したがって、10! を計算するには以下のように書きます:
(let ((g (lambda (h n)
(if (< n 2)
1
(* n (h h (- n 1)))))))
(g g 10))
g の本体の評価中、h の値は let が確立した g の値と同じです。つまり、g の実行中、h は実行中の関数を参照します。関数呼び出し (h h (- n 1)) が発生すると、この同じ値が h への引数として渡されます: h は自分自身を自分自身に渡します。
しかし、私たちがやりたいのは、関数への自己参照の管理を他の引数の管理から分離することです。この場合、h の管理を n の管理から分離したいのです。これを処理する通常の方法は、カリー化 (currying) と呼ばれる技法です。この例をカリー化する前に、カリー化の別の例を見てみましょう。以下も 10! を計算するプログラムですが、少し巧妙な方法です:
(letrec ((f (lambda (n m)
(if (< n 2)
m
(f (- n 1) (* m n))))))
(f 10 1))
ここでのトリックは、結果を計算するためにアキュムレータ m を使用することです。この関数は Scheme では反復的ですが、それは重要ではありません。f の定義をカリー化しましょう:
(letrec ((f (lambda (n)
(lambda (m)
(if (< n 2)
m
((f (- n 1)) (* m n)))))))
((f 10) 1))
カリー化のアイデアは、すべての関数が1つの引数を持ち、複数の引数を渡すことはネストした関数適用で達成されるということです: 最初の適用は2番目の引数を取り、値の計算を完了する関数を返します。上記のコードでは、再帰呼び出し ((f (- n 1)) (* m n)) には2つのステップがあります: 適用する適切な関数が計算され、次にそれが正しい引数に適用されます。
このアイデアを使用して、他の階乗プログラムをカリー化できます:
(let ((g (lambda (h)
(lambda (n)
(if (< n 2)
1
(* n ((h h) (- n 1))))))))
((g g) 10))
このコードでは、再帰呼び出しにも2つのステップがあり、最初のステップは適用する適切な関数を計算することです。しかし、その適切な関数は、関数を自分自身に適用することによって計算されます。
関数を自分自身に適用することが、自己参照の基本機能を得る方法です。プログラムの最後の行の自己適用 (g g) は、g 自身を引数として g を呼び出します。これは、変数 h が外側の g に束縛されているクロージャを返します。このクロージャは数値を取り、基本的な階乗計算を行います。その計算が再帰呼び出しを実行する必要がある場合、クロージャが保持している h を、クロージャが保持している h を引数として呼び出しますが、これらすべての h は let で定義された関数 g に束縛されています。
このトリックを要約できます。letrec を使用する自己参照関数があるとします:
(letrec ((f (lambda (x) ... f ...)))
... f ...)
これは、let を使用する以下のような自己参照関数に変換できます:
(let ((f (lambda (r)
(lambda (x)
... (r r) ...))))
... (f f) ...)
ここで r は新しい識別子です。
階乗関数で h の管理を n の管理からさらに分離する方法に集中しましょう。階乗プログラムは以下のようでした:
(let ((g (lambda (h)
(lambda (n)
(if (< n 2)
1
(* n ((h h) (- n 1))))))))
((g g) 10))
攻略計画は、if 式を (h h) と n について抽象化することです。これにより2つのことが達成されます: 結果の関数は周囲の束縛から独立し、制御引数の管理が数値引数から分離されます。以下が抽象化の結果です:
(let ((g (lambda (h)
(lambda (n)
(let ((f (lambda (q n)
(if (< n 2)
1
(* n (q (- n 1)))))))
(f (h h) n))))))
((g g) 10))
f の定義をカリー化できます。これにより、それへの呼び出しも変更されます:
(let ((g (lambda (h)
(lambda (n)
(let ((f (lambda (q)
(lambda (n)
(if (< n 2)
1
(* n (q (- n 1))))))))
((f (h h)) n))))))
((g g) 10))
関数 f の定義は、関数 g に深く埋め込まれている必要はないことに注意してください。したがって、関数の主要部分—階乗を計算する部分—を残りのコードから抽出できます:
(let ((f (lambda (q)
(lambda (n)
(if (< n 2)
1
(* n (q (- n 1))))))))
(let ((g (lambda (h)
(lambda (n)
((f (h h)) n)))))
((g g) 10)))
2つのことに注意してください: 第一に、f の形式は再び階乗のパラメータ化された形式です。第二に、この式を f について抽象化できます。これにより、以下のように Y が生成されます:
(define Y (lambda (f)
(let ((g (lambda (h)
(lambda (x)
((f (h h)) x)))))
(g g))))
これが Y を導出する一つの方法です。
正しさの証明
Y が関数に対する適用的順序不動点演算子であることを思い出してください。これは以下のように述べられます:
((Y f) x) = ((f (Y f)) x)
この性質を使用して、以下の関数が階乗を計算することを証明しましょう:
(Y (lambda (f)
(lambda (n)
(if (< n 2)
1
(* n (f (- n 1)))))))
帰納法を使用して証明します。F を以下とします:
F = (lambda (f)
(lambda (n)
(if (< n 2)
1
(* n (f (- n 1))))))
∀n, n ≥ 0, ((Y F) n) = n! を示します。鍵となる性質を使用して、最初のステップは以下に気づくことです:
((Y F) x) = ((F (Y F)) x)
G を (Y F) とします。((Y F) 1) = ((F (Y F)) 1) = ((F G) 1) です。F の定義を見ると、以下が分かります:
((F G) 1) = (if (< n 2)
1
(* n (G (- n 1))))
ここで n は 1 に束縛されています。1 < 2 なので、if 式の値は 1 で、これは 1! です。これが基底ステップです。
次に帰納ステップです。1 ≤ i ≤ m に対して ((Y F) i) = i! を仮定します。((Y F) (m+1)) を考えます。以前と同様に、これを以下に簡約できます:
((Y F) (m+1)) = ((F G) (m+1)) = (if (< n 2) 1 (* n (G (- n 1))))
ここで n は m+1 に束縛されています。m は少なくとも 1 なので、m+1 は少なくとも 2 です。したがって、この式の値は以下です:
(* n (G (- n 1)))
G は (Y F) なので、これは以下に簡約されます:
(* n ((Y F) (- n 1)))
帰納法の仮定により、これは単に (m+1)m! = (m+1)! です。これで (Y F) が階乗関数であるという非形式的な証明が完了します。
次に、Y が関数に対する適用的順序不動点演算子であることを証明しましょう。すなわち、∀x に対して以下が成り立つことを証明します:
((Y F) x) = ((F (Y F)) x)
Y の定義を思い出してください:
(define Y (lambda (f)
(let ((g (lambda (h)
(lambda (x)
((f (h h)) x)))))
(g g))))
Y の定義を見ると、以下が分かります:
(Y F) = (g g) = (lambda (x) ((f (h h)) x))
ここで g は Y の定義内の内部関数で、f は F に束縛され、h は g に束縛されています。(Y F) の結果に引数を供給すると、以下が真です:
((Y F) x) = ((f (h h)) x)
ここで h は Y の定義内の内部関数 g に束縛されています。h を g で置換すると、この等式を以下のように書き直せます:
((Y F) x) = ((f (g g)) x)
ここで g は Y の定義内の内部関数です。しかし、f が F に束縛され、(Y F) = (g g) であることを思い出すと、これは単に以下に簡約されます:
((Y F) x) = ((F (Y F)) x)
これが示したかったことです。x が範囲できる領域について少し自由に話しましたが、これは概要であり、形式的な証明ではありません。
この性質と一意性の性質を組み合わせると、Y がまさに自己参照を実装するために必要な関数であることが分かります。
Common Lisp での Y
Common Lisp では Y はどのように見えるでしょうか? 以下のようになります:
(defun y (f)
(let ((g #'(lambda (g)
#'(lambda (x)
(funcall (funcall f (funcall g g)) x)))))
(funcall g g)))
Y は1つの引数の関数に対してのみ機能します。しかし、Common Lisp には可変個数の引数を扱うメカニズムがあるため、これは大きな問題ではありません:
(defun super-y (f)
(let ((g #'(lambda (g)
#'(lambda (&rest x)
(apply (funcall f (funcall g g)) x)))))
(funcall g g)))
任意の個数の引数を持つ関数を super-y に渡すことができます。以下は例です:
(defun fact (n)
(funcall
(super-y
#'(lambda (f)
#'(lambda (n m)
(if (< n 2)
m
(funcall f (- n 1) (* m n))))))
n 1))
Y の拡張
Y について学んだので、2つの相互再帰関数を扱えるように拡張したいと思います。Y の定義を思い出しましょう:
(define Y (lambda (f)
(let ((g (lambda (h)
(lambda (x)
((f (h h)) x)))))
(g g))))
Y の本体では、f への呼び出しが組み込まれていることに注意してください。これには実際の問題はありませんが、拡張では f を g の類似物への引数として渡す必要があります。以下は、この単純な変更を加えた Y の様子です:
(define Y (lambda (f)
(let ((g (lambda (h r)
(lambda (x)
((r (h h f)) x)))))
(g g f))))
この関数は前のものと同じ効果を持ちますが、g には追加のパラメータがあり、これは一度に複数の関数を扱うために g を使用することが可能であることを意味します。ただし、Y は少し異なる必要があります。
Y2 は Y に類似していますが、相互再帰関数のペアを扱う関数になります。これらの相互再帰関数の記述は、関数のペアのそれぞれに1つずつ、2つのパラメータを持つ lambda 式になります。以下は Y2 の使用方法の簡単な例です:
((Y2 (lambda (f g) (lambda (n) (if (< n 1) 'even (g (- n 1)))))
(lambda (f g) (lambda (n) (if (< n 1) 'odd (f (- n 1))))))
n)
これら2つの関数の本体では、f は関数のペアの最初のものを参照し、g は2番目のものを参照します。上記の式は以下と等価であることを意図しています:
(letrec ((f (lambda (n) (if (< n 1) 'even (g (- n 1)))))
(g (lambda (n) (if (< n 1) 'odd (f (- n 1))))))
(f n))
Y2 の定義でいくつかのパラメータの名前を変更すると、Y2 を理解しやすくなるので、今名前を変更しましょう:
(define Y (lambda (f)
(let ((h (lambda (h r)
(lambda (x)
((r (h h f)) x)))))
(h h f))))
この Y の定義を見ると、何を変更する必要があるかが分かります。第一に、Y2 には f と g と呼ばれる2つのパラメータが必要です。第二に、h 内の r への呼び出しは、f を表す引数と g を表す引数の2つの引数を渡す必要があります。以下が最終結果です:
(define Y2 (lambda (f g)
(let ((h (lambda (h r)
(lambda (n)
((r (h h f) (h h g)) n)))))
(h h f))))
最後に、任意の正の数の関数を扱う super-Y のバージョンを見てみましょう:
(defun super-yn (f &rest g)
(let ((h #'(lambda (h r)
#'(lambda (&rest x)
(apply
(apply r
(funcall h h f)
(mapcar #'(lambda (f) (funcall h h f)) g))
x)))))
(funcall h h f)))