lambda 演算是函数式编程语言核心的通用计算模型。它基于lambda-terms,这是一种最小的编程语言,仅具有函数定义、函数调用和变量。 Lambda 术语根据以下规则构建:
- 任何变量 (来自某个无限字母表的单个字母)都是 lambda 项。
- 如果 和 是 lambda 项,则 是 lambda 项,称为 到 的应用。
- 如果 是变量, 是项,则 是 lambda 项,称为抽象。抽象定义了一个匿名函数,以 作为参数并发送回 。
如果对于所有变量 , 中出现的所有 都包含在 中的某个抽象 中,则称 lambda 项 是封闭的。最小的这样的抽象被认为是绑定变量的出现。换句话说,如果 lambda 项的所有变量都绑定到封闭函数定义的参数,则该 lambda 项是封闭的。例如,项 是封闭的,而项 不是封闭的,因为 没有绑定。
此外,只要绑定抽象不发生变化,我们就可以重命名变量。这意味着 和 应该被认为是等效的,因为我们只是重命名了一个参数。与此类重命名等效的两个项称为-equivalent。请注意, 和 不等价于 ,因为绑定第一个变量的抽象是外部变量,并成为内部变量。然而,和是等价的。
下表重新组合了最多可以使用 符号编写的 lambda 项,符号包括括号、、点和变量。
令 为最多可以使用 符号编写的不同封闭 lambda 项的数量,其中 彼此等价的项只应计算一次。已知 、、 和 。
查找 。给出答案以 为模。
题解待补充
这道题的题目已收录,解题思路、代码和答案将在后续补充。