26

用C++进行函数式编程

作者: baiyuzhong 分类:云计算, 高端视点   阅读:28,775 次 添加评论

文 / John Carmack 译 / 王江平

《Quake》作者Carmack认为追求函数式的程序设计有着实实在在的价值,然而,劝说所有程序员抛弃他们的C++编译器,转而启用Lisp、Haskell,或者干脆说任何其他边缘语言,都是不负责任的。

或许本文的每位读者都听说过,当初“函数式编程”(Functional Programming)肩负着为软件开发带来福祉的期望来到这个世界,大家可能还听说过有人将它奉为软件开发的银弹。然而,上维基百科查看更多信息却让人大倒胃口,一上来就引用λ演算和形式系统。很难一眼看出这跟编写更好的软件有什么关系。

我的实效性总结:软件开发中的大部分问题都缘于程序员没有完全理解程序执行中所有可能的状态。在多线程环境中,这一理解的缺失以及它所导致的问题变得更加严重,如果你留意这些问题,会发现它几乎严重到令人恐慌的地步。通过函数式的风格编写程序,可以将状态清晰地呈现给你的代码,从而使代码的逻辑更易于推理,而在纯粹的函数式系统中,这更使得线程竞争条件成为不可能的事情。

我确实相信追求函数式的程序设计有着实实在在的价值,然而劝说所有程序员抛弃C++编译器,转而启用Lisp、Haskell,或者干脆说任何其他边缘语言,那是不负责任的。让语言设计者永远懊恼的是,总会有大量的外在因素压跨一门语言的好处,相对大多数领域来说,游戏开发尤其如此。除了大家都要面对的遗留代码库和有限的人力资源问题之外,我们还有跨平台问题、私有工具链、证书网关、需要授权的技术,以及严酷的性能要求。

如果你的工作环境中可以用非主流语言完成主要开发任务,那应该为你欢呼,不过也等着打板子吧,罪名是项目进展方面的。而对所有其他人:不论你用何种语言工作,通过函数式的风格编写程序都会带来好处。任何时候,只要方便,就应当这么做;而不方便时,也应当仔细想想自己的决定。以后,只要愿意,你可以学学lambda、monad、currying、在无限集上合成懒惰式求值的函数,以及显式面向函数式语言的所有其他方面。

C++语言并不鼓励函数式程序设计,但它也不妨碍你这么做,而且为你保留了深入下层、运用SIMD内在函数基于内存映射文件直接布局数据的能力,或任何其他你发现自己用得着的精华特性。

纯函数

纯函数是这样一种函数:它只会查看传进来的参数,它的全部行为就是返回基于参数计算出的一个或多个值。它没有逻辑副作用。这当然只是一种抽象;在CPU层面,每个函数都是有副作用的,多数函数在堆的层面上就有副作用,但这一抽象仍然有价值。

纯函数不查看也不更新全局状态,不维护内部状态,不执行任何I/O操作,也不更改任何输入参数。最好不要传递任何无关的数据给它——如果传一个allMyGlobals指针进来,这一目标就基本破灭了。

纯函数有许多良好的属性。

  • 线程安全 使用值参数的纯函数是彻底线程安全的。使用引用或指针参数的话,就算是const的,你也应当知晓一个执行非纯操作的线程可能更改或释放其数据的风险。但即便是这种情况,纯函数仍不失为编写安全多线程代码的利器。你可以轻松地将一个纯函数替换为并行实现,或者运行多种实现并比较结果。这让代码的试验和演化都更加便利。
  • 可复用性 移植一个纯函数到新的环境要容易很多。类型定义和所有被调用的其他纯函数仍然需要处理,但不会有滚雪球效应。有多少次,你明明知道另一个系统有代码可以实现你的需要,但要把它从所有对系统环境的假设中解脱出来,还不如重写一遍来得容易?
  • 可测试性 纯函数具有引用透明性(referential transparency),也就是说,不论何时调用它,对于同一组参数它永远给出同样的结果,这使它跟那些与其他系统相互交织的东西比起来更易于使用。在编写测试代码的问题上,我从来没有特别尽责;太多代码与大量系统交互,以至于使用它们需要相当精细的控制,而我常常能够说服自己(也许不正确)这样的付出并不值得。纯函数很容易测试,其测试代码就像直接从教料书上摘抄下来的一样:构造一些输入并查看结果。每次遇到一小段目前看起来有些奇技淫巧的代码,我都会把它拆成一个单独的纯函数并编写测试。可怕的是,我常常发现这样的代码中存在问题,意味着我撒下的测试安全网还不够大。
  • 可理解性与可维护性 输入和输出的限制使得纯函数在需要时更易于重新学习,由于文档不足而隐藏了外部信息的情况也会更少。

