ラベル Y Combinator の投稿を表示しています。 すべての投稿を表示
ラベル Y Combinator の投稿を表示しています。 すべての投稿を表示

2011/03/03

ニコニコわいこんびねーた

Gauche が 0.9.1 になってっから（？）、それまで gauche.experimental.apps モジュールにあった ^ とか ^x とかが使えるようになっているみたいです。引数をリストで受け取る時とか笑顔の顔文字みたいになりますよね。(^ _ ^) みたいな。

これで Y コンビネータもすっきりー！
(define Y (^c ((^f (f f))(^g (c (^ x (apply (g g) x)))))))

ということで以前書いた Y コンビネータ関連エントリ。

そういえば、Emacs で scheme を書くときに scheme-mode と一緒に quack.el を使っているのですが、その quack.el の pretty-lambda って機能。lambda が自動で λ って表記になるんです。これ、ちょっといじれば emacs-lisp-mode とかに使えるようになるんじゃないかなー。（誰得）

written by time: 0 件のコメント:
labels : , ,

2010/05/27

「そのプロセスにおいて、Schemeを使うことに関する多くの勘を やしなうだろう。」

数nの階乗を計算するが、手続きの最終行で自身に再帰できるようにするた めに名前"fact"が必要であるように思える。しかし、我々はそれは必要でない ことを理解し、そのプロセスにおいて、Schemeを使うことに関する多くの勘を やしなうだろう。

これが本当かどうかは置いといて、みんなもっと Y Combinator で遊ぼうよー！

 計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)The Little Schemer, 4th EditionThe Seasoned Schemer
written by time: 0 件のコメント:
labels : , ,

Yコンビネータ 継続編

fixed point of call/cc だそうです。
タイトルに Y Combinator と入れましたが、正確にはそうではないようです。

すごくおもしろそうだったのでプリントアウトして頑張って読んでます。印刷したら10ページありました。まだ3ページくらいしか読んでないので、残りを読んでみます。

で、一見してもよくわかりません。よくわからないので、いじくり回してみました。先日ノーマルな Y Combinator でやったことの、逆過程のようなことをやりました。
結果、理解できてないのですが、なんとなく雰囲気がつかめた気がします。気がするだけかもしれません。
以下コード。



入門Common Lisp―関数型4つの特徴とλ(ラムダ)計算計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)
written by time: 0 件のコメント:
labels : ,

2010/05/14

pluggable Y Combinator 2

さっきの続き。
コードは以下のとおり。

おもしろいな～。

追記

