lisp - 使用 lisp 简化一个简单的 bool 表达式

Question

我有一个简单的 bool 表达式，以 lisp 列表的形式呈现，如下所示:'(OR 0 (AND A1 A2))

前面的列表是((A1 AND A2)OR 0)的表示。

无论如何，我正在编写一个函数来简化这个表达式..例如:

像这样调用函数“reduce”:

(减少'(OR 0 (AND A1 A2)))

会产生

(和 A1 A2)

我首先尝试创建基本规则，所以我定义了以下身份:

(AND 1 S) == S,

(或 0 S)== S，

(AND 0 S) == 0,

( 或 1 S) == 1,

(不是 O)== 1，

(不是 1)== 0.*

我正在考虑定义 6 个函数，每个规则一个，然后在包装器中一个一个地调用它们，我是 lisp 的新手，所以我不知道如何实现它，我用 java 做过一次，但我不知道如何使用 lisp 的语法处理这样的问题所以请帮助我..

Answer 1

考虑到您的解决方案的复杂性，这是我的实现，它更短且更易读:

(defun reduc (exp)
  (if (atom exp) 
      exp
      (flet ((helper (op args n) ; and and or is nearly the same code so we factor it out
               (let ((newargs (remove n args)) (cn (- 1 n)))
                 (cond
                  ((null newargs) n)
                  ((some (lambda (e) (eql cn e)) newargs) cn)
                  ((null (cdr newargs)) (car newargs))
                  ((cons op newargs))))))
        (let ((op (car exp)) (args (mapcar #'reduc (cdr exp))))
          (ecase op
            ((not) (if (= 1 (length args))
                       (let ((arg1 (car args)))
                         (if (and (numberp arg1) (<= 0 arg1 1)) (- 1 arg1) exp))
                       (error "'not' must have exactly one parameter")))
            ((and) (helper op args 1))
            ((or)  (helper op args 0)))))))

测试:

? (reduc '(OR 0 (AND A1 A2))) 
(AND A1 A2)
? (reduc '(OR 0 (AND A1 1 A2)))
(AND A1 A2)
? (reduc '(or ERROR (not 0)))
1
? (reduc '(AND ERROR (not 0)))
ERROR
? (reduc '(OR 0 (AND A1 0))) 
0
? (reduc '(OR 0 (AND A1 1))) 
A1