中国领先的IT技术网站
51CTO旗下网站
所谓函数式编程，到底意味着什么？
《Clojure编程》第2章函数式编程，本章接下来介绍的这些对你来说应该都是一些很熟悉的概念，但是这些概念值得再过一遍以便更深入地理解Clojure 风格的函数式编程。本节为大家介绍所谓函数式编程，到底意味着什么。
作者：徐明明/杨寿勋 译来源：电子工业出版社| 09:02
第1部分 函数式编程以及并发
第2章 函数式编程
函数式编程在软件开发领域中是一个见仁见智的概念。虽然在该领域中有很多不同的见解，但是Clojure 无疑是一种函数式语言，而这也是Clojure 本身许多优点和特性的源泉。
在这一章中，我们会：
1． 介绍到底什么是函数式编程。
2． 解释为什么你应该关注函数式编程。
3． 讨论Clojure 的具体实现&&使得Clojure 成为一门优秀语言的原因。
在这个学习的过程中，我们希望使得函数式编程&&特别是Clojure 风格的函数式编程不是那种学术研究风格的函数式编程，可以像这些年的过程式编程、面向对象式编程一样改进你的软件设计和开发。
如果你已经对函数式编程非常熟悉（不管是通过Ruby、JavaScript 或者更纯正的函数式编程如Scala、F# 或者Haskell 等），那么接下来介绍的这些对你来说应该都是一些很熟悉的概念，但是这些概念值得再过一遍以便更深入地理解Clojure 风格的函数式编程。
如果你对函数式编程完全是陌生的，或者一开始你对函数式编程是持质疑态度的，那么我们强烈建议你读一读这一章，你不会后悔的！再回忆一下第1 章提到的：Clojure要求你提高你的水平，同时作为让你这样做的回报，它也会使你的水平越来越高；就像如果要学习面向对象编程、Java 或者Ruby，你要提高自己的水平；学习函数式编程、Clojure，你也需要提高你自己的水平。但是作为回报，你所得到的不只是一个&新的思维方式&，而且还会得到一些实用的工具和理论来解决我们日常生活中每天都要遇到的编程挑战。
编程挑战。
所谓函数式编程，到底意味着什么？
函数式编程是一个比较大的概念，在不同的语言里面有不同的解释。在Clojure 中，函数式编程意味着：
我们希望操作不可变的值，这包括：
我们使用简单抽象的不可变数据结构，而不是有可变状态的数据结构。
把函数本身当做值的一种，从而使得我们可以使用高阶函数。
我们更喜欢对数据进行声明式的处理，而不是命令式的控制、遍历。
我们喜欢通过对函数进行递增式的组合，使用高阶函数以及不可变数据结构，在更高的抽象级别（或者说正确的级别) 来解决复杂的问题。
这些都是你可能听说过的Clojure 中其他更高级特性的基础，比如Clojure 对于多线程编程，或者更通用的说法是对于对象标识和对象状态所提供的明确定义的语义，我们会在第4 章中分别介绍。
【责任编辑： TEL：（010）】&&&&&&
大家都在看猜你喜欢
热点热点头条头条热点
24H热文一周话题本月最赞
讲师：126225人学习过
讲师：90211人学习过
讲师：41545人学习过
精选博文论坛热帖下载排行
本书结合大量的典型实例，详细介绍了用Java来编写网络应用程序的技术。本书的范例都基于最新的JDK 1.5版本，书中内容包括：Java网络编程的...
订阅51CTO邮刊面向对象与函数式编程做对了什么？ - 知乎专栏
{"debug":false,"apiRoot":"","paySDK":"/api/js","wechatConfigAPI":"/api/wechat/jssdkconfig","name":"production","instance":"column","tokens":{"X-XSRF-TOKEN":null,"X-UDID":null,"Authorization":"oauth c3cef7c66aa9e6a1e3160e20"}}
{"database":{"Post":{"":{"contributes":[{"sourceColumn":{"lastUpdated":,"description":"吾与吾家小儿的成长","permission":"COLUMN_PRIVATE","memberId":230,"contributePermission":"COLUMN_PUBLIC","translatedCommentPermission":"all","canManage":true,"intro":"吾与吾家小儿的成长","urlToken":"parenting","id":2196,"imagePath":"4b70deef7","slug":"parenting","applyReason":"","name":"父母心","title":"父母心","url":"/parenting","commentPermission":"COLUMN_ALL_CAN_COMMENT","canPost":true,"created":,"state":"COLUMN_NORMAL","followers":358,"avatar":{"id":"4b70deef7","template":"/{id}_{size}.jpg"},"activateAuthorRequested":false,"following":false,"imageUrl":"/4b70deef7_l.jpg","articlesCount":53},"state":"accepted","targetPost":{"titleImage":"/v2-246e0cc8d8dcfb86c708_r.png","lastUpdated":,"imagePath":"v2-246e0cc8d8dcfb86c708.png","permission":"ARTICLE_PUBLIC","topics":[726],"summary":"面向对象编程，其核心是对象与消息。对象是待解问题里的实体，消息是解决问题过程中实体之间的互动。函数式编程，其核心是函数与调用。函数是待解问题里的概念，调用是解决问题过程中的推导。面向对象做对了消息派发，函数式编程做对了执行控制。对于面向对…","copyPermission":"ARTICLE_COPYABLE","translatedCommentPermission":"all","likes":0,"origAuthorId":0,"publishedTime":"T14:42:40+08:00","sourceUrl":"","urlToken":,"id":2018369,"withContent":false,"slug":,"bigTitleImage":false,"title":"面向对象与函数式编程做对了什么？","url":"/p/","commentPermission":"ARTICLE_ALL_CAN_COMMENT","snapshotUrl":"","created":,"comments":0,"columnId":2196,"content":"","parentId":0,"state":"ARTICLE_PUBLISHED","imageUrl":"/v2-246e0cc8d8dcfb86c708_r.png","author":{"bio":"人生如梦","isFollowing":false,"hash":"26e0fb9e77dcc7bc8a30ef","uid":20,"isOrg":false,"slug":"pinxue","isFollowed":false,"description":"如果答案字很少，说明我在用手机。如果态度很不好，说明我在驾车等红灯。","name":"品雪","profileUrl":"/people/pinxue","avatar":{"id":"v2-223b0e0adf28fb3e6e72c2","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"memberId":230,"excerptTitle":"","voteType":"ARTICLE_VOTE_CLEAR"},"id":509204}],"title":"面向对象与函数式编程做对了什么？","author":"pinxue","content":"面向对象编程，其核心是对象与消息。对象是待解问题里的实体，消息是解决问题过程中实体之间的互动。函数式编程，其核心是函数与调用。函数是待解问题里的概念，调用是解决问题过程中的推导。面向对象做对了消息派发，函数式编程做对了执行控制。对于面向对象编程，消息触发接收者的动作，消息的派发由编译器或运行时管理。函数调用是消息派发的一种实现手段， 执行效率高，通常在编译时已经决定消息由接收者的哪段代码响应。更为灵活的实现里，编译器只生成消息分发调用，运行库里面的消息分发机制在执行时查表决定到底执行哪一段代码。由于消息分发机制的存在，架构演进时将对象替换或分开布署是非常方便的。如果一开始就采用灵活的分发机制，那么替换消息目标对象或者将对象分布到不同进程、节点上可以变成对使用者完全透明，可能只需要做一些配置修改就行，当然这样在不需要这种灵活性时就有一点性能上的代价。函数式编程环境里的函数是自包含的，不允许状态依赖，执行顺序也不是一道顺序的指令流，很自然的需要编译器或运行时提供任务调度机制，这样高阶函数、lambda表达式之类的执行片段才能当做数据传递并在正确的时刻、环境下执行。由于执行控制机制的存在，函数式编写异步处理和并发响应是非常便利的。在对世界进行抽象方面，咋一看，面向对象认为一切都是对象，状态与行为并列；函数式认为一切都是函数，状态附着于行为；而对象之间只应该通过消息互动，应用开闭原则(OCP)，其实状态也是附着于行为的；因此可以说FP在抽象手段方面更直白，而OOP则有更多的犯错机会。另一方面，严格说来，函数式编程里的状态是以函数的参数和返回值来表达的，因此变化过程是清晰、可预测的，但用来表达问题未免繁琐，实践里还是拿闭包将状态与行为封到一起方便。以及在冯氏架构的机器上还得尽量搞成尾调用，不然容易爆栈，虽然坑在机器架构不配合，不过这年头没得选嘛。顺便一提，类、继承、多态都不是面向对象编程必备的部分，仅仅是为了方便代码重用而搞出来的。实际上，Alan Kay 在正式提出 Object-Oreinted 之前，Simula I/67 已经存在并实现了继承，但是 Alan Kay 认为继承并不适合做为OOP基本组成部分，这要感谢他的生物学背景(本科专业数学与分子生物学)让他更希望用细胞计算机的方式看待程序。写到这里，不禁对 Scala 产生了一点兴趣……但是扫了一眼语法，算了，还是 JavaScript 比较爽。找插图的时候发现，Oreilly 居然出了本以这个为主题的书，还是免费的：。插图就是书的封面了，算是帮它做个广告吧。","updated":"T06:42:40.000Z","canComment":false,"commentPermission":"anyone","commentCount":16,"collapsedCount":0,"likeCount":90,"state":"published","isLiked":false,"slug":"","lastestTipjarors":[],"isTitleImageFullScreen":false,"rating":"none","titleImage":"/v2-246e0cc8d8dcfb86c708_r.png","links":{"comments":"/api/posts//comments"},"reviewers":[],"topics":[{"url":"/topic/","id":"","name":"编程"},{"url":"/topic/","id":"","name":"面向对象编程"},{"url":"/topic/","id":"","name":"函数式编程"}],"adminClosedComment":false,"titleImageSize":{"width":718,"height":1080},"href":"/api/posts/","excerptTitle":"","column":{"slug":"parenting","name":"父母心"},"tipjarState":"activated","tipjarTagLine":"计算机的书普遍挺贵的……","sourceUrl":"","pageCommentsCount":16,"tipjarorCount":0,"annotationAction":[],"hasPublishingDraft":false,"snapshotUrl":"","publishedTime":"T14:42:40+08:00","url":"/p/","lastestLikers":[{"bio":"","isFollowing":false,"hash":"4a575b7f25df351dcd8ec1bb013b56c6","uid":20,"isOrg":false,"slug":"dan-bo-xiang","isFollowed":false,"description":"","name":"單柏祥","profileUrl":"/people/dan-bo-xiang","avatar":{"id":"da8e974dc","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"","isFollowing":false,"hash":"61fd0c05aa160d04367e","uid":64,"isOrg":false,"slug":"xiang-hao-fan","isFollowed":false,"description":"","name":"项昊凡","profileUrl":"/people/xiang-hao-fan","avatar":{"id":"da8e974dc","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":null,"isFollowing":false,"hash":"b07b4fe49a9a31","uid":829000,"isOrg":false,"slug":"wangmeiwang","isFollowed":false,"description":"","name":"wangmeiwang","profileUrl":"/people/wangmeiwang","avatar":{"id":"da8e974dc","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"软件工程专业","isFollowing":false,"hash":"5484f36bcfb5c2d69cb5d","uid":681400,"isOrg":false,"slug":"liu233w","isFollowed":false,"description":"软件工程专业15级学生，（自认为）准程序员\n\n个人博客： liu233w.github.io\nGitHub主页： /liu233w","name":"不科学的科学君","profileUrl":"/people/liu233w","avatar":{"id":"4fcccf4b1b8a20ffd873e1fd98c37cb9","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"没事喜欢鼓捣代码","isFollowing":false,"hash":"254fc0bcdead685a3d20","uid":52,"isOrg":false,"slug":"jacquesdong","isFollowed":false,"description":"","name":"依然","profileUrl":"/people/jacquesdong","avatar":{"id":"7a48a4032","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false}],"summary":"面向对象编程，其核心是对象与消息。对象是待解问题里的实体，消息是解决问题过程中实体之间的互动。函数式编程，其核心是函数与调用。函数是待解问题里的概念，调用是解决问题过程中的推导。面向对象做对了消息派发，函数式编程做对了执行控制。对于面向对…","reviewingCommentsCount":0,"meta":{"previous":{"isTitleImageFullScreen":true,"rating":"none","titleImage":"/50/v2-ab989d3656e6dee9bcfd96ee1fb7c9ad_xl.jpg","links":{"comments":"/api/posts//comments"},"topics":[{"url":"/topic/","id":"","name":"PlayStation VR"},{"url":"/topic/","id":"","name":"虚拟现实（VR）"},{"url":"/topic/","id":"","name":"编程"}],"adminClosedComment":false,"href":"/api/posts/","excerptTitle":"","author":{"bio":"人生如梦","isFollowing":false,"hash":"26e0fb9e77dcc7bc8a30ef","uid":20,"isOrg":false,"slug":"pinxue","isFollowed":false,"description":"如果答案字很少，说明我在用手机。如果态度很不好，说明我在驾车等红灯。","name":"品雪","profileUrl":"/people/pinxue","avatar":{"id":"v2-223b0e0adf28fb3e6e72c2","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"column":{"slug":"parenting","name":"父母心"},"content":" 里说过，PSVR 是可以接电脑的：比较简单的是处理盒的 USB 线插到 PS4 主机上，但接 PSVR 的 HDMI 线插电脑上，不过这样意义不大。好一点则是，处理盒的 USB 插电脑上，PSVR头盔的输入 HDMI 线接电脑，但是要先在 PS4 上打开头盔电源完成初始化，并且原本输出给 PSVR头盔的 HDMI 口还得插个设备骗盒子。更进一步的，可以用一根 HDMI 线对接处理器合的 HDMI PS4 和 HDMI 头盔口，然后头盔的白口线接盒子，头盔的HDMI线插电脑上，这样就完全脱离 PS4 主机了。PSVR 的头部运动数据，可以通过 HID 接口读取，但是深度信息是用 PS Camera 在主机上生成的，目前访问不到。从
可以看出 macOS 下通过 IOKit 进行 HID 初始化：- (id) init {\n\tif((self = [super init])) {\n\t\n\t\tIOHIDManagerRef managerRef = IOHIDManagerCreate(kCFAllocatorDefault, kIOHIDOptionsTypeSeizeDevice);\n\t\tIOHIDManagerScheduleWithRunLoop(managerRef, CFRunLoopGetMain(), kCFRunLoopDefaultMode);\n\t\tIOHIDManagerSetDeviceMatching(managerRef, (__bridge CFMutableDictionaryRef)@{\n\t\t\t@kIOHIDVendorIDKey: @(0x054C),\n\t\t\t@kIOHIDProductIDKey: @(0x09AF)\n\t\t});\n\t\tIOHIDManagerRegisterInputValueCallback(managerRef, PSVR_HID_InputValueCallback, (__bridge void *)(self));\n\t\tIOHIDManagerOpen(managerRef, 0);\n
NSLog(@\"PSVR HID opened!\");\n\t}\n\treturn self;\n}\nHID 数据读取：- (void) _processHIDValue: (IOHIDValueRef) hidValue {\n\tif(IOHIDValueGetLength(hidValue) != 64) {\n\t\treturn;\n\t}\n\t\n\tNSData * data = [NSData dataWithBytes: IOHIDValueGetBytePtr(hidValue) length: 64];\n}\n原始数据略复杂，有用的：yawAcceleration: (int_16)[20] + (int_16)[36]pitchAcceleration: (int_16)[22] + (int_16)[38]rollAcceleration: (int_16)[24] + (int_16)[40]这个接口已经有比较多的封装了，Objective-C 的，C# 的和 Node.js 的都有了，拿 PSVR 到 github 上一搜就有。其中
有收集更多的控制接口信息，包括控制头盔的剧院、VR模式。显示部分，在全屏模式下，将屏幕等分成左右两块，屏幕上的内容会按照 equirectangle 的公式制造到球面上。如果内容已经是360全景2D的，直接放上去就行了，否则需要自己重新投影变化一下。相应的变换也已经有人搞过了，投影矩阵抄过来是：2D 360° Regular左右眼均显示全画面SCNMatrix4MakeRotation(M_PI, 0, 1, 0)3D 360° Horizontal (Stacked)左右分别显示上、下的一半画面SCNMatrix4MakeRotation(M_PI, 0, 1, 0)3D 180° Vertical (Side By Side)左右分别显示左、右的一半画面SCNMatrix4MakeRotation(M_PI / 2.0, 0, 1, 0)等忙活完手上的事情，得要好好折腾一下……","state":"published","sourceUrl":"","pageCommentsCount":0,"canComment":false,"snapshotUrl":"","slug":,"publishedTime":"T14:08:32+08:00","url":"/p/","title":"PSVR 的技术资料","summary":" 里说过，PSVR 是可以接电脑的： 比较简单的是处理盒的 USB 线插到 PS4 主机上，但接 PSVR 的 HDMI 线插电脑上，不过这样意义不大。好一点则是，处理盒的 USB 插电脑上，PSVR头盔的输入 HDMI 线接电脑，但是要先在 PS4 上…","reviewingCommentsCount":0,"meta":{"previous":null,"next":null},"commentPermission":"anyone","commentsCount":4,"likesCount":6},"next":{"isTitleImageFullScreen":false,"rating":"none","titleImage":"","links":{"comments":"/api/posts//comments"},"topics":[{"url":"/topic/","id":"","name":"编程"},{"url":"/topic/","id":"","name":"函数式编程"},{"url":"/topic/","id":"","name":"历史"}],"adminClosedComment":false,"href":"/api/posts/","excerptTitle":"","author":{"bio":"人生如梦","isFollowing":false,"hash":"26e0fb9e77dcc7bc8a30ef","uid":20,"isOrg":false,"slug":"pinxue","isFollowed":false,"description":"如果答案字很少，说明我在用手机。如果态度很不好，说明我在驾车等红灯。","name":"品雪","profileUrl":"/people/pinxue","avatar":{"id":"v2-223b0e0adf28fb3e6e72c2","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"column":{"slug":"parenting","name":"父母心"},"content":"有个叫
(希尔伯特)的德国人，1900 年在巴黎数学家大会上抛出了 10 个世纪难题，会后又加了一堆，合称 。其中 (指的是 23 问题清单上的第 10 个)，一直悬而未决。1928 年在 意大利波伦亚举行的数学家大会上，Hilbert 和 Wilhelm Ackermann (阿克曼)发表了 \"Principles of Mathematical Logic\"，其中 Hilbert 10th 问题给出了更为形式化的描述，细化成三个子问题：First, was mathematics complete ... Second, was mathematics consistent ... And thirdly, was mathematics decidable?\" (Hodges p. 91, Hawking p. 1121)时年 22 岁的 Kurt G?del (哥德尔)在会上听了 Hilbert 的演讲后，就决定拿这个问题做博士论文了。1929 年他完成了论文，证明了一阶谓词演算中所有逻辑上有效的公式都是可以证明的。这个一阶谓词演算完备性，也就被称为哥德尔完备性定理。然后，1930 年他顺利地在维也纳拿到了博士学位。1930 年 9 月 8 日，在德国柯尼斯堡召开了一次三个科学社区的联合会议。已经 68 岁、被哥廷根(G?ttingen)大学强制退休的 Hilbert 做开幕致辞，也是他的。这次会议第三天的一个圆桌讨论上 Kurt G?del 阐述了他的不完备性定理，解决了前两点，并于次年发表了题为“On Formally Undecidable Propositions in Principia Mathematica and Related Systems I”的论文，正如名字所示，他当时想着要写个 II 的，不过从来没真正动手写。在这部长篇大论里，G?del 首先证明了一个形式系统中的所有公式都可以表示为自然数，并可以从自然数反过来得出相应的公式。这对于今天的程序员都来说，数字编码、程序即数据计算机原理，这些最核心、最基本的常识，在那个时代却是脑洞大开的创见。运用这个编码系统，G?del 证明在系统 T 内可以形式化定义命题
P (我在系统 T
内不可被证明)，从而给确定性问题给出了否定回答。(过程太啰嗦，想了解细节请看)第3点则被称为 Entscheidungsproblem (发音 [?nt'?a??d??sp?o?ble:m], 是 'decision problem' 的德文说法)。要解决 Entscheidungsproblem 问题，首先要提供 effective computation 的数学定义。Entscheidungsproblem 引起了许多数学家的兴趣。其中有两个现在广为人知，一个叫 Alan Turing (图灵)，一个叫 Alonzo Church (丘奇)，两人在同在1936年独立给出了否定答案。Alan Turing 1935 年跑去听 Max Newman (纽曼)讲“数学的基础”高级课程，从而迷上了确定性问题，并发明了图灵机模型来定义有效计算。Universal turing machine 模型是一个通用计算机模型，这是划时代的进步。图灵机隐含了存储计算的机器模型，这深刻的影响了 Manchester、EDVAC、ENIAC 等机器的建造者，图灵本人后来还亲自操刀了 ACE 机器的设计。总之，基于存储计算的通用计算机由此发源，然后才有了日后兴旺发达的编程行业。而 Church 在 1933 年就搞出来一套以纯λ演算为基础的逻辑，以期对数学进行形式化描述，他学生 Stephen Kleene 和J. Barkley Rosser 随后提出 Kleene–Rosser 悖论，证明最初的系统不自洽。好在纯λ演算部分是自洽的，Kleene 试图在λ演算系统里重现 G?del 不完备定理时，搞定了用 λ 演算来表达算术和递归函数。这些成绩将 λ演算的研究引向了λ可定义性(definability)。1934 年 G?del 来到普林斯顿访问。3 月时，Church 向他提出可以用 λ可定义来表达有效运算的猜想， G?del 对此深表怀疑。1931 年 G?del 在不完全定理论文中已经引了入原始递归函数(primitive recursive function)， 这时候他进一步将其一般化成为通用递归函数，加上了两个约束而使之成为有效的(effective)，形成了通用递归模型。由于 G?del 1934 年演讲时表示核心概念来自 Jacques Herbrand (厄布朗)在 4 月 7 日 信件里跟他探讨的内容，所以称为 G?del-Herbrand recursive function。本来这里有一段凄美的故事，丫拖到当年 7.25 才给 Herbrand 回信，可惜 Herbrand 7.27 就在 Alps 登山时意外身亡了，1932 年 Herbrand 前一年提交的论文在身后发表。不过呢，最早那封信 1986 年被人翻出来了，2004年 CMU 的 Wilfried Sieg 研究后发现，貌似 G?del 记错了，信里面讨论的其实是 G?del 第二不完备定理与 Hilbert 形式系统的冲突，这个通用递归系统极有可能是 G?del 自己折腾出来的 ()。不过，这倒不影响 Herbrand 的天才啦，虽然 23 岁就英年早逝，但发的两篇论文已经对数学的基础做出根本性的贡献，有用他名字命名的定理。那为毛 Wilfried Sieg 后来要专门写个文公布这事儿呢？因为他 1994 年写了篇文章说 Herbrand 跟 G?del 之间这桩轶事，还老被人引用，这谁能受得了呀。而 G?del 对 Church 的λ演算系统的怀疑，也促使 Church 师徒去证明任何递归函数都是都是 λ可定义的，这就是 λ可定义模型。1935 年 Church 向数学界宣布他的论题时其实还不是很确定，直到 1936 年发表的文章才正真确认了这一论点。简单说来，λ演算是一个更符合数学公式表达习惯的系统，因此在 1960 年代之前，这套东东主要是数学家们玩，跟计算机编程没啥关联。而 G?del 更欣赏 Turing 的模型，是因为图灵机对计算的表达更加直接。1935/36 这个时间段上，我们有了三个有效计算模型：通用图灵机、通用递归函数、λ可定义。Rosser 1939 年正式确认这三个模型是等效的。值得一提的是，图灵 1936 年 5.28 向\"Proceedings of the London Mathematical Society\"提交了论文\"'On Computable Numbers, with an application to the Entscheidungsproblem\"，不过因为 Church 在美国早一步发表了\"An unsolvable problem in elementary number theory\"，这篇对基础数学和计算机两个领域都极其重要的文章发表得并不顺利。尽管 Newman 费劲巴拉的解释两者的方法完全不同，图灵还是不得不修改论文，加了个附录引述了 Church 的工作，并证明两者是等价的，1936 年 11 月 12 日正式提交，1937 年才得以付印出版。在修改过程中，图灵了解到普林斯顿那边儿除了 Church 还有 G?del, Kleene (克莱尼), Rosser (罗瑟) 以及 Bernays (奈斯)等一堆逻辑学研究者，于是兴冲冲跑去当 graduated student，去了才失望的发现除了 Church 其他人前一年都离开了。而 Church 也就当收了个挂单和尚，所以两个人关系并不亲密。图灵在这里拿到了博士学位，学位论文里意外的提到了一个不动点组合子Θ，这是第一个公开发表的不动点组合子。前边已经多次提到函数，这全都是数学意义上的函数，最早的定义可以追溯到 1889 年 Giuseppe Peano (皮亚诺)，尽管对函数和类(指变量值的集合)的抽象符号一直在发展，但都没有对 substitution 和 convension 提供形式化定义，要等到 1920 年代组合子逻辑和更晚的 λ演算出现时才给出。Hilbert 研究组里的 Sch?nfinkel 1920 年 12.7 演讲中就已经提出了组合子逻辑(combinatory logic)，1924 年他的同事 Heinrich Behmann (贝曼)整理成文发表了。不过他后来回了莫斯科，1927年发现他因为精神疾病而在住院治疗，只在 1929 发过一篇论文，最终在 1942 年贫病而死。二战恶劣的生存环境下邻居拿他的研究手稿去烧火取暖…… 一直等到 Curry Haskell (柯里) 1927 在普林斯顿大学当讲师时，才重新发现了 Moses Sch?nfinkel 关于组合子逻辑的成果。Moses Sch?nfinkel 的成果预言了很多 Curry 在做的研究，于是他就跑去哥廷根大学与熟悉 Moses Sch?nfinkel 工作的 Heinrich Behmann、Paul Bernays 两人一起工作，并于 1930 年以一篇组合子逻辑的论文拿到了博士学位。Curry Brooks Haskell 整个职业生涯都在研究组合子，实际开创了这个研究领域，λ演算中用单参数函数来表示多个参数函数的方法被称为 Currying (柯里化)，虽然 Curry 同学多次指出这个其实是 Sch?nfinkel 已经搞出来的，不过其他人都是因为他用了才知道，所以这名字就这定下来了；后来有三门编程语言以他的名字命名，分别是：Curry, Brooks, Haskell。Curry 在 1928 开始开发类型系统，他搞的是基于组合子的 polymorphic，Church 则建立了基于函数的简单类型系统。程序正确性证明和程序验证，它的一些基本概念和方法是 40 年代后期诺伊曼和图灵等人提出的。诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。不过图灵的这一成果长期不受重视。通用计算机诞生之后，大家都发现直接折腾机器码实在是没效率了，于是搞出了符号汇编语言，但是表达逻辑还是太不直接了。于是 1952 年 Halcombe Laning 提出了直接输入数学公式的设想，并制作了 GEORGE 编译器演示该想法。受这个想法启发，1953 年 IBM 的 John Backus 组建了一支强大的队伍开始给 IBM 704 主机研发数学公式翻译系统，1954 年中发布了规范草稿，并在 1956 年 10 月编制出使用手册，第一个 FORTRAN (FORmula TRANslating 的缩写)编译器 1957.4 正式发行。FORTRAN 程序的代码行数比汇编少 20 倍，尽管大家怀疑编译器生成代码的性能会不如手写(那会儿机时很贵)，还是迅速流行开了。FORTRAN 的成功，让很多人认识到直接把代数公式输入进电脑是可行的，并开始渴望能用某种形式语言直接把自己的研究内容输入到电脑里进行运算。John McCarthy 1956 年在 Dartmouth 的一台 IBM 704 上搞人工智能研究时，就想到要一个代数列表处理(algebraic list processing)语言。他的项目需要用某种形式语言来编写语句，以记录关于世界的信息，而他感觉列表结构这种形式挺合适，既方便编写，也方便推演。做为 IBM plane geometry 项目的顾问，他先忽悠 Herbert Gelernter 和 Carl Gerberin 给 FORTRAN 加上了 list processing，搞出了 FLPL (FORTRAN List Processing Language)，并在该项目中成功应用。** 正因为是在 IBM 704 上开搞的，所以 LISP 的表处理函数才会有奇葩的名字： car/cdr 什么的。其实是取 IBM704 机器字的不同部分，c=content of，r=register number, a=address part, d=decrement part ()不过 1957~58 年间亲自拿 FORTRAN 写了个国际象棋程序之后，觉得还是太麻烦，于是他 58 年整个夏天都泡在 IBM 的信息研究部琢磨新的语言，以免去自己人工将列表结构翻译成 FORTRAN 程序的麻烦。这种新的编程语言有很多创造性的特性，John McCarthy 提到：* 用条件表达式来写递归函数 (Church 是用高阶函数的)* 使用 Church 1941 的符号来表示函数，以便将函数做为参数传递 * 因为看不懂 Church 书里其余的部分，所以就不掂记着实现他那个更通用的函数定义方式了 (也就是除了用 lambda 关键字，其实 最早的 LISP 不是基于 λ演算实现的，理论基础是 Kleene 的一阶递归函数，不过现在的 LISP 实现都是基于 lambda calculus 的了)这个列表处理语言就叫 LISP。等等，好不容易想得挺美了，可是 IBM 的家伙们对 FLPL 已经很满意了，居然忽悠不动了！1958 秋天，John McCarthy 在 MIT EE 混上了 Assistant Professor，跟数学系的 Marvin Minsky 一起立了个人工智能的项目，开始自己实现 LISP 。这段故事很长，自己去看吧，这里就提一个，数学上的函数应该结果只跟传入的参数有关，不受其它状态的影响，除了返回值也不影响其它地方的状态，这叫没有副作用，但是实际程序里副作用却能极为方便的提升执行效率，纠结呀，最后 LISP 里还是有副作用的。不过有数学洁癖的这帮家伙后来()论证了 Pure LISP 是可以不支持副作用的，这样才能方便的用一阶谓语逻辑去证明程序的性质。John McCarthy 对图灵机当然也是很熟悉的，他还很得意的指出， 要显摆 LISP 比图灵机简洁，实现一下 universal LISP function 就明白了嘛，比 universal Turing machine 要简洁好理解就对了。这个就是 LISP 的 eval 函数啦。结果为了实现 eval，Nathaniel Rochester 先发明了 LABEL，以便可以用 LISP 数据来表示 LISP 函数，D.M.R. Part 接着指出用 Church 的 Y 算子其实光用 λ 不用 LABEL 也能搞定。然后， S.R. Russell 发现，这个 eval 实现完全可以当 LISP 解释器嘛。LISP 开发者们机智的采用了逐步 bootstrap LISP 的实现策略，后来又有了解释器，最后 Timothy Hart and Michael Levin 拿 LISP 写出了第一个能工作的 LISP 编译器，这也是世界上第一个用被编译语言写的编译器。LISP 影响很大，后来衍生出 CommonLisp, Scheme 等许多方言。1978 年对自由变量绑定问题(FUNARG)的分析，让大家认识到元编程与高阶编程是不一样的，这也是 LISP 的一大贡献。不过，尽管 LISP 各种牛叉，在数字计算上比 FORTRAN 慢 10 到 100 倍也是要了命了。而且，递归式的表达式，看起来也没有命令式的直观易懂。所以，在工程应用方面应用比较有限。1955 年开始，搞算法研究的人们就在探讨能直接书写算法的编程语言，欧美的计算机科学家们 1958 年在 ETH Zurich 开了个会，建立了一个委员会来定义一种通用高级编程语言，称为
ALGOL (ALGOrithmic Language) ，1958 年首次发表的报告称为
ALGOL58。1959 年在巴黎又开了次会，定下了 ALGOL60，这个才真正有实现，后来还有个 ALGOL68 不过没人鸟，所以今天说 ALGOL 就是指 ALGOL60。John Backus 为了形式化的描述 ALGOL58 语法规范，发明了 Backus normal form，Peter Naur 在描述 ALGOL60 时进行了修改和扩展，后来 Donald Knuth 建议改名为 Backus-Naur normal form，简称 BNF范式，搞文法的都少不了要用到的。Naur 等在研究 Label 实现时搞出来 program point 的概念，后来演变成了 continuation。Niklaus Wirth 1966年发展了 ALGOL W，因为 IBM 觉得太超前没要，他后来改吧改吧变成了 Pascal 。ALGOL 是相当超前的，这是第一个结合了命令式和 λ演算的编程语言。尽管一般不认为 ALGOL 是函数式语言，但是它确实实现了 call-by-name，Naur 1964 更订版 ALGOL60 规范精确定义了过程调用的效果，跟 λ演算的 β-reduction 完全一致，它的变量绑定也跟 λ 的规则很相近，1964 年 Landin 给实现了 closure 。从 1964 年的\"The Mechanical Evaluation of Expressions\"开始，Landin 写了一系列论文研究编程语言与 λ演算之间的关系，并发明了第一个函数式抽像机器 SECD(1965 Correspondence between ALGOL 60 and Church's Lambda-notation I/II)，并从 66 年的The Next 700 Programming Languages\"开始阐述他理想中的编程语言 ISWIM(if you see what I mean)，基本上就是sugared lambda + assignment + control 。John Backus 在1970年代搞了 FP 语言，1977 年发表。虽然这门语言并不是最早的函数式编程语言，但他是 Functional Programming 这个词儿的创造者， 1977 年他的图灵奖演讲题为()。1973 年 Robin Milner 的研究组在 Edinburgh University 搞了 ML (Meta Language) 用以研究 LCF(Logic for Computable Functions)，后来演变出 OCaml 和 Standard ML。[From LCF to HCL]()1974 年 MIT 的 Barbara Liskov 带着学生搞出了 CLU 语言，这个语言带有 cluster (早期的类实现)、异常处理机制、iterator、最早的 generator (yield)。76年左右，大家开始关注 Laziness。而 1987 年从美国俄勒冈州波特兰(in Portland, Oregon)召开的函数式编程语言与计算架构会议(FPCA '87 )开始，建立函数式编程开放标准的运动开始了，形成了 Haskell，不过只是书面规范，要到 1990 才开始有实现。参考资料：(参考了太多，有一些随手记过来了，更多的当时没有记，现在也懒得再一一找回来了，见谅。)","state":"published","sourceUrl":"","pageCommentsCount":0,"canComment":false,"snapshotUrl":"","slug":,"publishedTime":"T17:57:04+08:00","url":"/p/","title":"函数式编程的早期历史","summary":"有个叫
(希尔伯特)的德国人，1900 年在巴黎数学家大会上抛出了 10 个世纪难题，会后又加了一堆，合称 。 其中 (指的是 23 问题清单上的第 10 个)，一直悬而未决。1928 年在 意大利波伦亚举行的数学家大…","reviewingCommentsCount":0,"meta":{"previous":null,"next":null},"commentPermission":"anyone","commentsCount":35,"likesCount":561}},"annotationDetail":null,"commentsCount":16,"likesCount":90,"FULLINFO":true}},"User":{"pinxue":{"isFollowed":false,"name":"品雪","headline":"如果答案字很少，说明我在用手机。如果态度很不好，说明我在驾车等红灯。","avatarUrl":"/v2-223b0e0adf28fb3e6e72c2_s.jpg","isFollowing":false,"type":"people","slug":"pinxue","bio":"人生如梦","hash":"26e0fb9e77dcc7bc8a30ef","uid":20,"isOrg":false,"description":"如果答案字很少，说明我在用手机。如果态度很不好，说明我在驾车等红灯。","profileUrl":"/people/pinxue","avatar":{"id":"v2-223b0e0adf28fb3e6e72c2","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false,"badge":{"identity":null,"bestAnswerer":null}}},"Comment":{},"favlists":{}},"me":{},"global":{"experimentFeatures":{"ge3":"ge3_9","ge2":"ge2_1","appStoreRateDialog":"close","nwebStickySidebar":"sticky","qrcodeLogin":"qrcode","favAct":"default","default":"None","mobileQaPageProxyHeifetz":"m_qa_page_nweb","newMore":"new","iOSNewestVersion":"4.2.0","newMobileColumnAppheader":"new_header","sendZaMonitor":"true","homeUi2":"default","answerRelatedReadings":"qa_recommend_by_algo_related_with_article","wechatShareModal":"wechat_share_modal_show","liveReviewBuyBar":"live_review_buy_bar_2","qaStickySidebar":"sticky_sidebar","androidProfilePanel":"panel_b","liveStore":"ls_a2_b2_c1_f2","zcmLighting":"zcm"}},"columns":{"next":{},"parenting":{"following":false,"canManage":false,"href":"/api/columns/parenting","name":"父母心","creator":{"slug":"pinxue"},"url":"/parenting","slug":"parenting","avatar":{"id":"4b70deef7","template":"/{id}_{size}.jpg"}}},"columnPosts":{},"columnSettings":{"colomnAuthor":[],"uploadAvatarDetails":"","contributeRequests":[],"contributeRequestsTotalCount":0,"inviteAuthor":""},"postComments":{},"postReviewComments":{"comments":[],"newComments":[],"hasMore":true},"favlistsByUser":{},"favlistRelations":{},"promotions":{},"switches":{"couldAddVideo":false},"draft":{"titleImage":"","titleImageSize":{},"isTitleImageFullScreen":false,"canTitleImageFullScreen":false,"title":"","titleImageUploading":false,"error":"","content":"","draftLoading":false,"globalLoading":false,"pendingVideo":{"resource":null,"error":null}},"drafts":{"draftsList":[],"next":{}},"config":{"userNotBindPhoneTipString":{}},"recommendPosts":{"articleRecommendations":[],"columnRecommendations":[]},"env":{"edition":{},"isAppView":false,"appViewConfig":{"content_padding_top":128,"content_padding_bottom":56,"content_padding_left":16,"content_padding_right":16,"title_font_size":22,"body_font_size":16,"is_dark_theme":false,"can_auto_load_image":true,"app_info":"OS=iOS"},"isApp":false},"sys":{},"message":{"newCount":0},"pushNotification":{"newCount":0}}}