(define-struct nt (sub))
(define-struct nd (lft rgt))
(define-struct cll (name arg))
;; A BER is one of: 
;; -- Boolean 
;; -- Symbol
;; -- (make-nt BER)
;; -- (make-nd BER BER)
;; -- (make-cll Symbol BER) ;; function call 

(define-struct fun (name para body))
;; FBER = (make-fun Symbol Symbol BER)

;; bad-function-body? : BER Symbol Symbol -> Boolean 
;; does the given expression containy any symbols other than fname or argname

(check-expect (bad-function-body? true 'f 'x) false)
(check-expect (bad-function-body? 'x 'f 'x) false)
(check-expect (bad-function-body? 'x 'f 'y) true)
(check-expect (bad-function-body? (make-nt false) 'f 'y) false)
(check-expect (bad-function-body? (make-nd true false) 'f 'y) false)
(check-expect (bad-function-body? (make-cll 'f 'x) 'f 'y) true)
(check-expect (bad-function-body? (make-cll 'f 'y) 'g 'y) true)

(define (bad-function-body? body fname argname)
  (cond
    [(boolean? body) false]
    [(symbol? body) (not (symbol=? body argname))]
    [(nt? body) (bad-function-body? (nt-sub body) fname argname)]
    [(nd? body) (or (bad-function-body? (nd-lft body) fname argname)
                    (bad-function-body? (nd-rgt body) fname argname))]
    [(cll? body) (or (not (symbol=? (cll-name body) fname))
                     (bad-function-body? (cll-arg body) fname argname))]))

;; fevaluator: BER FBER -> Boolean or '*error*
;; determine the boolean value of a BER; it it contains symbols, produce '*error*
;; may contain the name of the function 

(define (evaluator e def)
  (if (or (contains-symbol? e (fun-name def)) 
          (bad-function-body? (fun-body def) (fun-name def) (fun-para def)))
      '*error*
      (real-evaluator e def)))

(define fdef (make-fun 'f 'x true))
(check-expect (evaluator true fdef) true)
(check-expect (evaluator 'x fdef) '*error*)
(check-expect (evaluator false fdef) false)
(check-expect (evaluator (make-nt false) fdef) true)
(check-expect (evaluator (make-nd true (make-nt false)) fdef) true)
(check-expect (evaluator (make-nd true (make-nt false)) fdef) true)
(check-expect (evaluator (make-nd true (make-nt 'x)) fdef) '*error*)
  
;; contains-symbol? : BER Symbol -> Boolean 
;; does the given expression containy any symbols other than fname? 

;; true 'f ==> false 
;; 'x 'f ==> true 
;; (make-nt 'x) 'f ==> true 
;; (make-nd false false) 'f ==> false 
;; (make-nd (make-nt true) false) 'f ==> false 

;; (make-cll 'f true) 'f ==> false 
;; (make-cll 'f true) 'g ==> true
;; (make-cll 'f (make-nt 'x)) 'f ==> true

(define (contains-symbol? e fname) 
  (cond
    [(boolean? e) false]
    [(symbol? e)  true ]
    [(nt? e) (contains-symbol? (nt-sub e) fname)]
    [(nd? e) (or (contains-symbol? (nd-lft e) fname) (contains-symbol? (nd-rgt e) fname))]
    [(cll? e) (or (not (symbol=? (cll-name e) fname)) 
                  (contains-symbol? (cll-arg e) fname))]))

(check-expect (contains-symbol? 'x 'f) true)
(check-expect (contains-symbol? true 'f) false)
(check-expect (contains-symbol? (make-nd true 'x) 'f) true)
(check-expect (contains-symbol? (make-nd 'x true) 'f) true)
(check-expect (contains-symbol? (make-nd 'x false) 'f) true)
(check-expect (contains-symbol? (make-nt false) 'f) false)

(check-expect (contains-symbol? (make-cll 'f true) 'f) false)
(check-expect (contains-symbol? (make-cll 'f true) 'g) true)
(check-expect (contains-symbol? (make-cll 'f (make-nt 'x)) 'g) true)



;; real-evaluator : SBER FBER -> Boolean
;; determine the boolean value of a BER (without symbols)


;; true 'any ==> true 
;; false 'any ==> false 
;; (make-nd true false) 'any ==> false 
;; (make-nd false (make-nt false)) 'any --> false 
;; (make-nt (make-nd true false)) 'any --> true 
;; (make-cll 'f true)  (make-fun 'f 'y true) ==> true 
;; (make-cll 'f true)  (make-fun 'f 'y false) ==> false 
;; (make-cll 'f true)  (make-fun 'f 'y 'y) ==> true 


(define (real-evaluator e def)
  (cond
    [(boolean? e) e]
    ;[(symbol? e) ????]
    [(nt? e) (not (real-evaluator (nt-sub e) def))]
    [(nd? e) (and (real-evaluator (nd-lft e) def) (real-evaluator (nd-rgt e) def))]
    [(cll? e) (real-evaluator
               (replace (fun-body def) (fun-para def) (real-evaluator (cll-arg e) def))
               def)]))

(check-expect (real-evaluator true fdef) true)
(check-expect (real-evaluator false fdef) false)
(check-expect (real-evaluator (make-nt false) fdef) true)
(check-expect (real-evaluator (make-nd true (make-nt false)) fdef) true)
(check-expect (real-evaluator (make-nd true (make-nt false)) fdef) true)


;; replace : BER Symbol Boolean -> BER 
;; replace all occurrences of x in b with a 

;; BODY   PARA   ARGVAL   Desired Result  
;;  'x      'x      true        true 
;;  'y      'x      true        bad input example
;;  true    'x      false       true 
;;  (make-nd true 'x) 'x false  (make-nd true false)
;;  (make-nt true) 'x false     (make-nt true)
;;  (make-cll 'f 'x) 'x false   (make-cll 'f false)

(define (replace b x a) 
  (cond
    [(boolean? b) b]
    [(symbol? b) a]
    [(nt? b) (make-nt (replace (nt-sub b) x a))]
    [(nd? b) (make-nd (replace (nd-lft b) x a) (replace (nd-rgt b) x a))]
    [(cll? b) (make-cll (cll-name b) (replace (cll-arg b) x a)) ]))


(check-expect (replace 'x 'x true) true)
(check-expect (replace 'y 'x true) true)
(check-expect (replace true 'x true) true)

;; --- 

(check-expect 
 (evaluator (make-cll 'f false)
            (make-fun 'f 'x (make-nd (make-nt 'x) (make-cll 'f (make-nt 'x)))))
 false)


;; WARNING: the following goes into an infinite loop
;; STEP 7: termination NO NO NO !!!
(evaluator (make-cll 'f false)
           (make-fun 'f 'x (make-nd (make-cll 'f (make-nt 'x)) (make-nt 'x))))