;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname 2015-11-23-lerner) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f)))
;; A Husky expression (HExp) is one of:
;; -- Boolean                           -- booleans
;; -- Number                            -- numbers
;; -- (list 'const SExp)                -- constant values
;; -- Ident                             -- identifiers
;; -- (list 'if HExp HExp HExp)         -- if expressions
;; -- (list 'fun [Listof Idents] HExp)  -- lambdas
;; -- [Listof HExp]                     -- function applications
;; An Ident is a Symbol other than 'if, 'const, or 'fun

#|
Some examples of Husky expressions:
'(if (< (abs -5) 6) true 17)
==> {by the rules of how quote works}
(list 'if '(< (abs -5) 6) true 17)
==> {again}
(list 'if (list '< '(abs -5) 6) true 17)
==> {again}
(list 'if (list '< (list 'abs -5) 6) true 17)
|#

;; ALWAYS-5 is the function that always returns 5
(define ALWAYS-5 '(fun (x) 5))

;; IDENTITY is the function that returns its argument unchanged
(define IDENTITY '(fun (x) x))

;; ABS is a HExp representing the absolute-value function
(define ABS '(fun (x) (if (< x 0) (- 0 x) x)))


;; Is s the same keyword as the given keyword?
(define (keyword=? kwd s)
  (and (symbol? s) (symbol=? s kwd)))

;; A HValue is one of
;; Boolean
;; Number
;; SExp
;; Closure
;; A Prim is a (make-prim [some ISL function])
;; A Closure is a (make-clos [Listof Ident] HExp Env)
(define-struct clos (params body env))
(define-struct prim (func))

#|
We're going to implement functions and function-application without resorting to
"substituting" values for identifiers in our syntax.  Instead, we're going to
use an *environment* that maps identifiers to values.  Whenever we evaluate
an identifier, we just look it up in the environment.  By storing values, we ensure
that we preserve the same evaluation order as ISL does: arguments to functions are
evaluated exactly once, before the function gets called, and can be reused many times
within the function body.

Evaluating a function must create some kind of value.  We call this value a "closure".
Closures need to keep track of the names of the function parameters, and the function body.
They also must keep track of the environment in which they were created, or else
we'll break the scoping rules that match our expectations from ISL.
|#


(define-struct pair (fst snd))

;; An Environment is a [Listof [Pair Ident HValue]]
(define (lookup name env)
  (cond
    [(empty? env)
     (error 'no-such-symbol "Can't find symbol in environment: " name)]
    [else
     (if (symbol=? name (pair-fst (first env)))
         (pair-snd (first env))
         (lookup name (rest env)))]))
(check-expect (lookup 'x (list (make-pair 'x 5) (make-pair 'y 6))) 5)
(check-expect (lookup 'x (list (make-pair 'y 5) (make-pair 'x 6))) 6)
(check-expect (lookup 'x (list (make-pair 'x 5) (make-pair 'x 6))) 5) ;; newer bindings "shadow" older ones
(check-error (lookup 'x (list)) "no-such-symbol: Can't find symbol in environment: 'x")

     
  
;; eval : HExp Env -> HValue
(define (eval hexp env)
  (cond
    [(boolean? hexp) hexp] ;; Booleans evaluate to themselves
    [(number? hexp) hexp]  ;; Numbers evaluate to themselves
    [(symbol? hexp)        ;; If we get a symbol,
     (lookup hexp env)]    ;; look it up in the environment
    [else      ;; everything else is a list of some sort
     (local
       ((define e1 (first hexp))) 
       (cond
         [(keyword=? 'const e1)
          (second hexp)]   ;; constants evaluate to the SExp inside
         [(keyword=? 'if e1) ;; If expressions...
          (local ((define c (second hexp))
                  (define t (third hexp))
                  (define f (fourth hexp)))
            (if (eval c env) ;; ... evaluate the condition, and 
                (eval t env) ;; if it's true, evaluate the true branch
                (eval f env)))] ;; otherwise evaluate the false branch
         [(keyword=? 'fun e1) ;; Functions evaluate to closures
          ;; which store all the arguments, the body, *and the current environment*
          (make-clos (second hexp) (third hexp) env)]
         [else ;; function application
          (local (;; Must evaluate the function
                  (define the-fun (eval (first hexp) env))
                  ;; and evaluate all the arguments
                  (define the-args (map (λ(a) (eval a env)) (rest hexp))))
            (cond
              [(prim? the-fun) ;; if it's a built-in "primitive" function
               (apply (prim-func the-fun) the-args)] ;; call that function
              [(clos? the-fun) ;; otherwise it's a Husky function
               (local
                 ((define the-params (clos-params the-fun))
                  (define the-body (clos-body the-fun))
                  (define the-clos-env (clos-env the-fun))
                  (define the-new-env
                    (append ;; add new bindings to the environment mapping
                     (map (λ(p a) (make-pair p a)) the-params the-args) ;; each parameter to the given argument value
                     the-clos-env)) ;; and add it to the closure's saved environment
                  )
                 (eval the-body the-new-env))] ;; evaluate the body in that new environment
              [else
               (error 'not-a-function "Didn't get a function " the-fun)] ;; oops
              ))]))]))




(define ENV0 (list
              (make-pair '< (make-prim <))
              (make-pair '> (make-prim >))
              (make-pair '+ (make-prim +))
              (make-pair '- (make-prim -))))


(define ADDER '(fun (x) (fun (y) (+ x y))))

;; Double-check that our environments and closures work properly
(check-expect (eval (list (list ADDER 5) 3) ENV0) 8)
(check-expect (eval (list ABS (list (list ADDER -5) -3)) ENV0) 8)
;; Just because a function is named "+" doesn't mean it actually does addtion...
(check-expect (eval (list (list ADDER 5) 3) (cons (make-pair '+ (make-prim *)) ENV0)) 15)