Scheme:CPS

Scheme:CPS

pitecan.comへの移転のためか、増井さんちのWiki掲示板は以前のコンテンツがなくなっているようなので、Google cacheから転載します。-- SHIMADA (2003/07/26 05:41:15 PDT)


転載ここから ----

普通の奴らの上を行け」の追記文に出てくる、WebBasedアプリケーションと継続について。 継続と聞くとSchemeのcall/ccを連想するかもしれませんが、むしろここで重要なのは、「継続渡しスタイル(Continuation Passing Style, CPS)」です。CPSそのものは、 PerlでもRubyでもJavaでも書けます。どっちかというと、普通の手続き指向から考え方を変えるのがポイントなんで。

CPSのポイント。手続きは呼び出したら戻ってきません。行ったっきりです。ですから、その手続きの後で何か別のことをやりたいなら、「その後にして欲しいこと=継続」を手続きに渡してやります。

ちょっと長くなりますが、例を挙げた方がわかりやすいでしょう。例えば次のコードを見て下さい(Schemeで失礼)。

  (define (match data pred cont)
    (cond 
      ((null? data)     
       (cont #f #f))
      ((pred (car data)) 
       (cont (car data) (lambda () (match (cdr data) pred cont))))
      (else (match (cdr data) pred cont))))

手続きmatchは、データのリスト、述語関数、および継続手続きを取り、述語関数が真を返すデータをリストから探します。そういうデータが見つかれば、継続手続きに見つかったデータと、更に探索を続けるための継続 を渡します。見つからなければ、継続手続きに#fを渡します。

例えば、与えられたデータのリストから奇数であるものを表示してみます。

  (define (find-odd data)
    (match data odd?
           (lambda (found cont)
             (if found
                 (begin (format #t "found:~s~%" found) (cont))
                 (format #t "end.~%")))))

formatは標準のSchemeには無いですが、大抵の処理系に入っているでしょう。実行してみます。("gosh>"はScheme処理系の出すプロンプトです)

  gosh> (find-odd '(0 1 2 3 4 5))
  found:1
  found:3
  found:5
  end.

これだけじゃ全然ありがたみがわからないでしょうが、ユーザが一度に全部を検索するのでなく、ひとつひとつ検索結果を調べて、検索を続けるかどうかを決めたいとしたらどうでしょう。

  (define (find-odd-1 data)
    (match data odd?
           (lambda (found cont)
             (if found
                 (begin (format #t "found:~s~%" found) cont)
                 (begin (format #t "end.~%") #f)))))

これは一回毎に結果を表示して、「検索を続ける」ための手続きを返す関数です。実行してみます。

 gosh> (define next #f)
 next
 gosh> (set! next (find-odd-1 '(0 1 2 3 4 5)))
 found:1
 #<closure 101a7558>
 gosh> (set! next (next))
 found:3
 #<closure 101a74c8>
 gosh> (set! next (next))
 found:5
 #<closure 101a7498>
 gosh> (set! next (next))
 end.
 #f

一回毎に結果が表示され、「検索を続ける」関数をnextに再代入しています。(#<closure 101a7558> 等はset!の戻り値です。処理系によってはset!は値を戻さないかもしれません)

ここで注目して欲しいのは、一度find-odd-1から戻ってきた後は、ユーザに対するフロントエンドは処理の内容からは一切独立しているというところです。とにかく作業を続けたければ、nextを呼び出せば良い。ここでは単純な繰り返し処理でしたが、場合によっては別の処理に 継続を飛ばしても良いし、ユーザがYesと答えた場合とNoと答えた場合それぞれへの 継続を返すようなインタフェースにしても良い。いずれにせよ、処理の途中状態はフロントエンドからは隠蔽されているわけです。

ここまできたらWebアプリへの応用はストレートでしょう。サーバ側でユーザのセッションIDに対して現在の継続を記憶しておき、ユーザのレスポンスが来たら継続を呼び出す、ということを繰り返すだけです。

もちろん、処理の途中状態をトランジェントなクラスの中に明示的に保存するようにしておいたって同様のことは実現できます。継続渡しの場合、途中状態がクロージャの環境に保存されているだけとも言えます。

以上、継続渡しの説明でした。--Shiro

転載ここまで ----

Tags: 継続, CPS


Last modified : 2013/04/27 07:38:01 UTC