作为一名有追求的程序员,对于计算机基础的理论一定要有所了解。最近几年,随着分布式、云计算等技术的发展,函数式编程语言也趋于流行。如果要学习函数式编程,一定要深入理解它背后的理论知识。从收益的角度上讲,这些基础理论知识几十年不变,是十分值得花时间进行学习的。lambda演算(Lambda Calculus)就属于这样一套理论,可以说它在函数式编程领域就如牛顿万有引力定律一样基础。接下来这篇文章我将主要介绍lambda演算的基本知识,最后我还会尝试用es6的箭头函数来演示如何利用lambda演算来实现编程语言中的基本组成要素。

lambda演算是什么?

Image result for lambda calculus.png

要了解一个事物,先了解它的历史一定是重中之重。lamda表达式最初是由一个美国普林斯顿大学的数学家Alonzo Church在1932年所发明的。他也是”计算机科学之父”——图灵的博士生导师。

我们都知道现代的计算机基本上都是基于图灵机的。在图灵机中,所有的计算过程其实都是基于状态的,这也是为什么我们平常写代码要声明并使用变量的原因:变量主要作用就是用来存储状态。而Alonzo Church所提出的lamda演算(lamda calcus)模型实际上是基于函数的。图灵机模型和Lambda演算模型虽然是两种不同的理论模型,但它们实际上是等价的,这也意味着,任何基于图灵机的计算机程序都能等价地翻译成基于lambda演算模型的程序。

lambda演算是一套研究函数定义、函数应用和递归的形式系统。它基本的组成部分就是三种表达式: 1. 函数定义 2. 标识符引用 3.函数应用。

那么到底什么是lamda表达式呢,它又是由哪些基本组成要素构成的呢?我们都知道在函数式编程语言里面,最基本的组成单位就是函数。lambda表达式从定义上来讲可以看做是一个匿名的纯函数。ES6中引入了箭头函数,它的本质实际上就是我们这里所说的lambda表达式:

1
const lambda = x => x + 1;

实际上现在大部分的编程语言都引入了lambda表达式这一特性,如Java, c#和es6等。我们通常将lambda表达式,看作是一个黑盒,只关心它的输入和输出。由于没有内部状态,用函数式编程的思想写代码就与用命令式语言写代码截然不同。作为一个纯函数,每一次运行定义好的lambda表达式的时候,结果都应该是一致的。

在纯粹的lambda演算中实际上是没有任何内置的数据结构和逻辑控制语句的,但是我们可以使用函数来建构整个编程语言的所有要素。

lambda演算中的一些基本规则,可以类比到我们比较熟悉的ES6语法:

lambda表达式 ES6 箭头函数
定义函数 λx.x x => x
柯里化 curry λx. λy.x+y x => y => x + y
应用 application (λx. λy.x+y) 5 1 (x => y => x + y) (5) (1)

如何实现

在实现具体的逻辑之前,我们需要明确的一点是:在lambda演算中,lambda表达式本身既可以是操作数也可以是函数,就好像一只鸡(lambda表达式),既可以吃虫子(另一个lambda表达式),也可以被狐狸(还有一个lambda表达式) 吃(请原谅我这糟糕的类比),它们统称为动物(lambda表达式)。归根结底就是,在这个封闭的概念世界里,只有一类事物,那就是lambda表达式(函数),我们可以利用这个最基础的概念生成其它的概念和运算逻辑。

在纯粹的函数式编程世界里,没有1,2,3这样的数字也没有+-*/这样的基本运算符,所以这些我们都需要自己手动去实现。

数字

首先作为一门计算机设计语言,数字是关键,所谓”数是万物本源“在计算机世界里简直就是真理。那么我们如何利用lamda表达式来表示数呢?在这里,我们采用函数调用次数来表示自然数,用这样的编码方式表示的自然数也叫邱奇数

有了理论的指导,我们很容易就能写出下面的代码:

1
2
3
4
const ZERO = f => x => x;
const ONE = f => x => f(x);
const TWO = f => x => f(f(x));
...

有了数字后,然后还需要再定义一个转换函数,它可以将ZEROONE这种函数式定义转成我们所熟悉的数字,方便调试。

1
2
3
const toNumber = n => n(i => i+1)(0);
console.log(toNumber(ONE));
// 1

计算

