David Madore 的 Scheme 迷题解释

win_hate

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

1. 
   
2. (define (id x) x)
   
3. (define (f x) (display "O")  x)
   
4. (define (g x) (display "-")  x)
   
5. 
   
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 编辑 ]

win_hate

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

win_hate

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

win_hate

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

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

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

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

win_hate

drscheme，就是 plt 里带 gui 那个，在我这里本身就跑不了。

不过在 plt 带的  mzscheme 是可以运行的。

win_hate

原帖由 swordfish.cn 于 2008-9-6 10:21 发表
我在 MIT-Scheme 里面运行了，结果是这样的：


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

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


Why

应该这样

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

复制代码

win_hate

我这里没有 MIT-Scheme，但感觉

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

复制代码

是有问题的。这样定义了一个函数 call/cc，其参数个数为 0，这与一般的 call/cc 不同。原来的 call/cc 有一个参数。

你定义出来的 call/cc 不接收参数，所以 (call/cc id) 应该是出错的。

[ 本帖最后由 win_hate 于 2008-9-6 11:03 编辑 ]

win_hate

原帖由 cobrawgl 于 2008-9-6 10:46 发表
还是有问题啊，怎么回事？

那你改成这样

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

复制代码

win_hate

把 call/cc 换成 call-with-current-continuation 或者

(define call/cc call-with-current-contination)

win_hate

原帖由 MMMIX 于 2008-9-6 11:32 发表

有试过从源码编译么？

没有。自从用了 Ubuntu，已经很少自己动手编译了。看来正是如你所说，Debian 的二进制包有问题。