;Copyright (C) 1993 by Matthew Belmonte.
;
;This is an evaluator for a language of well-formed formulae (WFF's) in the
;propositional calculus.  It demonstrates techniques to be understood and used
;in the design of your PURPLE evaluator, the final project for Theoretical
;Foundations of Computer Science at Johns Hopkins CTY.  This version of the WFF
;evaluator was prepared by Matthew Belmonte, based on his implementation of the
;same algorithm in Pascal.

;NOTE: Since WFFs have Boolean values, these evaluation functions return Boolean values.
;In the parser that you are writing, some subtrees (arithmetic expressions) will have
;numeric values, and some subtrees (statements) will not have any meaningful value at all.
;So use this evaluator as a loose guide, but DON'T follow it very closely; it WILL NOT WORK
;if what you're trying to evaluate is not a Boolean.

(define make-pair
  (lambda (a b)
    (cons a (cons b '()))))

(define set-variable
  (lambda (var val)
    (set! bindings (set-variable-help var val bindings))))

(define set-variable-help
  (lambda (var val bindings)
    (cond
      [(eq? var (first (first bindings)))
       (cons (make-pair var val) (rest bindings))]
      [else (cons (first bindings) (set-variable-help var val (rest bindings)))])))

(define get-variable
  (lambda (var)
    (let ((binding (assoc var bindings)))
      (cond
        [(list? binding) (first (rest binding))]
        [else (error "undefined variable" var)]))))

(define evaluate
  (lambda (tree)
    (cond
      [(eq? 'not-token (root tree)) (not (evaluate (left-child tree)))]
      [(eq? 'and-token (root tree)) (and (evaluate (left-child tree)) (evaluate (right-child tree)))]
      [(eq? 'or-token (root tree)) (or (evaluate (left-child tree)) (evaluate (right-child tree)))]
      [(eq? 'implies-token (root tree)) (or (not (evaluate (left-child tree))) (evaluate (right-child-tree)))]
      [(eq? 'equiv-token (root tree)) (eq? (evaluate (left-child tree)) (evaluate (right-child tree)))]
      [(letter? (root tree)) (get-variable (root tree))])))

;top-level function
(define run-evaluator
  (lambda ()
    (begin
      (init-evaluator)
      (set-bindings) ;we assume that this routine is supplied elsewhere - it uses set-variable.
      (evaluate (parse-formula)))))