; This is the main procedure of the expression evaluator
(define run
    (lambda (bindings)
        ; Save the bindings for testing purposes: after a crash, run can
        ; be called with (run last-bindings) to start where it left off.
        ; WARNING:  last-bindings should not appear anywhere else in your
        ;           code!!!!
        (set! last-bindings bindings)
        (display "\n>")         ; display a user prompt
        (let ((expr (read)))    ; Read a statement from the user
            (cond
                ((eq? expr 'quit)
                    (display "Done!"))
                ;;;; Place your code here to handle all ;;;;
                ;;;; valid statements from the user     ;;;;
                ;;;; and display appropriate messages   ;;;;
                ;;;; for invalid statements             ;;;;

                ;;;; After handling each statement, call run    ;;;;
                ;;;; recursively with the new bindings          ;;;;
                ; Sample case:
                ((eqv? expr 1)
                    (display 1)
                    (run bindings))
                (else
                    (display "Unknown statement type")
                    (run bindings))
            )
        )
    )
)


;;;; Define all helper procedures required by run here ;;;;



;----------- Supplied Utility Procedures -----------

; Returns #t iff symbol is an arithmetic operator that is allowed for use
; in infix expressions.
(define infix-operator?
    (lambda (symbol)
        (member symbol '(+ - * / ^ % < <= = > >=))
    )
)


; Returns #t iff symbol is bound a to builtin procedure
; Note: this code only works in MIT Scheme
(define builtin?
    (lambda (symbol)
        (if (not (symbol? symbol))
            (display-all symbol
             "is not a symbol---you are calling builtin?  incorrectly.\n"))
        (and (symbol? symbol)
             (environment-bound? () symbol)
             (procedure? (eval symbol ())))
    )
)

; Display an error message.
;  Allowed calls to this procedure:
;   (display-error 'unbound symbol)
;       displays error saying symbol is unbound
;   (display-error 'syntax)
;       displays an error saying the user entered an invalid expression
;   (display-error 'internal)
;       displays an internal error message--the use should never see it!
;   (display-error 'arity function)
;       displays an error saying a function was used with the wrong number
;       of arguments  (you will only need this for Bonus 2).
;   (display-error 'apply expr)
;       displays an error saying that expr is not a function
;       (you will only need this for Bonus 2).
(define display-error
    (lambda (type . args)
        (cond ((and (eq? type 'unbound) (pair? args)
                    (symbol? (car args)) (null? (cdr args)))
                  (display-all "Undefined symbol:" (car args) "\n"))
              ((and (eq? type 'syntax) (null? args))
                  (display-all "Invalid or unsupported expression.\n"))
              ((and (eq? type 'internal) (null? args))
                  (display-all "An internal error occurred--please contact"
                               "your system vendor for a patch.\n"))
              ((and (eq? type 'arity) (pair? args)
                    (or (symbol? (car args)) (procedure? (car args)))
                    (null? (cdr args)))
                  (display-all "Function" (car args)
                               "called with the wrong number of arguments.\n"))
              ((and (eq? type 'apply) (pair? args) (null? (cdr args)))
                  (display-all "The object" (car args) "is not a function."))
              (else
                  (display-all "Invalid call to display-error--fix"
                               "your code, the user should never see"
                               "this.\n"))
        )
    )
)

; Display a number of objects, with a space between each.
; You may use this instead of display, where convenient.
(define display-all
    (lambda lst
        (cond ((null? lst) ())
              ((null? (cdr lst)) (display (car lst)) ())
              (else (display (car lst)) (display " ")
                    (apply display-all (cdr lst))))
    )
)

; This bindings variable is defined for your convenience.
; Feel free to modify it for your own testing.
; Note: ` stands for quasiquote.  Like quote, quasiquote inhibits the
; evaluation of its argument, but it permits the use of , (unquote) to
; specify that some parts should still be evaluated, in this case the
; lambda expression.
(define bindings `((a . 1) (b . 2) (f . ,(lambda (x) (* x x)))))
; This variable is modified each time you call run.  It must be defined
; before set! can be called, so we define it to be the empty list initially.
(define last-bindings ())


;----------- Bindings -----------
; Returns the last inserted binding for symbol
; (as a pair ( symbol .  binding ) ) if symbol
; has a binding in bindings, () otherwise.
; Pre: symbol is a symbol, bindings is a list of bindings
(define get-binding
    (lambda (symbol bindings)
        () ;;;; Remove this line and complete this procedure ;;;;
    )
)

; Returns a new binding list with the binding ( symbol . value ) inserted
; Pre: symbol is a symbol, bindings is a list of bindings
(define set-binding
    (lambda (symbol value bindings)
        () ;;;; Remove this line and complete this procedure ;;;;
    )
)

; Returns the variable symbol of the binding
(define bound-var
    (lambda (binding)
        () ;;;; Remove this line and complete this procedure ;;;;
    )
)

; Returns the value of the binding
(define bound-value
    (lambda (binding)
        () ;;;; Remove this line and complete this procedure ;;;;
    )
)

; Validate an expression from the user
(define validate-bindings
    (lambda (expr bindings)
        () ;;;; Remove this line and complete this procedure ;;;;
    )
)

; Build a proper Scheme expression from expr with bindings resolved using
; bindings, or builtin procedures
(define resolve-bindings
    (lambda (expr bindings)
        () ;;;; Remove this line and complete this procedure ;;;;
    )
)

; Convert any infix subexpressions to prefix notation
(define infix-to-prefix
    (lambda (expr)
        () ;;;; Remove this line and complete this procedure ;;;;
    )
)