;(compose hoge (compose fuga ... は (compose hoge fuga ... で良かった。

(time ((Y (compose (make-memoize)(make-trace) fib)) 10))
;(time ((Y (compose (make-memoize) (make-trace) fib)) 10))
; real 0.000
; user 0.000
; sys 0.000
; call with : 10
; call with : 9
; call with : 8
; call with : 7
; call with : 6
; call with : 5
; call with : 4
; call with : 3
; call with : 2
; call with : 1
; call with : 0
89

プログラミングGauche
written by time: 0 件のコメント:
labels : , ,

pluggable Y Combinator

pluggable と付いてますが、メモ化された Y Combinator と違って、ただの素の Y Combinator です。
どちらかというと、メモ化関数を Y Combinator に対応させるということで良いと思います。コードはこちら。

参考にしたのは、昨日に引き続きこちら。これすごくおもしろいです。やばいです。
written by time: 0 件のコメント:
labels : , ,

2010/05/13

メモ化された Y Combinator

メモ化は The Seasoned Schemer にも出てきますね。Y Combinator は昨日のコレを改造しました。


すげー。これカッチョイイな！！memoized-Y 。

こちらを参考にしました。こんな使い方があったとは・・・。
私も以前 JS で Y してるコードがありましたので、うｐ。

ほんと、「マクロのない Sceme」といったノリだなーなどと。

追記

少し修正したので。


On LispThe Seasoned Schemer
written by time: 0 件のコメント:
labels : , , ,

不動点

Y = ^f.(^x.f(xx))(^x.f(xx))
128 ：名無しさん＠お腹いっぱい。[sage]：2008/01/18(金) 20:49:28 ID:c/ULHqOA0
このスレのほとんどのことはスマリヤンの "To Mock a Mockingbird" に書いてあります。Ｙについては "Little Schemer" を読んだら簡単に導出できます。


written by time: 0 件のコメント:
labels : , ,

2010/05/12

Scheme 紙面プログラミング


紙面で Scheme プログラミングしてみました。
帰ってから、実際に動かしたコードは下の方に掲載しました。

なぜこんなことをしたのか

手元にノートしかない状態に長時間置かれたためです。結構、オススメかもしれません。

なぜ Y Combinator なのか

他に適当なネタが思いつきませんでした。すぐ書けるようなものだと、暇つぶしになりませんし・・・。

Y Combinator については、以下の記事を見たときの衝撃からか、何かと気になる存在です。
The Little Schemer, 4th Edition 含め、何度も書いているので、どういうものか理解できている（つもり）です。
いつも Web 上の解説を読んだり、The Little Schemer, 4th Edition のやり方を真似てやっていました。
しかし、どれもしっくりこないので、自力で、自分の頭で考えてやってみました。

やってみてどうだったか

紙でいけます。さすが黒板言語。意外と楽しめます。紙面でやるネタが他にも欲しくなりました。
括弧の対応がすごく難しいですね。しばらくすると慣れてきます。

lambda は ^ （カレット）で書きました。lambda は紙に書くには長すぎました。

結果

階乗から Y Combinator を取り出せ（導き出せ）ました。

目的は、「再帰」の部分と「階乗」の部分を分離すること、と考えて良いのかもしれません。
分離した「再帰」に「階乗」の部分を引数で渡せるようにする、とも言えると思います。
もしくは、「再帰」を一般化するとか「抽象化する」でも良いのかもしれません。

本当の目的はよくわかりません。たぶんλ計算の本を読むと分かるのだと思います。

これができたからといって、特にお得なことはありません。知りません。ですが、頭の体操としては非常におもしろいです。私は好きです。

コード


ではまず、普通の階乗を定義します。


意外とここが一番難しいかもしれません。階乗の定義から手続き名を取り去ります。つまり define を使わないわけですが、名前が無いと再帰できませんよね。
名前を付けるには引数にしてしまえば良い、ということです。ある意味ここが分かれば、もうできたも同然です。ここが頭の中で動かなければ、これ以降が厳しいかもしれません。自分を呼び出す自分に自分を渡す、みたいな。


次に、(f f) の部分を f と書けるようにしたいと思います。ここでは、引数を一つ取る無名関数で包んでしまえば良いです。すると、それを丸ごと外から渡すことができるようになります。(f f) → (lambda (x)((f f) x)) 。


2 で包んだ (lambda (x)((f f) x)) を外から渡せるようにしたいと思います。(lambda (f)(lambda (n) ... の関数をさらに 無名関数で包んで、その中で引数に (lambda (x)((f f) x)) を渡してあげれば良いですね。f のままでも良いのですが、紛らわしいので f を g にしました。これで内側の f には (lambda (x)((g g) x)) が入るようになります。


そうすると、内側の (lambda (f) ... がそのまま「階乗」の部分です。これを分離するのが目的ですから、一番外側で外部から引数として受け取るようにしてあげれば良いです。良い名前が思い浮かばなかったので、concrete の c にしました。できあがり。


単一引数しか受け取れないのもアレなので、可変長引数に対応してみようとしました。たぶん、できたのではないかと思います。apply してあげれば良いです。テストでアキュムレータを第二引数に取る階乗を渡してみましたが、動いているようですね。


これで「再帰」と「階乗」が分離できました。この「再帰」の部分が Y Combinator ということで良いと思います。

あとは、名前を付けるなりして動かしてみます。


The Little Schemer, 4th Edition の9章に出てきますね。The Seasoned Schemer の16章には Y! と Y-bang というのが出てきます。


追記

追記するほどのことでもありませんが・・・。

Y Combinator で検索すると Paul Graham が関わっているベンチャーキャピタルが先に出てきますよね。
あと、MITの盾は Y Combinator ですね。 YF = F(YF) 。

The Little Schemer, 4th EditionThe Seasoned Schemer
written by time: 0 件のコメント:
labels : ,

2010/04/01

TSS length, Y!, Y-bang

The Seasoned Shcemer P.119からまたもやlengthを使ったY Combinatorが出てきます。The Little Schemerで出てきたY Combinatorと違うのは、どうやら副作用を使うところのようです。名前にも「！（bangと読むらしい）」がついています。

ここ、ちょっとよくわかりませんでした。再読が必要かもしれません。取り合えずコードは書いてみました。


The Seasoned Schemer
written by time: 0 件のコメント:
labels : , ,

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 SchemerとThe 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))))))


