2010-09-27
“The Why of Y”のトレース、というかおいしいとこだけ…
不動点演算子がどこからきたのか知りたい、と思ったので、そのものずばりの文書を見る。印象に残ったところだけでも書きとめておこうと思いました。
こちら、
The Why of Y / Richard P. Gabriel / Lucid, Inc. and Stanford University
http://www.dreamsongs.com/Files/WhyOfY.pdf
です。
ここでいうYはZとも呼ばれているそうです。
注意点！！
あたしの勝手に抱いたイメージがそのまま投影されちゃっていますので、原文を先に読まれることを強く強くおすすめします。m(__)m
＃そもそも、原文抜きでは意味不明ですね…
＃そういった意味でちゃんと邦訳するというのも良いのかも…と思った…
感想
S式をこねくりまわしていたらば、いつのまにか目的のYが発見できちゃったね、という流れに見えちゃいました。この“いつのまにか”てきなところが印象的でした。
あとは、Lispになっているのをじーっと見ていたらばklop関数が怖くなくなった(^^
ここでいうklop関数といったのは、不動点コンビネータの“ジャン・ウィレム・クロップによって組み立てられた”のものです。
以下本文です。
原文を先に読まれることを強く強くおすすめします。m(__)m
気分を高揚させるためにまずこの美しい写真でイメージを膨らませましょう、
http://weitz.zenfolio.com/ilc2009/h2807fbc9#h2807fbc9
イメージイメージイメージ…(^^ 心の準備はできましたか？
以下、＃のところはあたしのさえずりです。
以下本当の本文です。
ポイントはこれ。
To derive Y, I will start with an example recursive function, factorial. In the derivation I will make use of three techniques. The first is to pass an additional argument to avoid using any self-reference primitives from Scheme. The second is to convert multiple-parameter functions to nested single-parameter functions in order to separate manipulation of the self-reference parameters from manipulation of ordinary parameters. The third is to introduce functions through abstraction.
“Yを導き出すために、例として再帰的関数の階乗を取り上げます。その中で、3つの技法を扱います。
1.追加の引数を渡すことで、Schemeの自己参照機能を利用するのを避けます。
2.複数の引数を取る関数を入れ子になった複数の1引数関数に変換することで、自己参照の引数とそれ以外の引数の操作を区別します。
(define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1))))))
1.追加の引数でもってSchemeの自己参照プリミティブの利用を避ける。
引数にhを追加します。
＃っと、いきなり山場なんだけれども…。ここでg自体を渡しちゃう！
(let ((g (lambda (h n) (if (< n 2) 1 (* n (h h (- n 1))))))) (g g 10))
2.自己参照のための引数を他の引数の操作と区別するために、複数の引数の関数を入れ子になった1引数の関数群へと変換する。
このような手法を“curry(ing)”と呼ぶ。例えばこんなものですね。
(letrec ((f (lambda (n m) (if (< n 2) m (f (- n 1) (* m n)))))) (f 10 1)) ;; ↓ (letrec ((f (lambda (n) (lambda (m) (if (< n 2) m ((f (- n 1)) (* m n))))))) ((f 10) 1))
“curry(ing)”とは、どんな関数も1つのみ引数を持つことにしちゃって、複数の引数を渡すことを、入れ子になった関数の適用として達成されるようにすること。
＃日本語がが…
例えば、
((f (- n 1)) (* m n))
では、
まず適用すべき関数が計算されてから、その結果が正しい引数の下で評価されます。
(let ((g (lambda (h) (lambda (n) (if (< n 2) 1 (* n ((h h) (- n 1)))))))) ((g g) 10))
(さて)
自己参照の基本機能を得るには、関数をそれ自体に適用してしまえばよい。そうすれば外側のg(自分自身)をhとして掴まえたクロージャを得られる。再帰的に呼び出したければ、hを引数hで呼べばよい。ああそうそう、ここでいうhはletで定義された関数gのことだね。
＃“h's”の“'s 〜”ということなんだろうけども、“〜”が何を意味しているのかちょっとわからない…“hの定義”ということになるのかなあ(T^T
＃そしてだんだんと3へ。
(h h)やnへと及んじゃっているif式を抽象化しよう。ねらいは2つ。
結果となる関数は、周囲の束縛とは独立させること。
＃“abstract `if` expression over `(h h)` and `n`.”のイミがわからないヒー＞＜
＃(h h)を計算して(qとして)渡し、渡される関数の方では数値の計算を行なうだけにする、というようにすることで“区別する”、ということになるのかなあ(T^T
結果は以下。
(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))
そしたらば、“curry”だね。
(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)))
気づいた？
fは変数化された階乗を計算する主たる部分なんだってことと、fの中に隠れちゃっていたこの↓式を抽象化できたんだってこと。
(define Y (lambda (f) (let ((g (lambda (h) (lambda (x) ((f (h h)) x))))) (g g))))
フォッフォッフォッ。Yのできあがりじゃよ(^^
＃“abstract”の意味がとてもむつかしい＞＜
Permalink | コメント(0) | トラックバック(0) | 22:41 
Y'(チューリングの不動点演算子)
『計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)』の問2.1.5なのだけれども、
Y' ≡ X X (ただしY' ≡ λ xy.y (x x y))のとき、
すべてのMについて Y' M →→β M (Y' M) が成り立つことを示せ。
Y' M ≡ (λ xy.y (x x y)) X M
→β (λ y.y (x x y)) [x := X] M
≡ (λ y.y (X X y)) M
→β (y (X X y)) [y := M]
≡ M (X X M) ≡ M (Y' M)
こうですか？すごくよくわかっていません本当にごめんなさい＞＜
Permalink | コメント(0) | トラックバック(0) | 22:44 