Emacs LISP - DeMorgan'ify a list

Question

I am in an Artificial Intelligence course and we were given a program to write. The program is apparently simple, and all other students did it in java. However I know that it can be done in LISP with less work. Well. Less typing. But I've been reading about LISP for a week now, and I am amazed by it. I am determined to learn more, and use LISP for a lot more than just this class. I'm 23 and am learning a language formed in 1958. It's kind of romantic. I am having a lot of fun avoiding my mousepad like the plague.

The example he gives tells the entire program. He notes that he uses recursion, and not prog. I understand what that means, at least.

(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)))))

I understand De Morgan's laws. I just don't get how I'm supposed to handle this! What I have so far is... embarrassing. My notebook is filled with pages of me trying to draw this out. I will give you my closest attempt at the simplest case which is:

(not (or a b))

I figure if I can handle this, I may be just fine to handle the rest. Maybe. I made a function called boom, and that above statement is what I call a boomable list.

(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

I print at the end for debugging. Changes to the list operands does not reflect changes in original sexp (huge let down for me).

Tell me what I have is bogus, and guide me.

Answer 1

An Emacs Lisp solution using pattern matching, based on Rainer Joswigs Common Lisp solution:

(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))))

Answer 2

Common Lisp, without simplification:

(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))))))