阴阳之谜是怎么起作用的?

我不认为我完全理解这一点,但我只能想到一个( 极其

• yin 和 yang 是第一个在 let* (yin yang)
• 下一个@和*被打印,然后另一个*被打印,因为这一次, 尹 重新绑定到第二个call/cc的值。
• (阴阳) 它在原版中执行 的环境 ,在哪里 绑定到第一个调用/cc,因此控件返回到打印另一个@。这个 杨 ** . 所以在第三关, @* 将被打印,然后这个双星打印继续被调用,所以它以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 . 但是简化阴/阳中的调用将是一个错误,因为它们没有传递一个普通的值。正在传递函数a .

var x = get-cc;
print x;
x(5);

最初 x 设置为当前延续对象(请放心),并且 print x 被执行,打印出类似 <ContinuationObject> . 到现在为止,一直都还不错。

但延拓就像一个函数;它可以用一个参数调用。它所做的是:接受论点,然后 跳 无论在哪里,延续被创造,恢复所有的上下文,并使之成为 获取抄送 返回此参数。

在我们的例子中,论点是 5 var x = get-cc 声明,只是这次 获取抄送 退货 十 变成 5 ,下一个语句继续打印5。然后我们尝试调用 5(5) ,这是一个类型错误,程序崩溃。

注意调用continuation是 跳 ,不是电话。它永远不会返回到调用continuation的地方。这很重要。

程序的工作原理

如果你遵循这一点,那么不要抱太大的希望:这一部分真的是最难的。下面是我们的程序,删除变量声明,因为这是伪代码:

yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);

第一次命中第1行和第2行时,它们现在很简单:获取延续,调用函数(arg),print @ ,返回,将该延续存储在 yin . 与相同 yang . 我们现在印刷了 @*

下一步,我们调用延续 尹 ,传递它 杨 . 这让我们跳到1号线,就在里面,得到cc,然后让它返回 相反。价值 现在被传递到函数中 @ 杨 . 现在 尹 有。接下来我们继续第2行:取得信用证,打印 * 杨 . 我们现在有 @*@* . 最后,我们去3号线。

尹 * . 我们现在有 @*@** . 最后,打电话给 继续,它将跳转到第1行,打印一个 @

显然,这很难理解,更难解释。最好的方法是在一个调试器中一步一步地完成它,这个调试器可以表示continuations,但是唉,我不知道有什么。我希望你过得愉快;我当然有。

先思考,最后可能的答案。

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

; 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 作为 尹 正在初始化。

The output is @*

(二者) A 和 B 计算连续性。)

现在 (yin yang) 评估为 (A B)

我们知道什么 做。它是这样做的:

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

