私は、Scheme で call/cc のセマンティクスを把握しようとしています。ウィキペディアの継続に関するページには、例として陰陽パズルが示されています。
(let* ((yin
((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
(yang
((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))) )
(yin yang))
が出力されるはず@*@**@***@****@...ですが、理由がわかりません。私はそれが出力されることを期待しています@*@*********...
陰陽パズルがそのように機能する理由を誰かが詳しく説明できますか?
このパズルを理解する上での問題の少なくとも半分は、ほとんどの人が慣れていない Scheme 構文にあると思います。
まず第一に、個人call/cc x的には、 は同等の代替案である よりも理解しにくいと思いますx get/cc。それはまだx を呼び出し、現在の continuation を渡しますが、どういうわけか、私の脳回路で表される方が受け入れやすいです。
それを念頭に置いて、構造(call-with-current-continuation (lambda (c) c))は単純になりますget-cc。これで次のようになります。
(let* ((yin
((lambda (cc) (display #\@) cc) get-cc))
(yang
((lambda (cc) (display #\*) cc) get-cc)) )
(yin yang))
次のステップは、内部ラムダの本体です。(display #\@) cc、より馴染みのある構文で (とにかく、私にとって) を意味しprint @; return cc;ます。途中で、 のように書き直しlambda (cc) body、function (arg) { body }かっこの束を削除し、関数呼び出しを C のような構文に変更して、次のようにします。
(let* yin =
(function(arg) { print @; return arg; })(get-cc)
yang =
(function(arg) { print *; return arg; })(get-cc)
yin(yang))
今ではもっと意味があり始めています。これを取得するために、これを完全に C ライクな構文 (またはお好みで JavaScript ライク) に書き直すのは小さなステップです。
var yin, yang;
yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);
これで最も難しい部分は終わりました。Scheme からこれをデコードしました。冗談だ; 私はこれまで Scheme の経験がなかったので、大変でした。それでは、これが実際にどのように機能するかを理解しましょう。
陰と陽の奇妙に定式化されたコアを観察してください。関数を定義し、すぐにそれを呼び出します。のように見えますが(function(a,b) { return a+b; })(2, 3)、これは に簡略化できます5。しかし、yin/yang 内の呼び出しを単純化するのは間違いです。通常の値を渡していないからです。関数にcontinuationを渡しています。
続きは一見奇獣。もっと単純なプログラムを考えてみましょう:
var x = get-cc;
print x;
x(5);
最初xは現在の継続オブジェクトに設定され (我慢してください)、print x実行されて のように出力され<ContinuationObject>ます。ここまでは順調ですね。
しかし、継続は関数のようなものです。1 つの引数で呼び出すことができます。それが何をするか: 引数を取り、その継続が作成された場所にジャンプget-ccし、すべてのコンテキストを復元し、がこの引数を返すようにします。
この例では、引数は5であるため、基本的にそのステートメントの途中に戻りますがvar x = get-cc、今回のみget-ccが返されます5。Soにxなり5、次のステートメントは print 5 に続きます。その後5(5)、型エラーである を呼び出そうとすると、プログラムがクラッシュします。
継続の呼び出しは呼び出しではなくjumpであることに注意してください。継続が呼び出された場所に戻ることはありません。それは重要です。
それに従った場合は、期待しないでください。この部分は本当に難しいです。これが疑似コードであるため、変数宣言を削除したプログラムをもう一度示します。
yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);
最初に 1 行目と 2 行目がヒットしましたが、今は単純です: 継続を取得し、関数 (arg) を呼び出し、print@を返し、その継続を に保存しyinます。と同じyang。を印刷しまし@*た。
次に、 で継続を呼び出し、yinを渡しますyang。これにより、get-cc のすぐ内側の 1 行目にジャンプし、yang代わりに戻ります。の値がyang関数に渡され、 が出力され、@の値が返されますyang。今yinはその継続が割り当てられていyangます。次に 2 行目に進みます: c/c を取得し、印刷*し、c/c を に保存しyangます。ができ@*@*ました。そして最後に、3 行目に移動します。
yin行 2 が最初に実行されたときからの続きがあることを思い出してください。そこで、2 行目にジャンプして、1 秒*を出力して を更新しyangます。ができ@*@**ました。最後に、継続を再度呼び出すと、yin1 行目にジャンプし、@. 等々。率直に言って、この時点で私の脳は OutOfMemory 例外をスローし、すべてを追跡できなくなります。しかし、少なくとも@*@**!
明らかに、これは理解するのが難しく、説明するのがさらに困難です。これを行うための完璧な方法は、継続を表すことができるデバッガーでそれをステップ実行することですが、残念ながら、私は何も知りません。楽しんでいただけたでしょうか。私は確かに持っています。
私はこれを完全には理解していないと思いますが、これについては1つの（非常に手が波打つ）説明しか考えられません。
yinとyangが最初にバインドされたときに出力されlet*ます。(yin yang)が適用され、最初の呼び出し/ccが終了した直後にトップに戻ります。yinは2番目の呼び出し/ccの値に再バインドされるためです。(yin yang)が再度適用されますが、今回は元yangの環境で実行されyinており、最初の呼び出し/ ccにバインドされているため、制御は別の@の出力に戻ります。yang引数には、2回目のパススルーで再キャプチャされた継続が含まれます。これは、すでに見てきたように、結果として印刷されます**。したがって、この3番目のパスで、@*が印刷され、次にこの二重星印刷の継続が呼び出されるため、3つ星になり、この3つ星の継続が再キャプチャされます...陰陽パズルはスキームで書かれています。あなたがSchemeの基本的な構文を知っていることを前提としています。
でも知らないと思うのでlet*、call-with-current-continuationこの2つのキーワードについて説明します。
let*すでに知っている場合は、スキップできますExplain call-with-current-continuation
let*のように見える は のようletに動作しletますが、定義された変数 ((yin ...)と(yang ...)) を 1 つずつ熱心に評価します。つまり、最初に を評価しyin、 を評価しyangます。
ここで詳細を読むことができます: Using Let in Scheme
call-with-current-continuationすでにわかっている場合は、 にスキップできますYin-Yang puzzle。
説明するのは少し難しいcall-with-current-continuationです。そこで、比喩を使って説明します。
魔法を知っている魔法使いをイメージしてcall-with-current-continuationください。彼が呪文を唱えると、彼は新しい宇宙を作成し、自分自身をそこに送ります. しかし、彼は新しい宇宙で何もできず、誰かが彼の名前を呼ぶのを待っていました. 呼ばれた魔法使いは、可哀想な「誰か」を手に元の宇宙に戻り、魔法使いの人生を歩むことになる。呼び出されない場合、新しいユニバースが終了すると、ウィザードも元のユニバースに戻ります。
よし、もっとテクニカルになろう。
call-with-current-continuation関数をパラメーターとして受け入れる関数です。call-with-current-continuation関数で呼び出すと、呼び出されFた現在実行中の環境がcurrent-continuationパラメーターとしてパックされ、C関数に送信されF、実行されFます。したがって、プログラム全体は になり(F C)ます。またはより JavaScript: F(C);. C関数のように動作します。Cで が呼び出されていない場合はF、通常のプログラムであり、 がF戻ると、の戻りcall-with-current-continuation値として値を持ちFます。しかしC、 をパラメータVで呼び出すと、プログラム全体が再び変更されます。プログラムは呼び出されたときの状態に戻ります。call-with-current-continuationしかし、今call-with-current-continuationでは値が得られます。V. そして番組は続く。
例を見てみましょう。
(define (f return)
(return 2)
3)
(display (f whatever)) ;; 3
(display (call-with-current-continuation f)) ;; 2
(display (call-with-current-continuation (lambda (x) 4))) ;; 4
原因の最初のdisplay出力。3
しかし、2番目のdisplay出力2. なんで？
それに飛び込みましょう。
評価するとき(display (call-with-current-continuation f))は、最初に評価し(call-with-current-continuation f)ます。プログラム全体が次のように変更されることがわかっています。
(f C)
の定義を考えると、fがあり(return 2)ます。を評価する必要があり(C 2)ます。そんな時、continuation呼ばれる存在。したがって、プログラム全体を元に戻します
(display (call-with-current-continuation f))
しかし今、call-with-current-continuation価値があります2。したがって、プログラムは次のようになります。
(display 2)
パズルを見てみましょう。
(let* ((yin
((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
(yang
((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
(yin yang))
もっと読みやすくしましょう。
(define (id c) c)
(define (f cc) (display #\@) cc)
(define (g cc) (display #\*) cc)
(let* ((yin
(f (call-with-current-continuation id)))
(yang
(g (call-with-current-continuation id))))
(yin yang))
プログラムを脳内で実行してみましょう。
let*yin最初に評価させてください。yinは
(f (call-with-current-continuation id))
ですから、まず評価し(call-with-current-continuation id)ます。それは現在の環境をパックC_0し、タイムラインの他の継続と区別するためにそれを呼び出し、まったく新しい宇宙に入ります: id. しかし、idただ返しますC_0。
何であるかを覚えておく必要C_0があります。C_0は次のようなプログラムです。
(let* ((yin
(f ###))
(yang
(g (call-with-current-continuation id))))
(yin yang))
###はプレースホルダーであり、将来、取り戻される値によって埋められますC_0。
しかし、idただ返しますC_0。を呼び出しませんC_0。呼ばれたら、C_0の宇宙に入ります。しかし、そうではなかったので、評価を続けyinます。
(f C_0) ;; yields C_0
fのような関数ですがid、出力するという副作用があり@ます。
したがって、プログラムの出力@と letyinは になりますC_0。これでプログラムは次のようになります
(let* ((yin C_0)
(yang
(g (call-with-current-continuation id))))
(yin yang))
評価後yin、評価を開始しyangます。yangは
(g (call-with-current-continuation id))
call-with-current-continuationここで、 という名前の別の継続を作成しますC_1。C_1は：
(let* ((yin C_0)
(yang
(g ###)))
(yin yang))
###はプレースホルダです。この継続では、yinの値が決定されることに注意してください (それが何をするかlet*です)。yinの値がここにあると確信していC_0ます。
(id C_1)であるためC_1、yangの値は
(g C_1)
g出力するという副作用があり*ます。したがって、プログラムはそうします。
yangの値は現在C_1です。
これまでに表示した@*
したがって、次のようになります。
(let* ((yin C_0)
(yang C_1))
(yin yang))
yinとの両方yangが解かれるので、 を評価する必要があり(yin yang)ます。これは
(C_0 C_1)
ホーリー SH*T!
しかし、最後に、C_0呼び出されます。だから私たちはC_0宇宙に飛び込み、これらのたわごとをすべて忘れます。私たちは二度とこの宇宙に戻ることはありません。
C_0バックで取るC_1。プログラムは次のようになります (何C_0の略か忘れた場合は、戻って確認してください)。
(let* ((yin
(f C_1))
(yang
(g (call-with-current-continuation id))))
(yin yang))
yinああ、の値はまだ決定されていないことがわかりました。だから評価する。を評価する過程で、 asの副作用yinを出力します。そして、私たちは今であることを知っています。@fyinC_1
評価を開始し、再びyang遭遇call-with-current-continuationしました。私たちは実践されています。C_2以下を表す継続を作成します。
(let* ((yin C_1)
(yang
(g ###)))
(yin yang))
そして、a*をg実行中として表示します。そして、私たちはここに来ます
(let* ((yin C_1)
(yang C_2))
(yin yang))
したがって、次のようになりました。
(C_1 C_2)
あなたは私たちがどこに行くのか知っています。C_1さんの宇宙に行きます。記憶から思い出す (または Web ページからコピーして貼り付ける)。それは今です：
(let* ((yin C_0)
(yang
(g C_2)))
(yin yang))
C_1の宇宙では、yinの値が決定されていることがわかっています。そこで、評価を開始しyangます。私たちが実践しているように、それが表示され、次のようになることを直接お伝えします*。
(C_0 C_2)
これで印刷が完了し、を使って宇宙に@*@**行きます。C_0C_2
yin私たちが慣れているように、「@」を表示し、 isであり、次を表すC_2新しい continuation を作成することをお伝えします。C_3
(let* ((yin C_2)
(yang
(g ###)))
(yin yang))
を表示する*と、yangはC_3になり、
(C_2 C_3)
そして、私たちは続けることができます。しかし、ここでやめておきます。陰陽パズルの最初のいくつかの出力が何であるかを示しました。
*増える理由は？今、あなたの頭は詳細でいっぱいです。私はあなたのために要約を作ります。
簡単にするために、Haskell のような構文を使用します。とccの略ですcall-with-current-continuation。
#C_i#で囲まれている場合#は、継続がここに作成されていることを意味します。;出力を意味します
yin = f cc id
yang = g cc id
yin yang
---
yin = f #C_0# ; @
yang = g cc id
yin yang
---
yin = C_0
yang = g #C_1# ; *
yin yang
---
C_0 C_1
---
yin = f C_1 ; @
yang = g #C_2# ; *
yin yang
---
C_1 C_2
---
yin = C_0
yang = g C_2 ; *
yin yang
---
C_0 C_2
---
yin = f C_2 ; @
yang = g #C_3#; *
yin yang
---
C_2 C_3
---
yin = C_1
yang = g C_3 ; *
yin yang
---
C_1 C_3
---
yin = C_0
yang = g C_3 ; *
yin yang
---
C_0 C_3
注意深く観察すれば、次のことは明らかです。
C_0によって始まった唯一の宇宙ですf。その他は によって開始されgます。C_0 C_n常に新しい継続を行いC_maxます。実行されていないC_0最初の宇宙だからです。g cc idC_0 C_nも表示@。C_n C_mwhich n is not 0 が表示されます*。C_0 C_nに、プログラムはC_0 C_n@*@**@***...(n != 0) がすべての継続の中で最大の番号であると仮定し、次に
C_0 C_n呼び出されます。
仮定:C_0 C_nが呼び出されたとき、C_nは現在の最大番号付き継続です。
今は次のように作成され
C_0 C_nます：
yin = f C_n ; @
yang = g #C_{n+1}#
yin yang
したがって、次のように結論付けます。
定理 I.C_0 C_nが呼び出されると、 が である継続 が生成され
yinますC_n。
次に、次のステップですC_n C_{n+1}。
yin = C_{n-1}
yang = g C_{n+1} ; *
yin yang
その理由yinはC_{n-1}、作成時に定理 IC_nに従ったからです。
そして、C_{n-1} C_{n+1}が呼び出され、 がいつ作成されるかがわかり、定理 IC_{n-1}にも従いました。だから私たちは持っています。C_{n-2} C_{n+1}
C_{n+1}インバリエーションです。したがって、2 番目の定理があります。
定理 II。とC_n C_mを呼ぶn < mとn > 0となりC_{n-1} C_mます。
そして、手動でチェックしC_0 C_1 C_2 C_3ました。彼らは仮定とすべての定理に従います。そして、私たちは最初@にどのよう*に作成されるかを知っています。
したがって、以下にパターンを記述できます。
C_0 C_1 ; @ *
C_[1-0] C_2 ; @ * *
C_[2-0] C_3 ; @ * * *
...
厳密ではありませんが、次のように書きたいと思います。
QED
最初に熟考し、最後に可能な答え。
コードは次のように書き直すことができると思います。
; call (yin yang)
(define (yy yin yang) (yin yang))
; run (call-yy) to set it off
(define (call-yy)
(yy
( (lambda (cc) (display #\@) cc) (call/cc (lambda (c) c)) )
( (lambda (cc) (display #\*) cc) (call/cc (lambda (c) c)) )
)
)
または、何が起こっているかを確認するのに役立ついくつかの追加の表示ステートメントを使用します。
; create current continuation and tell us when you do
(define (ccc)
(display "call/cc=")
(call-with-current-continuation (lambda (c) (display c) (newline) c))
)
; call (yin yang)
(define (yy yin yang) (yin yang))
; run (call-yy) to set it off
(define (call-yy)
(yy
( (lambda (cc) (display "yin : ") (display #\@) (display cc) (newline) cc)
(ccc) )
( (lambda (cc) (display "yang : ") (display #\*) (display cc) (newline) cc)
(ccc) )
)
)
またはこのように：
(define (ccc2) (call/cc (lambda (c) c)) )
(define (call-yy2)
(
( (lambda (cc) (display #\@) cc) (ccc2) )
( (lambda (cc) (display #\*) cc) (ccc2) )
)
)
可能な答え
これは正しくないかもしれませんが、試してみます。
重要な点は、「呼び出された」継続がスタックを以前の状態に戻すことです-他に何も起こらなかったかのように。もちろん、表示@や*文字で監視していることを知りません。
最初に、これを行うyin継続を定義します。A
1. restore the stack to some previous point
2. display @
3. assign a continuation to yin
4. compute a continuation X, display * and assign X to yang
5. evaluate yin with the continuation value of yang - (yin yang)
しかし、yang継続を呼び出すと、次のことが起こります。
1. restore the stack to some point where yin was defined
2. display *
3. assign a continuation to yang
4. evaluate yin with the continuation value of yang - (yin yang)
ここから始めます。
初めて取得yin=Aし、初期化さyang=Bれyinてyangいます。
The output is @*
(AとB継続の両方が計算されます。)
今は初めて(yin yang)として評価されます。(A B)
私たちは何ができるか知ってAいます。これは次のことを行います。
1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B, we don't compute it.
4. compute another continuation B', display * and assign B' to yang
The output is now @*@*
5. evaluate yin (B) with the continuation value of yang (B')
(yin yang)として評価されるようになりました(B B')。
私たちは何ができるか知ってBいます。これは次のことを行います。
1. restore the stack - back to the point where yin was already initialised.
2. display *
3. assign a continuation to yang - this time, it is B'
The output is now @*@**
4. evaluate yin with the continuation value of yang (B')
が と評価されるところまでスタックが復元されたのでyin=A、(yin yang)と評価され(A B')ます。
私たちは何ができるか知ってAいます。これは次のことを行います。
1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B', we don't compute it.
4. compute another continuation B", display * and assign B" to yang
The output is now @*@**@*
5. evaluate yin (B') with the continuation value of yang (B")
私たちは何ができるか知ってB'います。これは次のことを行います。
1. restore the stack - back to the point where yin=B.
2. display *
3. assign a continuation to yang - this time, it is B"
The output is now @*@**@**
4. evaluate yin (B) with the continuation value of yang (B")
(yin yang)として評価されるようになりました(B B")。
私たちは何ができるか知ってBいます。これは次のことを行います。
1. restore the stack - back to the point where yin=A and yang were being initialised.
2. display *
3. assign a continuation to yang - this time, it is B'"
The output is now @*@**@***
4. evaluate yin with the continuation value of yang (B'")
が と評価されるところまでスタックが復元されたのでyin=A、(yin yang)と評価され(A B'")ます。
.......
私たちは今、パターンを持っていると思います。
を呼び出すたびに、 when に戻るまで継続(yin yang)のスタックをループし、を表示します。毎回a を書き込んで、継続のスタックをループします。Byin=A@B*
（これが大体合っていれば本当に嬉しいです！）
ご質問ありがとうございます。
別の答えが言ったように、まず で単純化(call-with-current-continuation (lambda (c) c))しget-ccます。
(let* ((yin
((lambda (cc) (display #\@) cc) get-cc))
(yang
((lambda (cc) (display #\*) cc) get-cc)) )
(yin yang))
現在、2 つのラムダは、副作用に関連するまったく同じ関数です。fこれらの関数を (for display #\@) とg(for ) と呼びましょうdisplay #\*。
(let* ((yin (f get-cc))
(yang (g get-cc)))
(yin yang))
次に、評価順序を決める必要があります。明確にするために、すべての評価ステップを明示的にする「ステップ式」を導入します。最初に聞いてみましょう: 上記の関数には何が必要ですか?
fとの定義が必要gです。ステップ式では、
s0 f g =>
最初のステップは を計算するyinことですが、それには の評価が必要で(f get-cc)、後で が必要ですget-cc。
大まかに言えば、get-cc「現在の継続」を表す値を提供します。これs1は次のステップだからです。だから私たちは書く
s0 f g => s1 f g ?
s1 f g cc =>
パラメータはスコープレスであることに注意してください。つまり、fとgins0とs1は同じである必要はなく、現在のステップ内でのみ使用されます。これにより、コンテキスト情報が明確になります。さて、 の値はcc？「現在の継続」なので、同じ値にバインドされているのと同じs1ようなものです。fg
s0 f g => s1 f g (s1 f g)
s1 f g cc =>
を取得したらcc、 を評価できf get-ccます。また、f次のコードでは が使用されていないため、この値を渡す必要はありません。
s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin =>
次は同様ですyang。しかし、もう 1 つの値を渡す必要があります: yin.
s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin => s3 g yin (s3 g yin)
s3 g yin cc => s4 yin (g cc)
s4 yin yang =>
最後に、最後のステップは に適用するyangことyinです。
s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin => s3 g yin (s3 g yin)
s3 g yin cc => s4 yin (g cc)
s4 yin yang => yin yang
これで、ステップ式の構築が完了しました。それをSchemeに戻すのは簡単です：
(let* ([s4 (lambda (yin yang) (yin yang))]
[s3 (lambda (yin cc) (s4 yin (g cc))]
[s2 (lambda (yin) (s3 yin ((lambda (cc) (s3 yin cc))))]
[s1 (lambda (cc) (s2 (f cc)))])
(s1 s1))
詳細な評価順序 (ここでは、 の本体内のラムダは、ではなくs2部分評価として単純に表現されています):s3 yin(lambda (cc) (s3 yin cc))
(s1 s1)
=> (s2 (f s1))
=> @|(s2 s1)
=> @|(s3 s1 (s3 s1))
=> @|(s4 s1 (g (s3 s1)))
=> @*|(s4 s1 (s3 s1))
=> @*|(s1 (s3 s1))
=> @*|(s2 (f (s3 s1)))
=> @*@|(s2 (s3 s1))
=> @*@|(s2 (s3 s1))
=> @*@|(s3 (s3 s1) (s3 (s3 s1)))
=> @*@|(s4 (s3 s1) (g (s3 (s3 s1))))
=> @*@*|(s4 (s3 s1) (s3 (s3 s1)))
=> @*@*|(s3 s1 (s3 (s3 s1)))
=> @*@*|(s4 s1 (g (s3 (s3 s1))))
=> @*@**|(s4 s1 (s3 (s3 s1)))
=> @*@**|(s1 (s3 (s3 s1)))
=> ...
s2(またはを評価するときs4は、パラメーターが最初に評価されることを思い出してください。