推理机中的规则和事实（循环？）定义

Question

我正在研究一个向后链接引擎作为一个学校项目。到目前为止，我主要用 C 语言完成项目，因此我决定为该项目尝试 Haskell。为了入门，我阅读了 LYAH，并开始在我的推理引擎中实现规则和事实的表示。到目前为止，这就是我得到的

module Inference () where

type Op = Bool -> Bool -> Bool
type Label = String
type Fact = (Label, [Rule])
data Rule = Operation Rule Op Rule
          | Fact Fact

eval_fact:: [Label] -> Fact -> Bool
eval_fact proved (label,rules) = label `elem` proved || any (eval_rule proved) rules

eval_rule:: [Label] -> Rule -> Bool
eval_rule proved (Fact x) = eval_fact proved x
eval_rule proved (Operation r op r') =  eval_rule proved r `op` eval_rule proved r'

想法是拥有某种图形，其中事实节点指向规则节点，除非事实已经在已知事实列表中。

但是，在这里我遇到了定义我的事实和规则的问题。

做类似

的事情

let fact_e = ("E", [Fact ("C", [(Operation (Fact ("A", [])) (||) (Fact ("B", [])))])])

在ghci中为了表示规则

C => E
A || B => C

行得通。但我真的不知道以编程方式构建这些规则的方向是什么。此外，我看不出如何使用该方案处理循环规则（例如添加规则 E => A）。

我在 Haskell wiki 上看到有一些方法可以使用名为 "Tying the knot" 的技巧在 haskell 中定义自引用数据结构，但我不知道如何 (或者即使）我应该在目前的情况下应用它。

我的问题本质上是，我是在朝着正确的方向前进，还是完全倒退了？

P.S ：在我看来，我的代码也没有达到应有的简洁程度（绕过 [Label] 列表，重复 eVal_rule proved 多次...），但是我真的不知道如何用另一种方式做到这一点。

Answer 1

想法是首先将规则解析为不是自引用的中间表示。例如，给定表示：

type Program = [(Label, [Rule_P])]
data Rule_P = Operation_P Rule_P Op Rule_P | Fact_P Label

那么规则集：

C => E
A || B => C
E => A
F => E

会被隐含目标解析、聚集，表示为：

prog1 :: Program
prog1 = [ ("E", [ Fact_P "C"                                       -- C => E
                , Fact_P "F" ])                                    -- F => E
        , ("C", [ Operation_P (Fact_P "A") (||) (Fact_P "B") ])    -- A || B => C
        , ("A", [ Fact_P "E" ]) ]                                  -- E => A

然后，将其转换为循环 self-referential 知识库（使用您原来的 Fact 类型）：

type Knowledge = [Fact]

你这样打结：

learn :: Program -> Knowledge
learn program = knowledge

  where

    knowledge :: [Fact]
    knowledge = [ (target, map learn1 rules_p) | (target, rules_p) <- program ]

    remember lbl = fromJust (find ((==lbl) . fst) knowledge)

    learn1 :: Rule_P -> Rule
    learn1 (Fact_P lbl) = Fact (remember lbl)
    learn1 (Operation_P rule1 op rule2) = Operation (learn1 rule1) op (learn1 rule2)

这也许值得一些解释。我们通过简单地应用 learn1 来创建 knowledge，将原始程序中每个出现的非 self-referential Rule_P 转换为 self-referential Rule知识库。函数 learn1 以明显的递归方式执行此操作，并且它 "ties the knot" 在每个 Fact_P 通过查找（remembering） [=18= 主体中的标签] 我们正在定义中。

无论如何，为了向自己证明它是 self-referential，您可以在 GHCi 中使用它：

> know1 = learn prog1
> Just [Operation factA _ _] = lookup "C" know1
> Fact ("A", [factE]) = factA
> Fact ("E", [factC, _]) = factE
> Fact ("C", [Operation factA' _ _]) = factC
> Fact ("A", [factE']) = factA'

当然，尝试：

> eval_fact [] $ fromJust $ find ((=="E").fst) (learn prog1)

将循环直到它用完内存，因为它试图（不成功地）从 C 从 A 从 E 证明 E，等等，所以你需要添加一些逻辑来中止循环证明。

推理机中的规则和事实（循环？）定义

Rules and Facts (cyclic ?) definition in an inference engine

haskell

recursive-datastructures

cyclic-reference

inference-engine