逻辑编程入门--clojure.core.logic

野性酷女 2022-04-17 04:59 182阅读 0赞

此文已由作者张佃鹏授权网易云社区发布。

欢迎访问[网易云社区][Link 1]，了解更多网易技术产品运营经验。

#### 1. 逻辑编程思维： ####

逻辑编程（逻辑程序设计）是种编程范型，它设置答案须匹配的规则来解决问题，而非设置步骤来解决问题。过程是：

事实+规则=结果

简单的说，事实就是一些已知输入，规则是应该遵循的限定条件，输入和输出应该遵循一定的规则，然后找出所有满足这些规则的输出，便是结果。在逻辑编程时，我们没必要去关心寻找结果的过程，而注重的是输出结果。   逻辑编程的要点是将正规的逻辑风格带入计算机程序设计之中，数学家和哲学家发现逻辑是有效的理论分析工具，很多问题可以自然地表示成一个理论。说需要解答一个问题，通常与解答一个新的假设是否跟现在的理论无冲突等价。逻辑提供了一个证明问题是真还是假的方法。创建证明的方法是人所皆知的，故逻辑是解答问题的可靠方法。逻辑编程系统则自动化了这个程序，人工智能在逻辑编程的发展中发挥了重要的影响。

#### 2. clojure.core.logic概述： ####

clojure.core.logic是clojure一个库，专门为了实现逻辑编程，core.logic是miniKanren的一个实现。miniKanren中一个重要的概念就是goal，根据goal来推测可能的结果，这就是它的核心概念。   我们在使用core.logic编程时，获取逻辑编程的结果，一般都遵循以x下形式：

(run* [logic-variable]
           logic-expressions)
       ;;or
       (run n [logic-variable]
           logic-expressions)

run或者run函数可以执行逻辑表达式，返回满足条件的结果。返回的结果是一个关于logic-variable的数组。如果是run则返回所有满足逻辑表达式条件的逻辑变量，如果是run n，则返回前n个满足条件的变量。这里要注意的一点是：普通的逻辑表达式的返回结果只有两种：succeed/fail，如果找到满足条件的结果，则返回succeed，否则返回fail。只有使用run函数才能返回最终我们想要的输出结果。下面是run函数的使用示例：

