构造计算中的递归

Question

如何在（纯）calculus of constructions中定义一个递归函数？我在那里没有看到任何固定点组合器。

Answer 1

CS stack exchange 中的人可能能够提供更多见解，但这里是一个尝试。

归纳数据类型在构造演算中用Church encoding定义：数据类型是其折叠函数的类型。最基本的例子是自然数，使用类似 Coq 的符号定义如下：

nat := forall (T : Type), T -> (T -> T) -> T

这种编码产生两件事：(1) 用于构造自然数的术语 zero : nat 和 succ : nat -> nat，以及 (2) 用于编写递归函数的运算符 nat_rec。

zero : nat
zero T x f := x

succ : nat -> nat
succ n T x f := f (n T x f)

nat_rec : forall T, T -> (T -> T) -> nat -> T
nat_rec T x f n := n T x f

如果我们对术语 x : T 和 f : T -> T 提出 F := nat_rec T x f，我们会发现以下等式是有效的：

F zero = x
F (succ n) = f (F n)

因此，nat_rec 允许我们通过为基本情况指定 return 值 x 和函数 f 来定义递归函数来处理 f 的值递归调用。请注意，这不允许我们在自然数上定义任意递归函数，而只能定义那些对其参数的前身执行递归调用的函数。允许任意递归会打开部分函数的大门，这会损害微积分的稳健性。

这个例子可以推广到其他归纳数据类型。例如，我们可以将自然数列表的类型定义为其折叠右函数的类型：

list_nat := forall T, T -> (nat -> T -> T) -> T

Recursion in the calculus of construction