Y combinator

scheme

昨晩と今日の午前中、以下な定義をひたすらニラんでおりました。

((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))))))))

le に渡されるのは一引数な手続きオブジェクトを引数に一引数な手続きオブジェクトを戻す手続きであることが分かります。
また、テキストの記述によれば (mk-length mk-length) および (lambda (x) (mk-length mk-length) x) も一引数な手続きオブジェクトを戻すとのこと。本当にそうなの? というあたりでヒッカカッてるカンジだったりして。

書いてみる

ええと

(lambda (mk-length mk-length))

な手続きに渡されてるのが

(lambda (mk-length)
  (le (lambda (x) ((mk-length mk-length) x))))

な手続きオブジェクト。ちなみに le が捕捉してるのは手続きオブジェクトを引数に取って一引数な手続きをオブジェクトを戻す手続き。ということは (mk-length mk-length) という式は一引数な手続きオブジェクトを戻す、ということで良いのか。
あるいは、

(lambda (x) ((mk-length mk-length) x))

という式が手続きオブジェクトを戻す、というあたりが鬼門なのかな。あ、冷静に考えたら上の式はそれ自体が手続きオブジェクトなのか。遅延評価、という言葉が頭をよぎりますな。というか問題はこっから先。

問題の式が何を戻すか

というと手続きオブジェクト、という理解で良いはず。

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

上記の mk-length は以下な手続きオブジェクトを束縛してる、で良いのかな。

(lambda (mk-length)
  (le (lambda (x)
        ((mk-length mk-length) x))))

引数として渡されているのは自分自身。また、le が捕捉しているのは引数として渡された以下な手続きオブジェクト。

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

で、この節のてっぺんの手続きを戻すのか。直上の手続きオブジェクトの引数 length に渡されるのは mk-length が束縛してる手続きオブジェクトなのか。

適用順 Y combinator

テキストによれば定義が以下。以前見たのとはちょっと違う形。

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

Y に渡す引数は一引数な手続きオブジェクトで一引数な手続きオブジェクトを戻すものである必要がある。ちなみに Y 自身も手続きオブジェクトを引数として受け取って、一引数な手続きオブジェクトを戻すのか。
そうか、lambda でくるんで評価を遅らせているというのがポイントなのか。

ということは

やはり (Y Y) は終わらない、ということで良いのかな。