Y combinator - yamanetoshi's diary

最近ネト界隈で目につくなぁというか気になるなぁ、と思いつつ google 先生におうかがいしてみると青木さんがドキュメントを書いてらっしゃるでないの。しかも scheme 使ってるな。

(define fact-maker
  (lambda (proc)
    (lambda (n)
      (if (zero? n)
      1
      (* n ((lambda (arg) ((proc proc) arg)) (- n 1)))))))

から次の段階なソレが微妙。_くくりだす_という記述がヒントか。ええと

(lambda (arg) ((proc proc) arg))

を f に置き換えて上記の fact-maker に渡せばくくり出せる。

(fact-maker (lambda (arg) ((proc proc) arg)))

すれば

(define fact-maker
  (lambda (f)
    (lambda (n)
      (if (zero? n)
      1
      (* n (f (- n 1)))))))

な書き方ができる、という事??

上記は微妙にダウト。というか脳の中で情報が整理できていないのでもう少し前からトライ。
まず

(define fact-maker
  (lambda (proc)
    (lambda (n)
      (if (zero? n)
	  1
	  (* n ((proc proc) (- n 1)))))))

という手続きが定義されているとして

(fact-maker fact-maker)

は proc が fact-maker に束縛された

(lambda (n)
  (if (zero? n)
      1
      (* n ((proc proc) (- n 1)))))

な手続きを戻す。ここで lambda でククッて遅延評価なテクを使って (proc proc) とか fact-maker という名前をなんとかして上記の lambda な式から排除する取り組みなのだろうか。そのための第一歩として上記の fact-maker を

(lambda (proc)
  (lambda (n)
    (if (zero? n)
	1
	(* n ((lambda (arg) ((proc proc) arg)) (- n 1))))))

な形にした上で上記の alternative なブロックにある lambda 式を受け取って上記の fact-maker 手続きが戻している lambda な手続き

(lambda (n)
  (if (zero? n)
      1
      (* n ((proc proc) (- n 1)))))

と同じ機能を持つ手続きを戻すには

(lambda (f)
  (lambda (n)
    (if (zero? n)
	1
	(* n (f (- n 1))))))

という手続き (ドキュメントでは fact0 と名前が付いていた) を作って

(lambda (arg) ((proc proc) arg))

を外に出しつつ手続きを作っておいて、fact-maker が戻す lambda 式を戻す手続きを作れば良い。それが

(lambda (proc) (fact0 (lambda (arg) ((proc proc) arg))))

になる、という事??
確かに上記の lambda 式に名前を付けたら (fact0 なソレは前提) fact-maker と同じ機能になるな。まだオチてませんがなんとなく理解。でも最終的にできた手続き定義とその手続きの

((Y fact0) 5)

な式は脳内置き換えができません。(とほほほ

これって λ算法なナニ的に導出する公式というか定理みたいなのがあるんだろうな。