;;> The AE interpreter
#lang typed-scheme

#| BNF for the AE language:
   <AE> ::= <num>
          | { + <AE> <AE> }
          | { - <AE> <AE> }
          | { * <AE> <AE> }
          | { / <AE> <AE> }
|#

;; AE abstract syntax trees
(define-type AE
  [Num (n Number)]
  [Add (lhs AE) (rhs AE)]
  [Sub (lhs AE) (rhs AE)]
  [Mul (lhs AE) (rhs AE)]
  [Div (lhs AE) (rhs AE)])

(: parse-sexpr : (Sexpr -> AE))
;; to convert s-expressions into AEs
(define (parse-sexpr sexpr)
  (match sexpr
    [(number: n) (Num n)]
    [(list op left right)
     (let ([make-node
            (match op
              ['+ Add]
              ['- Sub]
              ['* Mul]
              ['/ Div]
              [else (error 'parse-sexpr "don't know about ~s" op)])])
       (make-node (parse-sexpr left)
                  (parse-sexpr right)))]
    [else (error 'parse-sexpr "bad syntax in ~s" sexpr)]))

(: parse : (String -> AE))
;; parses a string containing an AE expression to an AE AST
(define (parse str)
  (parse-sexpr (string->sexpr str)))

(: eval : (AE -> Number))
;; consumes an AE and computes the corresponding number
(define (eval expr)
  (cases expr
    [(Num n)   n]
    [(Add l r) (+ (eval l) (eval r))]
    [(Sub l r) (- (eval l) (eval r))]
    [(Mul l r) (* (eval l) (eval r))]
    [(Div l r) (/ (eval l) (eval r))]))

(: run : (String -> Number))
;; evaluate an AE program contained in a string
(define (run str)
  (eval (parse str)))

;; tests:
(test (run "3") => 3)
(test (run "{+ 3 4}") => 7)
(test (run "{+ {- 3 4} 7}") => 6)