Javascript函数式编程系列(1)-lambda演算与函数

marvin

marvin

Javascript函数式编程系列(1)-lambda演算与函数

编程语言有很多种, 每一种都有特定的使用领域, 例如html, sql分别用于网页和数据库查询, 其他的通用类型的语言都会遇到使用自定义函数的情况, 这也是编写程序的主要工作, 那么函数式编程和函数有什么区别呢?

命令式编程中函数的作用

  • 代码复用 维护一个函数比在代码里找出和修改它的多个副本，要容易得多
  • 抽象 将程序的一段代码提取成一个函数, 用对该函数的调用来取代这段代码, 程序的代码就被精简了, 与此同时程序的内容变得更抽象了, 这里的函数就是对其中代码的抽象，就像函数的名称对其所做事的概括, 当处理的问题越来越复杂时, 人们需要在越来越抽象的层次上思考. 在程序中发现可复用逻辑，减少重复代码, 就提升了抽象级别.
  • 封装 抽象是针对函数的调用者而言的, 封装则是针对函数内的代码, 一个函数代表对其参数的一种动作, 封装使得这种动作的细节不为外界所知, 不受外界干扰, 可以随时调整.

lambda 演算

在命令式编程中函数起到的作用是极其关键的, 不过在这样的编程语言中, 函数并不是代码的全部, 它只是程序的组件, 程序在细节上还运用了许多其他工具, 如变量声明和赋值, if 等流程控制语句. 而在函数式编程的理论基础 lambda 演算中, 一切都是函数, 整个程序就是由函数的定义和调用组成的. 数字是函数, 除了参数以外没有变量, 控制流语句也变身为函数.

lambda 演算是 20 世纪30年代美国数学家邱奇提出的一套数理逻辑的形式体系. 20 世纪初期, 作为数学基础的数理逻辑成为大批数学家 最感兴趣 的领域之一, 希尔伯特 、 罗素 、哥德尔、图 灵 、邱奇等人都从不 同方面做出了重 要的贡献. 图灵和邱奇关心的问 题可以概括为对数学里可计算的函数建立一套形式体系, 从而可以对有关计算的基础性数学问题进行表述和研究, 图灵建立起来的体系是图灵机, 邱奇创建的则是 lambda 演算, 两套理论以不同方式描述了可计算性, 根据邱奇一图灵论题 (Church-Turing thesis), 图灵机和 lambda 演算是等价的. 而后这些关于计算的数学理论也成为了计算机科学的基础, 图灵机可以看作命令式编程的前身, lambda 演算则是函数式编程的理论基础.

定义

lambda 演算的对象是 lambda 表达式, 它由以下成分组成.

  • 变量 v1, v2, ..., vn
  • 抽象符号 λ 和 点号 .
  • 括号 ()

lambda 表达式的集合 Λ, 可以递归地定义

  • 如果 x 是一个变量, 那么 x 属于集合 Λ
  • 如果 x 是一个变量并且 M 属于集合 Λ, 那么 (λx.M) 属于集合 Λ
  • 如果 M 和 N 属于集合 Λ, 那么 (MN) 属于集合 Λ

前两条规则称为抽象, 第三条规则称为应用, 在运用抽象规则构建的 lambda 表达式中, λ 后面跟随的变量 x 称为绑定的变量, M 中出现的其他变量则称作自由的, 例如, (λy.(yx)) 中的 y 是绑定的, x 是自由的. 可以看出抽象和应用分别对应函数的定义和调用, 绑定变量则相当于函数的参数.

记法

lambda 表达式可以根据以下惯例在含义不变的前提下, 简化形式

  • 最外层的括号可省略: (MN) 可写作 MN
  • 表达式的应用运算是左关联的 (left associative), 所以 MNP 相当于 (MN)P
  • 应用比抽象的优先级高, 所以 λx.MN 的含义是 λx.(MN) 而不是 (λx.M)N, 其中的括号也可省略, 对此规则的另一种理解是, 确定抽象的范围时, 边界尽可能向右延伸
  • 连续抽象可以缩写: 例如 λx.λy.λz.N 可以简写为 λxyz.N

化约

lambda 表达式可以进行3种化约(reduction), 其中最常用和重要的是下面两种:

α变换(α－conversion)

更改表达式中的绑定变量, 例如 λx.x 可变换为 λy.y, 这就相当于 函数的参数更名

β化约(β－reduction)

