;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "reader.ss" "plai" "lang")
; Lecture Notes 
; Programming Languages and Types
; 
; October 21, 2009
; Instructor: Sebastian Erdweg
; Lecture notes by Klaus Ostermann

; Use this file with DrScheme and the PLAI language level

; Based on PLAI by Shriram Krishnamurthi 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


; FAE is FWAE without "with"

(define-type FAE
  [num (n number?)]
  [add (lhs FAE?) (rhs FAE?)]
  [with (name symbol?) (named-expr FAE?) (body FAE?)]
  [id (name symbol?)]
  [fun (param symbol?) (body FAE?)]
  [app (fun-expr FAE?) (arg-expr FAE?)])


(define (desugar expr)
  (type-case FAE expr
    [num (n) expr]
    [add (l r)  (add (desugar l) (desugar r))]
    [id (v) expr]
    [fun (bound-id bound-body) 
         (fun bound-id (desugar bound-body))]
    [app (the-fun the-arg) 
         (app (desugar the-fun) (desugar the-arg))]
    [with (id ne body)
          (app (fun id (desugar body)) (desugar ne))]))



; a *closure* is a function together with the environment in which it was defined

; Let's fix the interpreter!


(define-type FAE-Value
   [numV (n number?)]
   [closureV (param symbol?) (body FAE?) (env Env?)])


(define-type Env
  [emptyEnv]
  [anEnv (name symbol?) (val FAE-Value?) (rest Env?)])


(define (lookup name env)
  (type-case Env env
    [emptyEnv () (error 'lookup "name not found")]
    [anEnv (n value rest)
           (if (symbol=? n name)
               value
               (lookup name rest))]))



; Let's define the interpreter

; interp: FAE Env -> FAE-Value
(define (interp expr env)
  (type-case FAE expr
    [num (n) (numV n)]
    [add (l r) (numV (+ (numV-n (interp l env)) (numV-n (interp r env))))]
    [id (v) (lookup v env)]
    [fun (bound-id bound-body) (closureV bound-id bound-body env)]
    [app (fun-expr arg-expr)
      (let ((closure-val (interp fun-expr env))
            (arg-val (interp arg-expr env)))
        (interp (closureV-body closure-val)
                (anEnv (closureV-param closure-val) arg-val (closureV-env closure-val))))]
    [else (error 'interp "please desugar first")]))
        
         



; Tests

(define test1 
  (with 'x (num 3)
         (with 'f (fun 'y (add (id 'x) (id 'y)))
               (with 'x (num 5)
                     (app (id 'f) (num 4))))))

(define testres1
  (interp (desugar test1) (emptyEnv)))




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; The significance of static scoping and closures

; What programming style do they enable?

; filter : (a -> Bool), listof(a) -> listof(a)
(define (filter p x)
  (cond
     [(empty? x) empty]
     [(p (car x)) (cons (car x) (filter p (cdr x)))]
     [else (filter p (cdr x))]))

; gt : int -> (int -> Bool)
(define (gt x)
  (lambda (n)
    (if (> n x)
        true
        false)))

(define testFilter
  (filter (gt 5) (list 1 2 3 4 5 6 7 8 9)))