2010/03/28

また出てきたYコンビネータ。Y!。

また出てきました。今度はThe Seasoned Schemerに。The Little Schemerでも9章で出てきました。理解できなくて散々書きました。
Yコンビネータは、いろんなサイトや解説記事を読みましたが、結局The Little Schemerが一番わかりやすかったです。The Seasoned SchemerではY!が出てきます。「!」ということで、副作用ありです。side effectです。その名もY-bang。ワイバーンみたい。
The Little SchemerThe Seasoned Schemer合わせて20章のうちで、初めて副作用が出てくるのが15章です。ここまで代入などを使わずにきて、急に使うことになるとさすがに気持ち悪く感じますね。

ちなみにY!が出てくるのは16章です。
Thunk you, Peter J. Landin.
だそうです。
1
2
3
4
5
6
7
8
9
10
11
12
(define Y!
 (lambda (L)
  (let ((h (lambda (l)(quote ()))))
   (set! h
    (L (lambda (arg)(h arg))))
   h)))

(define Y-bang
 (lambda (f)
  (letrec
   ((h (f (lambda (arg)(h arg)))))
   h)))
あれ、でも下のY-bangは副作用あるか?

そういえば、Yコンビネータはこれを見たときに、理解のきっかけになりました。
1
2
3
4
5
6
7
((lambda (f) 
   (f f 10)) 
 (lambda (f n) 
   (cond 
    ((< 0 n) 
     (print "hello") 
     (f f (- n 1))))))


The Seasoned SchemerThe Little Schemer, 4th Edition計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

0 件のコメント:

コメントを投稿