阴阳拼图是如何运作的？

Question

我试图掌握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))

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

有人可以详细解释为什么阴阳谜题会这样工作吗？

Answer 1

正如另一个答案所说，我们首先用 get-cc 简化 (call-with-current-continuation (lambda (c) c)) 。

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

注意参数是无范围的，这意味着s0和s1中的f和g不是必要的相同，并且它们只能在当前步骤中使用。这使得上下文信息变得明确。现在，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 => 

最后，最后一步是将阳应用到阴。

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主体内的lambda简单地表示为部分求值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 时，将首先计算参数

Answer 2

这是混淆大师 David Madore 的一个古老谜题，他
创建了 Unlambda。 comp.lang.scheme 中已经讨论过几个谜题
次。

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

Answer 3

我心里还不知道，但我可以用 Unlambda 变体中的铅笔和纸来推断它。

阴阳谜题的 Unlambda 变体是：

``r`ci`.*`ci

其运行结果是：（

*
**
***
****
*****
******
*******
...

在维基百科页面中查看它 call/cc: Examples。）

我已经推断出这是如何产生的，我正在展示 LaTeX 中的树重写和连续重新插入：

\documentclass[10pt]{article}
\usepackage[margin=0.2in]{geometry}
\usepackage{longtable} 
\usepackage{amsmath}
\newcommand{\parens}[1]{\left(#1\right)}
\newcommand{\angles}[1]{\left\langle#1\right\rangle}
\DeclareMathOperator{\callcc}{c}
\DeclareMathOperator{\id}{i}
\DeclareMathOperator{\brk}{r}
\DeclareMathOperator{\prnt}{.\!\!*}
\newcommand{\cont}{\mathop{\mathit{cont}}}
\newcommand{\yingyang}{\ying\parens{yang}}
\newcommand{\ying}{\brk  \parens{\cc}}
\newcommand{\yang}{\prnt \parens{\cc}}
\newcommand{\currc}{\callcc \id}
\usepackage{tikz}
\usetikzlibrary{trees}
\begin{document}
    \begin{longtable}{c|c|c}
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {yingyang}
            child {node {ying}
                child {node {$\brk$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            }
            child {node {yang}
                child {node {$\prnt$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {yingyang}
            child {node {ying}
                child {node {$\brk$}}
                child {node {\bf 1:\boxed{\callcc \Leftarrow \id}}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            }
            child {node {yang}
                child {node {$\prnt$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\brk \parens{\id \cont_1} \operatorname{yang}$}
            child {node {$\brk \parens{\id \cont_1}$}
                child {node {$\brk$}}
                child {node {$\id \cont_1$}
                    child {node {$\id$}}
                    child {node {$\cont_1$}}
                }
            }
            child {node {yang}
                child {node {$\prnt$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        \\\hline
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\brk \cont_1 \operatorname{yang}$}
            child {node {$\brk \cont_1$}
                child {node {$\brk$}}
                child {node {$\cont_1$}}
            }
            child {node {yang}
                child {node {$\prnt$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\cont_1 \operatorname{yang}$}
            child {node {$\cont_1$}}
            child {node {yang}
                child {node {$\prnt$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\cont_1 \operatorname{yang}$}
            child {node {$\cont_1$}}
            child {node {yang}
                child {node {$\prnt$}}
                child {node {\bf 2:\boxed{\callcc \Leftarrow \id}}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        \\\hline
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\cont_1 \parens{\prnt \parens{\id \cont_2}}$}
            child {node {$\cont_1$}}
            child {node {$\prnt \parens{\id \cont_2}$}
                child {node {$\prnt$}}
                child {node {$\id \cont_2$}
                    child {node {$\id$}}
                    child {node {$\cont_2$}}
                }
            };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\cont_1 \parens{\prnt \cont_2}$}
            child {node {$\cont_1$}}
            child {node {$\prnt \cont_2$}
                child {node {$\prnt$}}
                child {node {$\cont_2$}}
            };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\cont_1 \cont_2$}
            child {node {$\cont_1$}}
            child {node {$\cont_2$}
            };
        \end{tikzpicture}
        \\\hline
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\brk \cont_2 \operatorname{yang}$}
            child {node {$\brk \cont_2$}
                child {node {$\brk$}}
                child {node {$\cont_2$}}
            }
            child {node {yang}
                child {node {$\prnt$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[level distance=1cm,
            level 1/.style={sibling distance=2cm},
            level 2/.style={sibling distance=1cm},
            level 3/.style={sibling distance=0.5cm}]
            \node {$\cont_2 \operatorname{yang}$}
            child {node {$\cont_2$}}
            child {node {yang}
                child {node {$\prnt$}}
                child {node {currc}
                    child {node {$\callcc$}}
                    child {node {$\id$}}
                }
            };
        \end{tikzpicture}
        &
    \end{longtable}
\end{document}

Answer 4

这是类似于 JavaScript 的伪代码翻译：

function call(generatorFunction) {
  const generator = generatorFunction();
  const f = generator.next().value;
  const k = (x) => generator.next(x).value;
  return generator.next(f(k)).value;
}

call(function* () {
  const v = yield k => 3 * 4;
  return v + 5;
}); // 17

call(function* () {
  const v = yield k => k(3 * 4);
  return v + 5;
}); // if generators had "early return"ed, this would have been 17.

function printYin(k) {
  console.log("@");
  return k;
}

function printYang(k) {
  console.log("*");
  return k;
}

call(function* () {
  const v = yield k => k;
  const yin = printYin(v);
  call(function* () {
    const v = yield k => k;
    const yang = printYang(v);
    return yin(yang); // (*)
  })
});

// (*) It's illegal in javascript to resume a generator inside itself,
// but one can imagine a fantasy language where this is legit.

Answer 5

理解Scheme

我认为理解这个难题的至少一半问题是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 @;返回抄送；。在我们这样做的同时，我们还将 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 内部的调用将是一个错误，因为我们没有向它传递一个普通值。我们向函数传递一个延续。

乍一看，延续是一头奇怪的野兽。考虑一个更简单的程序：

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

最初 x 设置为当前的延续对象（请耐心等待），并且 print x 被执行，打印类似 的内容;。到目前为止，一切都很好。

但延续就像一个函数；它可以用一个参数来调用。它的作用是：获取参数，然后跳转到创建延续的位置，恢复所有上下文，并使其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 行，打印 @。等等。坦率地说，此时我的大脑抛出了 OutOfMemory 异常，我忘记了一切。但至少我们到达了@*@**！

显然，这很难理解，甚至更难解释。执行此操作的完美方法是在可以代表延续的调试器中单步执行它，但可惜的是，我不知道有任何延续。我希望你喜欢这个；我当然有。

Answer 6

我不认为我完全理解这一点，但我只能想到一个（极端手波）解释：

• 第一个 @ 和 * 在 yin 和 yang 首先绑定在 let* 中。 (yin yang) 被应用，并且在第一次呼叫/抄送完成后立即返回到顶部。
• 打印下一个 @ 和 *，然后打印另一个 *，因为这一次，yin 被重新绑定到第二个 call/cc 的值。
• 再次应用(yin yang)，但这次它在原始yang的环境中执行，其中yin 绑定到第一个 call/cc，因此控制返回到打印另一个 @。 yang 参数包含在第二次传递时重新捕获的延续，正如我们已经看到的，这将导致打印 **。因此，在第三遍中，将打印 @*，然后调用此双星打印延续，因此最终得到 3 颗星，然后重新捕获此三星延续， ...

Answer 7

阴阳谜题是用Scheme编写的。我假设您知道Scheme 的基本语法。

但我假设您不知道 let* 或 call-with-current-continuation，我将解释这两个关键字。

解释 let*

如果您已经知道这一点，可以跳到 解释 call-with-current-continuation

let*，它看起来像 let，作用类似于 let，但会评估其定义的变量（(yin ...) 和 (yang ...)< /code>) 一一热切地。这意味着，它将首先评估yin，然后评估yang。

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

解释call-with-current-continuation

如果你已经知道了，你可以跳到阴阳谜题。

解释call-with-current-continuation有点困难。所以我用一个比喻来解释一下。

想象一个知道咒语的巫师，该咒语是call-with-current-continuation。一旦施展咒语，他就会创造出一个新的宇宙，并将自己送入其中。但在新宇宙中他什么也做不了，只能等待有人叫他的名字。一旦被召唤，巫师就会回到原来的宇宙，带着那个可怜的家伙——“某人”——继续他的巫师生活。如果没有被召唤，当新宇宙结束时，巫师也会回到原来的宇宙。

好吧，让我们更技术一些。

call-with-current-continuation 是一个接受函数作为参数的函数。一旦你用函数F调用call-with-current-continuation，它就会打包当前的运行环境，称为current-continuation ，作为参数C，发送给函数F，并执行F。所以整个程序就变成了(FC)。或者更多的 JavaScript：F(C);。 C 的行为就像一个函数。如果F中没有调用C，那么它是一个普通程序，当F返回时，call-with-current-continuation 的值是 F 的返回值。但如果使用参数V调用C，则会再次改变整个程序。当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阳）。这

(C_0 C_1)

真是天哪！

但最终，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)

And we can continue。但我就到这里为止，我已经向你展示了阴阳谜题的前几个输出是什么。

为什么*的数量增加了？

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

我将使用类似 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未被执行的第一个Universe。
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在创建时遵循定理I。

然后调用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

Answer 8

首先沉思，最后可能的答案。

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

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

We从这里开始。

第一次通过时，您会得到 yin=A 和 yang=B 作为 yin 和 yang > 正在初始化。

The output is @*

（A 和 B 延续都会被计算。）

现在 (yin yang) 被评估为 (AB)第一次。

我们知道 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 延续堆栈，每次写入一个 * 。

（如果这大致正确，我会非常高兴！）

谢谢你的提问。