トップ
新規
単語検索
ヘルプ
継続
をテンプレートにして作成
開始行:
#contents
*継続とは?[#y87e71e0]
まず、大域脱出の例を見てみましょう。
[[SEND+MORE=MONEY:http://tsukimi.agusa.i.is.nagoya-u.ac.j...
でも、
return"ラベル"を定義して、
(return (list S E N D '+ M O R E '= M O N E Y))
なんてことをやっています。
リストlisと述語手続きpredを取り、lisの各要素に順にpredを...
(define (find pred lis)
(call/cc
(lambda (return)
(for-each (lambda (elt) (if (pred elt) (return elt...
#f)))
lambda (return) はちょっと奇妙です。
私は脳内で、
(define (find pred lis)
(let/cc
return
(for-each (lambda (elt) (if (pred elt) (return elt)))...
#f))
と読んでいます。
この継続を、グローバル変数などに保存しておくこともできま...
例えば、継続returnを取り出して、グローバル変数 k に保存し...
(define k #f)
(+ 1 (call/cc (lambda (return)
(set! k return)
(return 1))))
= 2
return、および k には、あそこに戻る継続が入っています。
それで、
(k 10)
= 11
(k 50)
= 51
になります。
継続というのは、計算のスタックを取り出したものです。計算...
<>
1
+
です。そして、
return = k = (+ 1 <>)
です。lambda式で書くと
return = k = (lambda (x) (+ 1 x))
です。
実は、計算のスタックは、lambda式で書きなおすことができま...
(print (+ 1 2)) = ((lambda (x) (print x)) ((lambda (x) (...
(* 3 (+ 1 2)) = ((lambda (x) (* 3 x)) ((lambda (x) (+ 1 ...
スタックのコピーである継続がなぜlambda計算から自然と生ま...
** 発展学習 CPS "Continuation Passing Style" 継続渡しスタ...
さきほどの"計算のスタックをlambda式で書き直す"は、CPSと呼...
range 関数を書いてみます。 range 0 9 = (0,...,9)
(define (range a b)
(if (> a b)
[]
(cons a (range (+ a 1) b))))
(print (range 0 2)) のスタックはこうなるでしょう。
[]
cons 2
cons 1
cons 0
print
lambda式で書き直すと、
((lambda (x) (print x)) ((lambda (x) (cons 0 x)) ((lambd...
となります。
継続渡しスタイルは、このlambda (x)流の書きかたを陽にする...
range 関数はこうなります。
(define (range a b k)
(if (> a b)
(k [])
(range (+ a 1) b (lambda (x) (k (cons a x))))))
- 実際に (range 0 3 (lambda (x) (print x)))
と実行してごらんなさい。
- ときほぐすと、
((lambda (x) (print x)) ((lambda (x) (cons 0 x)) ((lambd...
と等しくなることを確かめなさい。
この k に入っているものこそ、継続です。
バトー、忘れないで。あなたがプログラムを書くとき、継続は...
**何ができるの? [#c933f2be]
- 大域脱出
- 例外処理
- コルーチン(軽量スレッド)
**天使のオペレータ amb [#u2719f75]
- [[非決定性:http://www.shido.info/lisp/scheme_amb.html]]
- [[amb@Wiliki:http://www.shiro.dreamhost.com/scheme/wili...
例えば、
(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関数は、引数なしで...
"8 11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
が実行されて、jに8が入ると同時に、
この時点のツヅキ、
"11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
を取り出して、スタックにpush...という感じです。
* 実際の使用例 [#s806e503]
- 論理パズル(カロタンパズルや地図の塗り分け)が[[紹介され...
- 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...
(O (amb (lset-difference = digs (list S E N ...
(R (amb (lset-difference = digs (list S E N ...
(Y (amb (lset-difference = digs (list S E N ...
(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))))
**参考文献 [#vf61a3fe]
-[[SICP.Nondeterministic Computing:http://mitpress.mit.ed...
-[[独習 Scheme 三週間:http://www.sampou.org/scheme/t-y-sc...
-[[なんでも継続:http://www.shiro.dreamhost.com/scheme/doc...
-[[Scheme:なぜSchemeにはreturnが無いのか:http://www.shiro...
-[[Schemeを作ろう 第3回:http://www.jah.ne.jp/~naoyuki/Wri...
-[[Scheme入門 継続:http://www.shido.info/lisp/scheme_cc.h...
- 継続には副作用がある。
[[Scheme:call/ccと副作用:http://www.shiro.dreamhost.com/s...
-[[名大の謎の天才h003149b氏:http://www.ice.nuie.nagoya-u....
*OCamlでcall/cc [#v1ede6b7]
Leroyのcall/ccライブラリ
http://pauillac.inria.fr/~xleroy/software.html
があります。
*継続サーバ [#z633f1a1]
-[[もとネタになった、Queinnec氏の論文PDF:http://www-spi.l...
-[[境界を越える: 継続とWeb開発、そしてJavaプログラミング:...
-[[継続サーバの実装の最先端、Seaside:http://www.seaside.s...
-[[Seasideの開発者が継続のゆくえについて語る:http://small...
-[[Haskellの継続サーバWASH:http://www.informatik.uni-frei...
-[[SchemeによるCPSスタイルの継続サーバKahua:http://www.ka...
-[[WebBasedアプリケーションと継続について、わかりやすい説...
* [[Ocsigen:http://www.ocsigen.org/]] OCamlによる継続ベー...
- [[論文 Typing web interaction with Objective Caml:http:...
- 継続ベースWebプログラミング Continuation-based Web prog...
- XHTMLの静的チェック Static checking of XHTML
- セッションの自動管理 Automatic management of sessions
- モジュール指向 Concise and modular programming
- Webサーバ、実装は協調スレッドによる。 Web server, imple...
- カウンタはこう書けます。
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:http://www.ocsigen.org/tuto/compt]]
終了行:
#contents
*継続とは?[#y87e71e0]
まず、大域脱出の例を見てみましょう。
[[SEND+MORE=MONEY:http://tsukimi.agusa.i.is.nagoya-u.ac.j...
でも、
return"ラベル"を定義して、
(return (list S E N D '+ M O R E '= M O N E Y))
なんてことをやっています。
リストlisと述語手続きpredを取り、lisの各要素に順にpredを...
(define (find pred lis)
(call/cc
(lambda (return)
(for-each (lambda (elt) (if (pred elt) (return elt...
#f)))
lambda (return) はちょっと奇妙です。
私は脳内で、
(define (find pred lis)
(let/cc
return
(for-each (lambda (elt) (if (pred elt) (return elt)))...
#f))
と読んでいます。
この継続を、グローバル変数などに保存しておくこともできま...
例えば、継続returnを取り出して、グローバル変数 k に保存し...
(define k #f)
(+ 1 (call/cc (lambda (return)
(set! k return)
(return 1))))
= 2
return、および k には、あそこに戻る継続が入っています。
それで、
(k 10)
= 11
(k 50)
= 51
になります。
継続というのは、計算のスタックを取り出したものです。計算...
<>
1
+
です。そして、
return = k = (+ 1 <>)
です。lambda式で書くと
return = k = (lambda (x) (+ 1 x))
です。
実は、計算のスタックは、lambda式で書きなおすことができま...
(print (+ 1 2)) = ((lambda (x) (print x)) ((lambda (x) (...
(* 3 (+ 1 2)) = ((lambda (x) (* 3 x)) ((lambda (x) (+ 1 ...
スタックのコピーである継続がなぜlambda計算から自然と生ま...
** 発展学習 CPS "Continuation Passing Style" 継続渡しスタ...
さきほどの"計算のスタックをlambda式で書き直す"は、CPSと呼...
range 関数を書いてみます。 range 0 9 = (0,...,9)
(define (range a b)
(if (> a b)
[]
(cons a (range (+ a 1) b))))
(print (range 0 2)) のスタックはこうなるでしょう。
[]
cons 2
cons 1
cons 0
print
lambda式で書き直すと、
((lambda (x) (print x)) ((lambda (x) (cons 0 x)) ((lambd...
となります。
継続渡しスタイルは、このlambda (x)流の書きかたを陽にする...
range 関数はこうなります。
(define (range a b k)
(if (> a b)
(k [])
(range (+ a 1) b (lambda (x) (k (cons a x))))))
- 実際に (range 0 3 (lambda (x) (print x)))
と実行してごらんなさい。
- ときほぐすと、
((lambda (x) (print x)) ((lambda (x) (cons 0 x)) ((lambd...
と等しくなることを確かめなさい。
この k に入っているものこそ、継続です。
バトー、忘れないで。あなたがプログラムを書くとき、継続は...
**何ができるの? [#c933f2be]
- 大域脱出
- 例外処理
- コルーチン(軽量スレッド)
**天使のオペレータ amb [#u2719f75]
- [[非決定性:http://www.shido.info/lisp/scheme_amb.html]]
- [[amb@Wiliki:http://www.shiro.dreamhost.com/scheme/wili...
例えば、
(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関数は、引数なしで...
"8 11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
が実行されて、jに8が入ると同時に、
この時点のツヅキ、
"11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
を取り出して、スタックにpush...という感じです。
* 実際の使用例 [#s806e503]
- 論理パズル(カロタンパズルや地図の塗り分け)が[[紹介され...
- 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...
(O (amb (lset-difference = digs (list S E N ...
(R (amb (lset-difference = digs (list S E N ...
(Y (amb (lset-difference = digs (list S E N ...
(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))))
**参考文献 [#vf61a3fe]
-[[SICP.Nondeterministic Computing:http://mitpress.mit.ed...
-[[独習 Scheme 三週間:http://www.sampou.org/scheme/t-y-sc...
-[[なんでも継続:http://www.shiro.dreamhost.com/scheme/doc...
-[[Scheme:なぜSchemeにはreturnが無いのか:http://www.shiro...
-[[Schemeを作ろう 第3回:http://www.jah.ne.jp/~naoyuki/Wri...
-[[Scheme入門 継続:http://www.shido.info/lisp/scheme_cc.h...
- 継続には副作用がある。
[[Scheme:call/ccと副作用:http://www.shiro.dreamhost.com/s...
-[[名大の謎の天才h003149b氏:http://www.ice.nuie.nagoya-u....
*OCamlでcall/cc [#v1ede6b7]
Leroyのcall/ccライブラリ
http://pauillac.inria.fr/~xleroy/software.html
があります。
*継続サーバ [#z633f1a1]
-[[もとネタになった、Queinnec氏の論文PDF:http://www-spi.l...
-[[境界を越える: 継続とWeb開発、そしてJavaプログラミング:...
-[[継続サーバの実装の最先端、Seaside:http://www.seaside.s...
-[[Seasideの開発者が継続のゆくえについて語る:http://small...
-[[Haskellの継続サーバWASH:http://www.informatik.uni-frei...
-[[SchemeによるCPSスタイルの継続サーバKahua:http://www.ka...
-[[WebBasedアプリケーションと継続について、わかりやすい説...
* [[Ocsigen:http://www.ocsigen.org/]] OCamlによる継続ベー...
- [[論文 Typing web interaction with Objective Caml:http:...
- 継続ベースWebプログラミング Continuation-based Web prog...
- XHTMLの静的チェック Static checking of XHTML
- セッションの自動管理 Automatic management of sessions
- モジュール指向 Concise and modular programming
- Webサーバ、実装は協調スレッドによる。 Web server, imple...
- カウンタはこう書けます。
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:http://www.ocsigen.org/tuto/compt]]
ページ名: