lisp parsing for 'not'

Question

(defun simplify (x) 

 (if (and (not (null x)) (listp x))
   (if (and (equal '(car x) '(cadr x)) (equal '(car x) 'not))
      (simplify (cddr x))
      (cons (car x) (simplify (cdr x)))
     )
    'nil
  )
)

This lisp function is meant to take an expression as an argument then remove superfluous 'not's from it and return it. It checks if the argument is a non-empty list and returns nil if it isn't (base case). If it is non-empty, I want to check if the car(x) = car(cdr(x)) = 'not'. If they aren't detected to be a pair of 'not's then it should recurse and build on a list to return. If they are detected to be both 'not' then it should still recurse but also skipping both car(x) and car(cdr(x)). Right now all this code does is return an expression identical to the argument so I assume the problem is that my condition in the nested if statement isn't being set off properly, how can I check if car(x) and cadr(x) are both 'not'?

Answer 1

"when you assume..."

Actually, the test is semi-ok (but you'll end up taking (car nil) if x is (not) ). The problem is the recursion. Try it on paper:

(simplify '(and (not (not y)) (or x (not (not z))))`

1. (car x) is not not.

2. so: (cons (car x) (simplify (cdr x))

3. Now x is '((not (not y)) (or x (not (not z))))So(car x)is(not (not y)), which is not equal tonot`. Recurse again

4. Now x is ((or x (not (not z)))and(car x)is(or x (not (not z)))`. But you probably get the picture.

Hint: (map simplify x) and fix your termination condition to return x if x is an atom.

Answer 2

(equal '(car x) '(cadr x)) is always false, because the list (car x) is different from the list (cadr x). If you want to get the car and cadr of some particular x, you need to not quote these expressions.