written by time: 0 件のコメント:
labels : , , ,

2010/01/25

さっきの5の階乗

lambda, cond, zero?, +, -, 0, 1 だけで、というルールで階乗してね、ということで。

; 5の階乗
(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n)
      (cond ((zero? n) 1)
            (else (((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) 0)
                              (else (((lambda (f)
                                        (f f))
                                      (lambda (f)
                                        (lambda (n m)
                                          (cond ((zero? m) n)
                                                (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))
                                     n ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) ((lambda (n)(- n 1)) n)))))))) 5)

 

一応どうなっているかというと・・・。

こんなの書けてもお得なことは何もありません（と思います）。暇つぶしとか頭の体操（罰ゲーム？）としてどうぞ・・・。

 

インクリメントとデクリメントで加算を行なう無名関数を作る（無名関数での再帰ということで再帰はYコンビネータ的な）

;加算

((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) n)
            (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))

 

;実行してみる

(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) n)
            (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m)))))))) 3 4)

; -> 7

 

↑の加算で乗算を作る。再帰はY（ｒｙ

;乗算

((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) 0)
            (else (((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) n)
                              (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) n ((lambda (n)(- n 1)) m))))))))

;実行してみる

(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) 0)
            (else (((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) n)
                              (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) n ((lambda (n)(- n 1)) m)))))))) 4 5)

; -> 20

 

で最終的に階乗の手続きを作って5を渡してみる・・・

(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n)
      (cond ((zero? n) 1)
            (else (((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) 0)
                              (else (((lambda (f)
                                        (f f))
                                      (lambda (f)
                                        (lambda (n m)
                                          (cond ((zero? m) n)
                                                (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))
                                     n ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) ((lambda (n)(- n 1)) n)))))))) 5)

; -> 120

 

参考

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

 

 

written by time: 0 件のコメント:
labels : , , ,

2009/08/31

SchemeとJsでしつこくYCombinator

しつこいことにまたもやYCombinator。
Schemeの方はTechEd2009中に、眠くなったときや話がわからなくなった時に書いた（ｗ

download - ycombinator.scm.txt
download - ycombinator.js.txt
written by time: 0 件のコメント:
labels : , ,

2009/08/24

Jsのfunctionで暇つぶし（ejax）

またもや眠気覚ましに少し遊んでみた。

意味のあるコードではない。

 

いつまでたってもScheme初級者から抜け出せない私はJavaScriptよくで遊ぶ。

 

functionはもうちょっと短くfunくらいにならないかな。まぁ改めてみるとlambdaもなかなか冗長だな。^でいんじゃね。

 

ところで、ejaxとjs2-modeはやはりかなり良い。この二つが完全に連携してくれると助かるけどなー。

（ejaxはemacs lispで書かれたECMA標準に準拠したJavaScriptインタプリタ）

 

download - 10times.recursive.helloworld.js

 

普通の再帰

(function f (n){
   if (0 < n)
   {
     print("Hello, world !");
     f(n - 1);
   }
})(10);

 

マッチポンプ的な再帰に変換。自分に自分を呼び出す自分を渡して・・・

(function (f){
   f(f, 10);
})(function (f, n){
      if (0 < n)
      {
        print("Hello, world !");
        f(f, n - 1);
      }
    });

 

リテラルを一つ外にくくりだしてみる。無名関数はローカル変数の変わりになるというあれ。Schemeのletはlambdaでくくり出すのと同じだよーっていうあれ。

