haskell - 正确标记 AST

Question

一段时间以来，我一直在尝试构建标记的 AST。先介绍一下问题:

data E a
  = V a
  | LitInt Int
  | LitBool Bool
  | FooIntBool (E a) (E a) -- er…
    deriving (Eq,Show)

对我来说，这段代码的问题在于 FooIntBool .这个想法是它需要一个 int 表达式和一个 bool 表达式，并将它们粘合在一起。但是 E a可以是任何东西。鉴于上述 E 的定义，这将是有效的。 :

FooIntBool (LitInt 3) (LitInt 0)

你可以看到问题。那么，我们想要什么？带标签的表达式。鉴于 E 的当前定义，这是不可能的，所以让我们介绍一些 GADT:

data E :: * -> * -> * where
  V          :: a -> E l a
  LitInt     :: Int -> E Int a
  LitBool    :: Bool -> E Bool a
  FooIntBool :: E Int a -> E Bool a -> E (Int,Bool) a

这是相当不错的!我现在可以纠正这种代码:

FooIntBool (V "x") (LitBool False)

问题是当我想让它成为单子(monad)或应用程序时。这是不可能的。考虑 monad 的实现:

instance Monad (E l) where
  return = V

这是显而易见的，直截了当。让我们看看绑定(bind)实现:

  V x >>= f = f x -- obvious as well
  LitInt a >>= _ = LitInt a -- obvious yeah
  LitBool a >>= _ = LitBool a -- …
  FooIntBool a b >>= f = FooIntBool (a >>= ?) (b >>= ?) -- AH?

我们不能写 a >>= f和 b >>= f自从 f :: a -> E l b .我还没有找到解决这个问题的方法，我真的很好奇如何处理这个问题并且仍然能够使用 de Bruijn 索引(通过绑定(bind))。

Answer 1

我认为您键入的 AST 不太可能按照您想要的方式工作。变量没有类型化的事实会受到伤害。试着想象用环境编写解释器会是什么样子；您必须在环境中查找变量，然后要么将结果转换为正确的类型，要么因错误而失败。所以我将建议一个稍微不同的带有类型变量的 AST，以及一个尚未解释的类型参数的重新排序。

data E v a where
  V          :: v a -> E v a
  LitInt     :: Int  -> E v Int
  LitBool    :: Bool -> E v Bool
  FooIntBool :: E v Int -> E v Bool -> E v (Int, Bool)

现在，据我所知，不可能定义一个守法的 Monad例如这个。注意 E 的种类是 (* -> *) -> * -> * ;对于我们的目的而言，将其视为 (* -> *) -> (* -> *) 可能更直观。 .这在表面上与 Monad 兼容。预计， * -> * ，至少如果您部分申请 E对一些 v ，但随后类型变得很奇怪。我相信您已经意识到这一点，这就是您将变量类型参数放在最后的原因；这样做的预期效果是 (>>=)将代表替换。但是，如果我们使用我提出的这种新类型来做到这一点，它与 Monad 不兼容。一点也不。

不过，有一种不同的 monad 可以工作。我们可以从 * -> * 概括它的种类至 (k -> *) -> (k -> *) (其中 k 在这种情况下只是 * )。再次注意，我使用括号来强调这一点，就像 Monad 的大多数实例一样。 , E将被视为一元类型构造函数。我们将使用自然变换而不是任何旧的 Haskell 函数:

type a ~> b = forall x. a x -> b x

(顺便说一下， (~>) 的种类是 (k -> *) -> (k -> *) -> *。)

构建我们的新 HMonad类型类，我们可以复制 Monad并替换 (->)与 (~>) .有一个复杂之处，那就是我们必须颠倒 (>>=) 的参数顺序。 , 使类型工作:

class HMonad m where
  hreturn ::  a ~> m a
  hbind   :: (a ~> m b) -> (m a ~> m b)

我会告诉你 HMonad E 的实例然后尝试解释它:

instance HMonad E where
  hreturn = V
  hbind f e = case e of
    V v            -> f v
    LitInt x       -> LitInt x
    LitBool x      -> LitBool x
    FooIntBool a b -> FooIntBool (hbind f a) (hbind f b)

实际上，这看起来与 Monad 完全一样。实例将用于 AST 的无类型版本。请注意，正如预期的那样， hreturn只注入(inject)一个变量， hbind通过寻找变量并将函数应用于它们来执行一种类型安全的替换。这是由于较高等级的类型而起作用的。

你不能完全用绑定(bind)包做到这一点，因为它使用 Monad而不是这个鸽友 HMonad .有可能(甚至已经多次完成)编写一个适用于这样的类型化 AST 的 bound 版本，但尚不清楚它是否真的值得。