;;; CSE 341, 99su
;;; Assignment 2:  Scheme/Boolean Formulas
;;; alternate sample solution for simplify
;;; July, 1999
;;; Ken Yasuhara 


;;; simplify "and" expression; returns simplification or 
;;; 'cannot-simplify symbol
;;; arguments x, y are simplified Boolean expressions

(define (s-and x y)			
  (cond ((equal? x y)			; (and x x) => x 
	 x)
	((equal? y #t)			; (and x #t) => x 
	 x)
	((equal? y #f)			; (and x #f) => #f 
	 #f)
	;; cases where y is an "not" or "or" subexpression
	((pair? y)
	 (let ((op (car y)))
	   (cond 
	    ((and (equal? op 'not)	; (and x (not x)) => #f 
		  (equal? x (cadr y)))
	     #f)
	    ((and (equal? op 'or)	; (and x (or x/y y/x)) => x
		  (or (equal? x (cadr y))
		      (equal? x (caddr y))))
	     x)
	    (else
	     'cannot-simplify))))
	(else 
	 'cannot-simplify)))


;;; simplify "or" expression; returns simplification or
;;; 'cannot-simplify
;;; arguments x, y are simplified Boolean expressions

(define (s-or x y)			
  (cond ((equal? x y)			; (or x x) => x 
	 x)				   
	((equal? y #f)			; (or x #f) => x 
	 x)				   
	((equal? y #t)			; (or x #t) => #t
	 #t)
	;; cases where y is an "not" or "or" subexpression
	((pair? y)
	 (let ((op (car y)))
	   (cond 
	    ((and (equal? op 'not)	; (or x (not x)) => #t
		  (equal? x (cadr y)))
	     #t)
	    ((and (equal? op 'and)	; (or x (and x/y y/x)) => x
		  (or (equal? x (cadr y))
		      (equal? x (caddr y))))
	     x)
	    (else
	     'cannot-simplify))))
	(else 
	 'cannot-simplify)))


;;; simplify "not" expression; returns simplification or
;;; original expression
;;; argument x is a simplified Boolean expression

(define (s-not x)
  (cond ((equal? x #f)			; (not #f) => #t
	 #t)
	((equal? x #t)			; (not #t) => #f
	 #f)
	((and (pair? x)			; (not (not x)) => x
	      (equal? (car x) 'not))
	 (cadr x))
	(else 
	 (list 'not x))))


;;; try "and" and "or" simplifications with both arg. orders

(define (s-symmetric op x y)
  (let ((s-op (cond ((equal? op 'and) s-and)
		    ((equal? op 'or) s-or)
		    (error "s-symmetric:  invalid function " op))))
    ;; try simplifying in one order
    (let ((s-in-order (s-op x y)))
      ;; but if that fails
      (if (equal? s-in-order 'cannot-simplify)
	  ;; try the reverse order
	  (let ((s-reverse-order (s-op y x)))
	    ;; and if both failed
	    (if (equal? s-reverse-order 'cannot-simplify)
		;; just reform the original expression
		(list op x y)
		;; otherwise return the reverse order simplifcation
		s-reverse-order))
	  ;; otherwise return the first order simplification
	  s-in-order))))
	  

;;; top-level simplify

(define (simplify expr)
  (if (pair? expr)
      ;; pull out operation symbol op and simplification of first (of
      ;; possibly two) arguments sarg1
      (let ((op (car expr)) (sarg1 (simplify (cadr expr))))
	;; "and" or "or" expression case
	(cond ((or (equal? op 'and) 
		   (equal? op 'or))
	       ;; pull out simplification of second argument sarg2
	       (let ((sarg2 (simplify (caddr expr))))
		 (s-symmetric op sarg1 sarg2)))
	      ;; "not" expression case
	      ((equal? op 'not)
	       (s-not sarg1))))
      expr))


;;; end of file