为什么这个简单的 Morte 程序不能进行类型检查？

Question

我正在尝试通过 Morte 更好地理解构造微积分。我的第一次尝试是调用身份函数本身。然而，

(
λ (idType : *) →
λ (id : idType) → 
(id idType))

(∀(t : *) → ∀(x : t) → t)
(λ(a : *) → λ(x : a) → x)

该程序编译失败并出现错误：

Context:
idType : *
id : idType

Expression: id idType

Error: Only functions may be applied to values

这对我来说没有意义，因为 id 是类型 idType == (∀(t : *) → t → t) 的函数 (λ(a : *) → λ(x : a) → x)。为什么我会收到此错误消息？

Answer 1

你的

T = (λ (idType : *) →
     λ (id : idType) → 
    (id idType))

打错字了。否则 T nat 4 也会输入检查（假装我们有自然数来帮助直觉）。

如果你想写一个应用程序函数（像Haskell的$）你可以使用

apply = 
    (λ (a b : *) →
     λ (f : a -> b) → 
     λ (x : a) → 
     f x)

请注意，以上仅适用于非依赖性 f。在从属情况下，b 可以依赖于类型 a 的实际值，使事情变得更加复杂，因为现在 b 是一个函数。

applyDep = 
    (λ (a : *) →
     λ (b : a -> *) →
     λ (f : ∀(x : a) -> b x) → 
     λ (x : a) → 
     f x)

示例（简化语法）：

applyDep 
  Bool
  (λ (x : Bool) -> if x then Int else Char)
  (λ (x : Bool) -> if x then 4 else 'd')
  True

上面我对依赖函数（最后一个 lambda）相当草率，因为 if 类型不正确（分支的类型不同），但你可能会得到粗略的想法。为了更准确地写出来，我需要像依赖 match/case Coq 那样的东西（或者依赖于 Bool 的依赖消除器）：

fun x: Bool =>
  match x as y return (if y then Int else Char) with
  | True  => 3
  | False => 'a'
  end

在上面的"if"中，我要说清楚两个分支的类型是不同的（Int vs Char），但是如果我们可以输入将其作为 g x 的结果，其中 g = fun y => if y then Int else Char。基本上，结果类型现在取决于 x 值。

Answer 2

这里的问题是，使用教堂风格的打字（这里是一个很好的 blogpost and some discussion）所有内容都必须从一开始就打好：如果你有一个打好字的 f 和一个类型正确的 x，那么您可以将 f 应用到 x（如果类型匹配）。如果 f 的类型不正确，那么它就不是一个合法的术语并且你有一个错误，即使可以为 f x 分配一个类型。

你的 λ (idType : *) → λ (id : idType) → (id idType) 类型不正确：id 是类型 idType 的术语，它不是接收 * 的函数，所以你不能将其应用于 idType.

为什么这个简单的 Morte 程序不能进行类型检查？

Why won't this simple Morte program typecheck?

haskell

types

morte