haskell - 如何在我的 DSL 中处理许多不同类型的操作？

Question

假设 Haskell 将用于为特定领域语言实现解释器。 DSL 有大量的类型，表示为数据构造函数，以及大量的二进制表达式。天真的第一次尝试是类型类 BinaryOps封装 MyType 上的所有二元运算在 DSL 中:

data MyType = A String
            | B Integer
            | C Bool
            | D Double
         {- | E .. Z -}

class BinaryOps a where
    f :: a -> a -> a
    g :: a -> a -> a
    h :: a -> a -> a
    j :: a -> a -> a
    {- many more binary ops -}

instance BinaryOps MyType where
    f (A s1) (A s2) = {- Haskell expression on s1 and s2 -}
    f (A s1) (B s2) = {- ... -}
    f (B s1) (D s2) = {- ... -}
    f _ _ = error "f does not support argument types"

    g (D s1) (A s2) = {- Haskell expression on s1 and s2 -}
    g (D s1) (C s2) = {- ... -}
    g _ _ = error "g does not support argument types"

    h (B s1) (B s2) = {- Haskell expression on s1 and s2 -}
    h (B s1) (C s2) = {- ... -}
    h (B s1) (D s2) = {- ... -}
    h (C s1) (B s2) = {- ... -}
    h (D s1) (C s2) = {- ... -}
    h (D s1) (D s2) = {- ... -}
    h _ _ = error "h does not support argument types"

DSL 将有许多二进制表达式和许多内置类型。上面的解决方案不能很好地扩展:类定义会很大，“不受支持”的 DSL 类型的错误类型组合的数量会增加( error 调用)。

有没有更优雅的方法来使用类型类来解释 DSL 中的二进制表达式？或者确实，是否有类似 GADT 的东西提供了更具可扩展性的解决方案？

Answer 1

我不明白你为什么首先使用类型类。一个类型类比仅仅拥有正常的功能有什么好处？

只需将二元运算符定义为 Haskell 二元运算符，它们只是普通函数:

f :: MyType -> MyType -> MyType
f = ...

由于您所有的 DSL 类型都在 MyType 中，没有理由使用类型类。

包装和拆包

当然，这还是不能解决你的 error问题。我过去采用的一种方法是使用类型类来定义将原始类型“打包”和“提取”到您的 DSL 中的方法:

class Pack a where
  pack :: a -> MyType

class Extract a where
  extract :: MyType -> a

这是 String 的实例看起来像:

instance Pack String where pack = A
instance Extract String where
  extract (A str) = str
  extract _       = error "Type error: expected string!"

Extract类可以处理不兼容类型的错误处理。

这让您可以统一地将功能“提升”到您的 DSL 中:

-- Lifts binary Haskell functions into your DSL
lift :: (Extract a, Extract b, Pack c) => (a -> b -> c)
          -> MyType -> MyType -> MyType
lift f a b = pack $ f (extract a) (extract b)

如果您制作 MyType Pack 的一个实例和 Extract ，这将适用于纯粹的 Haskell 函数和了解您的 DSL 的函数。也就是说，感知函数只会得到某种 MyType并且必须手动处理，调用 error如果他们的 MyType争论不是他们所期望的。

所以这解决了你的 error您可以直接用 Haskell 编写函数的问题，但对于依赖于 MyType 的函数则不然。 .

错误处理

使用 pack也很好，因为切换到比 error 更好的错误处理机制非常简单。 .您只需切换 extract 的类型即可(甚至 pack ，如果合适的话)。也许你可以使用:

class Extract a where
  extract :: MyType -> Either MyError a

然后失败 Left (TypeError expected got)这会让你写出漂亮的错误消息。

这还可以让您轻松地将多个原始函数组合到 MyType 处的“案例”中。等级。基本思想是我们将多个可提升功能组合成一个 MyType -> MyType -> MyType在内部我们只使用第一个不会给我们错误的。这也可以为我们提供一些漂亮的语法:)。

这是相关的代码:

type MyFun = MyType -> MyType -> Either MyError MyType

(|:) :: (Extract a, Extract b, Pack c) => MyFun -> (a -> b -> c) -> MyFun
(f |: option) a b = case f a b of
  Right res -> return res
  Left err  -> (lift option) a b 

match :: MyFun
match _ _ = Left EmptyFunction

test = match |: (\ a b -> a ++ b :: String)
             |: (\ a b -> a || b)

不幸的是，我不得不添加一个 :: String类型签名，因为否则它是不明确的。如果我使用 + 也会发生同样的情况，因为它不知道要依赖什么样的数字。

现在 test是一个可以在两个 A 上正常工作的函数s 或两个 B s 并给出错误，否则:

*Main> test (A "foo") (A "foo")
Right (A "foofoo")
*Main> test (C True) (C False)
Right (C True)
*Main> test (A "foo") (C False)
Left TypeError

另请注意，这将在不同类型的参数上完美运行，例如可以组合 A 的情况。和 B值。

这意味着您现在可以方便地重铸您的 f , g , h等函数作为 Haskell 中的顶级名称。以下是您如何定义 f :

f :: MyFun
f = match |: \ s1 s2 -> {- something with strings -}
          |: \ s i   -> {- something with a string and an int -}
          |: \ i d   -> {- something with an int and a double -}
          |: {- ...and so on... -}

有时您必须用类型签名注释某些值，因为并不总是有足够的信息来使类型推断正常工作。仅当您使用来自类型类的操作(即 + )或使用更通用的类型(如 ++ )的操作时，才会出现这种情况。用于字符串( ++ 可以处理任何列表)。

您还必须更新 lift正确处理错误。这涉及将其更改为返回 Either并添加必要的管道。我的版本是这样的:

lift :: (Extract a, Extract b, Pack c) => (a -> b -> c) -> MyFun
lift f a b = fmap pack $ f <$> extract a <*> extract b

新类型

这主要解决了您的 error问题来自 |:为您构造检查错误。这种方法的主要弱点是，如果您希望 DSL 具有多个具有相同底层 Haskell 类型的类型，则它不会很好地工作，例如:

data MyType = A Double
            | B Double
            {- ... -}

您可以使用 newtype 解决此问题为 Double 创建一个包装器.像这样的东西:

newtype BDouble = B Double

instance Pack Double where pack = A

instance Pack BDouble where pack = B

-- same for Extract