(function (x){
   (function (f){
      f(f, x);
    })(function (f, n){
         if (0 < n)
         {
           print ("Hello, world !");
           f(f, n - 1);
         }
       });
})(10);

 

出力を行う部分を関数として外に出してみる。この辺から後はとくに面白みがない。

(function (y, action){
   (function (x){
      (function (f){
         f(f, x);
       })(function (f, n){
            if (0 < n)
            {
              action(n);
              f(f, n - 1);
            }
          });
    })(y);
})(10, function (v){
      print("Hello, world !");
    });

 

反復条件も関数として外に出してみる。pはpredicateのpということで。

(function (y, a, p){
   (function (x){
      (function (f){
         f(f, x);
       })(function (f, n){
            if (p(n))
            {
              a(n);
              f(f, n - 1);
            }
          });
    })(y);
})(10, function (v){
      print("Hello, world !");
    }, function(c){
      return 0 < c;
    });

 

ここで再帰のたびにデクリメントされる部分を関数として外に出したらfor文ぽいよねーなどと思いながら外にだしてみる。iはincrementのiかな。

(function (y, a, p, i){
   (function (x){
      (function (f){
         f(f, x);
       })(function (f, n){
            if (p(n))
            {
              a(n);
              f(f, i(n));
            }
          });
    })(y);
})(10, function (v){
      print("Hello, world !");
    }, function(c){
      return 0 < c;
    }, function (j){
      return j - 1;
    });
written by time: 0 件のコメント:
labels : ,

2009/05/22

[The Little Schemer]Y Combinator（再）

WS0803 

Y Combinatorとは

 

全景

「The Little Schemer」P.160 ～

;; Road to Y Combinator

(define inc
  (lambda (n)
    (+ n 1)))

 

;; normal length
(define length
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (inc (length (cdr l)))))))

 

;; without "define"

 

;; empty-list-length
(lambda (l)
  (cond
   ((null? l) 0)))

 

;; execute with empty-list
((lambda (l)
   (cond
    ((null? l) 0))) '())
;; => 0

 

;; execute with non-empty-list
((lambda (l)
   (cond
    ((null? l) 0))) '(1 2 3))
;; => #<undef>

 

;; 1-element-list-length
(lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))(cdr l))))))

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))(cdr l)))))) '())
;; => 0

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))(cdr l)))))) '(a))
;; => 1

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))
          (cdr l))))))
  '(1 2))
;; => *** ERROR: operation + is not defined between 1 and #<undef>

 

;;2-elements-list-length
(lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))

 

;; execute 2-elements-list-length
((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'())
;; => 0

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'(a))
;; => 1

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'(a b))
;; => 2

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'(1 2 3))
;; => *** ERROR: operation + is not defined between 1 and #<undef>

 

;;((lambda (length)
;;   (lambda (l)
;;     (cond
;;      ((null? l) 0)
;;      (else (inc (length (cdr l)))))))
;; 'eternity)

 

;; eternity style empty-list-length

(((lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc (f (cdr l)))))))
'eternity) '())
;; => 0

 

;; eternity style 1-element-list-length
(((lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l)))))))
  ((lambda (f)
     (lambda (l)
       (cond
        ((null? l) 0)
        (else (inc (f (cdr l)))))))
   'eternity))
'(1))
;; => 1

 

;; eternity style 2-elements-list-length
(((lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l)))))))
  ((lambda (f)
     (lambda (l)
       (cond
        ((null? l) 0)
        (else (inc (f (cdr l)))))))
   ((lambda (f)
      (lambda (l)
        (cond
         ((null? l) 0)
         (else (inc (f (cdr l)))))))
    'eternity)))
'(1 2))
;; => 2

 

;; without repetitions
((lambda (make-length)
   (make-length 'eternity))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc (f (cdr l))))))))

 

;; execute without-repetitions-eternity-stryle-length
(((lambda (make-length)
    (make-length 'eternity))
  (lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l))))))))
'())
;; => 0

 

(((lambda (make-length)
    (make-length
     (make-length 'eternity)))
  (lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l))))))))
'(1))
;; => 1

 

