有没有同学来讲解下王垠的代码的...

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4269 天前的主题，其中的信息可能已经有所发展或是发生改变。

居然更新了三篇 http://blog.sina.com.cn/s/articlelist_1569777711_0_1.html
中间说到一段:

“”“
我最精要的代码都放在 GitHub 上了。但是除非接受过专门的训练，你恐怕不会理解它们的价值。你会很难想象，这样一片普通人看起来像是玩具的 40 行代码，融入了我一个星期的日日夜夜的心血，数以几十计的推翻重写。这段代码，曾经耗费了一些顶尖专家十多年的研究。一个教授告诉我，光是想看懂他们的论文就需要不止一个月。而它却被我在一个星期之内闷头写出来了。我是在说大话吗？代码就摆在那里，自己去看看不就知道了。当我死后，如果有人想要知道什么是我上半生最重要的“杰作”，也就是这 40 行代码了。它蕴含的美，超越我给任何公司写的成千上万行的代码。
”“”

然后链接给出了这段代码, 应该是没错的...

https://github.com/yinwang0/gems/blob/master/cps.ss

作为 CoffeeScript 死党表示对 Racket 真心不深入
而且就算带着景仰, 代码理解上的藩篱也不是就能越过去的
求掌握了 Racket 的同学讲解.. Orz

代码

Racket

16 条回复 • 1970-01-01 08:00:00 +08:00

monkeydev

2013-03-03 19:14:38 +08:00

同观摩中

monkeydev

2013-03-03 19:16:39 +08:00

@jiyinyiyong 你blog怎么挂了啊

jiyinyiyong

2013-03-03 19:30:19 +08:00

@monkeydev 我的博客 VPS 太慢所以没去打理了.. 现在先改了微博网址

monkeydev

2013-03-03 19:31:58 +08:00

@jiyinyiyong 哦，我订阅你的blog，今天点开不能访问

monkeydev

2013-03-03 19:33:41 +08:00

@jiyinyiyong 如果你的blog是PHP的话，可以free一个虚拟主机给你

qiao

2013-03-03 19:34:42 +08:00

就是將一段代碼轉換爲等價的 Continuation Passing Style。這東西不好解釋，推薦去看這本書： Essentials of Programming Languages （搞 scheme 的都應該認識本書的作者， Daniel P Friedman，這人也是王珢在 Indiana 大學的導師）

limu

2013-03-03 19:34:44 +08:00

他自己以前说过:自动的CPS变换. 用伪C代码解释一个:
比如, 变换前的:
int sum(int* arr, int len){
if(len <= 0) return 0; else return arr[0] + sum(arr+1, len-1);
}
调用: print(sum([1,2,3,4], 4)) //输出 10;

变换后的:
void sum_cps(int sum, int* arr, int len, void (callback*)(int)){
if(len <= 0) callback(sum);
else sum_cps(sum + arr[0], arr+1, len-1, callback);
}
调用:(sum_cps, 0, [1,2,3,4], 4, print);
这样变换以后, 自动变成尾递归. sum 每次递归调用需要把arr[0] 压栈, len大时会堆栈溢出, 而sum_cps,需要的栈为0, 不会堆栈溢出.
递归调用是FP的根本, 所以自动实现这种变换意义很大.

hitmoon

2013-03-04 16:40:46 +08:00

感觉这种变换和迭代有点类似。

wenbinwu

2013-03-04 16:43:19 +08:00

在美帝上学的有自信是好的，自负就不好了

jiyinyiyong

2013-03-04 19:51:53 +08:00

@monkeydev 谢谢啦. 是一个入门级的 Node 博客.

jiyinyiyong

2013-03-04 19:52:34 +08:00

@qiao @limu 想不通, 那为什么王垠本人对此特别推崇呢?

wenbinwu

2013-03-04 19:56:23 +08:00

@jiyinyiyong 年轻~

monkeydev

2013-03-04 20:45:24 +08:00

@jiyinyiyong node表示是还是有点无能为力啊

dingstyle

2013-03-04 21:59:29 +08:00

楼上几位说得很清楚了，我在这里稍微补充一下：CPS的基本思想是将普通函数的return转换为调用另一个函数（即这个函数的continuation），由于函数永远都不会返回，我们也就不需要调用栈。举例来说呢，Chicken Scheme这样的编译器就会利用CPS来消除调用栈。
另外，如果一个程序写成了CPS形式的话，call/cc这个special form可以用一个普通函数来实现：

(lambda (f k) (f (lambda (v k0) (k v)) k))

由于call/cc一直是解释器性能优化的一个难点，不难理解CPS转换对于现代函数式语言的编译器、解释器的重要意义了。

jiyinyiyong

2013-03-04 22:11:29 +08:00

@dingstyle 那王垠做的这是什么?

dingstyle

2013-03-05 00:36:49 +08:00 via iPad

@jiyinyiyong 他做的是自动将一个普通程序转换为等价的CPS形式。