阴阳拼图是如何运作的？

Question

我正在尝试在Scheme中掌握call/cc的语义,并且关于continuation的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))

它应该输出@*@**@***@****@...,但我不明白为什么; 我希望它输出@*@*********......

有人可以详细解释为什么阴阳拼图的工作方式有效吗？

Answer 1

理解方案

我认为理解这个难题的问题至少有一半是Scheme语法,大多数人都不熟悉.

首先,我个人觉得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);

最困难的部分现在结束了,我们已经从Scheme解码了这个!开玩笑; 这很难,因为我以前没有使用过Scheme的经验.所以,让我们弄清楚它是如何实际运作的.

关于延续的入门读物

观察阴阳的奇怪的核心:它定义一个函数,然后立即调用它.它看起来就像(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行和第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行,打印a @.等等.坦率地说,在这一点上,我的大脑抛出了OutOfMemory异常,我忘记了所有事情.但至少我们得到了@*@**!

显然,这很难理解,甚至更难解释.完成这项工作的最佳方法是在调试器中逐步执行它,这可以代表延续,但是,我不知道.我希望你喜欢这个; 我当然有.

Answer 2

我不认为我完全理解这一点,但我只能想到一个(非常手工波浪)的解释:

• 第一@和*是当印刷yin和yang在首先结合let*.(yin yang)应用,并在第一次调用/ cc结束后立即返回到顶部.
• 打印下一个@和*,然后打印另一个*,因为此时间通过,yin重新绑定到第二个调用/ cc的值.
• (yin yang)再次应用,但这次它在原始yang环境中执行,其中yin绑定到第一个调用/ cc,因此控制返回打印另一个@.该yang参数包含在第二次传递时重新捕获的延续,正如我们已经看到的那样,将导致打印**.因此,在第三遍,@*将被打印,然后这个双星打印延续被调用,所以它最终得到3颗星,然后重新捕获这个三星级延续,...

Answer 3

首先是Musings,最后可能回答.

我认为代码可以像这样重写:

; 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写入的连续栈*.

(如果大致正确,我会很高兴!)

谢谢你的提问.

Answer 4

阴阳拼图是用Scheme写的.我假设你知道Scheme的基本语法.

但我假设你不知道let*或者call-with-current-continuation,我会解释这两个关键词.

说明 let*

如果您已经知道,可以跳过 Explain call-with-current-continuation

let*看起来像let,let但是会一个接一个地热切地评估它定义的变量((yin ...)和(yang ...)).这意味着,它将首先评估yin,而不是yang.

您可以在这里阅读更多内容: 使用Let in Scheme

说明 call-with-current-continuation

如果您已经知道,可以跳过Yin-Yang puzzle.

这有点难以解释call-with-current-continuation.所以我将用一个比喻来解释它.

想象一个知道咒语的巫师call-with-current-continuation.一旦他施放了这个咒语,他就会创造一个新的宇宙,然后将自己送给它.但他无法在新宇宙中做任何事情,而是在等待有人呼唤他的名字.一旦被召唤,巫师就会回到原来的宇宙,让那个可怜的家伙 - "有人" - 在手,然后继续他的巫师生活.如果未调用,则当新Universe结束时,向导也会返回到原始Universe.

好吧,让我们更具技术性.

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's返回值.但如果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)IS 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宇宙,忘记了所有关于这些事情的事情.我们永远不会再回到这个宇宙.

第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)

我们可以继续.但是我会停在这里,我已经向你展示了阴阳拼图的前几个输出.

为什么*增加的数量？

现在你的头脑里充满了细节.我会为你做一个总结.

我将使用类似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

如果你仔细观察,那对你来说是显而易见的

1. 有许多宇宙(实际上是无限的),但C_0它是唯一的宇宙开始f.其他人是从g.
2. C_0 C_n永远是一个新的延续C_max.这是因为C_0是第一宇宙g cc id还没有被执行.
3. C_0 C_n还显示@.C_n C_m其中n不为0将显示*.
4. 程序被推断出来的时间越长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创建它服从定理我.

然后C_{n-1} C_{n+1}被称为,我们知道什么时候C_{n-1}被创造,它也遵守定理我.所以我们有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