(((lambda (make-length)
    (make-length
     (make-length
      (make-length 'eternity))))
  (lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l))))))))
'(1 2))
;; => 2

 

;;What is recursion like?
;;It is like an infinite tower of applications of make-length to an arbitrary function.

 

;;Do we readly need an infinite tower?
;;Not really of course. Everytime we use length we only need a finite number. but we never know how many.

 

;; meke-length to make-length
((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))

 

;; execute make-length to make-length
(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'())
;; => 0

 

(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'(1))
;; => 1

 

(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'(1 2))
;; => 2

 

(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'(1 2 3 4 5))
;; => 5

 

;; without (f f)
(((lambda (make-length)
   (make-length make-length))
  (lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc
             ((lambda (x)
                ((f f) x))
              (cdr l))))))))
'(1 2 3 4 5))
;; => 5

 

;; move out (f f)
((lambda (f)
   (f f))
  (lambda (f)
    ((lambda (g)
       (lambda (l)
         (cond
          ((null? l) 0)
          (else
           (inc (g (cdr l)))))))
     (lambda (x)
       ((f f) x)))))

 

;; execute move-out-(f f)
(((lambda (f)
    (f f))
  (lambda (f)
    ((lambda (g)
       (lambda (l)
         (cond
          ((null? l) 0)
          (else
           (inc (g (cdr l)))))))
     (lambda (x)
       ((f f) x)))))
'(1 2 3 4 5))
;; => 5

 

;; extract function's body
;;(lambda (g)
;;    (lambda (l)
;;      (cond
;;       ((null? l) 0)
;;       (else (inc (g (cdr l)))))))
(((lambda (le)
    ((lambda (f)
       (f f))
     (lambda (f)
       (le (lambda (x)
             ((f f) x))))))
  (lambda (g)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (g (cdr l))))))))
'(1 2 3 4 5))
;; => 5

 

;; named y
(define y
  (lambda (le)
    ((lambda (f)
       (f f))
     (lambda (f)
       (le (lambda (x)
             ((f f) x)))))))

 

;; execute y with length
((y (lambda (g)
      (lambda (l)
        (cond
         ((null? l) 0)
         (else (inc (g (cdr l))))))))
'(1 2 3 4 5))

 

参考

 

The Little Schemer

The Little Schemer

posted with amazlet at 09.03.30

Daniel P. Friedman Matthias Felleisen
Mit Pr
売り上げランキング: 16078

おすすめ度の平均: 5.0

5 小さなScheme処理系で学ぶ数学基礎理論
5 Schemeが好きになります
5 英語であるのが苦痛にならない楽しさ
5 面白いスタイル

Amazon.co.jp で詳細を見る
written by time: 0 件のコメント:
labels : , ,

2008/12/24

【Scheme】Y-Combinator（Yコンビネータ/不動点演算子）

【Scheme】Y-Combinator（Yコンビネータ/不動点演算子）
■Y-Combinator
「Y-Combinator」を理解するために書いたコードを元に、思考の過程を書く。
■参考
記事最下に記載。
■材料
再帰を伴う処理を基に書いていく。
通例通り階乗（http://ja.wikipedia.org/wiki/階乗）を求める「fact」関数を例に取る。
■その前に・・・
Y-Combinatorは何がしたいのか？
・無名（匿名）関数で再帰を行いたい。
⇒ 普通は「fact」関数の定義の中で「fact」呼び出しが行われる。
⇒ 「fact」という名前を使わずに再帰したい。
■注
１）、「;」で始まるコメントは出鱈目な英語です。（DrScheme（http://www.db.is.kyushu-u.ac.jp/enshu/）の日本語表示が気持ち悪いから）
２）、「;=>」は実行結果の出力
まずは与えられた数字の階乗を求める関数、「fact」を定義してみる。
;normal fact
(define fact
  (lambda (n)
    (if (zero? n)
    1
    (* n (fact (- n 1))))))
(fact 5) ;=> 120
見慣れた感じ。 Schemeやったことなくても読めるはず。
;gate of normal fact
(define fact-maker 
  (lambda ()
    (lambda (n)
      (if (zero? n)
      1
      (* n (fact (- n 1)))))))
((fact-maker) 5);=> 120
factを直接呼び出したくない。 fact呼び出しをlambdaで包んで、fact-makerという名前をつけてみる。 factの名前を排除したかったが、結局最後のところでfactを呼び出している。 factへの入り口が変わったに過ぎない。
;receive fact
(define fact-maker
  (lambda (f) 
    (lambda (n)
      (if (zero? n)
        1
        (* n (f (- n 1)))))))
((fact-maker fact) 5);=> 120
さっきfactを包むのに使ったlambdaに引数fを追加して呼び出し時にfactを渡してみる。これでfactは処理の「外」に出た。まだ処理の中にfactの残骸が見える。
(if (zero? n)
  1
  (* n (f (- n 1))))
;maker receive maker
(define m
  (lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1)))))))
