David Madore 的 Scheme 迷题解释

Question

就是传说中的阴阳迷题，我把代码改了一下，本质是一样的。

2. (define (id x) x)
3. (define (f x) (display "O")  x)
4. (define (g x) (display "-")  x)
6. ((f (call/cc id)) (g (call/cc id)))

复制代码

这个程序的输出是什么？ 把代码执行一下就知道了，问题是为什么有这样的输出？

这个问题有点难分析，我尽量把关键点讲清。但前提是你必须对 continuation 有充分的理解。

这个问题的难点不在 continuation，而在 continuation 的折腾。

这里有三个函数，id 直接把参数返回，是一个单位映射。f, g 也直接把参数返回，但返回前有一个输出语句。所以 f, g 是带副作用的单位映射。

从代码上看，有两处 call/cc。而分析一下代码的执行流程，就会发现，前一个 call/cc 只执行了一次，产生了一个 continuation 对象。当然，这个对象会多次返回。而后一个 call/cc 则被反复调用，产生出一系列的 continuation 对象。

我们把第一个 call/cc 产生的 continuation 称为 c0，而由第二个 call/cc 产生的一系列 continuation 分别称为 c1, c2, c3, c4, .......

先忽略掉副作用，则 id, f, g 都是单位映射，它们的工作只不过是把 continuation 传来传去而已。

c0 先被制造出来，然后是 c1，之后 c0 作用在 c1 上，此时 c0 返回，得到 (f c1)， 进一步得到 c1，这是个关键点，此时执行的是 (c1 (g (call/cc id))，c2 被产出，得到 (c1 c2)

按造这个方法分析下去，不难发现 call/cc 产出 ck 后，会作为 c(k-1) 的输入，得到 ( c(k-1), ck).

从 (c(k-1), ck) 出发，从 continuation 上看，跳转(或返回) 为 ck-> c(k-2)->c(k-2)-> ... -> c1 得到 (c0 (f ck))

此后 (f ck) -> (c0 ck) -> (f ck) -> ck，从而下一个 call/cc 被调用， c(k+1) 产生。

最后把副作用算上，continuation 转换序列为

c0 | c1 c0 | c2 c1 c0 | c3 c2 c1 c0 | ......

c0 返回后会打引一个 O；ci (i>0) 返回后会打印一个 - (本来想打印 | 的，不过为了引人一点 lazy 味道，我让它躺下，成为 -).

所以输出为

O-O--O---O----O-----O------O-------O--------O---------O----------O-----------O--- ...... ;; 还有很多，很多....

[ 本帖最后由 win_hate 于 2008-9-5 22:55 编辑 ]

Answer 1

原帖由 win_hate 于 2008-9-6 09:48 发表

DrScheme 在我这里从来没有正常工作过，恩，应该说从来没工作过。不知到是 64 位还是 SCIM 输入法的问题。症状为对输入没有反应，CPU 使用率飙升一段时间，之后仍然不能输入。

呃，我用 DrScheme 基本没碰到什么问题，不论是 Linux 还是 Mac OS X。就是在 Debian 上 DrScheme 4 二进制版本安装后有问题，不过从源码编译后就好了。至于说中文输入法，我没在 DrScheme 中用过。

Answer 2

我在 MIT-Scheme 里面运行了，结果是这样的：

OO-OO-OO- ...

MIT-Scheme 中没有 call/cc 这样的函数，所以我：

2. (define (call/cc) (call-with-current-continuation))

复制代码

Why

Answer 3

我放到 drscheme 里怎么运行不了啊

Answer 4

原帖由 MMMIX 于 2008-9-6 08:22 发表

没用过 DrScheme 的集成开发环境吧？它的括号高亮相当有特色。

DrScheme 在我这里从来没有正常工作过，恩，应该说从来没工作过。不知到是 64 位还是 SCIM 输入法的问题。症状为对输入没有反应，CPU 使用率飙升一段时间，之后仍然不能输入。

3MIX 老大知道如何解决吗？

Answer 5

原帖由 flw 于 2008-9-6 00:11 发表

我觉得数括号比较头疼。

没用过 DrScheme 的集成开发环境吧？它的括号高亮相当有特色。

Answer 6

原帖由 win_hate 于 2008-9-5 23:55 发表
要不你来学 scheme，我来学 Haskell，那样就不用翻来翻去了。

我觉得数括号比较头疼。

Answer 7

要不你来学 scheme，我来学 Haskell，那样就不用翻来翻去了。

Answer 8

看不懂，谁能给翻译成 Haskell？

Answer 9

也可以撇开细节，只说每个 ck 被造出来后，打印一个 -，之后返回 c(k-1)，而我们知道从这个状态出发会打印 k-1 个 -，总共 k 个 -.