在Haskell中，如何根据GADT将无类型的AST解析为有类型的？

Question

我正在用 Haskell 编写一种特定于领域的语言，并已确定具有两个 AST 的设计：一个初始的无类型的表示语法和代表一切的最终类型。我正在写最后一个作为一个 GADT 以获得更好的类型检查。

我认为它几乎可以工作，但是我在编写一个函数时遇到了问题转换 initial -> final （检查类型，加上一些其他未显示的东西，就像所有的引用都对应一个变量）。

这是一个简化的例子：

{-# LANGUAGE GADTs, StandaloneDeriving #-}

module Main where

-- untyped initial AST

data Untyped
  = UNum Int
  | UStr String
  | UAdd Untyped Untyped
  deriving (Show, Eq)

-- typed final AST

data Typed a where
  TNum :: Int    -> Typed Int
  TStr :: String -> Typed String
  TAdd :: Typed Int -> Typed Int -> Typed Int

deriving instance Eq   (Typed a)
deriving instance Show (Typed a)

-- wrapper that allows working with a `Typed a` for any `a`
data TypedExpr where
  TypedExpr :: Typed a -> TypedExpr

这是我对 check 功能的尝试。基本情况很简单：

check :: Untyped -> Either String TypedExpr
check (UNum n) = Right $ TypedExpr $ TNum n
check (UStr s) = Right $ TypedExpr $ TStr s
-- check (Uadd e1 e2) = ???

但是如何添加 Add？它可以递归地评估子表达式以 Either String (TypedExpr (Typed a)) 类型的值，但我还没有成功打开它们，检查类型是否对齐（as 应该是 Ints），然后之后重新包装。我计划用大模式匹配来完成这一切，但是 GHC 不赞成：

My brain just exploded
  I can't handle pattern bindings for existential or GADT data constructors.
  Instead, use a case-expression, or do-notation, to unpack the constructor.

解释得很好 here，但我没看懂解释。它似乎我不要模式匹配。

更新：我一定是在没有注意到的情况下搞砸了其他事情。模式匹配有效，如 Nikita 所示。

所以我摆弄着试图强迫事情进入正确的形状，但还没有得到任何实质性的东西。如果这些是只是 Either String SomeValue 我想使用应用程序，对吗？是吗可以向它们添加另一级别的展开+类型检查吗？我怀疑 is close to what I want since the question is very similar, but again I don't understand it. This 也可能相关。

更新：毕竟是我想要的。但是直到 chi 在没有额外的 Type 类型的情况下编写了下面的中间版本之前，我才明白如何。这是一个可行的解决方案。诀窍是用一个新类型标记 TypedExprs，该类型只表示 Typed a 的 return 类型 (a):

data Returns a where
  RNum :: Returns Int
  RStr :: Returns String

-- extend TypedExpr to include the return type
data TypedExpr2 where
  TypedExpr2 :: Returns a -> Typed a -> TypedExpr2

这样 check 就不必知道每个子表达式是否是原始的 TNum 或 return 是 TNum:

的函数（如 Add）

check :: Untyped -> Either String TypedExpr2
check (UNum n) = Right $ TypedExpr2 RNum (TNum n)
check (UStr s) = Right $ TypedExpr2 RStr (TStr s)
check (UAdd u1 u2) = do
  -- typecheck subexpressions, then unwrap by pattern matching
  TypedExpr2 r1 t1 <- check u1
  TypedExpr2 r2 t2 <- check u2
  -- check the tags to find out their return types
  case (r1, r2) of
    -- if correct, create an overall expression tagged with its return type
    (RNum, RNum) -> return $ TypedExpr2 RNum $ TAdd t1 t2
    _ -> Left "type error"

GHC 足够聪明，知道任何 TypedExpr2 中的两个 a 必须匹配，因此，如果您尝试使用错误的总体 return 类型结尾。精彩！

Answer 1

您的确切问题可以通过以下解决方案轻松回答：

check (UAdd (UNum a) (UNum b)) = Right $ TypedExpr $ TAdd (TNum a) (TNum b)

然而，那里有很多设计迷宫的迹象。

您是否意识到，一旦将某些内容放入 TypedExpr 中，您就会丢失有关 a 类型的所有信息？这使您的 check 函数毫无意义。

我理解你这样做是因为只有这样才能统一你的GADT类型，否则你无法实现check功能。但实际上它只是证明你建模错误，GADT 可能不适合你的用例。

我不明白为什么 UAdd 构造函数超过 Untyped 值，而不是 Int，我不明白是什么让你选择了这个多阶段AST策略。

我可以继续，但我会在这里中断并建议您重新设计模型。

Answer 2

我的建议是使用 "plain" 类型域的表示（带有解释类型函数），然后将存在类型的 Singleton 具体化存储在 TypedExpr，即

{-# LANGUAGE DataKinds, KindSignatures, TypeFamilies #-}

data Type = TInt | TString

type family InterpT (a :: Type) where
  InterpT TInt = Int
  InterpT TString = String

-- plus the usual singletons stuff
-- ...

-- and finally
data Typed (a :: Type) where ...

data TypedExpr where
  TypedExpr :: Sing a -> Typed a -> TypedExpr

通过这种方式，您可以执行类似

的操作

check (UAdd e1 e2) = do
  TypedExpr t1 e1' <- check e1
  TypedExpr t2 e2' <- check e2
  case testEquality t1 t2 of
    Just Refl -> ... use e1' and e2' here, you know they have the same Type
    Nothing -> Left ...

找到一个完整的例子。

Answer 3

从技术上讲，它是可行的，但它非常不方便：您必须"dig"直到找到 GADT 构造函数。

check :: Untyped -> Either String TypedExpr
check (UNum n) = return $ TypedExpr $ TNum n
check (UStr s) = return $ TypedExpr $ TStr s
check (UAdd t1 t2) = do
    t1 <- check t1
    t2 <- check t2
    case (t1, t2) of
      (TypedExpr (TNum x)     , TypedExpr (TNum y))
         -> return $ TypedExpr $ TAdd (TNum x    ) (TNum y)
      (TypedExpr (TAdd x1 x2) , TypedExpr (TNum y))
         -> return $ TypedExpr $ TAdd (TAdd x1 x2) (TNum y)
      (TypedExpr (TNum x)     , TypedExpr (TAdd y1 y2))
         -> return $ TypedExpr $ TAdd (TNum x    ) (TAdd y1 y2)
      (TypedExpr (TAdd x1 x2) , TypedExpr (TAdd y1 y2))
         -> return $ TypedExpr $ TAdd (TAdd x1 x2) (TAdd y1 y2)
      _ -> Left "type error"

我会寻找替代方案。当构造函数的数量很大时，上述方法会出现组合爆炸。

在Haskell中，如何根据GADT将无类型的AST解析为有类型的？

In Haskell, how to parse an untyped AST to a typed one based on a GADT?

haskell

pattern-matching

typechecking

applicative

gadt