代码之家 › 专栏 › 技术社区 › Jivan

Haskell中用于DSL的智能链运算符

dsl operators haskell

Jivan · 技术社区 · 4 年前

我有一个 State sum类型,我需要评估这些状态列表中序列的有效性:

data State = Running | Idle | Stopped | Heating | Broken | Paused | Starting | Stopping
seq = [Stopped, Starting, Running, Paused, Running, Idle, Stopping, Stopped]

对于每一个元素 seq ,我需要评估它是否与前面的一个或多个项目兼容 i 属于 seq ,检查以下值 seq !! (i-1) 以及(可选) seq !! (i-2) .

然而,为了可读性和维护目的,我试图构建一个基于链式运算符的迷你DSL,这样对于中的每个元素 seq ,我可以根据它之前的顺序来评估它是否有效。

以下是一个玩具示例:

-- current/naive implementation
-- (real-world follows the same model but is much more complex)
isValid :: [State] -> Int -> Bool
isValid seq i =
      ite (curr == Running)    (prev1 `elem` [Starting, Idle, Paused])
    $ ite (curr == Idle)       (prev2 `elem` [Paused] && prev1 `elem` [Running])
    $ ite (curr == Broken)     (prev3 `elem` [Running] && prev2 `elem` [Heating] && prev1 `elem` [Heating])
    $ False
    where curr  = seq !! i
          prev1 = seq !! (i-1)
          prev2 = seq !! (i-2)

-- "ideal" implementation using a (|>) chaining operator
-- (with some syntactic liberties)
isValid :: [State] -> Int -> Bool
isValid seq i =
      Running  =>  [Starting, Idle, Paused]
    $ Idle     =>  [Paused]  |> [Running]
    $ Broken   =>  [Running] |> [Heating] |> [Heating]
    where (=>) curr prev   = -- ...
          (|>) prev1 prev2 = -- ...

我最挣扎的部分是,如何确保 (|>) 了解是否需要查找 i-1 vs i-2 或 i-3 取决于它被锁住的次数,所以:

[Starting]                         -- seq !! (i-1) == Starting
[Starting] |> [Running]            -- seq !! (i-2) == Starting && seq !! (i-1) == Running
[Starting] |> [Running] |> [Idle]  -- seq !! (i-3) == Starting && seq !! (i-2) == Running && seq !! (i-1) == Idle

我并不特别喜欢以下内容 确切地 与上面的“理想”版本一样多的句法糖,但任何接近它的想法或方法都会受到欢迎。

0 回复 | 直到 4 年前

Li-yao Xia 4 年前

你的DSL是一种语言谓词 (他们说某事是真是假) 上下文 (它们根据输入的不同部分进行评估)。

特别是 上下文 由输入和其中的索引组成:

type Context = ([State], Int)
type Predicate = Context -> Bool

然后,我们可以自上而下地研究语言,检查 isValid 从根。首先,它是一系列谓词。正如您所注意到的,每一行都是一个逻辑含义,如果任何含义被破坏,您希望谓词失败。所以我们从谓词的连词开始:

infixr 4 &&.
(&&.) :: Predicate -> Predicate -> Predicate
p &&. q = \c -> p c && q c

含义可以类似地定义,相应的布尔运算与 Ord 操作 (<=) .

(=>.) :: Predicate -> Predicate -> Predicate
p =>. q = \c -> p c <= q c

在您提出的语法中 (=>) 实际上不是 Predicate ,但是a State 。你可以把它分解成二进制运算 (=>.) 在我们刚刚定义的谓词上,加上一个将状态视为谓词的操作。当你写作时 Running => ... ,你试图说“如果当前状态是 Running 那么。。。“那么一个州 s 对应于谓词“当前状态为 s ":

current :: State -> Predicate
current s = \(seq, i) ->
  -- Naive version: (seq !! i) == s
  index i seq == Just s

-- Total indexing function
index :: Int -> [a] -> Maybe a
index i seq = listToMaybe (drop i seq)

我们还想先谈谈当前的州。一种方法是转换谓词,在指向前一状态的修改后的上下文中对其进行求值:

prev :: Predicate -> Predicate
prev p = \(seq, i) -> p (seq, i-1)

在右侧,您还有状态列表,这意味着如果当前状态是其中任何一个,则有一个匹配的谓词:

currentIn :: [State] -> Predicate
currentIn ss = \(seq, i) ->
  case index i seq of
    Nothing -> False
    Just s -> s `elem` ss

有了所有这些基本的构建块,我们可以构建更高级的组合子,更接近你想要的语法。

(|>) 在列表中查找当前状态(第一个参数),并将其第二个参数向后移动:

infixr 9 |>
(|>) :: [State] -> Predicate -> Predicate
ss |> q = currentIn ss &&. prev q

-- End delimiter/identity element for `(|>)`
true :: Predicate
true = \_ -> True

(=>+) 是一个左侧有一个状态的含义,但也会移动第二个参数,开始直接查看前一个状态(避免保留语法 => )

infixr 8 =>+
(=>+) :: State -> Predicate -> Predicate
s =>+ q = current s &&. prev q

您的示例的相关操作是 (&&.) , (|>) , (=>+) ,我们可以注意运算符优先级,避免使用括号。

isValid :: Predicate
isValid =
        Running  =>+  [Starting, Idle, Paused] |> true
    &&. Idle     =>+  [Paused]  |> [Running] |> true
    &&. Broken   =>+  [Running] |> [Heating] |> [Heating] |> true

最后,我们需要从序列中生成所有相关上下文,以验证整个序列:

allContexts :: [State] -> [Context]
allContexts seq = [(seq, i) | i <- [0 .. length seq - 1]]

validate :: [State] -> Bool
validate seq = all isValid (allContexts seq)

这应该足以让事情正常进行,但人们可能会有一个很大的抱怨,那就是所有这些列表查找都很昂贵。将上下文的表示更改为更适合DSL操作的表示将更有效。值得注意的是,我们希望能够查看当前状态以及之前的状态。因此,更好的表示应该更直接地提供这些状态:

type Context = [State]  -- A reversed prefix of the whole sequence, so the current state is at the head, and other states precede it.
-- Example:
-- - Old context: ([a,b,c,d,e], 1)    ("the element at position 1 in the list [a,b,c,d,e]")
-- - New context: [b,a]

allContexts :: [State] -> [Context]
allContexts seq = init (tails (reverse seq))  -- non-empty prefixes, reversed

你必须更新所有的组合子,但 isValid 应该保持不变。(为读者练习。)

Daniel Wagner 4 年前

考虑反向处理您的列表,并使用 tails 以获取前缀。所以:

isValidPrefix :: [State] -> Bool
isValidPrefix seq = case seq of
    Running:prev:_ -> prev `elem` [Starting, Idle, Paused]
    Idle:Paused:Running:_ -> True
    Broken:Running:Heating:Heating:_ -> True
    [] -> True -- presumably?
    [_] -> True -- also presumed
    _ -> False

isValidSequence :: [State] -> Bool
isValidSequence = all isValidPrefix . tails . reverse