函数式编程范式(1):历史与概述

@author chenyun

草稿

定义

函数式编程(英语:functional programming)或称函数程序设计,又称泛函编程,是一种编程范型,它将电脑运算视为数学上的函数计算,并且避免使用程序状态以及易变对象。函数编程语言最重要的基础是λ演算(lambda calculus)。而且λ演算的函数可以接受函数当作输入和输出。

历史

函数式编程中最古老的例子莫过于1958年被创造出来的LISP了。但是要提及函数式编程的例子却不得不从更早的λ演算说起。

图灵和阿隆佐·邱奇
是否存在一个通用模型来解决一切计算任务?1936年,阿隆佐·邱奇设计了一个名为lambda演算的形式系统。这个系统实质上是为一个超级机器设计的编程语言。在这种语言里面,函数的参数是函数,返回值也是函数。这种函数用希腊字母lambda(λ),这种系统因此得名。
除了阿隆佐,艾伦·图灵也在进行类似的研究。他设计了一种完全不同的系统(后来被称为图灵机),并用这种系统得出了和阿隆佐相似的答案。到了后来人们证明了图灵机和lambda演算的能力是一样的。有关lambda演算的支持请查阅维基百科

1949年第一台电子离散变量自动计算机诞生并取得了巨大的成功。它是冯·诺伊曼设计架构的第一个实例,也是一台现实世界中实现的图灵机。到了50年代末,一个叫John McCarthy的MIT教授(他也是普林斯顿的硕士)对阿隆佐的成果产生了兴趣。1958年他发明了一种列表处理语言(Lisp),这种语言是一种阿隆佐lambda演算在现实世界的实现,而且它能在冯·诺伊曼计算机上运行!很多计算机科学家都认识到了Lisp强大的能力。1973年在MIT人工智能实验室的一些程序员研发出一种机器,并把它叫做Lisp机。于是阿隆佐的lambda演算也有自己的硬件实现了!

特点概述

在函数式语言中,函数(lambda 演算)作为一等公民,可以在任何地方定义,在函数内或函数外,可以作为函数的参数和返回值,可以对函数进行组合。

函数式编程中的函数这个术语不是指计算机中的函数(实际上是Subroutine 子程序),而是指数学中的函数,即自变量的映射。也就是说一个函数的值仅决定于函数参数的值,不依赖其他状态。比如sqrt(x)函数计算x的平方根,只要x不变,不论什么时候调用,调用几次,值都是不变的。

与函数式编程对应的是命令式编程,命令式编程是面向计算机硬件的抽象,有变量(对应着存储单元),赋值语句(获取,存储指令),表达式(内存引用和算术运算)和控制语句(跳转指令).

命令式程序就是一个冯诺依曼机的指令序列.

常见语言和函数式编程

函数式编程语言

对比

命令式范式(OOP) 函数式范式
一切都是对象 第一等公民是函数
抽象和封装 带有闭包的Lambdas/Anonymous函数
有副作用 无副作用的调用
核心活动是组合和对象,这是通过加入新的方法实现的 核心活动是编写新的函数。
着重于数据和状态 不变性,大部分无态处理,没有状态和变量
基于图灵机 基于lambda演算

 面向对象和面向函数一直在争论,实际上纯粹的OOP和纯粹的FP都是极端的。

  • 对于OOP来讲:存在的并一定都是对象,函数就不是对象
  • 对于FP来说:存在的并不总是纯粹的,副作用总是真实存在
函数式中将超过计算的东西叫做副作用,因为文件读写,打印,随机数,这些东西都不是纯的计算过程,而是涉及到外部世界的交互,依赖于机器,不在理论的范畴。这些是不可避免的,因此副作用总是真实存在的。

副作用

但总的来说函数式编程是不可避免的潮流

enter image description here

最后

  1. 任何编程语言中都没有什么魔法或者万灵丹药,使其使用者成为好的程序员。
  2. 不要让世界适应你的模型。让你的模型适应世界。

接下来两篇, 我将以python为主要代码, java和scala,haskell为辅, 讲解函数式编程的主要特点. talk is cheap, show you the code.

函数式编程范式(2):特点
函数式编程范式(3):实战举例
傻瓜函数式编程

python初学者可以看看这篇文章 初步了解python的函数式编程