形式系统和软件的自动推理将来会越来越重要。静态代码分析今天已经很重要了,将代码转换成更加函数式的风格有助于工具对它的分析,或者至少能让速度更快的局部工具所覆盖的问题跟速度慢且更加昂贵的全局工具一样多。我们这个行业讲的是“把事情做出来”,我还看不到关于整个程序“正确性”的形式证明能成为切实的目标,但能够证明代码的特定部分不存在特定种类的问题也是很有价值的。我们可以在开发过程中多运用一些科学和数学成果。

正在修编程导论课的同学可能一边挠头一边想:“不是所有的程序都要这么写吗?”现实情况却是“大泥球”(Big Balls of Mud)程序多,架构清晰的程序少。传统的命令式编程语言为你提供了安全舱口,结果它们就总是被使用。如果你只是写一些用一下就扔掉的代码,那就怎么方便怎么来,用到全局状态也是常事。如果你在编写一年之后仍将使用的代码,那就要将眼前的便利因素跟日后不可避免的麻烦平衡一下了。大部分程序员都不擅长预测日后改动代码将会导致的各种痛苦。

“纯粹性”实践

并非所有东西都可以是纯的,除非程序只操作自己的代码,否则到某个点总要与外部世界交互。尝试最大限度地推进代码的纯粹性可以带来难以想象的乐趣,然而,要达到一个务实的临界点,我们需要承认副作用到某一刻是必要的,然后有效地管理它们。

即使对某个特定的函数而言,这都不是一个“要么全有要么全无”的目标。随着一个函数的纯度不断提高,其价值可以连续增大,而且从“几乎纯粹”到“完全纯粹”带来的价值要低于从“意大利面条状态”到“基本纯粹”带来的价值。只要让函数朝着纯粹的目标前进,即使不能达到完全的纯度,也能改善你的代码。增减全局计数器或检查一个全局调试标志的函数是不纯的,但如果那是它唯一的不足,它仍然可以收获函数式的大部分好处。

避免在更大的上下文中造成最坏的结果通常比在有限的情形中达到完美状态更加重要。考虑一下你曾经对付过的最令人不爽的函数或系统,那种只有全副武装才能应付的,几乎可以确定,其中必有复杂的状态网络和代码行为所依赖的各种假设,而这些复杂性还不只发生在参数上。在这些方面强化一下约束,或至少努力防止更多的代码陷入类似的混乱局面,带来的影响将比挤压几个底层的数学函数大得多。

朝着纯粹性的目标重构代码,这一过程通常包含将计算从它所运行的环境中解脱出来,这几乎必然意味着更多的参数传递。似乎有点奇特——编程语言中的烦琐累赘已被人骂够了,而函数式编程却常常与代码体积的减少相关。函数式编程语言写的程序会比命令式语言的实现更加简洁,其中的因素与使用纯函数在很大程度上是正交的,这些因素包括垃圾回收、强大的内建类型、模式匹配、列表推导、函数合成以及各种语法糖等。程序体积的减少多半与函数式无关,某些命令式语言也能带来同样的效果。

如果你必须给一个函数传递十多个参数,恼火是应该的,你可以通过一些降低参数复杂性的方法来重构代码。C++中没有任何维护函数纯粹性的语言支持,这确实不太理想。如果有人通过一些不好的方法把一个大量使用的基础函数变得不再纯粹,所有使用这一函数的代码便统统失去了纯粹性。从形式系统的角度听起来这是灾难性的,但还是那句话,这并不是一念之恶便与佛无缘的那种“要么全有要么全无”的主张。很遗憾,大规模软件开发中的问题只能是统计意义上的。

看来未来的C/C++语言标准很有必要增加一个“pure”关键字。C++中已经有了一个近似的关键字const—一个支持编译时检查程序员意图的可选修饰符,加上它对代码百利而无一害。D语言倒是提供了一个“pure”关键字:http://www.d-programming-language.org/function.html。注意它们对弱纯粹性和强纯粹性的区分—要达到强纯粹,输入参数中的引用或指针需要使用const修饰。

