guttyonのメモ帳・日記

antenna | bookmark | 2ch | hotmail | google | amazon

2003 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
2004 | 02 | 04 | 05 | 06 | 07 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 09 | 10 | 11 |
2006 | 01 |
 | 

2004-07-27

2004-07-23

[][]pythonのgeneratorとschemeのcall/ccを学んでみる

pythonschemeも素人なんで、大嘘こいてるかもしれません。ご注意を…

まず、pythonのジェネレータを用いたコードを書いてみる。

yield文のある関数は、自動的にジェネレータ関数となる。

ジェネレータ関数は、ジェネレータオブジェクトを返す。

オブジェクトと言ったのは、継続情報を持つから。

(つまり、ジェネレータ関数自体が、継続情報をもっているわけではない)

def t1:
  global b
  while True:
    print 'yield:t1'
    yield b
    print 'next:t1'

def t2:
  global a
  while True:
    print 'yield:t2'
    yield a
    print 'next:t2'

a = t1()
b = t2()
tgt = a
for i in range(5):
  tgt = tgt.next()

ジェネレータオブジェクトはnext()の返り値として、yieldの引数を返すことに注意すると、t1とt2が交互に動く事がわかる。

このコードをschemeで表現してみるのが、今回の目標。

そして、pythonのジェネレータとschemeのcall/ccに対して理解を得たい。

が、その前に3つほどschemeの作法を学んでみる。

C言語でいう関数staticな変数の宣言法を学ぶ。

関数を宣言する時は、以下のようにdefineの次にlambdaが来るのが普通である。

(define add
  (lambda (a b) (+ a b)))

それに対して、以下のコードは、lambdaの前にletで、nextを0に束縛している。

このように、lambdaの前にletを使う事により、C言語でいう関数staticな変数を宣言できる。

(状態を持つ関数を宣言できるともいう)

(define count
  (let ((next 0))
    (lambda ()
      (let ((v next))
        (set! next (+ next 1))
        v))))

この関数countは呼ぶたびに内部状態のnextがインクリメントする事になる。

関数を返す関数を学ぶ

以下の関数は、"nを足す関数"を返す関数である。

先に宣言したaddのlambdaから、引数を1つ奪ったもう1つのlambdaで囲んだ形になっている。

(define gen-add-n
  (lambda (n)
    (lambda (x) (+ x n)))) 

・繰り返しの方法を学ぶ

まずは、以下のコード。この実行文は無限に"hello"を出力し続ける。

(let loop ()
  (print "hello")
  (loop))

次は、決まった回数だけ繰り返してみるコード。

説明しにくいのだが、以下のコードは5回"hello"を出力する。

(let loop ((count 0))
  (if (not (= count 5))
    (begin
      (print "hello")
      (loop (+ count 1)))))

それでは、先のpythonのコードをschemeで書いてみる。

実際には等価じゃない以下のコードをまず。

;;;t1にstaticにcontがあるのが問題
(define t1dummy
  (let ((cont 0))
    (lambda ()
      (if (not (eq? cont 0))
          (cont)
          (call/cc (lambda (break)
                     (let loop ()
                       (print "yield:t1")
                       (call/cc (lambda (x) (set! cont x) (break b)))
                       (print "next:t1")
                       (loop)
                       )))))))

coroutineは、どのように振舞うべきだろうか?以下の2点が重要

・どこまで実行したか?の足跡情報を残す

・足跡情報を残したら、関数t1から抜けなければならない

これを踏まえて、上のコードの読んでみる。

外側のcall/ccで取得する継続情報breakは、内側のcall/cc内から外側のcall/ccの外まで一気に出る為(t1dummyから抜けたい)に用いる。

内側のcall/ccで取得する継続情報xは、関数static変数のcontに保存しておき、

次にt1dummy実行時、ここから実行されるように足跡情報を残す。

(contが継続情報を含み、初期値0では無い時、(cont)するだけで、

(print "next:t1")から実行されることになる。)

contに継続情報を保存できたら、(break b)で関数をぬける。

しかし、ここである事に気付く。

pythonのコードは、t1自体は、ジェネレータ関数であり、継続情報をstaticには持っていないことだ。

実際に継続情報を持つのは、t1()の返り値のジェネレータオブジェクトであった。

それを考慮し、以下のようにlambdaで関数を囲んでやりscheme版t1の完成となる。

(define t1
  (lambda ()
    (let ((cont 0))
      (lambda ()
        (if (not (eq? cont 0))
            (cont)
            (call/cc (lambda (break)
                       (let loop ()
                         (print "yield:t1")
                         (call/cc (lambda (x) (set! cont x) (break b)))
                         (print "next:t1")
                         (loop)
                         ))))))))

後は、

(define a (t1))
(define b (t2))
(define tgt a)
(let loop ((count 0))
  (if (not (= count 5))
    (begin
      (set! tgt (tgt))
      (loop (+ count 1)))))

とこんな感じだろうか。schemeに慣れてないので、かなりコードが長くなったが、

define-syntax等を用いて簡単に短くできるんだろう?(よく知らない)

2004-07-20

2004-07-14

DocBook

DocBook で文書を書こう!
http://members.at.infoseek.co.jp/zzyyb/docbook/
実用 DocBook 入門
http://www.linux.or.jp/JF/JFdocs/docbook-intro/

2004-07-08

2004-07-05

 | 
2003 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
2004 | 02 | 04 | 05 | 06 | 07 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 09 | 10 | 11 |
2006 | 01 |

最新キーワード

1. 斎藤一人
2. 安野ともこ
3. SAW2
4. トム・ウォーキンショー
5. マイケル・コンラッド
6. ミーン・マシーン
7. バリー・スコルニック
8. レオ・ペン
9. マイケル・ペン
10. ラルフ・ブライアンズ
Connection: close