Scheme手習いを読むとYコンビネータがわかるよ
「プログラミングGauche」の継続のところが理解できず、「Scheme手習い」という本に手を出した。このシリーズの本は、現在、3冊出版されているようだ。「Scheme手習い」、「Scheme修行」、「The Reasond Schemer」の3冊である。「The Reasond Schemer」は翻訳されていないので、元吉文男先生、横山晶一先生、それからオーム社様、どうか翻訳版をよろしくお願いします。
さて、「Scheme手習い」は9章でYコンビネータに到達し、10章でインタープリタを作る。今、10章を読んでいるところだが、9章で理解したYコンビネータについてまとめておこうと思う。
(define length (lambda (l) (cond [(null? l) 0] [else (+ 1 (length (cdr l)))]))) (define mklength (lambda (future) (lambda (l) (cond [(null? l) 0] [else (+ 1 ((mklength future) (cdr l)))])))) (define mklength (lambda (future) (lambda (l) (cond [(null? l) 0] [else (+ 1 ((future future) (cdr l)))])))) (define mklength (lambda (future) ((lambda (recur) (lambda (l) (cond [(null? l) 0] [else (+ 1 (recur (cdr l)))]))) (lambda (arg) ((future future) arg))))) (define M (lambda (recur) (lambda (l) (cond [(null? l) 0] [else (+ 1 (recur (cdr l)))])))) (define mklength (lambda (future) (M (lambda (arg) ((future future) arg))))) (define length ((lambda (future) (M (lambda (arg) ((future future) arg)))) (lambda (future) (M (lambda (arg) ((future future) arg)))))) (define Y (lambda (M) ((lambda (future) (M (lambda (arg) ((future future) arg)))) (lambda (future) (M (lambda (arg) ((future future) arg))))))) (define length (Y M))