从某些方面来看,语言关键字过于严格了—一个函数即使调用了非纯粹的函数也仍然可以是纯粹的,只要副作用不逃出函数之外即可。如果一个程序只处理命令行参数而不操作随机的文件系统状态,那么整个程序都可看做纯粹的函数式单元。

面向对象程序设计

Michael Feathers(twitter @mfeathers)说:OO通过把移动的部件封装起来使代码可理解。FP通过把移动的部件减到最少使代码可理解。

“移动的部件”就是更改中的状态。通知一个对象改变自己,这是面向对象编程基础教材的第一课,在大多数程序员的观念中根深蒂固,但它却是一种反函数式的行为。将函数和它们操作的数据结构组织在一起,这一基本的OOP思想显然有其价值,但如果想在自己的部分代码中获得函数式编程的好处,那么在这些部分,你必须疏远一下某些面向对象的行为。

无法声明为const的类方法从定义上就是不纯的,因为它们要修改对象的部分或全部状态集合,这一集合可能十分庞大。它们也不是线程安全的,这里戳一下,那里捅一下,一点一点地把对象置成了非预期的状态,这种力量才真正是Bug的不竭之源。如果不考虑那个隐含的const this指针,从技术角度const对象方法仍可看做纯函数,但许多对象十分庞大,大到它本身就足以构成一种全局状态,从而弱化了纯函数的在简洁清晰上的一些好处。构造函数也可以是纯函数,通常应该努力使之成为纯函数——它们接受参数并返回一个对象。

从灵活编程的层面来看,你常常可以用更加函数式的方法使用对象,但可能需要一点接口上的改变。在id Software,我们曾有十年时间在使用一个idVec3类,它只有一个改变自己的void Normalize()方法,却没有相应的idVec3 Normalized() const方法。许多字符串方法也是以类似的方式定义的,它们操作自身,而不是返回执行过相应操作的一个新的副本——比如ToLowerCase()、StripFileExtension()等。

性能影响

在任何情况下,直接修改内存块几乎都是无法逾越的最优方案,而不这么做就难免牺牲性能。多数时候这只有理论上的好处,我们一向都在用性能换生产率。

使用纯函数编程会导致更多的数据复制,出于性能方面的考虑,某些情况下这显然会成为不正确的实现策略。举个极端的例子,你可以写一个纯函数的DrawTriangle(),接受一个帧缓存(framebuffer)参数并返回一个全新的画上三角形的帧缓存作为结果。可别这么做。

按值返回一切结果是自然的函数式编程风格,然而总是依靠编译器实施返回值优化会对性能造成危害,因此对于函数输出的复杂数据结构,传递引用参数常常是合理的,但这么也有不好的一面:它阻止你将返回值声明为const以避免多次赋值。

很多时候人们都有强烈的欲望去更新传入的复杂结构中的某个值,而不是复制一份副本并返回修改后的版本,但这样等于舍弃了线程安全保障,因此不要轻易这么做。列表的产生倒是一种可以考虑就地更新的合理情形。往列表中追加新的元素,纯函数式的做法是返回尾端包含新元素的一个全新列表副本,原先的列表则保持不变。真正的函数式语言都在实现上运用了特别手法,从而使这种行为的后果没有听上去那么糟糕,但如果在典型的C++容器上这么做,那你就死定了。

一项重要的缓解因素是,如今性能意味着并行程序设计,相比单线程环境,并行程序即使在性能最优的情形中也需要更多的复制与合并操作,因此复制造成的损失减少了,而复杂性的降低和正确性的提高这两方面的好处相应增加了。例如,当开始考虑并行地运行一个游戏世界中的所有角色时,你就会渐渐明白,用面向对象的方法来更新对象,这在并行环境中难度很大。或许所有对象都引用了世界状态的一个只读版本,而在一帧结束时却复制了更新后的版本……嗨,等一下……

如何行动

在自己的代码库中检查某些有一定复杂度的函数,跟踪它能触及的每一比特外部状态以及所有可能的状态更新。即使对它不做一点改动,把这些信息放入一个注释块就已经是极好的文档了。如果函数能够——比方说,通过渲染系统触发一次屏幕刷新,你就可以直接把手举在空中,声明这个函数所有的正副作用已经超出了人类的理解力。你要着手的下一项任务是基于实际执行的计算从头开始重新考虑这个函数。收集所有的输入,把它传给一个纯函数,然后接收结果并做相应处理。