因为堆栈恢复到 , (阴阳) (A B') .

我们知道什么 做。它是这样做的:

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

(阴阳) 评估为 (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'")

因为堆栈恢复到 , 评估为 (A B'") .

我想我们现在有了一个模式。

(阴阳) B 直到我们回到什么时候 阴=A 我们展示 . 我们在一堆 B *

谢谢你的提问。

阴阳拼图是用方案写的。我想你知道Scheme的基本语法。

let* 或 call-with-current-continuation

解释 让*

如果你已经知道了,你可以跳到 Explain call-with-current-continuation

,看起来像 let 让 ,但将计算其定义的变量( (yin ...) (yang ...) )一个接一个地急切地。这意味着,它将首先评估 yin yang

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

解释 当前连续呼叫

如果你已经知道了,你可以跳到 Yin-Yang puzzle .

这有点难以解释 当前连续呼叫

想象一个知道咒语的巫师 当前连续呼叫 . 一旦他施了咒语,他将创造一个新的宇宙,并把他自己送到那里。但他可以 什么也不做 在新的宇宙里却在等待有人呼唤他的名字。一次

好吧,让我们更专业一点。

当前连续呼叫 接受函数作为参数的函数。一旦你打电话 带函数 F ,它将打包当前运行的环境,称为 current-continuation C ,并将其发送到函数 ,并执行 F . 所以整个程序就变成了 (F C) . 或者更像JavaScript: F(C); C 就像一个函数。如果 未被调用 F F 回报, 值为 的返回值。但如果 C 用参数调用 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 (call-with-current-continuation f)) (call-with-current-continuation f) . 我们知道这将改变整个计划

(f C)

考虑到 f ,它有一个 (return 2) . 我们必须评估 (C 2) . 就在那时 continuation

(display (call-with-current-continuation f))

但是现在, 有价值 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轮

让* 让我们来评估 第一。 是

(f (call-with-current-continuation id))

所以我们评估 (call-with-current-continuation id) 第一。它打包了当前的环境,我们称之为 C_0 id . 但是 身份证件 第0部分 .

我们应该记住什么 是。 第0部分 是这样一个程序:

(let* ((yin
         (f ###))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

###

但是 身份证件 . 它不叫 第0部分 第0部分 的宇宙。但是没有,所以我们继续评估 尹 .

(f C_0) ;; yields C_0

f 身份证件 @ .

@ 让我们 尹 成为 第0部分 . 现在程序变成

(let* ((yin C_0)
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

之后 尹 杨 . 杨 是

(g (call-with-current-continuation id))

当前连续呼叫 C_1 Cï1 是:

(let* ((yin C_0)
       (yang
         (g ###)))
      (yin yang))

是占位符。请注意,在此续文中, 尹 的值是确定的(这就是 让* 是的)。我们确信 尹 第0部分 在这里。

自 (id C_1) Cï1 ,所以 的值为

(g C_1)

g *

杨

现在,我们已经展示了 @*

所以现在变成了:

(let* ((yin C_0)
       (yang C_1))
      (yin yang))

作为两者 尹 和 如果问题解决了,我们应该评估 (yin yang) . 它是

(C_0 C_1)

但最后, 第0部分 被称为。所以我们飞到 忘记所有这些,我们再也不会回到这个宇宙了。

第0部分 Cï1 回来。程序现在变成(如果你忘记了什么 第0部分 代表,回去看看):

(let* ((yin
         (f C_1))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

的值尚未确定。所以我们评估一下。在评估过程中 @ 作为 的副作用。我们知道 是 Cï1

我们开始评估 杨 当前连续呼叫 再一次。我们练习过。我们创建一个延续 C_2

(let* ((yin C_1)
       (yang
         (g ###)))
      (yin yang))

我们展示了一个 * 作为 克

(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_0 C_2)

现在我们已经印好了 @*@** ,我们将 第0部分 的宇宙 Cè2

第二轮

尹 是 Cè2 ,我们创建一个新的延续 C_3

(let* ((yin C_2)
       (yang
         (g ###)))
      (yin yang))

我们展示 , 杨 Cï3

(C_2 C_3)

我们可以继续。但我就到此为止,我已经向你们展示了阴阳拼图的前几个输出是什么。

为什么 *

现在你脑子里充满了细节。我给你做个总结。

我将使用类似Haskell的语法来简化。以及 cc 当前连续呼叫 .

什么时候? #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. 第0部分 是唯一一个由 . 其他人是由 克 .
2. C_0 C_n C_max . 是因为 第0部分 g cc id 有 已经被处决了。
3. 第0部分 同时显示 @ . C_n C_m *
4. 第0部分 ,我会证明的 第0部分 被越来越多的其他表达式隔开,从而导致 @*@**@***...

一点数学知识

(n!=0)是所有连续体中编号最大的,然后 被称为。

假设:什么时候 第0部分 被称为, C_n

创建人 第0部分 这样地:

yin = f C_n ; @
yang = g #C_{n+1}#
yin yang

因此我们得出结论:

定理一。如果 第0部分 被称为,它将产生一个延续 ,其中 尹 库恩 .

C_n C_{n+1} .

yin = C_{n-1}
yang = g C_{n+1} ; *
yin yang

C_{n-1} 库恩 它被创造出来就服从了 定理一 .

C_{n-1} C_{n+1} 我们知道什么时候 C{n-1} 定理一 . 所以我们有 C_{n-2} C_{n+1} .

C_{n+1} 是变化中的。我们有第二个定理:

定理二。如果 库恩库姆 哪一个 n < m n > 0 被称为,它将成为 C_{n-1} C_m .

我们已经手动检查过了 第0部分 Cï1 Cï3 @ *

所以我们可以在下面写模式。

C_0 C_1 ; @ *
C_[1-0] C_2 ; @ * *
C_[2-0] C_3 ; @ * * *
...

虽然没有那么严格,但我想写:

Q.E.D。

正如另一个答案所说,我们首先简化 (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))

f display #\@ )以及 g (用于 display #\* ).

(let* ((yin (f get-cc))
       (yang (g get-cc)))
    (yin yang))

接下来我们需要计算出评估顺序。为了清楚起见,我将引入一个“步骤表达式”,它使每个求值步骤都显式化。首先让我们问一下:上面的函数需要什么?

和 . 在步骤表达式中,我们写

s0 f g =>

第一步是计算 yin 但这需要评估 (f get-cc) ,后者需要 获取抄送 .

粗略地说, s1 因为这是下一步。所以我们写

s0 f g => s1 f g ?
s1 f g cc =>

f 和 在里面 s0 s1级 不必相同,它们仅在当前步骤中使用。这使得上下文信息显式。现在,它的价值是什么 cc s1级 具有 和 绑定到相同的值。

s0 f g => s1 f g (s1 f g)
s1 f g 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 . 但现在我们还有一个价值要传递: .

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 => 

到 .

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

这是困惑大师大卫·马多尔的一个老谜题 创建Unlambda。这个难题已经讨论了好几次了 次。

泰勒·坎贝尔提出了一个很好的解决方案: 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