将一个抽象表达式主体中的绑定变量替换成某个 lambda 表达式, 例如将 λx.y x 中的 x 替换成 M, 就得到 yM. 这就相当于函数应用到实际参数上. β化约所依赖的变量替换, 用符号写作 E[V := R], 定义为将表达式 E 中所有自由的变量 V 替换成表达式 R. 具体替换的过程, 可以用以下规则递归地进行(其中 x 和 y 是变量, M 和 N 是任意 lambda 表达式)

  • x[x:=N] === N (将单个变量替换成表达式)
  • y[x:=N] === y, 如果 x ≠ y (要替换的变量与当前变量不同时, 当前变量保持不变)
  • (Ml M2)[x := N] === (Ml[x := N]) (M2[x:=N]) 对应用表达式进行替换, 结果是对表达式的两个组成项分别进行替换
  • ( λ x.M) [x := N] === λ x.M 对抽象表达式进行替换, 假如要替换的变量与绑定变量 相同, 表达式不变.
  • (λy.M)[x:=N] === λy.(M[x:=N]), 如果 x ≠ y 并且 y 在 N 中不是自由变量(对抽象表达式进行替换, 假如要替换的变量与绑定变量不同, 并且绑定变量在要被替换的表达式中不是自由变量, 对抽象表达式的主体进行变量替换)

这5条规则对应于 lambda 表达式定义的3条规则, 涵盖了所有可能的情况, 根据lambda表达式的定义规则, 可以从简单到复杂递归地构造出所有表达式, 根据替换规则, 可以从复杂到简单递归地对所有表达式进行变量替换.

这些规则看似繁琐, 实际上只是在各种情况下贯彻替换的定义, 关键是不同变量不能混淆, 这里的不同变量既包括名称不同, 也包括名称相同但含义不同. 这又分两种情况, 首先是同名的自由变量和绑定变量含义不同, 如 x 和 λx.x 两者中的 x. 其次是不同抽象表达式中的同名绑定变量含义不同, 如 λx.(xλx.x) 中出现的弟2个和弟4个x分别是外面和里面两个抽象表达式的绑定变量, 含义不同.

根据第5条规则进行替换时, 假如抽象表达式中的绑定变量在要被替换的表达式中是自由变量, 就必须先对该绑定变量进行 α 变换. 例如, (λx.y)[y:=x]的结果不是(λx.x),因为 y:=x中的 x 是自由变量, 替换后却变成了绑定变量, λx.y 和 y:=x 中的 x 原本是不相干的, 结果却成为同一个变量. 正确的步骤是先将 λx.y 表达式 α 转换成 λz.y, 再进行变量替换, 得到 λzx.

假如两个表达式通过化约能变成同一个表达式, 就被称为是等价的, 具体而言, 若两个表达式能通过 α 变成同一个表达式, 就被称为是 α 等价的, 若两个表达式能通过β化约变成同一个表达式, 就被称为是 β 等价的, 这些等价关系都用 === 符号来表示

算数

对各种值和运算可以构造出的 lambda 表达式都不止一种, 下面给出一种.

最基本的算数运算是自然数的加法. 1,2,3... 这些我们小时候用手指就能学会的数字, 普通人都当做最基本的数学概念, 但数学家们不满足于此, 要将数学纳入严密的公理系统. 邱奇以 lambda 表达式作为计算的基础, 首先就要用 lambda 表达式来表示数字, 他给出的定义如下:

0 := λf. λx.x

1 := λf. λx.f x

2 := λf. λx.f (f x)

3 := λf. λx.f (f (f x))

以这种方式表示的数字称为邱奇数, 从函数的角度来理解, 这些数字接收一个函数 f 作为参数, 返回一个以 x 为参数的函数, 这个函数通过对 x 重复应用 f 计算出返回值, 重复应用的次数就是它所代表的数字. 数字1对应的函数的返回值是 fx, 数字 2 对应的是 f ( f x), 数字 3 对应的是 f ( f (f x)), 注意这里括号的应用遵循 lambda 表达式的规则, 而不是数学上的习惯. 数字0是一个特殊情况, 它的返回值与 f 无关, 相当于应用了 f 函数0次. 数字本身用函数来定义, 这对初学者来说, 是新鲜而神奇的. 实际上, 这并没有脱离我们原本对自然数的观念. 0, 1, 2, 3...当我们最初学习这些数字时, 接触的两条基本的观念是: 它们有一个起点, 任何数字都有一个后续. 这里 0 是数字的起点, 1 是 0 的后续, 2 是 1 的后续, 3 是 2 的后续.. 而在邱奇数中, λf. λx.x 是起点, 每一个数字(函数)的后续就是对前一个函数的返回值再次应用一次 f. 这个后续函数也能表示为 lambda 表达式:

