scala - 使用内部 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 特性。无论如何我都会展示它。

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

现在我们使用重载的 Num 方法和 runShallow::Shallow -> Int

编写并执行我们的 Shallow DSL

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

值得注意的是，由于此浅嵌入中的所有内容都是在内部表示的，除了结果之外几乎没有任何结构，因为所有工作都已下降到我们的领域语言无法“看到”的宿主语言“它。

深度嵌入明确区分了 DSL 的表示和解释。通常，表示它的一种好方法是 ADT，它具有与最小基础 API 匹配的分支和参数。我们将只反射(reflect)整个 Num 类

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

值得注意的是，此表示将承认平等(请注意，这是可能的最小平等，因为它忽略了“值”和“等价”)并显示，这很好。我们通过实例化 Num

将它绑定(bind)到相同的内部 API

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

但现在我们必须创建一个解释器，将深度嵌入与宿主语言表示的值联系起来。这里出现了 Deep 嵌入的优势，因为我们可以轻松地引入多个解释器。例如，“showing”可以被认为是从 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

最后，我们不仅可以将事物解释为 Int，还可以将其解释为遵循 Num API 的任何其他事物

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)

最后，我们可以使用我们的 Deep ADT 来实现优化

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)