使用 'bound' 对依赖的 lambda 抽象进行类型检查的正确方法是什么？

Question

我正在实现一种简单的依赖类型语言，类似于 described by Lennart Augustsson, while also using bound 管理绑定的语言。

当对依赖的 lambda 项进行类型检查时，例如 λt:* . λx:t . x，我需要：

"Enter" 外层 lambda 绑定器，通过实例化 t 到 something
类型检查 λx:t . x，生成 ∀x:t . t
Pi-抽象t，产生∀t:* . ∀x:t . t

如果 lambda 是非依赖的，我可以在第 1 步用它的 type 实例化 t，因为我只需要知道类型在步骤 2 中进行类型检查时的变量。但是在第 3 步，我缺乏决定抽象哪些变量的信息。

我可以引入一个新的名称源并使用包含类型和唯一名称的 Bound.Name.Name 实例化 t。但我认为使用 bound 我不需要生成新名称。

我是否缺少替代解决方案？

Answer 1

我们需要某种上下文来跟踪 lambda 参数。但是，我们不一定需要实例化它们，因为 bound 为我们提供了 de Bruijn 索引，我们可以使用这些索引索引到上下文中。

不过，实际上使用索引有点复杂，因为类型级机制通过嵌套 Var-s。它需要使用多态递归或 GADT。它还阻止我们将上下文存储在 State monad 中（因为上下文的大小和类型在我们递归时会发生变化）。我想知道我们是否可以使用索引状态 monad；这将是一个有趣的实验。但我离题了。

最简单的解决方案是将上下文表示为函数：

type TC  a = Either String a -- our checker monad
type Cxt a = a -> TC (Type a) -- the context

a 输入本质上是一个 de Bruijn 索引，我们通过将函数应用于索引来查找类型。我们可以通过以下方式定义空上下文：

emptyCxt :: Cxt a
emptyCxt = const $ Left "variable not in scope"

我们可以扩展上下文：

consCxt :: Type a -> Cxt a -> Cxt (Var () a)
consCxt ty cxt (B ()) = pure (F <$> ty)
consCxt ty cxt (F a)  = (F <$>) <$> cxt a

上下文的大小在 Var 嵌套中编码。 return 类型的大小增加很明显。

现在我们可以编写类型检查器了。这里的要点是我们使用 fromScope 和 toScope 来获取活页夹，并且我们进行了适当扩展的 Cxt （其类型恰好对齐）。

data Term a
  = Var a
  | Star -- or alternatively, "Type", or "*"
  | Lam (Type a) (Scope () Term a)
  | Pi  (Type a) (Scope () Term a)
  | App (Type a) (Term a)  
  deriving (Show, Eq, Functor)

-- boilerplate omitted (Monad, Applicative, Eq1, Show1 instances)

-- reduce to normal form
rnf :: Term a -> Term a
rnf = ...

-- Note: IIRC "Simply easy" and Augustsson's post reduces to whnf
-- when type checking. I use here plain normal form, because it 
-- simplifies the presentation a bit and it also works fine.

-- We rely on Bound's alpha equality here, and also on the fact
-- that we keep types in normal form, so there's no need for
-- additional reduction. 
check :: Eq a => Cxt a -> Type a -> Term a -> TC ()
check cxt want t = do
  have <- infer cxt t
  when (want /= have) $ Left "type mismatch"

infer :: Eq a => Cxt a -> Term a -> TC (Type a)
infer cxt = \case
  Var a -> cxt a
  Star  -> pure Star -- "Type : Type" system for simplicity
  Lam ty t -> do
    check cxt Star ty
    let ty' = rnf ty
    Pi ty' . toScope <$> infer (consCxt ty' cxt) (fromScope t)
  Pi ty t -> do
    check cxt Star ty
    check (consCxt (rnf ty) cxt) Star (fromScope t)
    pure Star
  App f x -> 
    infer cxt f >>= \case
      Pi ty t -> do
        check cxt ty x
        pure $ rnf (instantiate1 x t)
      _ -> Left "can't apply non-function"

这里是the working code containing上面的定义。我希望我没有把事情搞得太糟。

使用 'bound' 对依赖的 lambda 抽象进行类型检查的正确方法是什么？

What is the right way to typecheck dependent lambda abstraction using 'bound'?

haskell

lambda-calculus

dependent-type