我如何处理DSL中许多不同类型的操作？ [英] How can I handle operations over many different types in my DSL?

问题描述

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

  data MyType = A String 
 | B整数
 | C Bool 
 | D Double 
 { -  | E .. Z  - } 
 
 class BinaryOps a其中
 f :: a  - > a  - > a 
 g :: a  - > a  - > a 
 h :: a  - > a  - > a 
 j :: a  - > a  - > a 
 { - 更多二进制操作 - } 
 
实例BinaryOps MyType其中
f（A s1）（A s2）= { -  s1和s2上的Haskell表达式 - } 
f（A s1）（B s2）= { -  ...  - } 
f（B s1）（D s2）= { -  ...  - } 
f _ _ =错误f不支持参数类型
 
g（D s1）（A s2）= { -  s1和s2上的Haskell表达式 - } 
g（D s1）（C s2）= { -  ...  - } 
g _ _ =错误g不支持参数类型
 
h（B s1）（B s2）= { -  s1和s2上的Haskell表达式 - } 
h（B s1）（C s2）= { -  ...  - } 
h（B s1）（D s2）= { -  ...  - } 
h（C s1）（B s2）= { - 。 （D s1）（C s2）= { -  ...  - } $ b $（D s1）（D s2）= { -  ...  - } 
h _ _ =错误h不支持参数类型
  

DSL有很多二进制表达式，类型。上面的解决方案不能很好地扩展：类定义将会很大，并且DSL类型的不支持的不良类型组合的数量将会增加（ error >调用）。

有没有更好的方法来使用类型类来解释DSL中的二进制表达式？或者的确，有没有像GADT那样提供更具扩展性的解决方案？

我不明白你为什么要使用首先是一个typeclass。

只要将二元运算符定义为Haskell二元运算符，它们就是正常函数：

  f :: MyType  - > MyType  - >由于所有的DSL类型都在 MyType ，没有理由使用类型类型。
 
 
 
打包和解包
 
 
 
当然，这仍然不能解决你的错误问题。我过去采用的一种方法是使用类型类来定义将原始类型打包和提取到DSL中的方法： 
 
 
  class Pack a where 
 pack :: a  - > MyType 
 
 class Extract a where 
 extract :: MyType  - > a 
  
以下是 String 的实例看起来像：
 实例包字符串其中pack = A 
实例提取字符串其中
提取（A str ）= str 
 extract _ = error类型错误：期望的字符串！ 
  
  Extract 类可以处理错误处理对于不兼容的类型。
 
 
 
这可以让您统一地将提升功能放入您的DSL中： 
 
 
   - 将二元Haskell函数提升到您的DSL 
 lift ::（提取a，提取b，包c）=> （a  - > b  - > c）
  - > MyType  - > MyType  - > MyType 
 lift fab = pack $ f（extract a）（extract b）
  
如果你make  MyType   Pack 和 Extract 的一个实例，这将会对于纯粹的Haskell函数和函数都可以识别你的DSL。也就是说，知道的函数只会得到某种 MyType ，并且必须手动处理它，调用 error 如果他们的 MyType 参数不符合他们的预期。
 
 
 
所以这解决了您的错误可以直接写入Haskell的函数的问题，但对于那些依赖于 MyType 的函数而言并不是真的。
 
 
 
错误处理
 
 
 
使用 pack 也很好，因为切换到更好的错误非常简单 - 处理机制比错误。您只需切换提取（或者甚至 pack ，如果适用）的类型。也许你可以使用： 
 
 
  class Extract a where 
 extract :: MyType  - > MyError a 
  
，然后失败并返回 Left（TypeError expected got） code>这可以让你写出漂亮的错误信息。
 
 
 
这也可以让你轻松地将多个原始函数组合成 > MyType 级别。基本思想是我们将多个可升级的函数组合成一个 MyType  - > MyType  - > MyType 和内部我们只是使用第一个不会给我们一个错误。这可以给我们一些漂亮的语法：）。
 
 
 
以下是相关代码： 
 
 
 键入MyFun = MyType  - > MyType  - > MyError MyType 
 
（| :) ::（Extract a，Extract b，Pack c）=> MyFun  - > （a→b→c）→> MyFun 
（f |：option）a b =大小写b 
右分辨率 - >返回res 
 Left err  - > （lift选项）ab 
 $ b $ match :: MyFun 
 match _ _ = Left EmptyFunction 
 
 test = match |：（\ ab  - > a ++ b :: String）
 |：（\ ab  - > a || b）
  
 
 
 <不幸的是，我不得不添加一个 :: String 类型的签名，否则它是不明确的。如果我使用 + ，也会发生同样的情况，因为它不知道依赖的数字是什么。
 
 
 
现在 test 是一个在两个 A  s或两个 B  s并给出错误，否则： 
 
 
  * Main>测试（Afoo）（Afoo）
正确（Afoofoo）
 *主要> test（C True）（C False）
 Right（C True）
 * Main> test（Afoo）（C False）
 Left TypeError 
  
另请注意，在不同的类型的参数上可以很好地工作，例如可以结合 A 和 B 值。
 
 
 
