Do Logic Programming in Lisa

A Tutorial for Logical Programming

Feb 15, 2020

见习魔法师

Lisa-Language
Logic-Programming

Lisa是一门与众不同的语言，几乎没有人愿意用她来开发软件，速度还贼慢，她融合了很多试验性的功能，其中有一个功能就是逻辑编程。和Prolog类似，可以解决三段论的问题。给出事实和规则，Lisa/Logical可以自动分析其中的逻辑关系，允许用户通过查询，完成复杂的逻辑运算。

本文将会分析两个例子，给出用lisa解决两个实例的方案。实例来自于xmonader的prolog教程。 基本介绍可以看这篇文章。

基本使用

进入Lisa的repl之后，你就可以开始交互式输入代码并执行了。 界面类似于： 

.____    .__
|    |   |__| ___________
|    |   |  |/  ___/\__  \
|    |___|  |\___ \  / __ \_
|_______ \__/____  >(____  /
        \/       \/      \/
Welcome to Lisa REPL by Somainer (moe.roselia.lisa).
Type in expressions for evaluation. (quit) to quit.

lisa>

在lisa>之后就可以输入代码了，为了新建一个逻辑上下文，我们需要打入如下代码： 

(import-env! logical)
(logical/new-context)
这样我们就可以开始进行逻辑编程了。 考虑到我们每一条事实就需要手动打(fact ...)很麻烦，我们这里可以写一个宏，将宏里面的所有代码外面都套上(fact )，即x => (fact x)。 取名为facts，代表要输入多个例子。 
(define-macro (facts (... fs))
    (define fact-clauses (map fs (lambda (x) (list 'fact x))))
    '(let () ~~fact-clauses))
当然，这个宏是为了少打几个字，不是十分重要，但是本文会用到。

我们以朋友关系为例子，来讲述基本用法。 

(facts
    (friend john julia)
    (friend john jack)
    (friend julia sam)
    (friend julia molly)

    (loves john julia)
    (loves julia sam)
    (loves sam julia))
从这里可以看出，事实是以列表的形式给出的。上面看似是标识符将被自动转换为原子类型。

我们知道，喜欢这个关系不是互相的，但是朋友关系是互相的。 因此，我们需要定义反向的关系。与prolog不同的是，rule和fact不能有相同名字，因此我们定义一个friend?规则，规定：

(define-rule (friend? x y)
    (or (friend x y)
        (friend y x)))

这里我们就已经可以开始询问Lisa了： 

lisa>(is-true? (friend? :jack :john))
[0]: Boolean = true
lisa>(is-true? (friend? :john :molly))
[1]: Boolean = false
lisa>(query (friend? :john x))
[2]: List = ({'x :julia} {'x :jack})
对于存在的事实，我们甚至可以询问两者有哪些关系（目前不能用于规则）。 (query ('relation :john :julia)) => ({'relation :friend} {'relation :loves})

和prolog不同的是，我们可以动态添加规则或者事实。 

(define-rule (sad-story x)
    (and (loves x y)
        (not (loves y x))))
这里，我们认为单相思是悲惨的故事，对于X来说，单相思就是存在这样的人Y，X喜欢Y，Y却不喜欢X。

然后我们可以继续询问Lisa： 

lisa>(is-true? (sad-story :john))
[3]: Boolean = true
lisa>(is-true? (sad-story :julia))
[4]: Boolean = false

保存当前上下文

我们可以将上下文保存到某一个变量上，以供下次使用。 

(define context (current-context)) ; 保存当前上下文
(pop-context!) ; 退出当前上下文

(logical/push-context context) ; 恢复context中的上下文。

地图染色

地图染色就是在如图所示的地图上，所有的区块染上三种颜色，要求相邻的区块的颜色不能相同。

Lisa解就十分显而易见，首先定义三种颜色： 

(fact (color red))
(fact (color green))
(fact (color blue))
接着定义染色规则： 
(define-rule (colorify a b c d e)
    (and
        (color a)
        (color b)
        (color c)
        (color d)
        (color e)
        (not (= a b))
        (not (= a c))
        (not (= a d))
        (not (= a e))
        (not (= b c))
        (not (= c d))
        (not (= d e))))
colorify是一个接受abcde五个变量的规则，该规则成立的条件是，该五个变量被分配到某种颜色上，且相邻的区块颜色不相同。

我们可以直接询问有多少解： 

(query (colorify a b c d e))

我们应该能得到六组解。

谁是凶手

Boddy 先生死于谋杀，现有六个嫌疑犯，每个人在不同的房间，每间房间各有一件可能的凶器，但不知道嫌疑犯、房间、凶器的对应关系。请根据下面的条件和线索，找出谁是凶手。

已知条件：六个嫌疑犯是三男（George、John、Robert）三女（Barbara、Christine、Yolanda）。

(facts
    (man george)
    (man john)
    (man robert)
    (woman barbara)
    (woman christine)
    (woman yolanda))

男人，女人，都是人： 

(define-rule (person x)
    (or (man x)
        (woman x)))

六个嫌疑犯分别待在六个房间：浴室（Bathroom）、饭厅（Dining Room）、厨房（Kitchen）、起居室（Living Room）、 储藏室（Pantry）、书房（Study）。每间房间都有一件可疑的物品，可以当作凶器：包（Bag）、火枪（Firearm）、煤气（Gas）、刀（Knife）、毒药（Poison）、绳索（Rope）。

(facts
    (location bathroom)
    (location dining)
    (location kitchen)
    (location livingroom)
    (location pantry)
    (location study)
    (weapon bag)
    (weapon firearm)
    (weapon gas)
    (weapon knife)
    (weapon poison)
    (weapon rope))

每个人都是不一样的： 

(define-rule (unique-people a b c d e f)
    (and
        (person a)
        (person b)
        (not (= a b))
        (person c)
        (not (= b c))
        (not (= a c))
        (person d)
        (not (= a d))
        (not (= b d))
        (not (= c d))
        (person e)
        (not (= a e))
        (not (= b e))
        (not (= c e))
        (not (= d e))
        (person f)
        (not (= a f))
        (not (= b f))
        (not (= c f))
        (not (= d f))
        (not (= e f))))
然后我们逐个分析事实：

线索一：厨房里面是一个男人，那里的凶器不是绳索、刀子、包和火枪。 

(and 
    (man kitchen)
    (not (= kitchen rope))
    (not (= kitchen knife))
    (not (= kitchen bag))
    (not (= kitchen firearm)))
也可以这么写，因为他只能用煤气或者下毒了。 
(and 
    (man kitchen)
    (or
            (= kitchen :gas)
            (= kitchen :poison)))

线索二：Barbara 和 Yolanda 在浴室或书房。 我们可以认为，浴室和书房都是女性，而且这个女性不是Christine，Barbara在浴室或书房，Yolanda也在浴室或书房。

(and
    (woman bathroom)
    (woman study)
    (not (= bathroom :christine))
    (not (= study :christine))
    (or (= :barbara bathroom) (= :barbara study))
    (or (= :yolanda bathroom) (= :yolanda study)))

线索三：带包的那个人不是 Barbara 和 George，也不在浴室和饭厅。

灵魂直译即可。

(and
    (not (= bag :barbara))
    (not (= bag :george))
    (not (= bag bathroom))
    (not (= bag dining)))

线索四：书房里面是一个带绳子的女人。

灵魂直译 

(and
    (woman rope)
    (= rope study))

线索五：起居室里面那件凶器，与 John 或 George 在一起。 

(and (man livingroom)
    (not (= livingroom :robert)))

线索六：刀子不在饭厅。

(not (= knife dining))

线索七：书房和食品储藏室里面的凶器，没跟 Yolanda 在一起。

(and
    (not (= :yolanda pantry))
    (not (= :yolanda study)))

线索八：George 所在的那间屋子有火枪。

(= firearm :george)

线索九：Boddy 先生死在食品储藏室里，那里的凶器是煤气。

(and
    (= pantry gas)
    (= x pantry)))

线索就是这些，我们可以开始写入口了， 我们只关心凶手是谁。我们假定凶手是X

(define-rule (murderer x)
    (and
        (unique-people bathroom dining kitchen livingroom pantry study)
        (unique-people bag firearm gas knife poison rope)
                ...
        ))
在省略号处，我们填上所有的线索，就能得出结果，凶手是Christine。 骗你的，这样写代码要跑好久。我们需要手动做一些优化，我们需要将最简单的情况拍到前面，比如线索八，能省去好多不必要的枚举。 最后进行简单的重新组织，一个可行的代码是： 
(define-rule (murderer x)
    (and
        (= firearm :george) ; Clue 8

        (unique-people bathroom dining kitchen livingroom pantry study)
        (unique-people bag firearm gas knife poison rope)

        (and
            (woman rope)
            (= rope study)) ; Clue 4

        (not (= knife dining)) ; Clue 6

        (and 
            (man kitchen)
            (not (= kitchen rope))
            (not (= kitchen knife))
            (not (= kitchen bag))
            (not (= kitchen firearm)))

        (and
            (woman bathroom)
            (woman study)
            (not (= bathroom :christine))
            (not (= study :christine))
            (or (= :barbara bathroom) (= :barbara study))
            (or (= :yolanda bathroom) (= :yolanda study)))

        (and
            (not (= bag :barbara))
            (not (= bag :george))
            (not (= bag bathroom))
            (not (= bag dining)))


        (and (man livingroom)
            (not (= livingroom :robert)))

        (and
            (not (= :yolanda pantry))
            (not (= :yolanda study)))

        (and
            (= pantry gas)
            (= x pantry))))


(query (murderer x))
[0]: List = ({'x :christine}) 这次，是真的能较快得出结果了。其实也没啥改动，就是把一些简单的情况排在前面，像我们在人工推理的时候也会把能直接确定的放在最前面。

r{{ changeExtraDisplaySettings({blurMainImage: true}) }}