succeed := λn. λf. λx.f ( n f x)

其中的 n 就是邱奇数, 后续函数可以被视为定义了数字的加一运算, 也就是返回值等于参数加一. 两个自然数 m 和 n 相加, 可以定义为 n 加了 m 次 1, 所以有加法的 lambda 表达式为:

add := λm. λn.m succeed n

可以验证:

add 2 3

=== (λm.λn.m succeed n) 2 3

=== 2 succeed 3

=== (λf.λx.f (f x)) succeed 3

=== succeed (succeed 3)

=== succeed (λf.λx.f (f (f (f x))))

=== λf.λx.f (f (f (f (f x))))

正是邱奇数 5 的表达式, 类似的, 还能给出减法, 乘法等其他算数运算的 lambda 表达式.

逻辑运算

我们再来看程序中至关重要的逻辑运算如何用 lambda 表达式来表示, 与算数运算一样, 第一步是给出布尔值的表达式.

TRUE := λx.λy.x

FALSE := λx.λy.y

它们被称为邱奇布尔值, 注意 FALSE 的定义和邱奇数 0 是等价的. 接着我们就可以定义常用的逻辑操作符:

AND := λp.λq.p q p

OR := λp.λq.p p q

NOT := λp.p FALSE TRUE

可以验证这些表达式化约的结果与我们熟悉的逻辑运算是一致的.

AND TRUE FALSE

=== (λp.λq.p q p) TRUE FALSE

=== TRUE FALSE TRUE

=== (λx.λy.x) FALSE TRUE

=== FALSE

我们还可以表达编程语言中常用的 if 语句:

IFELSE := λp.λa.λb.p a b

例如, 当条件 p 为 TRUE 时:

IFELSE TRUE a b

=== (λp.λa.λb.p a b) TRUE a b

=== TRUE a b

=== (λx.λy.x) a b

=== a

返回的结果是 a, 当条件 p 为 FALSE 时, 返回的结果是 b.

函数式编程的特点

从 lambda 的概念出发, 我们就能建立起精确描述所有计算的一种模型, 函数式编程的很多特点我们都可以在 lambda 演算中看到. lambda 演算的应用对象是 lambda 表达式, 得到的结果还是 lambda 表达式. 这就相当于一个函数的参数是函数, 返回值也是函数. lambda 表达式只有一个绑定变量, 相当于一元函数, λxyz.N 可以看做 λx.λy.λz.N 的简化形式, 这里对应了函数式编程的部分应用和复合技术. lambda 演算是没有副作用的, lambda 表达式作为数据都是不可变的, 这些都是函数式编程的重要特点. lambda 演算可以通过递归来进行重复的计算, 最早的编程语言之一 scheme 将 lambda 演算作为语言的核心, 其对列表的处理也成为函数式编程的一个特点.

javascript 中的函数

lambda 演算可以将计算描述为 lambda 表达式的定义和化约. 在以其为理论基础的函数式编程中, 代码由函数的定义和调用组成, 执行程序的过程就是逐级调用函数, 直至计算出最终的返回值. 一门编程语言, 能否被用来进行函数式编程, 关键是看其中的函数能不能充当 lambda 表达式的角色, haskell 这样的纯函数式编程语言中, 函数天生就是 lambda 表达式. 在类似 java 这种命令式编程语言中, 函数原本不具备 lambda 表达式的行为, 后来引入的 lambda 表达式功能则模拟了它. javascript 是带着几种语言的基因出现的, 支持多重编程范式是它的特点. 采用命令式编程范式时, 函数是静态创建的功能单元. 采用对象式编程时, 函数以方法的形式从属于对象. 采用事件驱动编程时, 函数的主要作用是传递预定义事件的处理逻辑. 这些时候 javascript 中的函数所扮演的角色和 c , java 这些命令式语言中的函数没有差别, 它所具备的 lambda 表达式的特征都被忽视了. 可以说函数式编程的风潮使得 javascript 的函数作为 lambda 表达式被重新发现了运用了.

