递归函数(一):开篇

提到函数式编程,人们最多想到的可能是它的某些性质,

例如,不可变性,无副作用,惰性求值,类型推导,等等。


然而,这些性质可能并不是它能吸引粉丝的根本原因,

而是它从工业界触手可及的直接应用出发,带我们看到了人类能力的边界,

函数式编程仿佛一座桥梁,让我们普通程序员也能窥探计算机科学的奥秘。


演算是一个简洁的演算系统,但是它的计算能力却能比肩复杂的现代计算机,

因为它的简洁性质,以及与Lisp语言的紧密关系,对演算有所了解的程序员也比较多。


提到编程语言,上下文无关文法,以及正则文法,熟悉的人可能会更多,

书写正则表达式,开发和应用DSL,甚至阅读编程语言的语法规范,都离不开它们。


然而,逻辑系统和递归函数论却鲜有人提及,

对如何书写递归函数人们可能仍旧心存畏惧,对类型的推导过程和原理也如坠迷雾。


其实,这是一块广袤的领域,其背景知识可能涉及了数学归纳法,良基或结构归纳法,

可计算性理论,不动点算子,哥德尔定理,以及证明论,模型论,等等。

数学背景,我们可能还需要补充,抽象代数,集合论,数理逻辑等离散数学的内容。


然而,我们的收获将是巨大的,

我们会看到用有限表示无限的递归思想,以及由这种思想导致的各种计算模型的能力限制。

递归与其他领域触类旁通之后,我们将走到数学,逻辑,计算机科学的交叉点上,

我认为这是一件值得高兴的事情。


递归函数(一):开篇

递归函数(二):编写递归函数的思路和技巧

递归函数(三):归纳原理

递归函数(四):全函数与计算的可终止性

递归函数(五):递归集与递归可枚举集

递归函数(六):最多有多少个程序

递归函数(七):不动点算子

递归函数(八):偏序结构

递归函数(九):最小不动点定理