haskell - 在Haskell中选择AST表示形式

Question

我目前正在研究玩具功能语言编译器，目的是学习与类型有关的事物和Haskell中的稍微先进的技术。

我相信我需要将信息附加到树上的每个节点上，例如原始源代码中的位置，以便更好地报告错误，推断类型，生成类型约束等。因此，最初我选择了这种方法:

data Expr a = ELam [Pat a]  (Expr a) a
            | ELet [Decl a] (Expr a) a
            | EIf  (Expr a) (Expr a) (Expr a) a
            | ECase (Expr a) [Alt a] a
            | EApp (Expr a) [Expr a] a
            | EVar Variable a
            | ECon Variable a
            | ELit Literal  a
            | ELOpSec (Op a) (Expr a) a
            | EROpSec (Op a) (Expr a) a
            | EInfix  (Expr a) (Op a) (Expr a) a
            | ENeg    (Expr a) a
-- Intermediate representation, removed after resolving infix expressions.
            | EParen  (Expr a) a
            deriving (Eq, Show, Functor, Generic1)

Functor是为了有效转换附加的节点而派生的，而 Generic1允许使用通用函数来获取该信息。

但是，在完成解析器后，我发现该结构对于将来的处理有点不友好。本质上，我想要一个两层结构，就像 here所提到的那样。我正在尝试的东西:

data Expr w = ELam  [w (Pat w)]  (w (Expr w))
            | ELet  [w (Decl w)] (w (Expr w))
            | EIf   (w (Expr w)) (w (Expr w)) (w (Expr w))
            | ECase (w (Expr w)) [w (Alt w)]
            | EApp  (w (Expr w)) [w (Expr w)]
            | EVar  (w Var)
            | ECon  (w Var)
            | ELit  (w Lit)
            | ELOpSec (w Var) (w (Expr w))
            | EROpSec (w Var) (w (Expr w))
            | EInfix  (w (Expr w)) (w Var) (w (Expr w))
            | ENeg    (w (Expr w))

最初的动机是为了更加方便/美观的模式匹配，因为可以将不必要的信息分离出来。此外，我刚刚阅读了 gentle introduction to recursion scheme，所以我希望可以利用现有的库。

但是，我尝试的上述代码被GHC拒绝。更确切地说，我不能使用它来自动派生 Eq实例。我尝试了一个复杂的独立推导:

deriving instance (Eq (a b))   => Eq   (Expr a)

但是在启用了多个扩展之后，它被拒绝了。我注意到 recursion-scheme库具有以下代码:

newtype Fix f = Fix (f (Fix f))

deriving instance Eq (f (Fix f)) => Eq (Fix f)

但是我无法理解该实例-我们将如何满足 Eq (f (Fix f))？

我注意到在ezyang的博客中，有关AST输入方法的内容，他使用了:

data ExpF a = Num Int
            | Bool Bool
            | Var Var
            | If a a a
            | Lambda Var a
            | App a a
newtype Exp = Exp (ExpF Exp)
newtype TExp = TExp (ExpF TExp, Type)

但是我在 Expr中有不同类型的节点，例如模式和声明。

我的问题是:

是否可以使用两层类型结构来表达我的AST？如何获得Eq和Show实例？

从长远来看，仅坚持使用我原来的老式AST类型会更好吗？

谢谢!

Answer 1

幸运的是，Eq的Expr w实例很容易编写。在编写Eq实例时，我们通常会要求数据类型中使用的所有类型的Eq实例。例如，如果我们要为

data E a b = A a
           | B b

我们需要一种比较 Eq和 a的方法

