模式匹配重写内部DSL？

Question

我的问题是关于DSL设计.它与内部与外部DSL有关,但更具体.背景信息:我已经完成了DSL in Action和其他教程.内部和外部之间的区别对我来说很清楚.我也有在Haskell开发外部DSL的经验.

我们来看一个非常简单的例子.下面是(简化的)关系代数表达式:

SELECT conditions (
  CROSS (A,B)
)

代数表达式(Haskell中的ADT)可以很容易地重写.例如,这可以简单地重写为:

JOIN conditions (A,B)

在我开发的DSL中,我总是采用这种方法:编写一个解析器来创建像上面那样的代数表达式.然后,使用允许像Haskell一样进行模式匹配的语言,应用一些重写并最终转换为目标语言.

这是问题所在.

对于我想开发的新DSL,我宁愿选择内部DSL.主要是因为我想利用宿主语言功能(在这种情况下可能是Scala).关于这是否是正确选择的争论不是重点.让我们假设它是一个不错的选择.

我想念的是:如果我选择内部DSL,那么就无法解析ADT.我喜欢的模式匹配重写在哪里适合这个？我必须放弃它吗？是否有最佳实践来充分利用这两个世界？或者我没有在这里看到正确的东西？

Answer 1

我将使用Haskell中的算术内部表达式语言来演示这一点.我们将实施双重否定消除.

内部DSL"嵌入"要么深或浅.浅嵌入意味着您依赖来自宿主语言的共享操作来运行域语言.在我们的例子中,这几乎消灭了我们问题的DSL-ness.无论如何我会展示它.

newtype Shallow = Shallow { runShallow :: Int }

underShallow1 :: (Int -> Int) -> (Shallow -> Shallow)
underShallow1 f (Shallow a) = Shallow (f a)

underShallow2 :: (Int -> Int -> Int) -> (Shallow -> Shallow -> Shallow)
underShallow2 f (Shallow a) (Shallow b) = Shallow (f a b)

-- DSL definition
instance Num Shallow where
  fromInteger n = Shallow (fromInteger n)   -- embed constants

  (+) = underShallow2 (+)         -- lifting host impl into the DSL
  (*) = underShallow2 (*)
  (-) = underShallow2 (-)
  negate = underShallow negate
  abs    = underShallow abs
  signum = underShallow signum

所以现在我们Shallow使用重载Num方法编写和执行我们的DSLrunShallow :: Shallow -> Int

>>> fromShallow (2 + 2 :: Shallow)
4

值得注意的是,因为这个Shallow嵌入中的所有内容都在内部表示,除了结果之外几乎没有任何结构,因为所有的工作都被下拉到我们的域语言无法"看到"它的宿主语言.

深度嵌入清楚地区分了DSL 的表示和解释.通常,表示它的一种好方法是ADT,它具有与最小基础API匹配的分支和arities.我们只是反映整个Num班级

data Deep
  = FromInteger Integer
  | Plus Deep Deep
  | Mult Deep Deep
  | Subt Deep Deep
  | Negate Deep
  | Abs Deep
  | Signum Deep
deriving ( Eq, Show )

值得注意的是,这种表示将承认相等(请注意,这是可能的最小相等,因为它忽略了"值"和"等价")并显示,这很好.我们通过实例化将它绑定到相同的内部APINum

instance Num Deep where
  fromInteger = FromInteger
  (+) = Plus
  (*) = Mult
  (-) = Subt
  negate = Negate
  abs    = Abs
  signum = Signum

但是现在我们必须创建一个解释器,它将深度嵌入与宿主语言中表示的值联系起来.这里Deep嵌入的一个优点在于我们可以简单地引入多个解释器.例如,"显示"可以被认为是从解释器Deep到String

interpretString :: Deep -> String
interpretString = show

我们可以将嵌入常量的数量计算为解释器

countConsts :: Deep -> Int
countConsts x = case x of
  FromInteger _ = 1
  Plus x y = countConsts x + countConsts y
  Mult x y = countConsts x + countConsts y
  Subt x y = countConsts x + countConsts y
  Negate x = countConsts x
  Abs x    = countConsts x
  Signum x = countConsts x

最后,我们可以将事物解释为不仅仅是API之后的Int任何其他事物Num

interp :: Num a => Deep -> a
interp x = case x of
  FromInteger n = fromInteger n
  Plus x y = interp x + interp y
  Mult x y = interp x * interp y
  Subt x y = interp x - interp y
  Negate x = negate (interp x)
  Abs x    = abs (interp x)
  Signum x = signum (interp x)

所以,最后,我们可以创建一个深度嵌入并以多种方式执行它

>>> let x = 3 + 4 * 5 in (interpString x, countConsts x, interp x)
(Plus (FromInteger 3) (Mult (FromInteger 4) (FromInteger 5)), 3, 23)

而且,这是结局,我们可以使用我们的DeepADT来实现优化

opt :: Deep -> Deep
opt x = case x of
  (Negate (Negate x)) -> opt x
  FromInteger n = FromInteger n
  Plus x y = Plus (opt x) (opt y)
  Mult x y = Mult (opt x) (opt y)
  Subt x y = Sub (opt x) (opt y)
  Negate x = Negate (opt x)
  Abs x    = Abs (opt x)
  Signum x = Signum (opt x)