((m m) 5);=>120
ここで、fact-makerはfactを置き換えるために作ったことを思い出してみる。 ((fact-maker fact) 5)を((fact-maker fact-maker) 5)としてみる。
ついでに「fact-maker」を「m」に置き換える（見づらかったので）。
fact-makerはfactを置き換えるためのものなので当然正常に動く。ただし、fact-makerはfactを引数に取っていた。置き換えると、fact-makerはfact-makerを引数に取らなければならない。
よって、fact-makerに渡されたfact-makerは引数fに割り当てられることになる。つまり、(f (- n 1))は((f f) (- n 1))となる。 ((fact-maker fact-maker) (- n 1)) ⇒ ((f f) (- n 1))
((m
  (lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1))))))) 5);=>120
呼び出しである((m m) 5)の引数であるmを直接mの中身と置き換えてみる。もちろん正常に動く。
(((lambda (f) 
  (lambda (n)
    (if (zero? n)
      1
      (* n ((f f) (- n 1))))))
  (lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1))))))) 5);=>120
((m m) 5)のmを両方ともmの中身で置き換えてみる。かなり冗長だけど、名前を使わずに再帰できてるっぽい。
; (f 5) equals ((lambda (n) (f n)) 5) ; ((lambda (n) ((f f) n)) 5)
(define m
  (lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((lambda (n) ((f f) n)) (- n 1)))))))
((m m) 5);=>120
((f f) (- n 1))の(f f)のところがｶｯｺﾜﾙｲ。 (f (- n 1))にしたい。そのためのステップとして、(fact 5)と((lambda (x) (fact x)) 5)は同じなので、(f f)が(lambda (n) ((f f) n))となる。
(【scheme】schemeのlambdaラムダλ（http://ameblo.jp/valvallow/entry-10182420367.html）を見ればわかるように（わかりにくすぎる）)
(define m
  (lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n (f (- n 1)))))))
(lambda (n) ((f f) n))を「外」に追い出して、fに渡すようにすると、m自体はこうなる。あとは、呼び出し時に(lambda (n) ((f f) n))を渡すようにすればいい。
((m m) 5)
とりあえず、この右側のmを(lambda (n) ((f f) n))に変えることができればOK。
((m
  (lambda (n) ((f f) n))) 5);=> error
これは、(lambda (n) ((f f) n))がその場で評価されようとしてしまうから。
;gate of y-combinator
(lambda (p)
  (m (lambda (n) ((p p) n))))
(lambda (n) ((f f) n))をmに渡す部分をlambdaにくるみ、fという名前をpに変更。
((m
  (lambda (p) 
    (m (lambda (n) ((p p) n))))) 5);=> 120
今、((m m) 5)の右側のmを置き換えることに成功したのでこういうことになる。正常に動作。
(((lambda (p)
  (m (lambda (n) ((p p) n))))
    (lambda (p)
      (m (lambda (n) ((p p) n))))) 5);=> 120
次に、((m m) 5)の左側のmも同様に置き換える。正常に動作。
;receive m receive 5
(((lambda (f)
  ((lambda (p)
    (m (lambda (n) ((p p) n))))
  (lambda (p)
     (m (lambda (n) ((p p) n)))))) m) 5)