javascript 中的函数可以做到任何 lambda 表达式能做的事, 这是它能被用来进行函数式编程的先天基础, 也是当诸多语言赶时髦引入 lambda 表达式时, javascript 加入类似语法, 却只称为箭头函数的原因. 与早已存在的函数表达式相比, 箭头函数只是更短小, 并且没有服务于对象的一系列行为. 采用箭头函数, 上面关于算数的 lambda 表达式对应的 javascript 代码如下:

const NUMBER = {
	0: f => x => x,
	1: f => x => f(x),
	2: f => x => f(f(x)),
	3: f => x => f(f(f(x))),
}

const succeed = n => f => x => f(n(f)(x));
const add = m => n => m(succeed)(n);

虽然理论上数字可以用这种函数的形式表达, 但在任何实际运算或编程语言中, 都不会这样做, 首先, 根据哥德尔第一不完备定理, 不存在能判断随意两个 lambda 表达式是否等价的算法. 而任何数字都有无穷多个可能的 lambda 表达式, 这就会导致明明两个函数返回的是同样的数字, 却因为表达式的形式不一样, 没法确定是否是同样的值. 其次, 即使能够判断, 用它们来表示数字进行计算是相当低效的. 所以上面的代码虽然定义了若干数字和后续, 加法两种运算, 却无法计算出 1 + 2 == 3

不过在逻辑运算中, 由上面的 lambda 表达式改写的 javascript 函数倒真的可以被用来编写一个有趣的程序:

const TRUE = x => y => x;
const FALSE = x => y => y;
const IFELSE = p => a => b => p(a)(b);

console.log(IFELSE(TRUE)('Hello world!')('error'));

定义函数

javascript 由多种定义函数的方式

  • 函数声明

函数声明是最基本的定义函数的方式, 它使用函数语句, 包含函数的名称, 形式参数和函数体:

function name([param, [, param[, ... param]]]) {
	statements
}

通过声明定义的函数会被提升, 在同一个作用域中任何位置声明的函数都能够被其他任何位置的代码调用.

函数的参数分为位置参数和命名参数两类, 前者在调用函数时只需传入参数的值, 函数根据其在实际参数列表中的位置将其绑定到某个形式参数. 后者在调用函数时同时传入参数的名称和值, 对应名称的形式参数获得该值. 位置参数的好处时简便, 命名参数的优点是灵活, 允许函数的调用者以任何顺序传递参数, 并且往往还能省略. javascript 只支持位置参数, 不过结合 es5 新增的解构赋值也能实现命名参数的效果：

function fullName({firstName, lastName}) {
	return `${firstName} ${lastName}`;
}

console.log(fullName({lastName: 'l', firstName: 'a'}))

es5也新增了默认参数和剩余参数的支持, 不再需要 || 操作符和 arguments 分别来模拟这些功能了

  • 函数表达式

函数表达式在语法上和函数声明很相似, 它可以出现在任何其他表达式可以出现的地方

function [name]([param[, param[, ... param]]]) {
	statements
}

表达式中的函数名称 name 是可选的, 不写名称, 就获得一个匿名函数, 这在返回函数和传递函数值的参数等情况下都很方便, 即使写上, 该名称也不会像函数声明中那样成为指向函数的标识符.

(function foo() {
	console.log('foo')
});
foo();
//=> TypeError: foo is not a function

要根据名称调用以表达式定义的函数时, 通常将该表达式赋值给一个常量, 以后该常量就指向函数, 可以被调用:

const fn = function foo() {
	console.log('foo')
};
fn();

函数表达式中的名称也不是全无用处, 它可以通过函数的 name 属性获取或在调用堆栈中查看, 帮助调试.

当函数带有名称时, 函数表达式和函数声明的语法是完全一样的, 要让它被识别为表达式, 就要将它放在表达式才能出现的语境中. 最简单的方法是将它放在用于控制表达式计算优先级的分组操作符()内, 这样计算出的函数可以即时调用. 与此相对, 函数声明作为语句, 求值结果是 undefined. 大量脚本利用函数表达式这一特点, 将所有代码置于一个顶级的匿名函数内, 即时调用, 从而确保脚本运行于独立的作用域, 不会和其他代码冲突. 这就是所谓的立即执行函数 IIFE

(function() {
	console.log('foo')
})()

本质上, 函数表达式都可以立即调用, 比如下面的几个变体, IIFE 模式只是清晰地突出了主题:

(function() {
	console.log('foo');
}())

// void 操作符对作为它操作数的表达式进行求值, 并返回 undefined
void function() {
	console.log('foo');
}()