经过上面的步骤,我们就定义了最基本的数字。有了这些数字,我们应该如何去做一些简单的加减乘除运算呢?既然数字表示的是调用函数次数的多少,那么在这里对于加法运算,我们也可以将它定义成调用函数的次数的相加。例如,要表示1+2等于3这一过程,输入的函数就应该调用三次。

1
2
3
4
5
6
const add = n => m => fn => x => m(fn)(n(fn)(x));

const TWO = add(ONE)(ONE);
const THREE = add(ONE)(TWO);
toNumber(THREE);
// 3

其中n和m表示add操作的两个操作数。

接着我们再来实现乘法,回顾一下大家小时候学习乘法的过程。n * m的一个朴素定义可以表示成: n个m相加。那么在这里,我们需要实现的就是先调用n次函数,将它的结果再调用m次。表示到代码中就像这样:

1
2
3
4
5
const multiply = n => m => fn => x => m(n(fn))(x);

const result = toNumber(multiply(TWO)(THREE));
console.log(result);
// 6

至于减法和除法,实现起来相对来说比较复杂,大家如果感兴趣的话,可以参考其他的资料进行学习。

控制语句

接下来我们再进一步考虑一下如何实现条件分支语句。条件分支语句中一个很重要的元素就是布尔值,先来定义TRUE和FALSE这两个基本的布尔值类型:

1
2
const TRUE = first => second => first;
const FALSE = first => second => second;

它表示的是从两个事物中选择其中一个事物,TRUE表示选择的第一个,而FALSE与之相反,选择的是第二个。

定义好基本的布尔值类型,再实现条件分支语句就很简单了:

1
2
3
const ifElse = boolFn => first => second => boolFn(first)(second);
// ifElse(TRUE)(x)(y) ===> x
// ifElse(FALSE)(x)(y) ===> y

再增加一个转换函数:

1
2
3
4
const toBoolean = boolFn => boolFn(true)(false);

console.log(toBoolean(TRUE));
// true

大功告成,Bingo!

逻辑

利用上述定义的布尔值,推导出三大逻辑运算:与(and)、或(or)、非(not)就顺理成章了。反转逻辑最简单,只要将上面定义条件分支语句的逻辑反过来就可以了。这与布尔值的定义也是强联系,如果说TRUE表示的是选择第一个分支条件,那么not就要反转这种逻辑:

1
2
3
const not = boolFn => first => second => boolFn(second)(first);
toBoolean(not(TRUE));
// false

至于或运算符,实质上应该是个带有两个操作数的运算,所以我们需要定义个高阶函数,需要调用两次,每次接收一个操作数。根据之前的定义,我们知道TRUE会返回第一个变量,FALSE会返回第二个变量。而或运算(or)的意思是只要两个操作数中有一个TRUE,就返回TRUE。那么我们只要使变量应用的顺序和调用顺序一致,就能保证当TRUE作为第一个参数时,正好应用到TRUE函数上, 当FALSE作为第一个参数时,函数返回第二个参数的值。

1
2
3
4
const or = first => second => first(first)(second);
toBoolean(or(TRUE)(FALSE)); // true
toBoolean(or(FALSE)(FALSE)); // false
toBoolean(or(TRUE)(FALSE)) // true

与操作与或操作相似,我们要保证当两个操作数都是TRUE的时候才会返回TRUE。将上面的实现逻辑反转一下,就能得到下面的代码:

1
2
3
4
const and = first => second => first(second)(first);
toBoolean(and(FALSE)(FALSE)); // false
toBoolean(and(FALSE)(TRUE)); // false
toBoolean(and(TRUE)(TRUE)); // true

这块逻辑可能比较绕,大家可以用心体会一下。

递归(Y组合子)

M.C. Escher – Drawing Hands.jpg

我们先从一个最简单的递归定义说起,下面这个故事想必大家都有听说过:

从前有座山,山里有座庙,庙里有个老和尚和小和尚,有一天老和尚对小和尚讲故事,讲的什么故事呢?从前有座山,山里有座庙,庙里有个老和尚和小和尚…

这样一个不停的引用自身的概念,其实就是递归的简单定义。

有了递归的定义后,我们再来深入思考一下,如何用lambda表达式来实现递归的基本逻辑。

