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

;; parse : sexp −> WAE
;; to convert s-expressions into WAEs
(define (parse sexp)
  (cond
    [(number? sexp) (num sexp)]
    [(symbol? sexp) (id sexp)]
    [(list? sexp)
     (case (first sexp)
       [(+) (add (parse (second sexp))
                 (parse (third sexp)))]
       [(-) (sub (parse (second sexp))
                 (parse (third sexp)))]
       [(with) (with (first (second sexp)) 
                     (parse (second (second sexp))) 
                     (parse (third sexp)))])]))

(parse 3)
(parse '{- 3 4})
(parse '{+ {- 4 7} 4})

;; subst : WAE symbol WAE!WAE
;; substitutes second argument with third argument in first argument,
;; as per the rules of substitution; the resulting expression contains
;; no free instances of the second argument
(define (subst expr sub-id val)
  (type-case WAE expr
             [num (n) expr]
             [add (l r) (add (subst l sub-id val)
                             (subst r sub-id val))]
             [sub (l r) (sub (subst l sub-id val)
                             (subst r sub-id val))]
             [with (bound-id named-expr bound-body)
                   (if (symbol=? bound-id sub-id)
                       (with bound-id
                             (subst named-expr sub-id val)
                             bound-body)
                       (with bound-id
                             (subst named-expr sub-id val)
                             (subst bound-body sub-id val)))] 
             [id (v) (if (symbol=? v sub-id) val expr)]))          



(define (calc an-ae)
  (type-case WAE an-ae
                           [num (n) n]
                           [add (l r) (+ (calc l) (calc r))]
                           [sub (l r) (- (calc l) (calc r))]
                           [with (bound-id named-expr bound-body)
                                 (calc (subst bound-body
                                              bound-id
                                              ;named-expr
                                              (num (calc named-expr))
                                              ))]
                           [id (v) (error 'calc ”free identifier”)]))

(define calc
  (let ([old-calc calc]
        [depth ""])
    (lambda (an-ae)
      (printf depth)
      (printf "Evaluating ")
      (print an-ae)
      (printf " ...\n")
      (let ([old-depth depth])
        (set! depth (string-append depth "|   "))
        (let ([result (old-calc an-ae)])
          (set! depth old-depth)
          (printf depth)
          (printf "Result ")
          (print result)
          (newline)
          result)))))

(test (calc (parse '{+ {- 3 4} 7})) 6)
(test (calc (parse '5)) 5)
(test (calc (parse '{+ 5 5})) 10)
(test (calc (parse '{with {x {+ 5 5}} {+ x x}})) 20)
(test (calc (parse '{with {x 5} {+ x x}})) 10)
(test (calc (parse '{with {x {+ 5 5}} {with {y {- x 3}} {+ y y}}})) 14)
(test (calc (parse '{with {x 5} {with {y {- x 3}} {+ y y}}})) 4)
(test (calc (parse '{with {x 5} {+ x {with {x 3} 10}}})) 15)
(test (calc (parse '{with {x 5} {+ x {with {x 3} x}}})) 8)
(test (calc (parse '{with {x 5} {+ x {with {y 3} x}}})) 10)
(test (calc (parse '{with {x 5} {with {y x} y}})) 5)
(test (calc (parse '{with {x 5} {with {x x} x}})) 5)

(newline)
(calc (parse '{with {x {- 2 1}} {with {y {+ x x}} y}}))