{-# LANGUAGE StandaloneDeriving #-}

deriving instance (Eq a, Eq b) => Eq (E a b)

如果类型是更高种类的...

data E w = EA (w A)
         | EB (w B)

...我们仍然需要一种方法来比较 b中任何地方发生的每种类型

{-# LANGUAGE FlexibleContexts #-}

deriving instance (Eq (w A), Eq (w B)) => Eq (E a b)

可以递归地完成同一件事，在推导如何比较数据类型时，请求一种比较内部类型的方法。除了上面使用的扩展之外，递归约束还需要 E。

{-# LANGUAGE UndecidableInstances #-}

data E w = EA (w A)
         | EB (w B)
         | EE (w (E w))

deriving instance (Eq (w A), Eq (w B), Eq (w (E w))) => Eq (E a b)

这也是 UndecidableInstances的递归方案代码正在执行的操作，但是 Fix中使用的唯一类型是 Fix，因此约束看起来有点神奇。

newtype Fix f = Fix (f (Fix f))

deriving instance Eq (f (Fix f)) => Eq (Fix f)

f (Fix f)的 Eq实例以相同的方式编写。该约束要求一种比较 Expr w中出现的每种类型的方法。

{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}

deriving instance (
    Eq (w (Pat w)),
    Eq (w (Decl w)),
    Eq (w (Alt w)),
    Eq (w Var),
    Eq (w Lit),
    Eq (w (Expr w))) => Eq (Expr w)

楷模

数据类型 Expr w具有某种不同寻常的种类 Expr w，我将其称为 模型。在给定 Functor 或 Monad 的情况下，这两种东西都具有 (* -> *) -> *类型，就可以产生数据类型(其类型为 * -> *)。 *是表达式的精确模型。 Expr Identity可以对表达式进行建模，该表达式的值是通过与外界交互来构造的。 Expr IO可以对分布在多台计算机上的 Expr ref进行建模，其中 Expr类型描述了获取其他组件的位置，例如数据库记录的标识符。 ref只是 Expr Proxy的构造函数，没有任何数据。您可能正在寻找类似于 Expr的东西，该东西在每个组件上为带有 Expr ((,) a)类型注释的表达式建模。

实际上，您可能正在寻找 a，它具有整个结构及其每个组件的注释。这看起来有点像垃圾。为了清理它，我们将为某些仿函数中的数据模型添加类型同义词。

type In f d = f (d f)

从源读取的表达式的一种可能类型是用每个组件来自的行号和列注释的表达式。

type SourcePos = (Int, Int)
type SourceExpr = In ((,) SourcePos) Expr

我将手工制作 (,) a (Expr ((,) a))的一些示例，以检查派生的 SourceExpr实例是否有效。

example1 :: SourceExpr  
-- if Var then Con else Lit
example1 = ((1, 1) , EIf ((1, 4), EVar ((1, 4) , Var)) ((1, 7) , ECon ((1, 12) , Var)) ((1, 16) , ELit ((1, 12) , Lit)))

example2 :: SourceExpr
-- if Var then Lit else Con
example2 = ((1, 1) , EIf ((1, 4) , EVar ((1, 4) , Var)) ((1, 7) , ELit ((1, 12) , Lit)) ((1, 16) , ECon ((1, 12) , Var)))

example3 :: SourceExpr
-- if Var
-- then Con
-- else Lit
example3 = ((1, 1) , EIf ((1, 4) , EVar ((1, 4) , Var)) ((2, 1) , ECon ((2, 6) , Var)) ((3, 1) , ELit ((3, 6) , Lit)))

为了进行测试，我还为 Eq等创建了数据类型。等，每个都有一个同名的构造函数。派生的 Pat实例可以令人满意地工作。

main = do
    print $ example1 == example1
    print $ example1 == example2
    print $ example1 == example3
    print $ example2 == example2
    print $ example2 == example3
    print $ example3 == example3

向前

From a long term of view, is it better to just stick with my original old plain AST types?

Haskell现有很少支持使用 Eq类型的模型或数据类型。如果您开始与他们合作，那么您首先需要的是一个数据模型 (* -> *) -> *的类，这些类是映射一些自然转换 d的仿函数。例如，您可以使用它从源表达式中删除注释。接下来，您需要的是用于数据模型的镜头式单板库，以及支持它的任何类似于 (forall a. f a -> g a) -> d f -> d g的工具。

您会迷失在鲜为人知的地方。有几种方法可以返回，但是我还没有完全考虑过其中两种方法。

如果您不喜欢 Applicative的派生实例的 UndecidableInstances要求，则可以删除显式递归，然后为用于 Expr递归出现的模型添加一个参数。这将与 Expr 的 PolyKinded版本兼容。

data Expr w e = ELam  [w (Pat w)]  (w (e w))
              | ELet  [w (Decl w)] (w (e w))
              | EIf   (w (e w)) (w (e w)) (w (e w))
              | ECase (w (e w)) [w (Alt w)]
              | EApp  (w (e w)) [w (e w)]
              | EVar  (w Var)
              | ECon  (w Var)
              | ELit  (w Lit)
              | ELOpSec (w Var) (w (e w))
              | EROpSec (w Var) (w (e w))
              | EInfix  (w (e w)) (w Var) (w (e w))
              | ENeg    (w (e w))

类型 MMorph仅出现在类型为 e的类型 e w中。如果我们将 *替换为 e w，则表明存在另一种更通用的类型，与具有良好现有库支持的类型更加一致。这个 a的种类为 Expr，这种情况更为常见。这是一种monad变压器。

data Expr w a = ELam  [w (Pat w)]  (w a)
              | ELet  [w (Decl w)] (w a)
              | EIf   (w a) (w a) (w a)
              | ECase (w a) [w (Alt w)]
              | EApp  (w a) [w a]
              | EVar  (w Var)
              | ECon  (w Var)
              | ELit  (w Lit)
              | ELOpSec (w Var) (w a)
              | EROpSec (w Var) (w a)
              | EInfix  (w a) (w Var) (w a)
              | ENeg    (w a)

无论哪种方式，您可能仍然想要与 (* -> *) -> (* -> *)兼容的镜头风格的单板库。