函数式程序设计语言

来自计算思维百科
跳转至: 导航搜索

在计算机科学中,函数式程序设计(Functional Programming) 是另外一种程序设计范式(programming paradigm)。

概念

在计算机科学中,函数式程序设计(Functional Programming) 是另外一种程序设计范式(programming paradigm)。传统的程序设计语言大都以冯诺依曼式的计算机为设计背景,因而又称为冯诺伊曼式语言, John Backus 于1977 年提出的函数式程序设计语言,是一类与命令式编程语言(如C、Java、Basic和Pascal等语言)具有不同风格的编程语言,它不以冯诺伊曼式的计算机为设计背景,因而又称为非冯诺伊曼式语言。函数式程序设计根源于λ演算,许多函数式编程语言可以看作是对λ演算进行的阐述。

10.4.1.png

图1 阿隆佐•邱奇(Alonzo Church)(来源于维基百科)

λ演算由阿隆佐·邱奇(Alonzo Church)(图 1和他的学生斯蒂芬·科尔·克莱尼(Stephen Cole Kleene)(图2)在20世纪30年代引入,利用λ演算,可以对任何可计算的函数进行表达和求值,故而它和图灵机是等价的。阿隆佐·邱奇是美国数学家和逻辑学家,为数理逻辑和理论计算机科学的发展做出了重大的贡献。他的代表性成果包括邱奇-图灵理论(Church–Turing thesis)和λ演算等。此外,邱奇还是一位非常成功的导师,他的学生中不乏名动天下的数学家和计算机科学家,例如图灵和克莱尼。克莱尼是美国数学家和逻辑学家,他的递归论研究奠定了理论计算机科学的基础,他也是正规表达式(regular expression)的发明者。

函数式编程语言与命令式编程语言(如C、Java、Basic和Pascal等)具有明显不同的风格,它具有更强的数学表达性,程序由函数的定义和调用构成,将计算机计算视为函数的计算。函数式程序设计曾经被称为应用性程序设计, John Backus于1977年10月17日在西雅图举行的ACM年会上获得计算机界最高奖图灵奖,会中他发表了题为“Can Programming be Literated from the von Neumann Style? A Functional Style and Its Algebra of Programs”的演说,提出了函数式程序设计的概念。

10.4.2.png

图2 斯蒂芬•科尔•克莱尼(Stephen Cole Kleene)(来源于维基百科)

特点

①函数是"第一等公民":所谓"第一等公民"(first class),指的是函数与其他数据类型处于平等地位,可以赋值给变量,也可以作为另一个函数的参数,或者作为别的函数的返回值。

②只用“表达式”,不用“语句”:“表达式”是一个有返回值的运算过程,而"语句"只是执行某种操作,没有返回值。函数式编程中只使用表达式,不使用语句,即每一步都是有返回值的运算。原因是函数式编程就是为了处理运算而产生的,不考虑系统的读写(I/O),而"语句"属于对系统的读写操作。但实际应用中I/O是必须的,因此,编程过程中,函数式编程要求把I/O限制到最小,不要有不必要的读写行为,保持计算过程的单纯性。

③没有"副作用":所谓“副作用”(side effect),指的是函数内部与外部的交互(如修改全局变量的值),产生运算以外的其他结果。函数式编程强调函数保持独立,所有功能就是为了一个新的返回值,不要有其他不相关的动作,尤其是不得修改外部变量的值。

④不修改状态:在其他类型的语言中,变量往往用来保存"状态",函数式编程不使用变量保存状态而使用参数保存状态。

⑤引用透明:引用透明(Referential transparency)指的是函数的运行不依赖于外部的变量或"状态",而其他类型的编程语言,函数的返回值往往与系统状态有关,不同的状态之下,返回值是不一样的。函数式编程语言的返回值只与输入参数有关,参数相同,则返回值相同。

函数式编程语言的代表有LISP、Haskell、Erlang、Scala、Ruby和Scheme 等。

LISP语言

约翰·麦卡锡(John McCarthy)等在1960年左右发明了LISP(LISt Processor列表处理器)语言。麦卡锡在1955年的达特矛斯会议上提出了“人工智能”的概念,并且因为在人工智能领域的贡献而获得了1971年图灵奖。

LISP是从1950年代Carnegie-Mellon大学的Newell、Shaw、Simon开发的IPL语言发展而来的,是一种基于λ演算的函数式编程语言,其特长在于操作符号性的数据和复杂的数据结构。LISP具有多个不同的版本,各个版本的语言不完全一样,1980年代Guy L. Steele编写了Common Lisp试图进行标准化,这个标准被大多数解释器和编译器所接受;在Unix/Linux系统中,一种和Emacs编辑器相结合的版本Emacs Lisp非常流行,并形成了自己的标准。Scheme 语言是 Lisp 的一个现代变种,诞生于1975年,由 MIT 的 Gerald J. Sussman and Guy L. Steele Jr. 完成。与其他LISP变种不同的是,Scheme是可以编译成机器码的。

Erlang语言

Erlang由瑞典电信设备制造商爱立信所辖的CS-Lab开发,是一种通用的面向并发的编程语言。Erlang并非一门新语言,它创立于1987年,目的是为了应对大规模的并发活动,只是当时还没有今天这样大量的对并发的需求,可谓生不逢时。Erlang语言创始人Joe Armstrong当年在爱立信使用Smalltalk做电话网络方面的开发,那个时候Smalltalk性能不高,满足不了电话网络的高性能要求。可能是习惯的原因,Joe Armstrong很喜欢Smalltalk,他定购了一台Tektronix Smalltak机器。但要过两个月的时间Joe才能看到机器,等待是一件超级无聊的事,好吧,就只有用Prolog,结果等机器到的时候,Joe已经已经深深的爱上了Prolog。经过一段时间的努力,Joe给Prolog加上了并发处理和错误恢复,就是最初的Erlang,1987年Erlang推出测试版,1991年向用户推出了第一个版本。目前,对并发与分布式的需求越来越多,于是Erlang开始得到更多人的关注。

Ruby语言

Ruby在20世纪90年代由日本人松本行弘开发,因为Perl发音与6月诞生石pearl(珍珠)相同,因此Ruby以7月诞生石ruby(红宝石)命名。松本行弘在设计Ruby时一个重要的理念就是减少编程时的不必要的琐碎时间,令编写程序的人高兴,强调程序设计时人的因素,而不是单单的只考虑机器,“人们,特别是电脑工程师们,常常从机器着想。他们认为:‘这样做,机器就能运行的更快;这样做,机器运行效率更高;这样做,机器就会怎样怎样怎样。’实际上,我们需要从人的角度考虑问题,人们怎样编写程序或者怎样使用机器上的应用程序。我们是主人,他们是仆人。”遵循上述的理念,Ruby 语言通常非常直观,按照编程人认为它应该的方式运行。

Haskell语言

1980 年代末期发布的Haskell,是在编程语言Miranda 的基础上进行了标准化的纯函数式编程语言,集合了很多函数式编程研究的思想,利用很简单的叙述就可以完成链表、矩阵等数据结构,现如今非常广泛地被用于研究的一种函数语言。现在以Haskell 为基础的语言有并行Haskell、扩充Haskell(旧名Goffin)、Eager Haskell、Eden、DNA-Hakell 和面向对象的变体(Haskell++, O'Haskell,Mondrian)。另外Haskell 还被作为在新语言设计时的样板,例如Python 中的Lambda 标记语句。

Meta Language语言

ML(Meta Language) 是一类通用的函数式编程语言,它是由爱丁堡大学的Robin Milner等在二十世纪七十年代晚期开发的,一般被归为非纯函数式编程语言,因为它允许副作用和指令式编程。今天在ML 家族中有好几种变种:两种主要的变种是Standard ML 和Caml。