parsing - 如何正确地脱糖语法树？ - 减少数据结构定义/构造函数禁用

Question

我正在用 Haskell 开发一门新语言，我遇到了句法树 T 脱糖的问题。

我有一组函数f1, f2,... fn，它们从“糖”中简化树T。它们被分成不同的递归函数，因此代码更具可读性(每个函数都有一些特定的任务，并且比将它们实现为一个递归更容易理解它们在做什么)。

用于脱糖的组合函数如下所示

f :: T -> T
f = f1 . f2 . f3 . ... . fn

我读过(并且我认为)Haskell 中的最佳实践是，您以某种方式表示数据，它们不会得到错误/未定义/不可能的值。问题是，每个函数 f1,...,fn 基本上都通过某些构造函数减少了类型 T。 (例如，应用于 T 的 f1 删除了一些糖，由一些构造函数表示，这些构造函数不能出现在任何后续函数 f2,...,fn 中)。

因此，为了保持最佳实践，我必须以某种方式定义类型 T1, T2,..., Tn，其中

f1 :: T -> T1
f2 :: T1 -> T2
...
fn :: Tn-1 -> Tn

请问我该怎么做？ 我曾考虑使用 Haskell 模板，但在我看来这有点矫枉过正。 是否有一些多态性方法？能否在不牺牲代码可读性的情况下克服此实现？

为什么重要？

我说的是最佳实践，这可能会被社区认为是基于意见的，所以我进一步解释一下。

所有函数 f1, f2,...,fn 都依赖于它们的前任。但是，如果 T 类型从 f1, f2,...,fn 传入和传出，编译器

1. 发出许多关于模式匹配的警告(如果它们没有被错误“This shouldn't be possible”正确处理)

2. 我没有得到关于代码正确性的很好的编译检查。编译器不知道，我是否不做某事，这是不可能的。 (例如，使用已被删除的语法糖)

一个具体的例子

为简单起见，我们假设 Haskell 模板 Language.Haskell.TH.Exp。如果我想对语言处理使用相同的方法，我可能想将 f1 定义为函数，它替换所有 ArithSeqE ([ 1 ,2 .. 10 ]) 为 AppEs (f x) 生成算术序列。

现在，我想(以某种方式)从 Language.Haskell.TH.Exp - T1 中定义一个新类型，它禁止使用构造函数 ArithSeqE，因此编译器知道它不能在任何进一步的 T2,T3,...Tn 中，因此 f2,f3,...,fn 不必对其进行模式匹配，也无法使用它。

Answer 1

我只能解决您的部分问题。我希望即使是部分解决方案也能激发更好的想法。

我的想法是参数化你的总和类型，每个构造函数有一个类型参数，你可以消除。这个想法是，虽然构造函数将保留，但您可以对它们进行参数化，以便它们无人居住。这样一来，虽然编译器仍然会提醒您匹配不可能的构造函数，但您的脱糖步骤之一实际上不可能将这样的构造函数留在原地。

假设你有这种类型:

data Expr = Value Int
          | Pair Value Value
          | Values [Expr]

您可能有一个脱糖步骤，将每个 Pair 替换为一个双元素 Values 构造函数。首先，我们需要用单字段构造函数替换双字段构造函数:

data PairContents = PairContents Value Value
data Expr = Value Int
          | Pair PairContents
          | Values [Expr]

然后，我们添加一个类型参数，允许我们允许或禁止 PairContents:

newtype No x = No Void
data PairContents = PairContents Value Value
data Expr pairf = Value Int
                | Pair (pairf PairContents)
                | Values [Expr]

现在，删除所有 Pair 构造函数的重构步骤可以具有类型

desugarPairs :: Expr Identity -> Expr No

Expr No 不可能包含任何Pair 构造函数，因为它的Pair 字段的类型是No PairContents，它是 Void，因此无法居住。

正如我所说，我的方法存在几个问题。这意味着如果你有 10 个重构步骤，每个重构步骤都需要 10 个类型参数；你仍然需要在下一步中对 Pair 进行模式匹配，即使你知道这是不可能的。我希望有人能有更好的建议。但至少这完成了一些事情:可以依靠您的重构步骤去除了它们声称去除的所有糖分。