V2EX 首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

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

  •  
  •   jiyinyiyong · 2013-03-03 19:06:37 +08:00 · 17667 次点击
    这是一个创建于 1668 天前的主题,其中的信息可能已经有所发展或是发生改变。
    居然更新了三篇 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
    16 回复  |  直到 1970-01-01 08:00:00 +08:00
        1
    monkeydev   2013-03-03 19:14:38 +08:00
    同观摩中
        2
    monkeydev   2013-03-03 19:16:39 +08:00
    @jiyinyiyong 你blog怎么挂了啊
        3
    jiyinyiyong   2013-03-03 19:30:19 +08:00
    @monkeydev 我的博客 VPS 太慢所以没去打理了.. 现在先改了微博网址
        4
    monkeydev   2013-03-03 19:31:58 +08:00
    @jiyinyiyong 哦,我订阅你的blog,今天点开不能访问
        5
    monkeydev   2013-03-03 19:33:41 +08:00
    @jiyinyiyong 如果你的blog是PHP的话,可以free一个虚拟主机给你
        6
    qiao   2013-03-03 19:34:42 +08:00   ♥ 2
    就是將一段代碼轉換爲等價的 Continuation Passing Style。這東西不好解釋,推薦去看這本書: Essentials of Programming Languages (搞 scheme 的都應該認識本書的作者, Daniel P Friedman,這人也是王珢在 Indiana 大學的導師)
        7
    limu   2013-03-03 19:34:44 +08:00   ♥ 3
    他自己以前说过:自动的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的根本, 所以自动实现这种变换意义很大.
        8
    hitmoon   2013-03-04 16:40:46 +08:00
    感觉这种变换和迭代有点类似。
        9
    wenbinwu   2013-03-04 16:43:19 +08:00
    在美帝上学的有自信是好的,自负就不好了
        10
    jiyinyiyong   2013-03-04 19:51:53 +08:00
    @monkeydev 谢谢啦. 是一个入门级的 Node 博客.
        11
    jiyinyiyong   2013-03-04 19:52:34 +08:00
    @qiao @limu 想不通, 那为什么王垠本人对此特别推崇呢?
        12
    wenbinwu   2013-03-04 19:56:23 +08:00
    @jiyinyiyong 年轻~
        13
    monkeydev   2013-03-04 20:45:24 +08:00
    @jiyinyiyong node表示是还是有点无能为力啊
        14
    dingstyle   2013-03-04 21:59:29 +08:00   ♥ 2
    楼上几位说得很清楚了,我在这里稍微补充一下:CPS的基本思想是将普通函数的return转换为调用另一个函数(即这个函数的continuation),由于函数永远都不会返回,我们也就不需要调用栈。举例来说呢,Chicken Scheme这样的编译器就会利用CPS来消除调用栈。
    另外,如果一个程序写成了CPS形式的话,call/cc这个special form可以用一个普通函数来实现:

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

    由于call/cc一直是解释器性能优化的一个难点,不难理解CPS转换对于现代函数式语言的编译器、解释器的重要意义了。
        15
    jiyinyiyong   2013-03-04 22:11:29 +08:00
    @dingstyle 那王垠做的这是什么?
        16
    dingstyle   2013-03-05 00:36:49 +08:00 via iPad   ♥ 1
    @jiyinyiyong 他做的是自动将一个普通程序转换为等价的CPS形式。
    DigitalOcean
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   552 人在线   最高记录 3541   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.7.5 · 51ms · UTC 19:49 · PVG 03:49 · LAX 12:49 · JFK 15:49
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1