haskell - 不断发展的数据结构

我正在尝试在Haskell中为类似C的语言编写编译器。编译器通过转换AST进行处理。第一遍解析输入以创建AST，并在符号表上打一个结，以允许在定义符号之前先定位符号，而无需前向引用。

AST包含有关类型和表达式的信息，并且它们之间可以存在连接。例如sizeof(T)是一个依赖于T类型的表达式，而T[e]是一个依赖于常量表达式e的数组类型。

类型和表达式由Haskell数据类型表示，如下所示:

data Type = TypeInt Id
          | TypePointer Id Type -- target type
          | TypeArray Id Type Expr -- elt type, elt count
          | TypeStruct Id [(String, Type)] -- [(field name, field type)]
          | TypeOf Id Expr
          | TypeDef Id Type

data Expr = ExprInt Int -- literal int
          | ExprVar Var -- variable
          | ExprSizeof Type
          | ExprUnop Unop Expr
          | ExprBinop Binop Expr Expr
          | ExprField Bool Expr String -- Bool gives true=>s.field, false=>p->field

其中Unop包括地址(&)和取消引用(*)等运算符，而Binop包括加号(+)和时间(*)等运算符...

请注意，每种类型都分配有唯一的Id。这用于构造类型依赖图，以便检测导致无限类型的循环。一旦确定类型图中没有循环，就可以在它们上应用递归函数而不会陷入无限循环，这是安全的。

下一步是确定每种类型的大小，为结构字段分配偏移量，并用指针算法替换ExprField。这样，我们可以确定表达式的类型，并从类型图中消除ExprSizeof，ExprField，TypeDef和TypeOf，因此我们的类型和表达式得到了发展，现在看起来更像这样:

data Type' = TypeInt Id
           | TypePointer Id Type'
           | TypeArray Id Type' Int -- constant expression has been eval'd
           | TypeStruct Id [(String, Int, Type')] -- field offset has been determined

data Expr' = ExprInt Type' Int
           | ExprVar Type' Var
           | ExprUnop Type' Unop Expr'
           | ExprBinop Type' Binop Expr' Expr'

请注意，我们已经删除了一些数据构造函数，并略微更改了其他一些数据构造函数。特别是，Type'不再包含任何Expr'，并且每个Expr'已确定其Type'。

因此，最后是一个问题:创建两组几乎完全相同的数据类型，还是尝试将它们统一为一个数据类型更好？

保留两个单独的数据类型可以使某些构造函数不再出现。但是，执行常数折叠以评估常数表达式的函数将具有以下类型:

foldConstants :: Expr -> Either String Expr'

但这意味着我们以后不能再使用Expr'进行常量折叠(想象一些操作Expr'的过程，并且希望折叠任何出现的常量表达式)。我们将需要另一个实现:

foldConstants' :: Expr' -> Either String Expr'

另一方面，保持单个类型将解决常量折叠问题，但将阻止类型检查器强制使用静态不变量。

此外，在第一遍过程中，我们应将哪些内容放入未知字段(例如字段偏移量，数组大小和表达式类型)中？我们可以用undefined或error "*hole*"填补漏洞，但是这感觉就像一场灾难正在等待发生(就像您甚至无法检查的NULL指针一样)。我们可以将未知字段更改为Maybe，并用Nothing填充漏洞(例如我们可以检查的NULL指针)，但随后的遍历中不得不将值始终从Maybe中拉出总是很烦人的Just。

最佳答案

希望有更多经验的人会有一个更优美，经过考验和准备好的答案，但这是我的看法。

您可以使用GADT以相对较少的费用吃掉馅饼并吃掉其中的一部分:

{-# LANGUAGE GADTs #-}

data P0 -- phase zero
data P1 -- phase one

data Type p where
     TypeInt     :: Id -> Type p
     TypePointer :: Id -> Type p -> Type p             -- target type
     TypeArray   :: Id -> Type p -> Expr p -> Type p   -- elt type, elt count
     TypeStruct  :: Id -> [(String, Type p)] -> Type p -- [(field name, field type)]
     TypeOf      :: Id -> Expr P0 -> Type P0
     TypeDef     :: Id -> Type P0 -> Type P0

data Expr p where
     ExprInt     :: Int -> Expr p                        -- literal int
     ExprVar     :: Var -> Expr p                        -- variable
     ExprSizeof  :: Type P0 -> Expr P0
     ExprUnop    :: Unop -> Expr p -> Expr p
     ExprBinop   :: Binop -> Expr p -> Expr p -> Expr p
     ExprField   :: Bool -> Expr P0 -> String -> Expr P0 -- Bool gives true=>s.field, false=>p->field

这是我们已更改的内容:

现在，数据类型使用GADT语法。这意味着构造函数是使用其类型签名声明的。 data Foo = Bar Int Char变成data Foo where Bar :: Int -> Char -> Foo(除了语法外，两者是完全等效的)。

我们在Type和Expr中都添加了一个类型变量。这是所谓的幻像类型变量:没有存储p类型的实际数据，它仅用于强制类型系统中的不变量。

我们已经声明了虚拟类型来表示转换之前和之后的阶段:阶段0和阶段1。 (在一个复杂的，具有多个阶段的系统中，我们可以潜在地使用类型级别的数字来表示它们。)

GADT让我们在数据结构中存储类型级别的不变量。这里有两个。首先是递归位置必须与包含它们的结构处于同一相位。例如，查看TypePointer :: Id -> Type p -> Type p，您将Type p传递给TypePointer构造函数，并得到一个Type p作为结果，并且这些p必须是相同的类型。 (如果我们想允许不同的类型，我们可以使用p和q。)

第二个是我们强制执行以下事实:某些构造函数只能在第一阶段使用。大多数构造函数在幻像类型变量p中都是多态的，但是其中一些构造函数要求它是P0。这意味着这些构造函数只能用于构造Type P0或Expr P0类型的值，而不能用于其他任何阶段。

GADT在两个方向上起作用。第一个是，如果您有一个返回Type P1的函数，并尝试使用一个返回Type P0的构造函数来构造它，则会出现类型错误。这就是所谓的“构造正确”:构造一个无效结构在静态上是不可能的(前提是您可以对类型系统中的所有相关不变量进行编码)。另一方面，如果您具有Type P1的值，则可以确保它的构造正确:不能使用TypeOf和TypeDef构造函数(实际上，如果您尝试模式匹配，则编译器会抱怨)，并且任何递归位置也必须为P1相位。本质上，在构建GADT时，您存储的是满足类型约束条件的证据，当您在其上进行模式匹配时，便可以检索该证据并加以利用。

那是容易的部分。不幸的是，除了允许使用构造函数之外，这两种类型之间还有一些区别:某些构造函数参数在各个阶段之间是不同的，而某些仅存在于转换后阶段。我们可以再次使用GADT对此进行编码，但是它不那么便宜且美观。一种解决方案是复制所有不同的构造函数，并分别为P0和P1构造一个。但是复制不是很好。我们可以尝试做得更细:

-- a couple of helper types
-- here I take advantage of the fact that of the things only present in one phase,
-- they're always present in P1 and not P0, and not vice versa
data MaybeP p a where
     NothingP :: MaybeP P0 a
     JustP    :: a -> MaybeP P1 a

data EitherP p a b where
     LeftP  :: a -> EitherP P0 a b
     RightP :: b -> EitherP P1 a b

data Type p where
     TypeInt     :: Id -> Type p
     TypePointer :: Id -> Type p -> Type p
     TypeArray   :: Id -> Type p -> EitherP p (Expr p) Int -> Type p
     TypeStruct  :: Id -> [(String, MaybeP p Int, Type p)] -> Type p
     TypeOf      :: Id -> Expr P0 -> Type P0
     TypeDef     :: Id -> Type P0 -> Type P0

-- for brevity
type MaybeType p = MaybeP p (Type p)

data Expr p where
     ExprInt     :: MaybeType p -> Int -> Expr p
     ExprVar     :: MaybeType p -> Var -> Expr p
     ExprSizeof  :: Type P0 -> Expr P0
     ExprUnop    :: MaybeType p -> Unop -> Expr p -> Expr p
     ExprBinop   :: MaybeType p -> Binop -> Expr p -> Expr p -> Expr p
     ExprField   :: Bool -> Expr P0 -> String -> Expr P0

在这里，我们使用一些辅助类型来强制执行以下事实:一些构造函数参数只能出现在第一阶段(MaybeP)，而有些在两个阶段之间是不同的(EitherP)。尽管这使我们完全是类型安全的，但感觉有点特别，我们仍然必须始终将内容包装在MaybeP和EitherP中。我不知道在这方面是否有更好的解决方案。但是，完全类型安全性是要解决的:我们可以编写fromJustP :: MaybeP P1 a -> a并确保它是绝对完全安全的。

更新:一种替代方法是使用TypeFamilies:

data Proxy a = Proxy

class Phase p where
    type MaybeP  p a
    type EitherP p a b
    maybeP  :: Proxy p -> MaybeP p a -> Maybe a
    eitherP :: Proxy p -> EitherP p a b -> Either a b
    phase   :: Proxy p
    phase = Proxy

instance Phase P0 where
    type MaybeP  P0 a   = ()
    type EitherP P0 a b = a
    maybeP  _ _ = Nothing
    eitherP _ a = Left a

instance Phase P1 where
    type MaybeP  P1 a   = a
    type EitherP P1 a b = b
    maybeP  _ a = Just  a
    eitherP _ a = Right a

相对于先前版本，Expr和Type的唯一变化是构造函数需要添加一个Phase p约束，例如ExprInt :: Phase p => MaybeType p -> Int -> Expr p。

在这里，如果知道p或Type中Expr的类型，您可以静态地知道MaybeP是()还是给定类型，以及EitherP属于哪种类型，并且可以直接使用它们作为该类型，而无需显式展开。如果不知道p，则可以使用maybeP类中的eitherP和Phase找出它们是什么。 (Proxy参数是必需的，因为否则编译器将无法分辨出您的意思。)这类似于GADT版本，如果知道了p，则可以确定MaybeP和EitherP包含哪些内容，否则，您必须将两种模式进行模式匹配。就“缺失”参数变为()而不是完全消失而言，该解决方案也不是完美的。

在这两个版本之间，构造Expr和Type似乎也很相似:如果要构造的值具有特定于相位的值，则必须在其类型中指定该相位。当您想在p中编写一个多态函数，但仍在处理特定于阶段的部分时，问题似乎就来了。使用GADT，这很简单:

asdf :: MaybeP p a -> MaybeP p a
asdf NothingP  = NothingP
asdf (JustP a) = JustP a

请注意，如果我只写了asdf _ = NothingP，编译器就会抱怨，因为不能保证输出的类型与输入的类型相同。通过模式匹配，我们可以找出输入是什么类型，并返回相同类型的结果。

但是，对于TypeFamilies版本，这要困难得多。仅使用maybeP和生成的Maybe，您就无法向编译器证明任何有关类型的信息。您可以通过这种方式获得一部分，而不必让maybeP和eitherP返回Maybe和Either，从而使它们像maybe和either这样的解构函数也可以使类型相等可用:

maybeP  :: Proxy p -> (p ~ P0 => r) -> (p ~ P1 => a -> r) -> MaybeP p a -> r
eitherP :: Proxy p -> (p ~ P0 => a -> r) -> (p ~ P1 => b -> r) -> EitherP p a b -> r

(请注意，我们为此需要Rank2Types，并且还要注意，这些本质上是MaybeP和EitherP的GADT版本的CPS转换版本。)

然后我们可以写:

asdf :: Phase p => MaybeP p a -> MaybeP p a
asdf a = maybeP phase () id a

但这还不够，因为GHC说:

data.hs:116:29:
 Could not deduce (MaybeP p a ~ MaybeP p0 a0)
 from the context (Phase p)
   bound by the type signature for
              asdf :: Phase p => MaybeP p a -> MaybeP p a
   at data.hs:116:1-29
 NB: `MaybeP' is a type function, and may not be injective
 In the fourth argument of `maybeP', namely `a'
 In the expression: maybeP phase () id a
 In an equation for `asdf': asdf a = maybeP phase () id a

也许您可以在某处使用类型签名来解决此问题，但在那一点看来，它比值得的麻烦得多。因此，在等待其他人提供进一步信息之前，我将建议您使用GADT版本，它是一种更简单，更强大的版本，但会产生一点句法噪音。

再次更新:这里的问题是，因为MaybeP p a是类型函数，并且没有其他信息可利用，所以GHC无法知道p和a应该是什么。如果我传入Proxy p并使用它代替解决phase的p，但a仍然未知。

关于haskell - 不断发展的数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10761583/