;-------------------------------------------------
; E n v i r o n m e n t 
;-------------------------------------------------
; We implement environments as a list of FRAMES.
; FRAMES are lists of variable -> value 
; associtations.  
;-------------------------------------------------


; F r a m e   S t r u c t u r e
; Frames are lists of variable -> value 
; associations implemented as dotted pairs:
; ( (var1 . val1) (var2 . val2) )

(define (make-empty-frame) '())
(define (empty-frame? frame) (null? frame))

; Frame Constructor
; If the var list and val list are valid
; then build frame 
(define (make-frame vars vals) (build-frame vars vals))
; Check that the var list and val list are valid:
;   a. Check that they are in fact lists
;   b. Check that they are the same size
(define (valid-varval-list? vars vals)
  (if (and (pair? vars) (pair? vals)) 
      (= (length vars) (length vals))))

; Build Frame
; Turn var list and val list into a single list 
; of dotted pairs (basically build a dotted pair 
; containing the car of each of the two lists, and 
; recursively call the function on the cdr of each 
; of the two lists.
; ( (var1 . val1) (var2 . val2) )
(define (build-frame vars vals)
  (cond ((null? vars) '())
  (else (cons (cons (car vars) (car vals)) (build-frame (cdr vars) (cdr vals))))))

; Walk the list and return true if var is 
; the first element in any dotted pair in 
; frame.
(define (defined? var frame)
  (cond
   ((empty-frame? frame) #f)
   ((eq? var (caar frame)) #t)
   (else (defined? var (cdr frame)))))

; Insert var -> val association in frame
(define (add-binding-to-frame var val frame)
  (cons (cons var val) frame))

; Substitute var -> val association in 
; place of the current var -> oldval in frame
(define (set-binding-in-frame var val frame)
  (cond
   ((empty-frame? frame) frame)
   ((eq? var (caar frame)) (cons (cons var val) (cdr frame)))
   (else (cons (car frame) (set-binding-in-frame var val (cdr frame))))))

; Return the val for given var in frame
(define notfound '~)
(define (lkp-binding-in-frame var frame)
  (cond
   ((empty-frame? frame) notfound)
   ((eq? var (caar frame)) (cdar frame))
   (else (lkp-binding-in-frame var (cdr frame)))))

; E n v i r o n m e n t   S t r u c t u r e

(define the-empty-environment '())
(define (empty-env? env) (eq? env the-empty-environment))

(define (first-frame env) (car env))
(define (enclosing-environment env) (cdr env))

(define (extend-environment vars vals base-env)
  (cons (make-frame vars vals) base-env))

(define (lookup-variable-value var env)
  (if (empty-env? env) notfound
      (let
	  ((binding (lkp-binding-in-frame var (first-frame env))))
	(if (eq? binding notfound) 
	    (lookup-variable-value var (enclosing-environment env))
	    binding))))

(define (set-variable-value var val env)
  (if (empty-env? env) env
      (let
	  ((frame (set-binding-in-frame var val (first-frame env))))
	(if (defined? var frame)
	    (cons frame (enclosing-environment env))
	    (cons frame (set-variable-value var val (enclosing-environment env)))))))

(define (define-variable var val env)
  (if (empty-env? env) notfound
      (let
	  ((frame (set-binding-in-frame var val (first-frame env))))
	(if (defined? var frame)
	    (cons frame (enclosing-environment env))
	    (cons (add-binding-to-frame var val (first-frame env)) (enclosing-environment env))))))