;; 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))]))


; Environment-based interpreter for FAE

; How to define the environment?

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

(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) (funV bound-id bound-body)]
    [app (fun-expr arg-expr)
      (let ((fun-val (interp fun-expr env))
            (arg-val (interp arg-expr env)))
        (interp (funV-body fun-val)
                (anEnv (funV-param fun-val) arg-val env)))]
    [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)))