logo标签列表

Emacs LISP - 将列表进行DeMorgan转换

emacslispdemorgans-law
4
我正在学习人工智能课程，我们被要求编写一个程序。这个程序很简单，其他学生都用Java完成了。但是我知道可以用LISP完成更少的工作。嗯，打字更少。但是我已经读了一周关于LISP的资料，我对它感到惊讶。我决心学习更多，并将LISP用于不止这门课程。我今年23岁，正在学习一种在1958年形成的语言。这有点浪漫。我很享受避免使用鼠标的乐趣。
他给出的例子包含整个程序。他指出使用了递归，而不是prog。至少我理解了这个意思。
(rewrite '(or a (and b (not (or c d)))))

--> (OR A (AND B (AND (NOT C) (NOT D))))

(rewrite '(and a (or b (not (and c (and d e))))))

--> (AND A (OR B (NOT C) (OR (NOT D) (NOT E)))))

我理解德摩根定律。但是我不知道该如何处理！我的尝试很失败，笔记本上充满了我试图绘制的页面。以下是我对最简单情况的最接近尝试：

(not (or a b))

我认为如果我能处理这个，我就可以很好地处理其他事情。也许吧。我写了一个叫做“boom”的函数，那个上面的语句是我称之为可“boom”的列表。

(defun boom (sexp)

  (let ((op (car (car (cdr sexp)))) 

    (operands (cdr (car (cdr sexp))))))

  (if (equal op 'and)

      (setcar sexp 'or)

    (setcar sexp 'and))

  (print operands)

  (print sexp))

                ;end boom

我在调试时在结尾处打印输出。 对列表操作数的更改不反映在原始S表达式中（这让我非常失望）。

请告诉我我的方法是错误的，并指导我正确的做法。

你说“DeMorgan-ify”; 这个点只是为了在内部的“或”或“与”上分配“非”吗？ - Joshua Taylor
根据他的输出，似乎是这样的。例如，“and”和“or”可以很容易地替换为“foo”和“bar”。逻辑似乎并不起任何作用。 - kaleoh
处理人工智能让我想到了谓词的使用，我的意思是你的程序应该首先学习一些知识（例如如何根据德摩根定律解释不同的运算符），然后它可以通过使用其知识基础来评估整个表达式（例如在飞行中链接谓词）- 请参见下面的谓词示例。 - floppy12
@floppy12 我同意。我更感兴趣的是学习AI解决这个问题的方法，而不是像我的Java同事一样编辑字符串或者像我一样编辑列表。你是在建议我先教会我的程序什么是“and”和“or”吗？“学习一些知识”让我在实现上感到困惑，但我确实理解你的观点。 - kaleoh
4个回答
5

这是一个使用模式匹配的Emacs Lisp解决方案，基于Rainer Joswigs的Common Lisp解决方案：

(defun de-morgan (exp)
  (pcase exp
    ((pred atom) exp)
    (`(not (and ,a ,b)) `(or ,(de-morgan `(not ,a))
                             ,(de-morgan `(not ,b))))
    (`(not (or ,a ,b)) `(and ,(de-morgan `(not ,a))
                             ,(de-morgan `(not ,b))))
    (x (cons (car x) (mapcar #'de-morgan (rest x))))))

(de-morgan '(not (or 1 2))) ; => (and (not 1) (not 2))
(de-morgan '(not (and 1 2))) ; => (or (not 1) (not 2))
(de-morgan '(or a (and b (not (or c d))))) ; => (or a (and b (and (not c) (not d))))
我理解反引号和逗号的组合所起到的作用。无论如何，我正在尝试理解。让我问一下，如果我正确的话：'(not (or ,a ,b)) '(and (not ,(demorgan a) (not ,(demorgan b)基本上你是在说，如果它匹配了(not (or ...))，那么你会将a和b都通过demorgan函数运行。你最后一行让我感到困惑，你能解释一下吗？x到底绑定了什么？ - kaleoh
1
@kaleoh 在最后一行，x 绑定到被匹配的表达式（与 exp 相同）。它基本上是“否则”子句，如果其他模式失败，则匹配任何内容。 - jkiiski
如果它匹配单个原子，则保留该原子 - 很好。 如果它匹配 '(not (and/or,a,b))，则替换为'(or/and (not ...))，并且将a和b都通过该函数运行 - 太棒了。 然后，如果它没有'not，则再次将其他部分推送到函数中，并保留刚才检查的内容。太好了！这正是我想要的结果，现在我知道了我希望在一周前就知道的工具。 - kaleoh
1
中间的几行确实检查表达式是否与 (not (and <anything> <anything>)) 匹配，并将构建一个形式如 (or (not ...) (not ...)) 的返回列表。由于 a 和 b 可能包含子列表，因此它们需要通过 de-morgan 进行传递。 - jkiiski
1
我将对 de-morgan 的调用移到了整个 (not ...) 周围。否则它将无法正确处理像 (not (and a (and b c))) 这样的情况。 - jkiiski
2

不进行简化的通用Lisp：

(defun de-morgan (exp)
  (cond ;; atom
        ((atom exp) exp)
        ;; (not (and p q))  or  (not (or p q))
        ((and (consp exp)
              (equal (car exp) 'not)
              (consp (cadr exp))
              (or (equal (caadr exp) 'and)
                  (equal (caadr exp) 'or)))
         (list (case (caadr exp)
                 (and 'or)
                 (or 'and))
               (de-morgan (list 'not (car  (cdadr exp))))
               (de-morgan (list 'not (cadr (cdadr exp))))))
        ;; otherwise some other expression
        (t (cons (car exp) (mapcar #'de-morgan (rest exp))))))
1
我认为使用模式匹配（通过optima）会更加简洁。我认为Emacs Lisp也有一种名为pcase的模式匹配，但我没有足够的经验来确定它是否适用于此。 - jkiiski
@jkiiski：是的，一个模式匹配库会帮助很多。除了小练习之外，我不会写没有它的代码。 - Rainer Joswig
1
这两个函数应该将not分配到括号中：
(defun de-morgan (formula)
  (if (listp formula)
      (let ((op (first formula)))
        (case op
          (and `(and ,(de-morgan (second formula)) ,(de-morgan (third formula))))
          (or `(or ,(de-morgan (second formula)) ,(de-morgan (third formula))))
          (not (de-morgan-negate (second formula)))))
    formula))

(defun de-morgan-negate (formula)
  (if (listp formula)
      (let ((op (first formula)))
        (case op
          (and `(or ,(de-morgan-negate (second formula)) ,(de-morgan-negate (third formula))))
          (or `(and ,(de-morgan-negate (second formula)) ,(de-morgan-negate (third formula))))
          (not (de-morgan (second formula)))))
    `(not ,formula)))



(de-morgan 'a)
(de-morgan '(not a))
(de-morgan '(not (not a)))
(de-morgan '(and a b))
(de-morgan '(not (and a b)))
(de-morgan '(not (or a b)))
(de-morgan '(not (and (and (not a) b) (not (or (not c) (not (not d)))))))
1
在 case 中不应该引用参数。(case 'quote ('and 'match) (t no-match)) 返回 match，因为 'and 是 (quote and) 的简写形式，而 case 需要一个关键表单列表的指示器。你提供了两个符号的列表：quote 和 and。 - Joshua Taylor
@JoshuaTaylor：谢谢，这表明我现在很少使用Lisp。 - choroba
0

编写一个快速脏版本并不太难。您只需要检查您的公式是否为原始命题变量（在这种情况下，是原子）、二元连词或否定。如果是否定，则需要处理内部。

(defun demorganify (formula)
  (if (atom formula)
      formula
    (let ((operator (first formula)))
      (case operator
        ((and or)
         (list* operator (mapcar 'demorganify (rest formula))))
        ((not)
         (let ((subformula (second formula)))
           (if (atom subformula)
               formula
             (let* ((suboperator (first subformula))
                    (new-suboperator (case suboperator
                                       ((not) 'not)
                                       ((and) 'or)
                                       ((or) 'and)))
                    (demorganify-and-negate (lambda (f)
                                              (demorganify (list 'not (demorganify f))))))
               (list* new-suboperator (mapcar demorganify-and-negate (rest subformula)))))))))))

虽然这段代码可以更简洁一些。

(demorganify '(not (or (not a) (not b)))) - Rainer Joswig
@RainerJoswig 抱歉，我现在添加了否定情况。OP没有说明是否应该删除双重否定。 - Joshua Taylor
关于双重否定，没有任何指示，所以我认为它是开放式的。 - kaleoh
在我的Emacs版本中，不存在first和rest。其中，first等同于car，而rest等同于cdr。对吧？ - kaleoh
我正在使用GNU Emacs 24。但是，car表示第一个元素，cdr表示剩余元素。 - Joshua Taylor
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接