次に、mを「外」に追い出したいので、mに変わるfを引けるようにする。ここではまだfを引けるようにlambdaでくくりだしただけで、mは置き換えていない。
;replace m to received f ;this is the y-combinator
(lambda (f)
  ((lambda (p) 
    (f (lambda (n) ((p p) n))))
  (lambda (p)
    (f (lambda (n) ((p p) n))))))
mを外から引いたfに置き換えて完了。これがYコンビネータ（不動点演算子）らしい。 factの部分が完全に消えうせた。つまりfactも「再帰」から開放された。
;receive 5 reveive m to execute y-combinator
(((lambda (f)
  ((lambda (p)
    (f (lambda (n) ((p p) n))))
  (lambda (p)
    (f (lambda (n) ((p p) n)))))) m) 5);=>120
階乗を求めるmとmの引数となる5を渡す。正常に動作する。
;named Y to y-combinator
(define Y
  (lambda (f)
    ((lambda (p)
      (f (lambda (n) ((p p) n))))
    (lambda (p)
      (f (lambda (n) ((p p) n)))))))
Yコンビネータに名前をつける。でも冗長さが残っててｶｯｺﾜﾙｲ。（同じ処理が2回書いてある）
((Y m) 5);=>120
((Y m) 10);=>3628800
;twice ;(lambda (p) ; (f (lambda (n) ((p p) n)))) ; to once
(define Y
  (lambda (f)
    ((lambda (h)(h h))
      (lambda (p)
        (f (lambda (n)((p p) n)))))))
((Y m) 5);=> 120
冗長な部分を排除したい。重複部分をlambdaでくくりだす。
;fibonacci
(define fib
  (lambda (n)
    (if (<= n 2)
      1
      (+ (fib (- n 1))(fib (- n 2))))))
(fib 10);=> 55
フィボナッチ数列を求める普通の関数。今度はフィボナッチ数列のコードで試してみる。
;Y-Combinator fibonacci
(define fib
  (lambda (f)
    (lambda (n)
      (if (<= n 2)
        1
        (+ (f (- n 1))(f (- n 2)))))))
((Y fib) 10);=> 55
正常に動作。
【全景】
 
;normal fact
(define fact
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))
(fact 5) ;=> 120
;gate of normal fact
(define fact-maker
  (lambda ()
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1)))))))
((fact-maker) 5)
;receive fact
(define fact-maker2
  (lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n (f (- n 1)))))))
((fact-maker2 fact) 5)
;maker receive maker
(define m
  (lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((f f) (- n 1)))))))
((m m) 5)
((m
(lambda (f)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((f f) (- n 1))))))) 5)
(((lambda (f)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((f f) (- n 1))))))
  (lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((f f) (- n 1))))))) 5)
; (f 5) equals ((lambda (n) (f n)) 5)
; ((lambda (n) ((f f) n)) 5)
(define m2
  (lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((lambda (n) ((f f) n)) (- n 1)))))))
((m2 m2) 5)
;(lambda (f)
;  (f0 (lambda (n) ((f f) n))))
; is one of fact-maker
(define f0
  (lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n (f (- n 1)))))))
;gate of y-combinator
(lambda (p)
  (f0 (lambda (n) ((p p) n))))
((m
  (lambda (p)
    (f0 (lambda (n) ((p p) n))))) 5)
(((lambda (p)
  (f0 (lambda (n) ((p p) n))))
(lambda (p)
  (f0 (lambda (n) ((p p) n))))) 5)
;receive f0 receive 5
(((lambda (f)
  ((lambda (p)
     (f0 (lambda (n) ((p p) n))))
   (lambda (p)
     (f0 (lambda (n) ((p p) n)))))) f0) 5)
;replace f0 to received f
;this is the y-combinator
(lambda (f)
  ((lambda (p)
     (f (lambda (n) ((p p) n))))
   (lambda (p)
     (f (lambda (n) ((p p) n))))))
;receive 5 reveive f0 to execute y-combinator
(((lambda (f)
  ((lambda (p)
     (f (lambda (n) ((p p) n))))
   (lambda (p)
     (f (lambda (n) ((p p) n)))))) f0) 5)
;named Y to y-combinator
(define Y
  (lambda (f)
    ((lambda (p)
       (f (lambda (n) ((p p) n))))
     (lambda (p)
       (f (lambda (n) ((p p) n)))))))
