将简单类型语言的非类型化 AST 转换为 GADT

Question

我有一个代表简单语言 AST 的 ADT：

data UTerm = UTrue
      | UFalse
      | UIf UTerm UTerm UTerm
      | UZero
      | USucc UTerm
      | UIsZero UTerm

此数据结构可以表示不遵循类型的无效术语语言规则，比如 UIsZero UFalse，所以我想使用一个 GADT 强制类型化：

{-# LANGUAGE GADTs #-}

data TTerm a where
  TTrue :: TTerm Bool
  TFalse :: TTerm Bool
  TIf :: TTerm Bool -> TTerm a -> TTerm a -> TTerm a
  TZero :: TTerm Int
  TSucc :: TTerm Int -> TTerm Int
  TIsZero :: TTerm Int -> TTerm Bool

我的问题是键入检查 UTerm 并将其转换为 TTerm。我的第一次以为是 UTerm -> Maybe (TTerm a)，但这当然行不通，因为并非对所有 a 都有效。我什至不知道类型是什么，因为我们不知道 a 是 Int 还是 Bool。然后我想我可以写一个 a:

的每个可能值的不同类型检查函数

import Control.Applicative

typecheckbool :: UTerm -> Maybe (TTerm Bool)
typecheckbool UTrue = Just TTrue
typecheckbool UFalse = Just TFalse
typecheckbool (UIsZero a) = TIsZero <$> typecheckint a
typecheckbool _ = Nothing

typecheckint :: UTerm -> Maybe (TTerm Int)
typecheckint UZero = Just TZero
typecheckint (USucc a) = TSucc <$> typecheckint a
typecheckint (UIf a b c) = TIf <$> typecheckbool a <*> typecheckint b <*> typecheckint c
typecheckint UTrue = Nothing
typecheckint UFalse = Nothing
typecheckint (UIsZero _) = Nothing

这适用于某些情况，适用于 TIf 需要它的语言子集 consequent 和 alternative 是 Ints（但 TIf TTrue TFalse TTrue 实际上是完全有效），并且我们知道表达式的目标类型打字。

从 UTerm 转换为 TTerm 的正确方法是什么？

Answer 1

标准技术是定义存在类型：

data ETerm_ where
    ETerm_ :: TTerm a -> ETerm

在这种情况下，您可能还需要一些术语级别的证据来证明您拥有哪种类型；例如

data Type a where
    TInt :: Type Int
    TBool :: Type Bool

那么真正的 ETerm 应该是这样的：

data ETerm where
    ETerm :: Type a -> TTerm a -> ETerm

有趣的类型检查案例类似于

typeCheck (UIf ucond ut uf) = do
    ETerm TBool tcond <- typeCheck ucond
    ETerm tyt tt <- typeCheck ut
    ETerm tyf tf <- typeCheck uf
    case (tyt, tyf) of
        (TBool, TBool) -> return (ETerm TBool (TIf tcond tt tf))
        (TInt , TInt ) -> return (ETerm TInt  (TIf tcond tt tf))
        _ -> fail "branches have different types"

Answer 2

作为@DanielWagner 回答的次要补充，您可能想要分解类型相等性检查，例如

...
case (tyt, tyf) of
        (TBool, TBool) -> return (ETerm TBool (TIf tcond tt tf))
        (TInt , TInt ) -> return (ETerm TInt  (TIf tcond tt tf))
        _ -> fail "branches have different types"

一种方法是使用平等证人：

import Data.Type.Equality

typeEq :: Type a -> Type b -> Maybe (a :~: b)
typeEq TInt  TInt  = Just Refl
typeEq TBool TBool = Just Refl
typeEq _     _     = Nothing

typeCheck :: UTerm -> Maybe ETerm
typeCheck (UIf ucond ut uf) = do
    ETerm TBool tcond <- typeCheck ucond
    ETerm tyt tt <- typeCheck ut
    ETerm tyf tf <- typeCheck uf
    case typeEq tyt tyf of
        Just Refl -> return (ETerm tyt (TIf tcond tt tf))
        _         -> fail "branches have different types"

如果您需要在类型检查例程的多个部分检查类型相等性，则此因式分解很方便。它还允许使用像 (t1,t2) 这样的对类型来扩展语言，这需要结构递归方法来检查类型相等性。

甚至可以为类型相等性编写完整的决策程序

{-# LANGUAGE EmptyCase #-}
typeEq2 :: Type a -> Type b -> Either (a :~: b) ((a :~:b) -> Void)
typeEq2 TInt  TInt  = Left Refl
typeEq2 TInt  TBool = Right (\eq -> case eq of)
typeEq2 TBool TBool = Left Refl
typeEq2 TBool TInt  = Right (\eq -> case eq of)

但我想，除非您尝试对非常高级的类型（例如 GADT）建模，否则可能不需要这个。

上面的代码使用空大小写来检查 eq 可能具有的所有可能值。因为它有类型，例如Int :~: Bool，并且没有与该类型匹配的构造函数，我们没有 eq 的可能值，因此不需要 case 分支。这将不会触发详尽警告，因为确实没有未处理的案例（OT：我希望这些警告是实际错误）。

除了使用 EmptyCase 你也可以使用 case eq of _ -> undefined 之类的东西，但是像上面那样在证明术语中使用底部是有问题的。

将简单类型语言的非类型化 AST 转换为 GADT

Converting an untyped AST for a simple typed language into a GADT

haskell

gadt