https://stackoverflow.com/questions/2694679
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在尝试掌握方案中呼叫/CC的语义，而连续的Wikipedia页面显示了阳阳的拼图为例：
(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))
它应该输出 @*@**@***@****@..., ，但我不明白为什么；我希望它能输出 @*@*********...
有人可以详细解释为什么阴阳拼图以其工作方式工作吗？
解决方案
我认为我不完全理解这一点，但我只能想到一个（极其 手动）解释：
- 第一个 @和 *在
yin和yang首先在let*.(yin yang)应用，然后在第一个呼叫/CC完成后，它返回到顶部。 - 下一个 @和 *打印，然后打印另一个 *，因为这次通过，
yin重新限制第二个呼叫/CC的值。 (yin yang)再次应用，但是这次 它在原始yang的环境, ， 在哪里yin被绑定到第一个呼叫/CC，因此控件可以返回打印另一个 @。这yang参数包含第二次通过重新捕获的延续，正如我们已经看到的那样，将导致打印**. 。因此，在第三次通行证中，@*将被打印，然后调用这种双星打印的延续，因此最终获得了3颗星，然后重新捕获了三星级的延续，...
其他提示
理解计划
我认为理解这个难题至少有一半的问题是方案语法，大多数人都不熟悉。
首先，我个人发现 call/cc x 比同等替代方案更难理解 x get/cc. 。它仍然 调用X，传递当前延续, ，但某种程度上更适合在我的脑电路中代表。
考虑到这一点，构造 (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))
下一步是内部lambda的主体。 (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);
现在最难的部分已经结束，我们已经从方案中解码了这一点！只是在开玩笑;这只是很难，因为我以前没有方案经验。因此，让我们弄清楚这是如何工作的。
连续底漆
观察阴和阳的奇特配制的核心：它定义了一个功能 然后立即称呼它. 。看起来就像 (function(a,b) { return a+b; })(2, 3), ，可以简化 5. 。但是，简化阴/阳内的呼叫是一个错误，因为我们不是将其传递给普通价值。我们正在传递功能 延续.
延续是一见钟情的奇怪的野兽。考虑更简单的程序：
var x = get-cc;
print x;
x(5);
最初 x 设置为当前的延续对象（与我同在），并且 print x 被执行，打印类似 <ContinuationObject>. 。到现在为止还挺好。
但是延续就像一个功能。可以用一个参数调用。它的作用是：采取争论，然后 跳 到达创建该延续的任何地方，恢复所有上下文并做到这一点 get-cc 返回此参数。
在我们的示例中，论点是 5, ，所以我们从本质上跳回中间 var x = get-cc 声明，只有这次 get-cc 返回 5. 。所以 x 变成 5, ，下一个语句继续打印5。在此之后，我们尝试致电 5(5), ，这是类型错误，程序崩溃。
观察到延续是一个 跳, ，不是电话。它永远不会返回到延续的位置。这很重要。
程序如何工作
如果您遵循这一点，那就不要寄希望：这部分确实是最难的。这再次是我们的程序，删除了变量声明，因为这是伪代码：
yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);
第1行1和2被击中，现在很简单：获取延续，调用功能（arg），打印 @, ，返回，存储该延续 yin. 。与 yang. 。我们现在打印了 @*.
接下来，我们称之为延续 yin, ，通过它 yang. 。这使我们跳到第1行，就在该GET-CC内部，并使其返回 yang 反而。的价值 yang 现在传递到打印的功能中 @, ，然后返回 yang. 。现在 yin 被分配了该延续 yang 拥有。接下来，我们只进入第2行：获取C/C，打印 *, ，将C/C存储在 yang. 。我们现在有 @*@*. 。最后，我们进入第3行。
记住这一点 yin 现在，从第2行首次执行时就可以延续。所以我们跳到第2行，打印一秒钟 * 和更新 yang. 。我们现在有 @*@**. 。最后，致电 yin 继续延续，将跳到第1行，打印 @. 。等等。坦率地说，在这一点上，我的大脑会抛出一个外观异常的例外，我失去了一切。但是至少我们必须 @*@**!
显然，这很难遵循甚至更难解释。这样做的理想方法是在可以代表连续性的调试器中逐步浏览它，但可惜，我不知道。我希望你喜欢这个；我当然有。
首先沉思，最后可能的答案。
我认为代码可以像这样重新编写：
; 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'").
.......
我认为我们现在有一个模式。
每次我们打电话 (yin yang) 我们循环通过一堆 B 继续进行，直到我们回到何时 yin=A 我们显示 @. 。我们循环穿过一堆 B 连续写作 * 每一次。
（如果这大致正确，我真的很高兴！）
感谢您的问题。
Yinyang拼图是用计划编写的。我认为您知道方案的基本语法。
但我认为你不知道 let* 或者 call-with-current-continuation, ，我将解释这两个关键字。
解释 let*
如果您已经知道，可以跳到 Explain call-with-current-continuation
let*, ，看起来像 let, ，表现得像 let, ，但会评估其定义的变量（ (yin ...) 和 (yang ...)）一一热切地。这意味着，它将首先评估 yin, ， 然后 yang.
您可以在此处阅读更多：使用让计划
解释 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, ，原因。
但是第二 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))
让我们在大脑中运行程序。
第0轮
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, ，但它具有副作用 - 输出 @.
因此程序输出 @ 然后让 yin 成为 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)
圣*t！
但最后， C_0 叫做。所以我们飞进 C_0 宇宙，忘记了所有这些sh*ts。我们将永远不会再回到这个宇宙。
第1轮
C_0 随身携带 C_1 背部。该程序现在变成了（如果您忘记了什么 C_0 代表，回去看看）：
(let* ((yin
(f C_1))
(yang
(g (call-with-current-continuation id))))
(yin yang))
啊，我们发现 yin尚未确定的价值。因此，我们评估它。在评估过程中 yin, ，我们输出 @ 作为 f的副作用。我们知道 yin 是 C_1 现在。
我们开始评估 yang, ，我们遇到 call-with-current-continuation 再次。我们被练习。我们创建一个延续 C_2 代表：
(let* ((yin C_1)
(yang
(g ###)))
(yin yang))
我们显示一个 * 作为 g 执行。我们来这里
(let* ((yin C_1)
(yang C_2))
(yin yang))
所以我们得到了：
(C_1 C_2)
你知道我们要去哪里。我们准备去 C_1的宇宙。我们从内存（或从网页复制和粘贴）回想起它。就是现在：
(let* ((yin C_0)
(yang
(g C_2)))
(yin yang))
我们知道 C_1的宇宙， yin已确定的值。所以我们开始评估 yang. 。正如我们的练习一样，我将直接告诉您它显示 * 并变成：
(C_0 C_2)
现在我们已经打印了 @*@**, ，我们要去 C_0宇宙与 C_2.
第2轮
正如我们的练习一样，我会告诉你我们显示“@”， yin 是 C_2, ，我们创建了一个新的延续 C_3, ，代表：
(let* ((yin C_2)
(yang
(g ###)))
(yin yang))
我们显示 *, yang 是 C_3, ，它变成了
(C_2 C_3)
我们可以继续。但是我会在这里停下来，我向您展示了Yin-Yang Puzzle的前几个输出。
为什么数量 * 增加？
现在您的头充满了细节。我将为您做一个摘要。
我将使用像语法这样的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 id拥有 不是 被执行。C_0 C_n也显示@.C_n C_m哪个不是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} 是什么时候 C_n 被创造出来了 定理i.
进而 C_{n-1} C_{n+1} 被称为，我们知道什么时候 C_{n-1} 创建，也服从 定理i. 。所以我们有 C_{n-2} C_{n+1}.
C_{n+1} 是内在的。因此，我们有第二个定理：
定理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-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))
现在，两个lambda只是与副作用相关的相同函数。让我们称这些功能 f （为了 display #\@） 和 g （为了 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 和 g 在 s0 和 s1 不需要相同，仅在当前步骤中使用它们。这使上下文信息明确。现在，价值是多少 cc？由于它是“当前延续”，所以有点相同 s1 和 f 和 g 绑定到相同的值。
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. 。但是现在我们还有一个值得传递的价值： 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
这完成了步骤表达式的结构。将其翻译回方案很简单：
(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))
详细的评估顺序（此处为lambda 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, ，该参数将首先评估
这是一个笨拙的大师戴维·麦德尔（David Madore）的古老难题，他创造了unlambda。该难题已被讨论过多次。
泰勒·坎贝尔（Taylor Campbell）的一个很好的解决方案：https://groups.google.com/d/msg/comp.lang.scheme/puedvrkyy5w/uijtc_t1loej
David Madore（1999）的原始帖子：https://groups.google.com/d/msg/comp.lang.scheme/fysq_wplxsw/awxez_uxw20j
