如果不可能在 CoC 上进行 O(1) 预测，那么为什么这样做有效？

Question

我一直认为已经证明 pred 在构造微积分上对于任何数据类型的编码都无法在常数时间内表达。现在，注意这个 nats 编码：

S0 : ∀ (r : *) . (r -> r) -> r -> r
S0 = λ s z . z

S1 : ∀ (r : *) (((∀ (r : *) . (r -> r) -> r -> r) -> a) -> (a -> a)))
S1 = λ s z . (s (λ s z . z))

S2 : (∀ (r : *) . ((∀ (r : *) . ((∀ (r : *) . (r -> r) -> r -> r) -> a) -> a -> a) -> a) -> a -> a)
S1 = λ s z . (s (λ s z . (s (λ s z . z))))

这只是 Scott 编码，除了我实际上是在键入整个术语而不是使用递归。我注意到的是，在这种看似愚蠢的编码下，我实际上不仅可以定义 Zero 和 Succ，还可以定义 O(1) Pred:

SNat 
    =  λ (n : Nat)
    -> (n * 
           (λ (p:*) -> (∀ (r:*) . (p -> r) -> r -> r))
           (∀ (r:*) -> (r -> r) -> r -> r))

SNat_Zero
    =  λ (r : *)
    -> λ (s : r -> r)
    -> λ (z : r)
    z

SNat_Succ
    =  λ (k : Nat)
    -> λ (n : SNat k)
    -> λ (r : *)
    -> λ (s : (SNat k) -> r)
    -> λ (z : r)
    (s n)

SNat_Pred
    =  λ (k : Nat)
    -> λ (n : SNat (Succ k))
    -> λ (n (Maybe (SNat k))
            (p:(SNat k) (Maybe_Just (SNat k) p))
            (Maybe_Nothing (SNat k)))

注意：我只是从另一种语法中通过肉眼翻译的。万一出现问题，this 是正确的。您可以运行通过克隆此 repo 并键入：

cd calculus-of-constructions
npm i -g
cd lib
coc type SNat_Pred
coc norm SNat_Pred

这可能是因为我的实现有某种错误，还是我误认为上述证明的存在？

Answer 1

我不太明白你的编码试图做什么。但是您的存储库似乎具有以下定义（从文件 Nat.coc 和 SNat.coc 翻译成类似 Coq 的语法）：

Definition Nat :=
  forall X : *, (X -> X) -> X -> X.

Definition SNat :=
  fun n : Nat => n * (* Some more stuff *).

如果我没理解错的话，SNat的定义是用自然数n迭代一个* -> *类型的函数。这看起来类型不正确，因为 n 将 * 类型的东西作为参数，因此需要 * : *，这在 CoC 中无效。

如果不可能在 CoC 上进行 O(1) 预测，那么为什么这样做有效？

If it is impossible to have O(1) pred on CoC, then why does this work?

functional-programming

coq

agda