;    This file contains the definitions needed for 
; the environment simulation of Assignment 2, 
; CS 152, Spring 2000.  
; 
;   A display is used to avoid linear searches
; for the appropriate frame at run time.  The
; display is stored as one of the components of
; an environment, along with the stack of frames.



;;;;;;;;;;;;;;; environments and displays ;;;;;;;;;;;;;;;;;


; Here are the constructor and selectors for environments.
; An environment is a pair consisting of a stack of frames
;   and a display.  Both are initially empty.

(define (make-environment) 
   (cons '() '()))

(define (get-frames e) (car e))
(define (get-display e) (cdr e))
  

; This is the constructor for a display.  When a frame
;   is added to or deleted from the environment,
;   the display is recreated from scratch starting
;   with the top frame, and continuing by adding frames
;   and then following their static links.  
;   The constructor takes the current environment as its
;   argument, so it must first find the top frame of the 
;   stack of frames.  It passes this frame to a helper 
;   function that does all the work -- unless the stack 
;   is empty, in which case it just returns the empty stack.

(define (make-display e)
  (define (helper f)
    (if (null? f) '() (cons f (helper (get-static-link f)))))
  (let ((frames (get-frames e)))
    (if (null? frames) '() (helper (car (get-frames e))))))
  
    
; This function adds a frame f to an environment e by 
;   pushing the frame onto the stack of frames, and 
;   updating the display from scratch.
; Note that the display is updated *after* the list of frames,
;   so that the call to "make-display" uses the new list of frames

(define (add-frame e f)
  (set-car! e (cons f (get-frames e)))
  (set-cdr! e (make-display e)))
  

; This function deletes a frame f to an environment e by 
;   popping from the stack of frames, and updating the 
;   display from scratch.
; Note that the display is updated *after* the list of frames,
;   so that the call to "make-display" uses the new list of frames
; This function does not check for empty list of frames  -- this
;   should be unnecessary in a well-formed compiler.

(define (delete-frame e)
  (set-car! e (cdr (get-frames e)))
  (set-cdr! e (make-display e)))
  

; This function looks up a binding in an environment, given
;   two offsets i and j.  It uses the first offset i as an 
;   index into the display, first checking that it is not 
;   too large.
; The frame that it finds is passed to the function 
;   "lookup-binding", along with the second offset j, to find
;   binding in that frame.
; If the lookup function fails because one of the offsets was
;   too large, it returns #f.

(define (lookup e i j) 
  (let ((display (get-display e)))
    (if (>= i (length display))
        #f
        (let ((frame (list-ref (get-display e) i)))
          (if frame (lookup-binding frame j) #f)))))

  
; This function looks up a binding in an environment, given
;   two offsets i and j.  It prints the result rather than 
;   returns it.  It works simply by calling the function 
;   "lookup", and printing the result following an initial
;   space.
 
(define (lookup-and-print e i j)
  (display " ")
  (display (lookup e i j)))


;;;;;;;;;;;;;;;;;;;; frames and bindings ;;;;;;;;;;;;;;;;;;;;

; Selector and constructors for frames (since only the filler
;   component of a binding needs to be stored in this 
;   simulation, no selector or constructor is used for
;   bindings).

; A frame is a pair consisting of a static link and a list of
;   bindings.  This list of bindings is initially empty.

(define (make-frame static-link)
  (cons static-link '()))

(define (get-static-link f) (car f))
(define (get-bindings f) (cdr f))


; This function adds a binding b to a frame f, destructively. 
;   Since offsets are defined under the assumption that 
;   bindings are added using a FIFO discipline, the new 
;   binding must be added to the end of the list.

(define (add-binding f b)
  (set-cdr! f (append (get-bindings f) (list b))))


; This function returns the binding at a given offset from
;   a given frame f.  It checks to see that the offset is
;   not too large.  If it is, it returns #f, and otherwise
;   it simply returns the element of the list of bindings
;   that is given by the offset.

(define (lookup-binding f offset)
  (let ((bindings (get-bindings f)))
    (if (>= offset (length bindings)) 
        #f 
        (list-ref bindings offset))))