函数式编程

函数式编程。

References

简明Lambda算子介绍

初探函数式编程【JavaScript篇】

函数式编程初探

什么是函数式编程思维?

斯坦福 编程范式 (CS107, Programming Paradigms, Cain Jerry),课程资源见Here

函数式编程 / 算法 / Python CS61A Spring 2018

函数式编程简介

函数式编程以函数为核心,万事万物皆归约为某一个对应的函数。

编程范式

函数式编程是一种“编程范式”(programming paradigm),也就是如何编写程序的方法论。

常见的编程范式有命令式编程(Imperative programming)声明式编程等。

比如,面向对象编程(OOP)是一种命令式编程。

命令式编程是面向计算机硬件的抽象,有变量(对应着存储单元),赋值语句(获取,存储指令),表达式(内存引用和算术运算)和控制语句(跳转指令),一句话,命令式程序就是一个冯诺依曼机指令序列

声明式编程通常被定义为除命令式以外的编程范式。声明式编程不用告诉电脑问题领域,从而避免随之而来的副作用。而命令式编程则需要用算法来明确的指出每一步该怎么做。

函数式编程作为一种声明式编程,是面向数学的抽象,将计算描述为一种表达式求值,一句话,函数式程序就是一个表达式。函数式编程更加强调程序执行的结果而非执行的过程,倡导利用若干简单的执行单元让计算结果不断渐进,逐层推导复杂的运算,而不是设计一个复杂的执行过程。

纯函数

纯函数:若一个函数的输出由且仅由其给定的输入决定,称其为纯函数。

如果一个函数内部的计算依赖全局变量,则它不是纯函数。

如果一个函数以引用的方式传递数据结构,并且其中对DS发生了修改,则它不是纯函数。

如果一个函数在过程中进行了额外的IO操作,则它不是纯函数。

函数式编程希望函数设计应该越纯越好。

副作用(side effect):函数的调用过程中,产生的没有体现为函数的返回值的附加效果。

一个纯函数是一个没有副作用的函数。

高阶函数

持久化数据结构

函数式编程中为了实现变量的immutable,并且降低各种操作的成本,引入了持久化数据结构。

λ演算系统

Lambda Calculus是美国逻辑学家Alonzo Church在1930年代发明的,并于1941年在论文《The Calculi of Lambda Conversion》中理论化。

Alonzo Church本意是创建形式化的数理逻辑系统,并未曾想到去创建一种编程语言。

事实上,直到计算机编程产生后,这一理论与编程之间的关系才被发现。

定义

λ演算(Lambda Calculus):λ演算是一套λ表达式变换和形式化的规则。

λ演算是图灵完全的,也就是说,这是一个可以用于模拟任何图灵机的通用模型)。

λ表达式:t是一个λ表达式,仅当如下条件之一成立时:

  • (一)变量:$t=x,\;\;\; x ∈ Var$
    • 表示参数或数学/逻辑值的字符或字符串
  • (二)抽象化:$t=λx.M,\;\;\; x ∈ Var\;且\;M是λ表达式$
    • 函数定义(M是一个λ表达式项)。变量x在表达式中已被绑定。
  • (三)应用 :$t=(M\;N),\;\;\; M和N均为λ表达式$
    • 将函数应用于参数。 M 和 N 是 lambda 项。

$\lambda$算子λ算子包含三种不同类型的λ表达式:

  • variables - 变量(用于引用λ表达式)
  • lambda abstraction - λ抽象(用于定义函数)
  • applications - 应用(用于调用函数)

其中application中的()并非必须的。使用()主要是因为后面即将阐述的application的结合律。

注意到λ表达式的(二)抽象化中,只规定了单个参数的情况。为了推广到多参数,我们引入了柯里化方法。

柯里化

对于“多参数函数”,Curry(柯里化)的处理技巧如下:

N参函数可以表述为返回N-1参函数的函数递归调用,即函数可以像“数据一样”被返回。

比如,对于1个二元函数:$y^x$,如果固定了$y=2$,则得到1个单元函数$2^x$。

这样的处理,使得每一个函数都只需要处理一个参数(从而利用单参函数实现多参函数功能)。

函数柯里化的对偶是Uncurrying,一种使用匿名单参数函数来实现多参数函数的方法。例如:

1
2
3
4
5
var foo = function(a) {
return function(b) {
return a * a + b * b;
}
}

这样调用上述函数:(foo(3))(4),或直接foo(3)(4)

实例

三参函数调用
1
2
3
4
var f1 = function(p1, p2, p3) { 
return p1 + p2 + p3;
};
f1(1, 2, 3); //output: 6
三次单参函数调用
1
2
3
4
5
6
7
8
var f3 = function(p1) {
return function(p2) {
return function(p3) {
return p1 + p2 + p3;
}
}
};
f3(1)(2)(3); // output: 6

λ表达式注记

参考康托尔、哥德尔、图灵——永恒的金色对角线

按照定义,λ表达式有三个基本语法:

  • <expr> ::= <identifier>
  • <expr> ::= lambda <identifier-list>. <expr>
  • <expr> ::= (<expr> <expr>)

前两条语法用于生成lambda表达式(lambda函数),如:

如:lambda x y. x + y,定义了一个实现x + y功能的二元匿名函数

最后一条规则就是用来调用一个lambda函数的:

如:((lambda x y. x + y) 2 3),传递参数23给匿名函数(lambda x y. x + y)

为了简洁,不妨记λ函数ADD = lambda x y. x + y。

从而得到一般形式的调用语句:(ADD 2 3)ADD(2, 3)

α变换(代数)

α变换:α变换共有三个规则,

  • $λx.M \longrightarrow λx’.M\;\;\;\;\;[x \longrightarrow x’] $
  • $λx.M \longleftarrow λx’.M\;\;\;\;\; [x \longleftarrow x’] $
  • $λx.M \longleftrightarrow λx’.M\;\;\;\;[x \longleftrightarrow x’] $

其中, x在M中不能是自由变量。且α变换前后不会改变表达式的值。

α变换的意义在于,Lambda表达式内部的绑定变量(非自由变量)的名称是可置换的。以数学中的多项式为例,可以理解多项式x+2y+2是等价意义的。 即,表达式中的所有绑定变量都是抽象的符号

例如,“lambda x y. x + y”转换为“lambda a b. a + b”。换句话说,函数的参数起什么名字没有关系,可以随意替换,只要函数体里面对参数的使用的地方也同时注意相应替换掉就是了。

β变换(参数代换)

β变换包含两个过程变换:β-Reduction和β-Abstraction。

  • β-Reduction(实化):指将λ表达式内部的绑定变量用函数的(实)参数代换的过程。
  • β-Abstraction(抽象化):指逆过程,即将经过β-Reduction后的表达式还原为原Lambda表达式的过程。

例如,“(lambda x y. x + y) 2 3”转换为“2 + 3”。当把一个抽象的lambda函数用到具体的参数身上时,只需用实际的参数来替换掉其函数体中的相应变量即可。

η变换(简化)

交换规则

Y协变器

0%