这意味着您现在可以方便地重新设定您的 f ， g ， h 等作为Haskell中的顶级名称。以下是您如何定义 f ：
  f :: MyFun 
f = match |：\ s1 s2  - > { - 有字符串的东西 - } 
 |：\ s我 - > { - 有字符串和int的东西 - } 
 |：\我d  - > { - 有int和double的东西 - } 
 |：{ -  ...等等...  - } 
  
有时您需要使用类型签名来注释某些值，因为没有足够的信息来使类型推断正常工作。只有在使用类型类操作时（例如 + ），或者使用像 ++ 的字符串（ ++ 可以在任何列表中使用）。 
 
 
 d还必须更新 lift 以正确处理错误。这涉及将其更改为返回任一并添加必要的管道。我的版本看起来像这样：
  lift ::（Extract a，Extract b，Pack c）=> （a→b→c）→> MyFun 
 lift f a b = fmap pack $ f< $>提取一个< *>提取b 
  
 
 
 
 Newtypes 
 
 
 
你的错误问题通过让 |：构造为你检查错误。这种方法的主要缺点是，如果您希望您的DSL具有多个类型相同的基础类型 Haskell类型，它将无法很好地工作：
  data MyType =双
 | B Double 
 { -  ...  - } 
  
您可以通过使用 newtype 来为 Double 创建一个包装。就像这样：
  newtype BDouble = B Double 
 
实例包Double其中pack = A 
 
实例包装双倍其中包= B 
 
  - 提取相同
  
 
Suppose Haskell is to be used to implement an interpreter for a domain specific language. The DSL has a large number of type, represented as data constructors, and a large number of binary expressions. A naive first attempt would be a type class BinaryOps encapsulating all binary operations over MyType in the 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"
The DSL will have many binary expressions, and many built-in types. The solution above won't scale particularly well: The class definition will be large, and the number of "unsupported" ill-typed combinations of DSL types will grow (the error calls).

Is there a more elegant way to use type classes for interpreting the binary expressions in the DSL? Or indeed, is there something like GADTs that provides a more scalable solution?
解决方案
I don't see why you're using a typeclass in the first place. What does a typeclass gain you over just having normal functions?

Just define binary operators as, well, Haskell binary operators which are just normal functions:
f :: MyType -> MyType -> MyType
f = ...
Since all your DSL types are in MyType, there's no reason to use a typeclass.

Packing and Unpacking

Of course, this still doesn't solve your error problem. One approach I've taken in the past is to use typeclasses to define ways to "pack" and "extract" primitive types into your DSL:
class Pack a where
  pack :: a -> MyType

class Extract a where
  extract :: MyType -> a
Here's what the instance for String would look like:
instance Pack String where pack = A
instance Extract String where
  extract (A str) = str
  extract _       = error "Type error: expected string!"
The Extract class can deal with error handling for incompatible types.

This lets you uniformly "lift" functions into your 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)
If you make MyType an instance of Pack and Extract, this will work for both purely Haskell functions and functions aware of your DSL. That said, the aware functions will just get some sort of MyType and will have to deal with it manually, calling error if their MyType argument isn't what they expected.

So this solves your error problem for functions you can write in straight Haskell but not really for ones that depend on MyType.

Error Handling

Using pack is also nice because it's pretty straightforward to switch to a better error-handling mechanism than error. You would just switch the type of extract (or even pack, if appropriate). Maybe you could use:
class Extract a where
  extract :: MyType -> Either MyError a
and then fail with Left (TypeError expected got) which would let you write nice error messages.

This would also let you easily combine multiple primitive functions into "cases" at the MyType level. The basic idea is that we combine multiple liftable functions into a single MyType -> MyType -> MyType and internally we just use the first one that doesn't give us an error. This can also give us some pretty looking syntax :).

Here's the relevant code:
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)
Unfortunately, I had to add a :: String type signature because it was ambiguous otherwise. The same would happen if I use +, since it doesn't know what kind of number to rely on.

Now test is a function which works correctly on two As or two Bs and gives an error otherwise:
*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
Also note that this would work perfectly happily on different types of arguments, like a case which could combine A and B values.

This means that you can now conveniently recast your f, g, h and so on functions as top-level names in Haskell. Here is how you could define 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... -}
You will sometimes have to annotate some of the values with type signatures because there isn't always enough information to make type inference work properly. This should only come up if you use operations from typeclasses (ie +) or use operations with more general types like ++ for strings (++ can work on any lists).

You'd also have to update lift to handle the errors properly. This involves changing it to return an Either and adding the necessary plumbing. My version looks like this:
lift :: (Extract a, Extract b, Pack c) => (a -> b -> c) -> MyFun
lift f a b = fmap pack $ f <$> extract a <*> extract b


Newtypes

This mostly solves your error problem by having the |: construct check errors for you. The main weakness with this approach is that it won't work very well if you want your DSL to have multiple types that have the same underlying Haskell type like:
data MyType = A Double
            | B Double
            {- ... -}
You could fix this by using newtype to create a wrapper for Double. Something like this:
newtype BDouble = B Double

instance Pack Double where pack = A

instance Pack BDouble where pack = B

-- same for Extract


                        
这篇关于我如何处理DSL中许多不同类型的操作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！