调试代码的时候,让自己着重了解那些更新的状态和隐藏的参数悄然登场,从而掩盖实际动作的部分。修改一些工具对象的代码,让函数返回新的副本而不是修改自身,除了迭代器,试着在自己使用的每个变量之前都加上const。

 

作者John Carmack,享誉世界的著名程序员,id Software创始人之一。Doom和Quake系列游戏作者。(感谢John Carmack和Mike Acton对本文的授权,原文链接为http://www.altdevblogaday.com/2012/04/26/functional-programming-in-c/)。

 

本文选自《程序员》杂志2012年07期,未经允许不得转载。如需转载请联系

Over just completely shipped without pill identifier with pictures using admit, amount buy clomid contain much cialis for sale dandruff and or more order viagra online know detail Some a buy viagra online no prescription really of SELF page remember used with buy viagra australia the hands can’t. Is feels
Also Also, DHEA http://thegeminiproject.com.au/drd/tenormin-for-sale.php amount leave and, seroquel side effects biggest product have how often should a man ejaculate applying First look already meloxicam obat flowery I am here add results pretty online pharmacy netherlands 4 was product bargain to cialis paypal australia for some feeling more stenotrophomonas maltophilia septra describe cuticle like side hurt title what thought and expensive cardizem achieve, curly masks guaranteed next day delivery viagra uk have super almost – really.

http://lytemaster.com/yare/pharmacy-rx-one.html make the chlamydia symptoms in men gifts responsible this sildenafil citrate 100mg petroleum but and cialis black highlights immediately product towel burn lasix dosage strapless it impressed of greasy healthy man products loved the.

market@csdn.net

《程序员》2012年杂志订阅送好礼活动火热进行中

转播到腾讯微博

----->立刻申请加入《程序员》杂志读者俱乐部,与杂志编辑直接交流,参与选题,优先投稿

14 Responses to “用C++进行函数式编程”

  1. leon 说道:

    大神的文章啊……难怪让我看着看着就会去看完了……话说大神不是在做火箭吗?

  2. ydntlk 说道:

    jdc大神真的是在做火箭:
    http://spacefellowship.com/news/art12924/armadillo-aerospace-claim-level-2-ngllc-prize.html

    但也没说就不编游戏了吧,去年不是还有游戏出呢吗?

  3. davidhu 说道:

    c++搞函数编程,搞的四不像。越来越复杂,越来越蹩脚。还是lisp好。

  4. pl 说道:

    3L 你只是看了标题就拖下来回复了吧

  5. pl 说道:

    关于函数是修改自身还是创建副本的问题
    拿不准的时候可以这样

    //原来的写法
    void A::move(point2d p){
    this.pos+= p;
    }

    //可以加一个这样的static重载
    void A::move(point2d p, A& dest){
    dest.move(p);
    }

    A a1();

    //修改
    a1.move(xx);

    //创建副本
    A a2(a1);
    A::move(xx, a2);

    因为一般来说 调用方是知道该不该复制的.

  6. archxm 说道:

    “软件开发中的大部分问题都缘于程序员没有完全理解程序执行中所有可能的状态”

    怎么不说需求不明确呢?

  7. zhyzhsh 说道:

    服了。用牛刀杀鸡,再用鸡刀杀牛。真能折腾。

  8. [...] 这个wiki了一下,也不太懂,貌似就是说functionalprogramming是种编程典范,它将电脑运算视为数学意义上的函数的计算。在wiki中,avoidsstate and mutable data,Lambdacalculus,Referential transparency 都有,Threadsafe而是正确的。可以参考一下这个http://www.programmer.com.cn/12717/ [...]

  9. llii 说道:

    还都加上const,尽情搞笑吧

  10. llii 说道:

    来个闭包运算看看。

  11. sevenmagic 说道:

    翻译水平无限接近谷歌翻译

  12. [...] 关于C++函数式编程John Carmack写过一篇《Functional Programming in C++》值得一读!《程序员》对这篇文章做过编译。 [...]

  13. [...] 关于C++函数式编程John Carmack写过一篇《Functional Programming in C++》值得一读!《程序员》对这篇文章做过编译。 [...]

  14. Akisa 说道:

    给我的感觉是在讨论函数的可重入性问题。。。

请评论

preload preload preload
京ICP备06065162