継続のバックアップ(No.4)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
継続へ行く。
- 1 (2007-01-27 (土) 00:29:45)
- 2 (2007-01-27 (土) 00:29:45)
- 3 (2007-01-27 (土) 00:29:45)
- 4 (2007-01-27 (土) 00:29:45)
- 5 (2007-02-03 (土) 15:33:00)
- 6 (2007-02-03 (土) 15:33:00)
- 7 (2007-02-03 (土) 15:33:00)
- 8 (2007-02-03 (土) 15:33:00)

継続とは?
- 何ができるの?
- 天使のオペレータ amb
実際の使用例
- 参考文献
継続サーバ
Ocsigen OCamlによる継続ベースWeb programming framework.

継続とは? &dagger;

↑

何ができるの? &dagger;

大域脱出
例外処理
コルーチン(軽量スレッド)

↑

天使のオペレータ amb &dagger;

非決定性

amb@Wiliki

例えば、
(let ((i (amb 4 6 7))
       (j (amb 5 8 11)))
  (if (prime? (+ i j))
       (list i j)
       (amb)))
;Value 23: (6 5)
のようにすると '(4 6 7) と '(5 8 11) のうちから二つの数の和が素数になる組の１つを返します。

これを理解するのに、自分は3ヶ月かかりました。 ambは、バックトラック演算子です。動きを大雑把に言うと、

(let (i (amb 4 6 7))で、 i に 4 が入ると同時に、この時点のツヅキ、

		"6 7))
     (j (amb 5 8 11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

を取り出して、スタックにpush。

次の行、 (j (amb 5 8 11))で、 j に 5が入ると同時に、この時点のツヅキ、

		"8 11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

を取り出して、スタックにpush。

(prime? (+ 4 5))は偽。(amb)が動く。amb関数は、引数なしで呼ばれると、スタックをpopして、中身の、ツヅキを実行。

		"8 11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

が実行されて、jに8が入ると同時に、この時点のツヅキ、

		  "11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

を取り出して、スタックにpush...という感じです。

↑

実際の使用例 &dagger;

論理パズル(カロタンパズルや地図の塗り分け)が紹介されています

SEND+MORE=MONEY [#x0d17572]

(use srfi-1)

;; stack of cc.
(define fail '())

;; nondeterminsm operator
(define (amb li)
  (if (null? li)
      ((pop! fail))
      (call/cc
       (lambda (cc)
	  (push! fail (lambda ()
		        (cc (amb (cdr li)))))
	  (car li)))))

(define (toint li)
  (fold (lambda (a b) (+ a (* b 10))) 0 li))

(define (solve)
  (let ((digs (iota 10 0))
         (digs1 (iota 9 1)))
    (let* ((S (amb digs1))
            (E (amb (lset-difference = digs (list S))))
            (N (amb (lset-difference = digs (list S E))))
            (D (amb (lset-difference = digs (list S E N))))
            (M (amb (lset-difference = digs1 (list S E N D))))
            (O (amb (lset-difference = digs (list S E N D M))))
            (R (amb (lset-difference = digs (list S E N D M O))))
            (Y (amb (lset-difference = digs (list S E N D M O R)))))
      (if
       (= (+ (toint (list S E N D))
              (toint (list M O R E)))
          (toint (list M O N E Y)))
       (list S E N D '+ M O R E '= M O N E Y)
       (amb '())))))

(print
 (call/cc
  (lambda (cc)
    ;; initial value for fail
    (push! fail
	    (lambda ()
	      (cc 'no-choise)))
    (solve))))

↑

参考文献 &dagger;

↑

継続サーバ &dagger;

↑

Ocsigen OCamlによる継続ベースWeb programming framework. &dagger;

論文 Typing web interaction with Objective Caml
継続ベースWebプログラミング Continuation-based Web programming
XHTMLの静的チェック Static checking of XHTML
セッションの自動管理 Automatic management of sessions
モジュール指向 Concise and modular programming
Webサーバ、実装は協調スレッドによる。 Web server, implemented with cooperative threads
カウンタはこう書けます。

let compt = 
  let next =
    let c = ref 0 in
      (fun () -> c := !c + 1; !c)
  in
  register_new_service 
    ~url:["compt"]
    ~get_params:unit
    (fun _ () () ->  return
      (html
       (head (title (pcdata "counter")) [])
       (body [p [pcdata (string_of_int (next ()))]])))

See this example here

継続 のバックアップ(No.4)