;;首先要导入clojure.core.logic库
    (use 'clojure.core.logic)
    
    ;;使用run*，会返回所有满足条件的结果
    (run* [q]
         ;;这里是逻辑表达式，后面会讲到
         (conde
           [(== q 1)]
           [(== q 2)]
           [(== q 3)]
           ))
    ;;=>(1 2 3)
    
    ;;返回前两个结果
    (run 2 [q]
         (conde
           [(== q 1)]
           [(== q 2)]
           [(== q 3)]
           ))
    ;;=> (1 2)
    
    ;;如果n大于所有满足条件结果的总数，则与run*返回结果一致
    (run 4 [q]
         (conde
           [(== q 1)]
           [(== q 2)]
           [(== q 3)]
           ))
    ;;=> (1 2 3)

当然run函数也可以接收多个参数，如果是多个参数，则以数组的形式返回：

;;接收两个参数，最后返回结果是一个包含数组的序列
    (run* [q1 q2]
          (== q1 1)
          (== q2 1)
          )
    ;;=> ([1 1])

#### 3. 逻辑表达式以及常用函数： ####

逻辑表达式的返回结果都是succeed或者fail，一个逻辑表达式中可以继续嵌套另外一个逻辑表达式，下面在介绍clojure中的常用逻辑函数同时穿插的介绍如何使用逻辑编程：

##### （1）==/!=/membero函数: #####

"=="/"!="函数用于判断两个逻辑变量是否相等或者不相等，是最常用的逻辑函数，而(membero  x  l)函数则表示只有x属于数组l时才会返回succeed：

;;找出等于1的数字
    (run* [q] (== q 1))
    ;;=> (1)
    
    ;;找出不等于1且属于数组[1 2 3]中的数字
    ;;;;这里的(!= q 1)与(membero q [1 2 3])两个逻辑表达式是与的关系（也就是必须两个逻辑表达式同时满足才返回succeed）
    (run* [q] 
         (!= q 1)
         ;;q只有是数组[1 2 3]中的一个元素，才会返回succeed
         (membero q [1 2 3]))
    ;;=> (2 3)

##### （2）fresh函数： #####

这个函数在逻辑编程时特别重要，如果我们想在逻辑表达式中用到其他变量怎么办？怎么像其它语言一样去声明一个局部变量？？fresh函数正是来解决以上疑问的，fresh函数可以声明几个局部的逻辑变量，有了这些局部逻辑变量以后，您就可以在逻辑表达式中随意发挥了：

;;q是一个包含两个元素的数组，第一个元素等于1，第二个元素是[2 3 4]中的一个
    ;;fresh函数和run函数使用规则类似，都接收一个[参数]，参数后面是并列的表示与关系的逻辑表达式
    (run* [q]
          (fresh [q1 q2]
                 (== q1 1)
                 (membero q2 [2 3 4])
                 (== q [q1 q2])
                 ))
    => ([1 2] [1 3] [1 4])

##### （3）succeed/fail #####

这两个逻辑表达式也比较常用，succeed就表示执行成功的逻辑表达式，fail就表示执行失败的逻辑表达式，下面我们定义一个逻辑表达式函数，输入参数是一个逻辑表达式，然后返回该输入参数的相反的结果：

;;该函数返回参数g的相反结果：
    (defn l-not [g]
      (conda
        (g fail)
        (succeed)
        ))
    ;;=> #'insight.main/l-not;;在run*函数中使用l-not函数
    (run* [q]
          (l-not (== 3 1))
          (== q 1)
          )
    ;;=> (1)

##### （4）conde/conda/condu函数/all函数： #####

在介绍fresh函数和run函数时提到这两个函数的主体部分的表达式是“与”的关系，那么怎么可以表达“或”的关系呢，conde/conda/condu这三个函数都可表示“或”的关系，但三者之间又有细微的差别，都是很实用的函数。   这里之所以要把all函数和它们三个函数放在一起，是因为在conda和condu函数中，会经常使用all函数。

-->conde函数：接收逻辑表达式组，只要满足其中任意一个表达式组，多个表达式组之间是or的关系，不像其他语言中的or函数，conde函数不存在求值短路现象，会返回分别满足所有表达式组的结果：

;;返回满足等于1，或者同时等于2和3，或者是字符串"yes"/"no"的结果
    (run* [q]
          (conde
          ;;其中[]表示的是一组表达式，[]中逻辑表达式默认是“与”的关系，这里[]也可以用()替换，但是为了区别，最好用[]
            [(== q 1)]
            [(== q 2) (== q 3)]
            [(membero q ["yes" "no"])]
            ))
    ;;=> (1 "yes" "no")

-->conda函数：该函数返回第一个满足条件的表达式组中的所有结果，但是特别要注意的是，相邻两个表达式组之间切换的条件，也就是如果第n个表达式组返回fail的情况下，什么情况下去继续求解第n+1个表达式组，假设第n个表达式组中有3个表达式\[expr1  expr2  expr3\]，只有当expr1失败的情况下，才会执行第n+1个表达式组，否则即使expr1返回succeed，expr2返回fail，conda函数就会直接返回fail，不会执行第n+1个表达式组。   那么如果我们想要使只要expr1、expr2，expr3有一个不成立就会执行第n+1个表达式组，怎么办？？使用all函数，把这三个表达式包含进去。这里逻辑有点混乱，看代码会清楚很多：

;;情况1：conda函数中，第一个表达式组中两个表达式都返回succeed，所以直接返回（2 3），不去执行第二个表达式组
    (run* [q]
          (conda
            ;;表达式组1：
            [succeed
             (conde
               [(== q 2)]
               [(== q 3)]
               )]
             ;;表达式组2：
            [(membero q ["yes" "no"])]
            ))
    ;;=> (2 3)
    
    ;;情况2：第一个表达式组中第一个表达式返回fail，则会继续执行第二个表达式组，所以返回（"yes" "no"）
    (run* [q]
          (conda
          ;;表达式组1：
            [fail
            ;;表达式嵌套
             (conde
               [(== q 2)]
               [(== q 3)]
               )]
          ;;表达式组2：
            [(membero q ["yes" "no"])]
            ))
    ;;=> ("yes" "no")
    
    ;;情况3：第一个表达式组中第一个表达式返回succeed，但是整个表达式返回fail，则不会执行第二个表达式，直接返回fail
    (run* [q]
          (conda
            [succeed
             fail
             (conde
               [(== q 2)]
               [(== q 3)])
             ]
            [(membero q ["yes" "no"])]
            ))
    ;;=> ()
    
    ;;情况4：可以用all函数改变情况3的执行结果
    (run* [q]
          (conda
            [(all
               succeed
               fail
               (conde
                 [(== q 2)]
                 [(== q 3)]))
             ]
            [(membero q ["yes" "no"])]
            ))
    => ("yes" "no")

-->condu函数:condu函数是conda函数的子集，它只返回conda函数返回结果集中的结果：

;;情况1：返回结果是conda返回结果的第一个元素
    (run* [q]
          (condu
            ;;表达式组1：
            [succeed
             (conde
               [(== q 2)]
               [(== q 3)]
               )]
             ;;表达式组2：
            [(membero q ["yes" "no"])]
            ))
    ;;=> (2)
    
    ;;情况2：返回结果是conda返回结果的第一个元素
    (run* [q]
          (condu
          ;;表达式组1：
            [fail
             (conde
               [(== q 2)]
               [(== q 3)]
               )]
          ;;表达式组2：
            [(membero q ["yes" "no"])]
            ))
    ;;=> ("yes")
    
    ;;情况3：返回结果是conda返回结果的第一个元素
    (run* [q]
          (condu
            [succeed
             fail
             (conde
               [(== q 2)]
               [(== q 3)])
             ]
            [(membero q ["yes" "no"])]
            ))
    ;;=> ()

当然以上所有逻辑表达式都可以嵌套使用。

##### （5）matche/matcha/matchu函数： #####

这三个函数的第一个参数是一个元素，该元素用于匹配后面的表达式组中第一个元素，类似于其它语言中的case函数，如果匹配成功，则执行该表达式组中的其它表达式。该三个函数与conde/conda/condu相对应：matche返回使任意一个表达式组成立的所有元素，matcha只返回所有表达式组中第一个使条件成立的所有元素，而matchu返回所有表达式组中第一个使条件成立的第一个元素：   -->matche函数:

;;用p去匹配每个表达式组中的第一个元素（这里的第一个不能是表达式，只能是元素），匹配成功则会执行后面的表达式，有没有很像case的赶脚，抛去第一个元素以后的匹配规则与conde一模一样：
    (run* [q]
          (fresh [p]
                 (matche [p]
                         (['virgin] succeed fail)
                         (['olive]  (conde
                                      [(== q 1)]
                                      [(== q 2)]
                                      ))
                         (['oil] (== q 3)))
                 ))
    ;;=> (3 1 2)

-->matcha函数:

;;这里的matcha函数还是有一点与conda函数不一样的地方，matcha不会关心每个表达式组中第一个表达式是否匹配成功，就像加了all一样：
    (run* [q]
          (fresh [p]
                 (matcha [p]
                         ;;这里虽然第一个表达式成功，但是还是会匹配后面的表达式组
                         (['virgin] succeed fail)
                         (['olive]  (conde
                                      [(== q 1)]
                                      [(== q 2)]
                                      ))
                         (['oil] (== q 3)))
                 ))
    ;;=> (1 2)

-->matchu函数:

;;matchu则是返回所有可能匹配的第一个元素，执行规则与matcha类似：
    (run* [q]
          (fresh [p]
                 (matchu [p]
                         ;;这里虽然第一个表达式成功，但是还是会匹配后面的表达式组
                         (['virgin] succeed fail)
                         (['olive]  (conde
                                      [(== q 1)]
                                      [(== q 2)]
                                      ))
                         (['oil] (== q 3)))
                 ))
    ;;=> (1)

##### （6）defne/defna/defnu函数： #####

这三个函数都是用来定义一个比较特殊的logic函数，这三个函数分别与matche/matcha/matchu三个函数的pattern相匹配，它们的匹配规则如下：

;;用defn定义含有matche的函数：
    (defn fun1 [val]
        (match [val]
            ([val1] expr11 expr12)
            ([val2] expr21 expr22)
        ))
    ;;fun1函数与下面的fun2函数等价：
    (defne fun2 [val]
        ([val1] expr11 expr12)
        ([val2] expr21 expr22)
    )

下面是这三个函数的使用示例：

;;defne函数：
    (defne exampleo [a b]
           ([:a y] (membero y [:x :y]))
           ([:b x] (membero x [:x :y :z])))
    ;;=> #'insight.main/exampleo(run* [q]
          (fresh [a b]
                 (== q [a b])
                 (exampleo a b)
                 ))
    ;;=> ([:a :x] [:b :x] [:a :y] [:b :y] [:b :z])
    
    ;;defna函数：
    (defna exampleo [a b]
           ([:a y] (membero y [:x :y]))
           ([:b x] (membero x [:x :y :z])))
    ;;=> #'insight.main/exampleo(run* [q]
          (fresh [a b]
                 (== q [a b])
                 (exampleo a b)
                 ))
    ;;=> ([:a :x] [:a :y])
    
    ;;defnu函数:(defnu exampleo [a b]
           ([:a y] (membero y [:x :y]))
           ([:b x] (membero x [:x :y :z])))
    ;;=> #'insight.main/exampleo(run* [q]
          (fresh [a b]
                 (== q [a b])
                 (exampleo a b)
                 ))
    ;;=> ([:a :x])

##### （7）组合类函数：appendo/conjo/conso/featurec函数 #####

-->conjo/conso/appendo: conjo函数/conso函数与clojure.core中的conj函数/cons函数相似，只不过conj/cons返回组合后的结果，而conjo/conso是将组合后的结果当作参数传入，判断三个参数能否组合成功，这两个函数都是元素与数组的组合，而appendo函数则是数组与数组的组合，判断两个数组连接是否可以组成第三数组：

;;conjo函数判断将第二个参数加到第一个参数数组的末尾是否等于第三个参数
    (run* [q]
          (conjo q 5 [1 2 3 4 5])
          )
    ;;=> ([1 2 3 4])
    
    ;;conso函数判断将第一个参数加到第二个参数数组的首部，是否等于第三个参数
    (run* [q]
          (conso 1 q [1 2 3 4 5])
          )
    ;;=> ((2 3 4 5))
    
    ;;appendo函数判断前两个数组连接是否哦等于第三个数组
    (run* [q]
          (appendo [1 2] q [1 2 3 4 5])
          )
    => ((3 4 5))

至于为什么上述两个返回结果一个是vector，一个是list，这与conj/cons函数的形式一致，可能往首部插时转换为链表形式，而尾部则是数组（我猜的）   -->membero函数/featurec函数：   membero/featurec函数主要是判断元素的存在性，membero函数某个元素是否属于某个数组，而featurec函数则用于判断某个map是否为另一个map的子集：

;;判断第二个map是否为第一个map的子集，这里特别要注意，map中的key一定是要给定的，只能value是未知数
    (run* [q]
          (fresh [q1 q2]
                 (featurec {:a 1 :b 2 :c 3} {:a q1 :b q2})
                 (== q [q1 q2])
                 ))
    ;;=> ([1 2])
    
    ;;membero函数：
    (run* [q]
          (membero q [1 2 3 4 5])
          )
    => (1 2 3 4 5)

##### （8）and/or函数 #####

and和or是另一个版本的的all和conde，它们的区别是：   ->and和or:  只接收一个列表作为参数，列表里的多个表达式之间的关系是“与”/“或”，   ->all函数: 接收多个表达式作为参数，多个表达式之间的关系是“与”，   ->conde函数: 接收多个表达式列表作为参数，多个表达式列表之间的关系是“或”

;;四个函数输入参数的区别：
    (and* [a b c])
    (or* [a b c])
    (all a b c)
    (conde [a] [b] [c])

下面我们用五重点内容种不同的形式表达：q属于\[1 2 3\]和\[2 3 4\]的交集或者q=5

;;or*/and*:
    (run* [q]
          (or* [
                (and* [(membero q [1 2 3])
                       (membero q [2 3 4])])
                (== q 5)])
          )
    ;;=> (5 2 3)
    
    ;;or*/all:
    (run* [q]
          (or* [
                (all (membero q [1 2 3])
                     (membero q [2 3 4]))
                (== q 5)])
          )
    ;;=> (5 2 3)
    
    ;;conde/all:
    (run* [q]
          (conde [(all (membero q [1 2 3])
                     (membero q [2 3 4]))]
                 [(== q 5)])
          )
    ;;=> (5 2 3)
    
    ;;conde/and*:
    (run* [q]
          (conde [
                (and* [(membero q [1 2 3])
                       (membero q [2 3 4])])]
                 [(== q 5)])
          )
    ;;=> (5 2 3)
    
    ;;conde的每个表达式组中的表达式之间默认情况下是“与”的关系
    (run* [q]
          (conde [
                  (membero q [1 2 3])
                  (membero q [2 3 4])]
                 [(== q 5)])
          )
    ;;=> (5 2 3)

##### （9）clojure普通函数在logic代码中的使用： #####

通过前面的叙述我们知道，逻辑表达式的返回结果只有两种情况：succeed/fail，如果我们想在clojure.core.logic中调用let、mapv、reduce等clojure普通函数怎么办？？我们是不是需要将这些函数的返回结果转换为succeed或者fail。其实这些事情core.logic中已经为我们做好了，它提供了一个project宏专门为我们解决logic代码中调用普通函数的问题：

;;因为逻辑变量a/b/c都要被普通函数调用，所以在project的第一个参数列表中将其声明，然后我们就可以在let中调用其他普通函数，最后将结果返回便可，返回的结果一定也是一个逻辑表达式结果
    (run* [q]
          (fresh [a b c] 
                 (membero a [[1 7] [2 10]])
                 (== b [3 8])
                 (== c [5 6])
                 (project [a b c]
                          (let [result (concat a b c)
                                result-sum (apply + result)
                                result-avg (/ result-sum (count result))]
                            (== q result-avg)))
                 ))
    ;;输出结果是两个组数组的平均值
    ;;=> (5 17/3)

[免费体验云安全(易盾)内容安全、验证码等服务][Link 2]

更多网易技术、产品、运营经验分享请[点击][Link 1]。

相关文章：  
【推荐】 [Android 标题栏（1）][Android _1]

[Link 1]: https://sq.163yun.com/blog?tag=M_tg_617_72
[Link 2]: https://www.163yun.com/free?tag=M_tg_617_72
[Android _1]: https://www.jianshu.com/p/a89ca67215ce