分享
 
 
 

Scheme语言的“阴阳谜题”

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

Scheme语言的“阴阳谜题”

Scheme语言里有一个著名的“阴阳谜题(Yin-yang puzzle)”,大概是这么几行代码:

(let* ((yin ((lambda (foo) (newline) foo)

(call/cc (lambda (bar) bar))))

(yang ((lambda (foo) (write-char #\*) foo)

(call/cc (lambda (bar) bar)))))

(yin yang))

程序虽然短,但我第一次看见时,却说什么也猜不出它的运行结果。从表面上看,我大致知道call/cc会让程序陷入一个死循环,但实在不清楚循环内部到底是个什么逻辑。把程序拿到Scheme环境里一运行,吓了我一跳,结果居然是这么个样子:

*

**

***

****

*****

******

*******

...

然后,我掰着手指头想了整整一天,才隐约明白了这个“阴阳谜题”的来龙去脉。看到网上谈这个谜题的人很多,详细拆解这个谜题的人却很少,我干脆把我对这个问题的理解写出来吧,不一定正确,仅供大家参考。

首先要弄清楚的是,这个“阴阳谜题”程序到底是个什么结构。我们从里向外看:

(call/cc (lambda (bar) bar))

这一句把当前继续(Current continuation)传到匿名过程(lambda (bar) bar)中,而后者简单地返回传入的参数。也就是说,这一句的作用其实是获取当前继续。下面这样的组合

((lambda (foo) (newline) foo)

(call/cc (lambda (bar) bar)))

意味着把当前继续作为参数,传到匿名过程(lambda (foo) (newline) foo)中,而后者先输出换行符,再简单地返回传入的参数。再进一步:

(yin ((lambda (foo) (newline) foo)

(call/cc (lambda (bar) bar))))

它的作用是在输出换行符后,令局部变量yin绑定到call/cc得到的继续。对yang的绑定也类似。而下面这句

(yin yang)

就是在当前的yin和yang的绑定环境中,以yang为参数调用yin。因为在Scheme中,所谓的继续(Continuation)就是一个过程,既可以被调用,也可以扮演参数的角色。所以,(yin yang)这样的语法是没有任何问题的,关键是(yin yang)这样的调用会产生什么结果,这就不是一眼可以看出来的了(也许是我自己太愚钝,聪明人多半可以很快找到答案的)。

算了,既然一眼看不出来,就先把(yin yang)这样的怪代码放到一边。整理一下思路,整个“阴阳谜题”实际上做了这么几件事:

① 开始执行(let*)结构

② 获得当前继续

③ 输出换行符

④ 把②获取的继续赋予yin

⑤ 获得当前继续

⑥ 输出星号

⑦ 把⑤获取的继续赋予yang

⑧ 以yang为参数调用yin

看上去就是这样8个步骤,但为了参透其运行逻辑,必须确定两件事:

1、(let*)到底是个什么结构?

这个问题用不着我来回答,Scheme书籍和资料里讲得很多了。只讲一点最重要的:(let*)中有一个变量列表,如这里的yin和yang,(let*)会先把第一个变量的绑定创建好,然后在第一个变量的绑定已知的环境内,把第二个变量的绑定创建好,依此类推,直到所有绑定创建好以后,就在包含所有这些变量绑定的环境内求得主体表达式的值。在本例中,主体表达式就是简单的一句话:(yin yang)

2、步骤②和⑤中获取的到底是什么继续?

如果读者搞不清什么是继续,或不清楚如何使用继续的话,最好先去查书查资料。我只强调一下,call/cc得到的继续其实就是call/cc所在的当前表达式的“全部未来”。“全部未来”这个字眼儿是从Scheme的标准文档R5RS里抄来的,它的意思是说,平常没有call/cc时,我们在求得表达式的值后要做什么事情,现在直接调用call/cc的结果过程时就会做什么事情。

也就是说,如果②处不是一个call/cc而是一个普通表达式,那么我们在求得表达式的值后,会做这些事情:输出换行符,把该表达式的值赋予yin,创建一个包含yin的新环境,然后在新环境中完成后续的步骤——我把这件事记作(A)。

现在,代码在②处获得了当前继续。这意味着,一旦我们在今后调用这个继续,调用时就会重复同样的步骤,而这时使用的“表达式的值”,就是我们在调用继续时传入的那个参数。

类似的,如果调用⑤处得到的继续,就会做这些事情:输出星号,把该表达式的值赋予yang,创建一个包含yang的新环境,然后在新环境中完成后续的步骤——我把这件事记作(B)。

好了,弄清楚这两个问题后,我们可以试着手工运行一遍“阴阳谜题”了。在下面的解析中,我们把②处获得的继续称为Ca,把⑤处获得的继续称为Cb:

1、获得继续Ca,输出换行符,把Ca赋予yin,我把这些步骤简记作:

\yin = Ca(_)

其中,\ 表示输出换行符,Ca(_)表示②处获得的继续,而在将该继续赋予yin之前,yin的值未定义,所以括号内简记为 _

2、在包含yin的环境中,获得继续Cb,输出星号,把Cb赋予yang,记作:

*yang = Cb( Ca(_) )

其中,Cb( Ca(_) )表示⑤处获得的继续,在将该继续赋予yang之前,yin的值是Ca(_)

3、调用(yin yang)。从刚才的分析,我们可以知道,这个调用要做的事情是,把yang绑定的继续Cb( Ca(_) )作为参数,调用yin绑定的继续Ca(_)。套用刚才分析出来的那句话(A),就是:输出换行符,把Cb( Ca(_) )的值赋予yin,创建一个包含yin的新环境,然后在新环境中完成后续的步骤。记作

\yin = Cb( Ca(_) )

4、现在要“完成后续的步骤”了。后续的步骤是⑤,所以接下来应该是:

*yang = Cb( Cb( Ca(_) ) )

5、又到了(yin yang)这一句了。现在yin和yang中绑定的过程和上一次不太一样了。最重要的是,yin中绑定的是Cb( Ca(_) )而不是Ca(...),这表示对yin的调用将要做(B)描述的事情,而不是(A)描述的事情。我们如法炮制,现在这个(yin yang)的意思是:输出星号,把Cb( Cb( Ca(_) ) )赋予yang,创建一个包含yang的新环境,然后在新环境中完成后续的步骤。记作

*yang = Cb( Cb( Ca(_) ) )

有一个问题是,现在的yin该是一个什么东西呢?注意,调用前,yin的值是Cb( Ca(_) ),我发明的这种记法表明了创建这个继续时的环境,即,获得这个继续时,yin的值是Ca(_)。而我们现在调用yin,从某种意义上说,这相当于回到了创建这个继续时的环境里,我们可以简单地认为,调用后,yin的值又变回了Ca(_)。记作(这里给出的只是“近似”的说法,后面我们会讨论yin的值为什么会变回去):

yin = Ca(_)

6、这回马上就又碰到了下一轮的(yin yang),因为yin的值是Ca(_),所以我们会回到(A)描述的事情中,记作:

\yin = Cb( Cb( Ca(_) ) )

7、就像这样“运行”下去,再多写几步:

*yang = Cb( Cb( Cb( Ca(_) ) ) )

*yang = Cb( Cb( Cb( Ca(_) ) ) )

yin = Cb( Ca(_) )

*yang = Cb( Cb( Cb( Ca(_) ) ) )

yin = Ca(_)

\yin = Cb( Cb( Cb( Ca(_) ) ) )

... ...

把我们上面7步得到的输出连起来:

******...

这不就是“阴阳谜题”的运行结果吗?好像事情还比较顺利,但我们还有一个问题没解决:当yin的值为Cb(...)时,在(yin yang)调用中,yin的值为什么会变回去?这个问题和Scheme使用的环境模型有关。建议大家回想一下《计算机程序的构造和解释(SICP)》一书第3章的内容。我仿照SICP的样子把“阴阳谜题”里的环境变化情况解释一下,在下面这两幅图中:

1、进入(let*)前,只有一个初始环境。把Ca绑定到yin,并创建包含yin的环境,这实际上相当于创建了一个包含yin的子环境,子环境中有个指针指向初始环境。就是左图中绿色的yin。其中,实线箭头表示引用父环境,虚线箭头表示变量绑定。

2、在刚创建的子环境中,把Cb绑定到yang,并创建包含yang的新的子环境,新子环境中有个指针指向包含yin的子环境。这就是左图中绿色的yang。

3、(yin yang)调用时,因为yin绑定的Ca过程的含义是重新创建包含yin的环境,所以,左图又多出了蓝色的yin,但这时yin的绑定指向绿色的Cb。接着创建蓝色的yang,它指向一个新的Cb。现在我们使用的是蓝色的yin和yang。

4、下一次(yin yang)调用,因为yin的绑定指向绿色的Cb,其含义是在绿色yin的环境下,重新创建包含yang的环境。于是,绿色yang被新创建的红色yang取代,而红色yang的绑定指向蓝色的Cb,红色yang的父环境还和绿色yang一致,是绿色的yin。这就是右图中的样子。现在,我们使用的是绿色的yin和红色的yang。也就是说,刚才还在使用指向Cb的yin,现在又恢复成使用绿色的yin了。这就是yin的值为什么会变回去的原因所在了。同时,因为红色yang这时指向了蓝色的Cb,下一次yin会变回到蓝色的yin,再下一次才会变回绿色的yin,因此,“阴阳谜题”每一行都会比上一行多输出一个星号。

这就是我推理出来的“阴阳谜题”的答案了(上面的讲解只是一种概念模型,与Scheme的具体实现并不完全等同)。不过,这个答案是手工推理出来的,能够被程序自动证明吗?应该是可以的,我把“阴阳谜题”扩展了一下,让程序可以自动跟踪每个继续的语义,并自动打印输出。修改后的代码如下:

(define cc-dict '())

(define (insert-cc! cc flag)

(if (assq cc cc-dict)

#f

(set! cc-dict

(cons

(cons cc (cons flag (length cc-dict)))

cc-dict))))

(define (display-cc cc prefix)

(display prefix)

(display #\()

((lambda (cc-pair)

(cond (cc-pair

(display (cadr cc-pair))

(display #\,)

(display (cddr cc-pair)))))

(assq cc cc-dict))

(display #\)))

(let ((count 5) (yang #f))

(call/cc

(lambda (exit)

(let* ((yin ((lambda (foo)

(write-char #\\)

(newline)

(insert-cc! foo #\a)

(display-cc foo "yin")

(display-cc yang "yang")

(set! count (- count 1))

(if (= 0 count) (exit 'end) foo))

(call/cc (lambda (bar) bar))))

(yang ((lambda (foo)

(write-char #\*)

(insert-cc! foo #\b)

(display-cc yin "yin")

(display-cc foo "yang")

foo)

(call/cc (lambda (bar) bar)))))

(yin yang)))))

上述代码显示了“阴阳谜题”前5行的运行过程,每次为yin、yang赋值前,代码都把yin、yang的内容打印出来,打印格式为 yin(a,0)yang(b,1) 或类似的格式,其中,yin(a,0) 表示 yin 的值为继续Ca,该继续是程序生成的第1个继续(基于0的索引)。上述代码的运行结果为:

yin(a,0)yang()*yin(a,0)yang(b,1)yin(b,1)yang()*yin(b,1)yang(b,2)*yin(a,0)yang(b,2)yin(b,2)yang()*yin(b,2)yang(b,3)*yin(b,1)yang(b,3)*yin(a,0)yang(b,3)yin(b,3)yang()*yin(b,3)yang(b,4)*yin(b,2)yang(b,4)*yin(b,1)yang(b,4)*yin(a,0)yang(b,4)yin(b,4)yang()

从这个运行结果里,我们可以清楚地看到yin、yang的变化情况,也可以看到在每一行中,yin是如何一步步地变回原来的值,并最终变回Ca以输出换行符的。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有