((Y f0) 5)
((Y f0) 10)
;twice
;(lambda (p)
;       (f (lambda (n) ((p p) n))))
; to once
(define Y2
  (lambda (f)
    ((lambda (h)(h h))
     (lambda (p)
       (f (lambda (n)((p p) n)))))))
((Y2 f0) 5)
;fibonacci
(define fib
  (lambda (n)
    (if (<= n 2)
        1
        (+ (fib (- n 1))(fib (- n 2))))))
(fib 10)
;Y-Combinator fibonacci
(define fib2
  (lambda (f)
    (lambda (n)
      (if (<= n 2)
          1
          (+ (f (- n 1))(f (- n  2)))))))
((Y fib2) 10)
【結論】
Yコンビネータはすごい。
何がすごいか、言語化できない。
ということは、まだ理解できていない。ということ。
求め方、組み方はなんとなく理解できた。
他の言語でも組める気はする。
JavaScript、Ruby、C#で試してみたい。
Yコンビネータの何がすごいのか、言語化できるように理解を深めたい。
Schemeの勉強になったし、Y-Combinatorの求め方もわかったし、遅延評価についてはまだイメージがぼやけってるけど、少しだけ想像できるようになってラッキー♪
なにより、すごくおもしろかったｗ
【参考】
[C#]Y Combinatorが凄すぎる！
http://d.hatena.ne.jp/yuji1982/20080124/1201177935
⇒ 発端の記事。
ちょうどyuji1982さんとTwitterなんかで話すようになったころ。
2008年の1月くらいにこの記事見て、yuji1982さんが遠い世界の人だと感じた。
Y コンビネータって何？ - IT戦記
http://d.hatena.ne.jp/amachang/20080124/1201199469
⇒ もう一つの発端。
世間はこれで火がついたっぽい。
yuji1982のブックマーク / Y combinator (11)
http://b.hatena.ne.jp/yuji1982/Y%20combinator/
⇒ 発端となったyuji1982さんのYコンビネータに関するブックマーク。
Y Combinator
http://www.loveruby.net/ja/misc/ycombinator.html
⇒ 今回は主にここを参考にした。
Scheme
Yコンビネータを読み解こう
http://d.hatena.ne.jp/tanakaBox/20080203/1202023473
⇒ 後で知ったページ。ここが一番わかりやすい。
Scheme
Y combinator on Scheme
http://fixedpoint.jp/2007/02/14/y.html
⇒ Scheme
不動点演算子ふたたび
http://d.hatena.ne.jp/sumii/20051203/1133575324
⇒ Scheme
C# 3.0 と不動点演算子
http://d.hatena.ne.jp/NyaRuRu/20070722#1
⇒ C#
以前から思ってたけど、異世界の人。
Yコンビネータができるまで（C#）
http://faroffsea.blogspot.com/2008/09/yc.html
⇒ C#
C#でYコンビネータ
http://blog.inomata.lolipop.jp/?eid=815474
⇒ C#
Recursive lambda expressions
http://blogs.msdn.com/madst/archive/2007/05/11/recursive-lambda-expressions.aspx
⇒ C#
不動点オペレータについて
http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/fix.html
⇒ Scheme
ホワット・ア・ワンダフル・ワールド
http://alohakun.blog7.fc2.com/blog-entry-894.html
⇒ 直接は関係ない。
そろそろ分かっておきたいY Combinator
http://d.hatena.ne.jp/authorNari/20081130/1227977113
⇒ Ruby
Yコンビネータメモ
http://d.hatena.ne.jp/gotin/20080127/1201372491
⇒ JavaScript
Yコンビネータ復習
http://faroffsea.blogspot.com/2008/02/y.html
⇒ Common Lisp
MIT（マサチューセッツ工科大学）の盾
http://groups.csail.mit.edu/mac/projects/scheme/
⇒ SICPはここの教科書らしい。

The Little Schemer, 4th Edition 計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)計算機プログラムの構造と解釈
written by time: 0 件のコメント:
labels : ,
登録: 投稿 (Atom)