// 逗号操作符对它地操作数从左至右进行求值, 并返回最后一个值
1, function() {
	console.log('foo');
}()
  • 箭头函数表达式

es5 引进了箭头函数表达式, 它是原有地函数表达式的精简版, 语法如下:

([param[, param]]) => {
	statements
}

([param[, param]]) => expression

前者的函数体可以包含一系列语句, 返回值需要使用 return 语句, 后者的函数体就是 一个表达式, 返回的就是该表达式的值, 与函数表达式相 比, 箭头函数表达式除了外形上更短小, 还做了以下功能和行为上的精简:

面向对象编程方面, JavaScript 为了支持面向对象编程, 给函数添加了许多相关的功能和行为, 箭头函数取消了这些行为, 更适合用于函数式编程. 箭头函数不会创建单独的 this 绑定, 箭头函数中的 this 使用的是包含该箭头函数的上下文中的 this 值. 因此箭头函数不能用作对象的构造函数, 也不适宜用来定义对象的方法. 另外箭头函数不能读取 new.target 属性, 也没有 prototype 属性, 也没有单独的 arguments 绑定

  • Function 构造函数

JavaScript 中的函数都是 Function 对象, Function 是它们的构造函数, 所以函数自然可以显式地调用 Function 来创建:

new Function([arg1[, arg2[, ...argN]]], functionBody)

Function 函数的参数都是字符串, 最后一个参数是函数体. 用字符串形式动态创建函数, 虽然能带来一定的灵活性, 但在安全性和性能上都会受到影响, 一般很少使用.

  • 定义特殊的函数
  1. 生成器函数:
function* name([param[, param[, ... param]]]) {
	arguments
}
  1. 生成器函数表达式:
function* [name]([param[, param[, ... param]]]) {
	statements
}
  1. GeneratorFunction 构造函数:
new GeneratorFunction(arg1, arg2, ... argN, functionBody), 其中 GeneratorFunction = Object.getPrototypeOf(function* () {}).constructor
  1. getter 和 setter 函数

对象的 getter 和 setter 是读取和写入某个属性时调用的函数, 分别用 get 和 set 语法定义:

get prop() { ... }
get [expression]() { ... }
set prop() { ... }
set [expression]() { ... }

这里的 prop 是属性的名称, expression 是计算出属性名称的表达式

调用函数

JavaScript 中的函数可以扮演多种角色, 也就有了与每一种角色相应的调用方式, 普通函数的调用方式最平凡, 就是在函数的名称后面用圆括号包围传递的参数. 用作构造函数时需要在函数名称前加上 new 操作符. 用作对象的方法时, 用点号或方括号的属性存取符来调用.

传递参数

对 JavaScript 中传递参数的方式, 学者们一直争论不断, 一方认为 JavaScript 对于两类数据类型采取不同的传递方式, 对于值按值传递, 对于引用按引用传递. 另一方认为 JavaScript 单纯使用按值传递的方式, 函数对于对象参数的修改之所以会影响到实际参数, 原因不是对象按引用传递, 而是对象作为引用 类型的本质决定的, 两种情况在调用函数时, 都是将变量值复制到形式参数中去, 因而都属于按值传递, 只不过通过后者的值仍能修改实际参数.

实际上, JavaScript 中所有的数据都是引用类型的, 调用函数时参数按值传递. 对于数字、字符串等不可变的数据类型, 函数中更改参数值获得的是该类型新的实例, 因而不会影响实际参数. 而对于对象这样的可变的数据类型, 在函数中修改参数值时, 变化就会反映到指向该对象的外部变量上

模块

当程序的规模变大时, 用模块来组织代码就变得很重要. 模块为代码提供了命名空间. 避免不同来源和功能的代码发生命名冲突. 模块将相关的数据和函数组织在一起, 除了对外暴露的接口, 内部成员都被封装起来, 就像函数的封装作用一样, 对其中代码的使用, 安全和维护都大有裨益.

在 es5 之前, javascript 没有内置的模块, 程序员想了很多方法来模拟和构建模块的功能. 主要有: 用即时的可调用函数表达式来防止代码污染全局作用域, 从而影响其他脚本和受其他脚本影响. 开发者社区还发明了 commonjs 和 amd 两套分别适用于服务器和浏览器的模块系统, 基于前者的 npm 已经称为世界上最大的代码库, es5 为语言加入了原生的模块支持.