Lambda-Calculus与组合子简介

简介：
本文介绍了Lambda-Calculus的基本概念和规则，并探讨了与其密切相关的组合子逻辑系统，为理解高级编程语言及函数式编程打下理论基础。 λ演算与组合逻辑是两种可以作为抽象编程语言的逻辑系统。它们都旨在描述程序在一种不被细节干扰的抽象环境中如何修改其他程序的一些基本特性。从某些角度来看，两者互为竞争对手；而在另一些方面，则相互支持。 λ演算是美国数理逻辑学家阿隆佐·丘奇于1930年左右发明的，作为包含高阶运算符（即作用于其它运算符上的运算符）在内的全面逻辑系统的一部分。实际上，在大多数高级语言中——无论是用于逻辑还是计算机编程的语言——λ演算或某种本质上等价的符号表示法都是关键组成部分。事实上，最初发现的第一批不可计算问题就是用λ演算而非图灵机这样的理想化计算机来描述和证明的。 组合逻辑与λ演算有着相同的目标，并且可以表达同样的计算概念，但其语法更为简单。它的基本理念由两个人提出：摩西·施纳芬克尔于1920年首次想到这一想法；哈斯凯尔·柯里七年后独立重新发现了它并将其发展成了一种实用的技术。 本书旨在向读者介绍这两个领域中的基础方法和成果。假设读者对命题逻辑、谓词逻辑以及递归函数有所了解，并且具备一定的数学归纳法实践经验。书中包含一些练习题，大部分题目（标记为*的题目）的答案可以在书末的附录中找到。在早期章节中还有一些没有答案的额外习题，以便需要时提供更多的常规练习机会。