;; 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(planet plai/plai:1:3/lang/reader)
(define-type DefrdSub
  [mtSub]
  [aSub (name symbol?)
        (value number?)
        (rest DefrdSub?)])

(mtSub)
(aSub 'x 1 (mtSub))
(aSub 'y 2 (aSub 'x 1 (mtSub)))

(define-type FunDef
  [fundef (fun-name symbol?)
          (arg-name symbol?)
          (body F1WAE?)])

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

; interp : F1WAE list-of-FunDef DefrdSub -> num
(define (interp a-wae defs ds)
  (type-case F1WAE a-wae
    [num (n) n]
    [add (l r) (+ (interp l defs ds) (interp r defs ds))]
    [sub (l r) (- (interp l defs ds) (interp r defs ds))]
    [with (bound-id named-expr body-expr)
      (interp body-expr
              defs
              (aSub bound-id
                    (interp named-expr defs ds)
                    ds))]
    [id (name) (find-value name ds)]
    [app (fname arg-expr)
         (local [(define f (find-def fname defs))]
           (interp (fundef-body f)
                   defs
                   (aSub (fundef-arg-name f)
                         (interp arg-expr defs ds)
                         (mtSub))))]))

;; find-value : symbol DefrdSub -> number
(define (find-value name ds)
  (type-case DefrdSub ds
    [mtSub () (error 'interp "free variable")]
    [aSub (name2 val2 rest)
          (if (symbol=? name name2)
              val2
              (find-value name rest))]))

(test (find-value 'a (aSub 'a 10 (mtSub))) 10)
(test/exn (find-value 'a (mtSub))
          "free variable")
(test (find-value 'a (aSub 'b 5
                           (aSub 'a 10 (mtSub))))
      10)

; find-def : sym list-of-FunDef -> FunDef
(define (find-def fname l)
  (cond
    [(empty? l) (error "no such function")]
    [else (if (symbol=? fname (fundef-fun-name (first l)))
              (first l)
              (find-def fname (rest l)))]))

(test (interp (id 'x) empty (aSub 'x 10 (mtSub)))
      10)

(test/exn (find-def 'x empty) "no such function")
(test (find-def 'f (list
                    (fundef 'g 'y (num 12))
                    (fundef 'f 'y (num 10))))
      (fundef 'f 'y (num 10)))

(test (interp (num 5) empty (mtSub))
      5)
(test (interp (add (num 1) (num 2)) empty (mtSub))
      3)
(test (interp (sub (num 1) (num 2)) empty (mtSub))
      -1)
(test (interp (with 'x (add (num 1) (num 17))
                (add (id 'x) (num 12)))
              empty
              (mtSub))
      30)
(test/exn (interp (id 'x) empty (mtSub))
      "free variable")

(test/exn (interp (app 'f (num 10)) empty (mtSub))
          "no such function")

(test (interp (app 'f (num 10))
              (list (fundef 'f
                            'y
                            (add (id 'y) (num 1))))
              (mtSub))
      11)
(test (interp (app 'f (num 10))
              (list
               (fundef 'f
                       'y
                       (with 'y (num 7)
                             (id 'y))))
              (mtSub))
      7)

(test/exn (interp (with 'y (num 10)
                    (app 'f (num 7)))
                  (list (fundef 'f 'x
                                (id 'y)))
                  (mtSub))
          "free variable")