题
我正在尝试掌握方案中呼叫/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