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