快速注册 找回密码

QQ登录

只需一步,快速开始

查看: 173|回复: 0

深入明白 Java 函数式编程系列第 1 部门 函数式编程头脑概论 ...

[复制链接]
  • TA的每日心情

    2020-5-20 10:16
  • 签到天数: 6 天

    [LV.2]偶尔看看I

    发表于 2020-6-27 14:18:05 | 显示全部楼层 |阅读模式
    媒介
    在讨论函数式编程(Functional Programming)的详细内容之前,我们起首看一下函数式编程的寄义。在维基百科上,函数式编程的界说如下:"函数式编程是一种编程范式。它把盘算当成是数学函数的求值,从而制止改变状态和利用可变数据。它是一种声明式的编程范式,通过表达式和声明而不是语句来编程。" (见 Functional Programming)
    函数式编程的头脑在软件开辟范畴由来已久。在浩繁的编程范式中,函数式编程固然出现的时间很长,但是在编程范式范畴和整个开辟社区中的盛行度不停不温不火。函数式编程有一部门狂热的支持者,在他们眼中,函数式编程头脑是办理各种软件开辟题目的终极方案;而别的的一部门人,则以为函数式编程的头脑并不轻易明白,学习曲线较陡,上手起来也有肯定的难度。大多数人更倾向于担当面向对象或是面向过程如许的编程范式。这也是造成函数式编程范式不停停顿在小众阶段的缘故原由。
    如许南北极化的反应,与函数式编程自己的特性是分不开的。函数式编程的头脑脱胎于数学理论,也就是我们通常所说的λ演算( λ-calculus)。一听到数学理论,大概许多人就感觉头都大了。这简直是造成函数式编程的学习曲线较陡的一个缘故原由。犹如数学中的函数一样,函数式编程范式中的函数有独特的特性,也就是通常说的无状态或引用透明性(referential transparency)。一个函数的输出由且仅由其输入决定,同样的输入永久会产生同样的输出。这使得函数式编程在处置惩罚许多与状态相干的题目时,有着自然的上风。函数式编程的代码通常更加简便,但是不肯定易懂。函数式编程的办理方案中透暴露优雅的美。
    函数式编程所涵盖的内容非常广泛,从其背后的数学理论,到此中包罗的根本概念,再到诸如 Haskell 如许的函数式编程语言,以及主流编程语言中对函数式编程方式的支持,相干的专有第三方库等。通过本系列的学习,你可以相识到许多函数式编程相干的概念。你会发现许多概念都可以在一样平常的开辟中找到相应的映射。好比做前端的开辟职员肯定听说过高阶组件(high-order component),它就与函数式编程中的高阶函数有着异曲同工之妙。盛行的前端状态管理方案 Redux 的焦点是 reduce 函数。库 reselect 则是影象化( memoization)的精妙应用。许多 Java 开辟职员已经切实的领会到了 Java 8 中的 Lambda 表达式怎样让对流(Stream)的操纵变得简便又天然。
    比年来,随着多核平台和并发盘算的发展,函数式编程的无状态特性,在处置惩罚这些题目时有着其他编程范式不可相比的自然上风。不管是前端照旧后端开辟职员,学习一些函数式编程的头脑和概念,对于手头的开辟工作和以后的职业发展,都是大有裨益的。本系列固然偏重的是 Java 平台上的函数式编程,但是对于其他配景的开辟职员同样有鉴戒意义。
    下面先容函数的根本概念。
    函数
    我们先从数学中的函数开始谈起。数学中的函数是输入元素的聚集到大概的输出元素的聚集之间的映射关系,而且每个输入元素只能映射到一个输出元素。好比典范的函数 f(x)=x*x 把全部实数的聚集映射到其平方值的聚集,如 f(2)=4 和 f(-2)=4。函数答应差别的输入元素映射到同一个输出元素,但是每个输入元素只能映射到一个输出元素。好比上述函数 f(x)=x*x 中,2 和-2 都映射到同一个输出元素 4。这也限定了每个输入元素所对应的输出元素是固定的。每个输入元素都必须被映射到某个输出元素,也就是说函数可以应用到输入元素聚集中的每个元素。
    用专业的术语来说,输入元素称为函数的参数(argument)。输出元素称为函数的值(value)。输入元素的聚集称为函数的界说域(domain)。输出元素和其他附加元素的聚集称为函数的到达域(codomain)。存在映射关系的输入和输出元素对的聚集,称为函数的图形(graph)。输出元素的聚集称为像(image)。这里必要留意像和到达域的区别。到达域还大概包罗除了像中元素之外的其他元素,也就是没有输入元素与之对应的元素。
    图 1 表现了一个函数对应的映射关系(图片泉源于维基百科上的 Function 条目)。输入聚集 X 中的每个元素都映射到了输出聚集 Y 中某个元素,即 f(1)=D、f(2)=C 和 f(3)=C。X 中的元素 2 和 3 都映射到了 Y 中的 C,这是正当的。Y 中的元素 B 和 A 没有被映射到,这也是正当的。该函数的界说域是 X,到达域是 Y,图形是 (1, D)、(2, C) 和 (3, C) 的聚集,像是 C 和 D 的聚集。
    图 1. 函数的映射关系
    我们通常可以把函数当作是一个黑盒子,对其内部的实现一无所知。只必要清晰其映射关系,就可以精确的利用它。函数的图形是形貌函数的一种方式,也就是列出来函数对应的映射中全部大概的元素对。这种形貌方式用到了聚集相干的理论,对于图 1 中如许的简朴函数比力轻易举行形貌。对于包罗输入变量的函数,如 f(x)=x+1,必要用到更加复杂的聚集逻辑。由于输入元素 x 可以是任何数,界说域是一个无穷聚集,对应的输出元素聚集也是无穷的。要形貌如许的函数,用我们下面先容的 λ 演算会更加直观。
    λ 演算
    λ 演算是数理逻辑中的一个情势体系,在函数抽象和应用的底子上,利用变量绑定和更换来表达盘算。讨论 λ 演算离不开情势化的表达。在本文中,我们只管会合在与编程相干的根本概念上,而不拘泥于数学上的情势化表现。λ 演算现实上是对前面提到的函数概念的简化,方便以体系的方式来研究函数。λ 演算的函数有两个紧张特性:
    λ 演算中的函数都是匿名的,没有显式的名称。好比函数 sum(x, y) = x + y 可以写成 (x, y)|-> x + y。由于函数自己仅由其映射关系来确定,函数名称现实上并没故意义。因此利用匿名函数是公道的。
    λ演算中的函数都只有一个输入。有多个输入的函数可以转换成多个只包罗一个输入的函数的嵌套调用。这个过程就是通常所说的柯里化(currying)。如 (x, y)|-> x + y 可以转换成 x |-> (y |-> x + y)。右边的函数的返回值是别的一个函数。这一限定简化了λ演算的界说。
    对函数简化之后,就可以开始界说 λ 演算。λ 演算是基于 λ 项(λ-term)的语言。λ 项是 λ 演算的根本单位。λ 演算在 λ 项上界说了各种转换规则。
    λ项
    λ 项由下面 3 个规则来界说:
    一个变量 x 自己就是一个 λ 项。
    假如 M 是 λ 项,x 是一个变量,那么 (λx.M) 也是一个 λ 项。如许的 λ 项称为 λ 抽象(abstraction)。x 和 M 中心的点(.)用来分隔函数参数和内容。
    假如 M 和 N 都是 λ 项,那么 (MN) 也是一个 λ 项。如许的λ项称为应用(application)。
    全部的正当 λ 项,都只能通过重复应用上面的 3 个规则得来。必要留意的是,λ 项最外围的括号是可以省略的,也就是可以直接写为 λx.M 和 MN。当多个 λ 项毗连在一起时,必要用括号来举行分隔,以确定 λ 项的剖析次序。默认的次序是左向关联的。以是 MNO 相称于 ((MN)O)。在不出现歧义的环境下,可以省略括号。
    重复应用上述 3 个规则就可以得到全部的λ项。把变量作为λ项是重复应用规则的出发点。λ 项 λx.M 界说的是匿名函数,把输入变量 x 的值更换到表达式 M 中。好比,λx.x+1 就是函数 f(x)=x+1 的 λ 抽象,此中 x 是变量,M 是 x+1。λ 项 MN 表现的是把表达式 N 应用到函数 M 上,也就是调用函数。N 可以是雷同 x 如许的简朴变量,也可以是 λ 抽象表现的项。当利用λ抽象时,就是我们通常所说的高阶函数的概念。
    绑定变量和自由变量
    在 λ 抽象中,假如变量 x 出如今表达式中,那么该变量被绑定。表达式中绑定变量之外的其他变量称为自由变量。我们可以用函数的方式来分别界说绑定变量(bound variable,BV)和自由变量(free variable,FV)。
    对绑定变量来说:
    对变量 x 来说,BV(x) = ∅。也就是说,一个单独的变量是自由的。
    对 λ 项 M 和变量 x 来说,BV(λx.M) = BV(M) ∪ { x }。也就是说,λ 抽象在 M 中已有的绑定变量的底子上,额外绑定了变量 x。
    对 λ 项 M 和λ项 N 来说,BV(MN) = BV(M) ∪ BV(N)。也就是说,λ 项的应用效果中的绑定变量的聚集是各自 λ 项的绑定变量聚集的并集。
    对自由变量来说,相应的界说和绑定变量是相反的:
    对变量 x 来说,FV(x) = { x }。
    对 λ M 和变量 x 来说,FV(λx.M) = FV(M) − { x }。
    对 λ 项 M 和 λ 项 N 来说,FV(MN) = FV(M) ∪ FV(N)。
    在 λ 项 λx.x+1 中,x 是绑定变量,没有自由变量。在 λ 项 λx.x+y 中,x 是绑定变量,y 是自由变量。
    在λ抽象中,绑定变量的名称在某些环境下是无关紧急的。如 λx.x+1 和 λy.y+1 现实上表现的是同样的函数,都是把输入值加 1。变量名称 x 或 y,并不影响函数的语义。雷同 λx.x+1 和 λy.y+1 如许的 λ 项在λ演算中被以为是相称的,称为 α 等价(alpha equivalence)。
    约简
    在 λ 项上可以举行差别的约简(reduction)操纵,重要有如下 3 种。
    α 变更
    α 变更(α-conversion)的目标是改变绑定变量的名称,制止名称辩论。好比,我们可以通过 α 变更把 λx.x+1 转换成 λy.y+1。假如两个λ项可以通过α变更来举行转换,则这两个 λ 项是 α 等价的。这也是我们上一节中提到的 α 等价的情势化界说。
    对 λ 抽象举行 α 变更时,只能更换那些绑定到当前 λ 抽象上的变量。如 λ 抽象 λx.λx.x 可以 α 变更为 λx.λy.y 或 λy.λx.x,但是不能变更为 λy.λx.y,由于两者的语义是差别的。λx.x 表现的是恒等函数。λx.λx.x 和 λy.λx.x 都是表现返回恒等函数的 λ 抽象,因此它们是 α 等价的。而 λx.y 表现的不再是恒等函数,因此 λy.λx.y 与 λx.λy.y 和 λy.λx.x 都不是 α 等价的。
    β 约简
    β 约简(β-reduction)与函数应用相干。在讨论 β 约简之前,必要先先容更换的概念。对于 λ 项 M 来说,M[x := N] 表现把 λ 项 M 中变量 x 的自由出现更换成 N。详细的更换规则如下所示。A、B 和 M 是 λ 项,而 x 和 y 是变量。A ≡ B 表现两个 λ 项是相称的。
    x[x := M] ≡ M:直接更换一个变量 x 的效果是用来举行更换的 λ 项 M。
    y[x := M] ≡ y(x ≠ y):y 是与 x 差别的变量,因此更换 x 并不会影响 y,更换效果仍旧为 y。
    (AB)[x := M] ≡ (A[x := M]B[x := M]):A 和 B 都是 λ 项,(AB) 是 λ 项的应用。对 λ 项的应用举行更换,相称于更换之后再举行应用。
    (λx.A)[x := M] ≡ λx.A:这条规则针对 λ 抽象。假如 x 是 λ 抽象的绑定变量,那么不必要对 x 举行更换,得到的效果与之前的 λ 抽象雷同。这是由于更换只是针对 M 中 x 的自由出现,假如 x 在 M 中是不自由的,那么更换就不必要举行。
    (λy.A)[x := M] ≡ λy.A[x := M](x ≠ y 而且 y ∉ FV(M)):这条规则也是针对λ抽象。λ 项 A 的绑定变量是 y,差别于要更换的 x,因此可以在 A 中举行更换动作。
    在举行更换之前,大概必要先利用 α 变更来改变绑定变量的名称。好比,在举行更换 (λx.y)[y := x] 时,不能直接把出现的 y 更换成 x。如许就改变了之前的 λ 抽象的语义。精确的做法是先举行 α 变更,把 λx.y 更换成 λz.y,再举行更换,得到的效果是 λz.x。
    更换的根本原则是要求在更换完成之后,原来的自由变量仍旧是自由的。假如更换变量大概导致一个变量从自由酿成绑定,必要起首举行 α 变更。在之前的例子中,λx.y 中的 x 是自由变量,而直接更换的效果 λx.x 把 x 酿成了绑定变量,因此 α 变更是必须的。在精确的更换效果 λz.x 中,z 仍旧是自由的。
    β 约简用更换来表现函数应用。对 ((λV.E) E′) 举行 β 约简的效果就是 E[V := E′]。如 ((λx.x+1)y) 举行 β 约简的效果是 (x+1)[x := y],也就是 y+1。
    η 变更
    η 变更(η-conversion)形貌函数的外延性(extensionality)。外延性指的是假如两个函数当且仅当对全部参数的效果雷同时,才被以为是相称的。好比一个函数 F,当参数为 x 时,它的返回值是 Fx。那么思量声明为 λy.Fy 的函数 G。函数 G 对于输入参数 x,同样返回效果 Fx。F 和 G 大概由差别的 λ 项构成,但是只要 Fx=Gx 对全部的 x 都建立,那么 F 和 G 是相称的。
    以 F=λx.x 和 G=λx.(λy.y)x 来说,F 是恒等函数,而 G 则是在输入参数 x 上应用恒等函数。F 和 G 固然由差别的 λ 项构成,但是它们的举动是一样,本质上都是恒等函数。我们称之为 F 和 G 是 η 等价的,F 是 G 的 η 约简,而 G 是 F 的 η 扩展。F 和 G 互为对方的 η 变更。
    纯函数、副作用和引用透明性
    相识函数式编程的人大概听说过纯函数和副作用等名称。这两个概念与引用透明性精密相干。纯函数必要具备两个特性:
    对于雷同的输入参数,总是返回雷同的值。
    求值过程中不产生副作用,也就是不会对运行情况产生影响。
    对于第一个特性,假如是从数学概念上抽象出来的函数,则很轻易明白。好比 f(x)=x+1 和 g(x)=x*x 如许的函数,都是典范的纯函数。假如思量到一样平常编程语言中出现的方法,则函数中不能利用静态局部变量、非局部变量,可变对象的引用或 I/O 流。这是由于这些变量的值大概在差别的函数实行中发生变革,导致产生不一样的输出。第二个特性,要求函数体中不能对静态局部变量、非局部变量,可变对象的引用或 I/O 流举行修改。这就包管了函数的实行过程中不会对外部情况造成影响。纯函数的这两个特性缺一不可。下面通过几个 Java 方法来详细阐明纯函数。
    在清单 1 中,方法 f1 是纯函数;方法 f2 不是纯函数,由于引用了外部变量 y;方法 f3 不是纯函数,由于利用了调用了产生副作用的 Counter 对象的 inc 方法;方法 f4 不是纯函数,由于调用 writeFile 方法会写入文件,从而对外部情况造成影响。
    清单 1. 纯函数和非纯函数示例
    int f1(int x) {
    return x + 1;
    }
    int f2(int x) {
    return x + y;
    }
    int f3(Counter c) {
    c.inc();
    return 0;
    }
    int f4(int x) {
    writeFile();
    return 1;
    }
    假如一个表达式是纯的,那么它在代码中的全部出现,都可以用它的值来取代。对于一个函数调用来说,这就意味着,对于同一个函数的输入参数雷同的调用,都可以用其值来取代。这就是函数的引用透明性。引用透明性的紧张性在于使得编译器可以用各种步伐来对代码举行主动优化。
    函数式编程与并发编程
    随着盘算机硬件多核的遍及,为了尽大概地使用硬件平台的本领,并发编程显得尤为紧张。与传统的下令式编程范式相比,函数式编程范式由于其自然的无状态特性,在并发编程中有着独特的上风。以 Java 平台来说,信赖许多开辟职员都对 Java 的多线程和并发编程有所相识。大概最直观的感受是,Java 平台的多线程和并发编程并不轻易把握。这重要是由于此中所涉及的概念太多,从 Java 内存模子,到底层原语 synchronized 和 wait/notify,再到 java.util.concurrent 包中的高级同步对象。由于并发编程的复杂性,纵然是履历丰富的开辟职员,也很难包管多线程代码不出现错误。许多错误只在运行时的特定环境下出现,很难排错和修复。在学习怎样更好的举行并发编程的同时,我们可以从别的一个角度来对待这个题目。多线程编程的题目根源在于对共享变量的并发访问。假如如许的访问并不必要存在,那么天然就不存在多线程相干的题目。在函数式编程范式中,函数中并不存在可变的状态,也就不必要对它们的访问举行控制。这就从根本上制止了多线程的题目。
    总结
    作为 Java 函数式编程系列的第一篇文章,本文对函数式编程做了扼要的概述。由于函数式编程与数学中的函数密不可分,本文起首先容了函数的根本概念。接着对作为函数式编程理论底子的λ演算举行了具体的先容,包罗λ项、自由变量和绑定变量、α变更、β约简和η变更等紧张概念。末了先容了编程中大概会碰到的纯函数、副作用和引用透明性等概念。本系列的下一篇文章将对函数式编程中的紧张概念举行先容,包罗高阶函数、闭包、递归、影象化和柯里化等。
    参考资源
    参考维基百科中关于 Functional Programming 的先容。
    参考维基百科中关于 λ 演算的内容。
    检察斯坦福大学哲学百科中关于 λ 演算的条目。
    您需要登录后才可以回帖 登录 | 快速注册

    本版积分规则

    社区精彩导读

    Powered by Discuz! X3.4 © 2006-2020 Comsenz Inc

    本站信息来自网络,版权争议与本站无关。一切关于该资源商业行为与[小城社区]无关。 如有侵犯您版权的,请邮件与我们联系处理(邮箱:10000@546800.com),本站将立即改正。
    快速回复 返回顶部 返回列表