这里我举一个简单的斐波那契数列的例子(1, 2, 6, 24…),如果语言中已经支持递归,很容易可以写出这样的代码:

1
const factrial => n => n == 0 ? 1 : n * factrial(n - 1);

如果语言中不支持递归,那么在lambda表达式中,我们并不能直接利用factorial这个名字来引用其自身。

不过可以换个思路,既然不能在函数声明里面使用未定义的函数名,那么我们可以将这个函数定义以参数的形式传进去:

1
const makeFactorial = factroial => n => n == 0 ? 1 : n * factroial(n - 1);

有了一个makeFactorial后,怎么使用呢? 假设,现在已经有了一个seed函数:

1
const seed = n => n;

它其实啥都没干,不过我们可以利用seed函数生成factorial0:

1
const factorial0 = makeFactorial(seed)

很容易知道,factorial0函数展开后是这样的:

1
const factorial0 = n => n == 0 ? 1 : n * (n => n)(n - 1);

我们知道这个函数在参数n等于0的时候结果是对的,而n等于其它数值的时候结果是0,显然不正确。不过,别着急,我们可以利用factorial0进一步构造factorial1:

1
const factorial1 = makeFactorial(factorial0)

它展开后:

1
const factorial1 = n => n == 0 ? 1 : n * factorial0(n - 1);

这个函数在n等于1的时候结果等于 1 * factorial0(0), 已知n 等于 0 时候,factorial0的结果是正确的,所以factorial1在n 等于0 和 n等于1的时候也都能正常工作。

同样的原理,我们可以继续构造出factorail2, factorial3, factorial4….

所以可以归纳出通用的factorial函数定义应该是长这个样子的:

1
const factorialn = makeFactorial(makeFactorial(...)); // 无穷个makeFactorial

到这里,我们进一步思考🤔,有没有什么办法能让这个makeFactorial函数不停递归下去呢?

我们先定义一个基本循环函数:

1
const loop = x => x(x);

这样当我用这个函数调用makeFactorial的时候,就会调用makeFactorial(makeFactorial),不过这样的定义好像缺少动力。要让它不停循环下去,我们可以让它再自身调用一次:

1
const loop = (x => x(x))(x => x(x))

可以看到当你将x = x => x(x)代入到loop函数后,展开结果如下:

1
const loop = (x => x(x))(x => x(x))

是不是又回到之前的定义了?

不过这样一个函数在javascript中使用是不行的,因为在javascript中参数是计算完后再传入到函数中去的,所以我们要延迟参数的计算, 将代码改成如下:

1
const loop = (x => x(x))(y => x(x)(y))

引入参数y后,只有最终展开到最后一层的时候,才会开始计算值,这也是延迟计算的思想。

有了这个loop函数后,我们最终的factorial函数就很容易构造了:

1
const factorial = loop(makeFactorial);

我们在控制台试一下效果:

1
factorial(4) = 24

实际上上面定义的那个loop函数,它就叫做Y组合子(Y combinator)。这也是在lambda演算中非常著名的一个概念,它是在不支持递归的编程语言中实现递归的关键,也是学习lambda演算理论的一个难点。要彻底理解它可能还需要多花点时间思考。

总结

至此,我们已经实现了数据,计算,逻辑和控制语句还有最重要的递归。这几个部分其实是编程语言中最核心的组成部分。从一个基本的组成元素——函数,再通过几个法则,就可以构建成整个计算机编程语言的核心要素,这就是lambda演算的神奇之处。

当然,整个lambda演算的理论要彻底理解肯定是不那么容易的,这篇文章也只是个人学习后的一些思路梳理,难免有所错漏。大家如果在阅读过程中,发现有不对的地方,欢迎交流指正。

——–转载请注明出处–———

微信扫描二维码,关注我的公众号.jpg
最后,欢迎大家关注我的公众号,一起学习交流。

参考资料

http://cgnail.github.io/academic/lambda-1/

http://mindhacks.cn/2006/10/15/cantor-godel-turing-an-eternal-golden-diagonal/

https://mvanier.livejournal.com/2897.html

https://zh.wikipedia.org/wiki/%E9%82%B1%E5%A5%87%E6%95%B0?wprov=sfla1

https://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9%E7%BB%84%E5%90%88%E5%AD%90?wprov=sfla1

https://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9?wprov=sfla1