; http://www.radford.edu/itec380/2008fall/Homeworks/Hw06/hw06.html
; Ian Barland, 2008.Nov.27

; Run this program in language-level 'Module',
; *not* 'Advanced Student'.
; (This is because we are exporting our functions
;  as a module, so the test-cases can use them.)

; These two lines make a module which exports everything
; (in Java terms: a package where everything is public).
;
#lang scheme
(provide (all-defined-out))
(require "scanner.ss")  ; scanner.ss must be in the same dir as this file.
(require test-engine/scheme-tests)


;;;;;;;;;;; language N0 ;;;;;;;;;;;;;;

; An Expr is one of:
; - a number
; - (make-paren-expr [Expr])
; - (make-bin-expr [Expr] [Bin-op] [Expr])
; - (make-is0-expr [Expr] [Expr] [Expr])
;
; A Bin-op is a string in the list BIN_OP_TOKENS:
;
(define BIN_OP_TOKENS (list "plus" "minus" "times"))

(define (bin-op? any-val) (member any-val BIN_OP_TOKENS))


(define-struct bin-expr (left op right) #:transparent)
(define-struct paren-expr (e) #:transparent)
(define-struct is0-expr (cond then else) #:transparent)
;
; The keyword 'transparent' makes structs with 'public' fields;
; in particular check-expect can inspect these structs.



; parse!: ( scanner -> expr)
; Return (our internal, parse-tree representation of) the first M0 expr
; at the front of the scanner.
; Side effect: Consumes tokens from scnr corresponding exactly
; to the returned expr.
;
(define (parse! scnr)
  (cond [(number? (peek scnr)) (pop! scnr)]
        [(string=? (peek scnr) "if")
         (let* {[open-is0 (pop! scnr)]  ; Pop off the "if" we just peeked at.  Ignore it.
                [subexpr1 (parse! scnr)]
                [the-is0-keyword  (pop! scnr)] ; pop off the "is0";  ignore it.
                [the-then-keyword (pop! scnr)] ; pop off the "then"; ignore it.
                [subexpr2 (parse! scnr)]
                [the-else-keyword (pop! scnr)] ; pop off the "else"; ignore it.
                [subexpr3 (parse! scnr)]
                [the-semicolon (pop! scnr)] ; pop off the ";"; ignore it.
                }
           (make-is0-expr subexpr1 subexpr2 subexpr3))]
        [(string=? (peek scnr) "(")
         ; Hmm, we have *either* a paren-expr, or a bin-expr.
         (let* {[open-paren (pop! scnr)]  ; Pop off the "(" we just peeked at.  Ignore it.
                [subexpr1 (parse! scnr)]  ; Read an *entire* expr, even if deeply nested!
                }
           (if (string=? (peek scnr) ")")
               (begin (pop! scnr)
                      (make-paren-expr subexpr1))
               (let* {[operator (pop! scnr)]
                      [subexpr2 (parse! scnr)]
                      [closing-paren (pop! scnr)]
                      }
                 (when (not (string=? closing-paren ")"))
                   (error 'parse! "Expected ')', got: ~v." closing-paren))
                 (when (not (bin-op? operator))
                   (error 'parse! "Expected one of ~v, got ~v." BIN_OP_TOKENS operator))
                 (make-bin-expr subexpr1 operator subexpr2))))]
         [else (error 'parse! "Unrecognized expr: ~v." (peek scnr))]))

; parse-string: (-> string expr)
; Convert the given string representing exactly *one* single Expr
; into our internal format (structs).
;
(define (parse-string str)
  (parse! (create-scanner str)))


; expr->string : (-> expr string) (a.k.a. toString)
; Return a human-readable version of our internal representaiton of Exprs.
; 
(define (expr->string e)
  (cond [(number? e) (number->string e)]
        [(paren-expr? e) (string-append
                          "("
                          (expr->string (paren-expr-e e))
                          ")"
                          )]
        [(bin-expr? e) (string-append
                        "(" 
                        (expr->string (bin-expr-left e))
                        " "
                        (bin-expr-op e)
                        " "
                        (expr->string (bin-expr-right e))
                        ")"
                        )]
        [(is0-expr? e) (string-append 
                        "if "
                        (expr->string (is0-expr-cond e))
                        " is0 then "
                        (expr->string (is0-expr-then e))
                        " else "
                        (expr->string (is0-expr-else e))
                        ";"
                        )]
        [else (error 'expr->string "unknown internal format?!: ~v" e)]
        ))
        



; eval : (-> expr val)
; Evaluate the given expr.
;
(define (eval e)
  (cond [(number? e) e]
        [(paren-expr? e) (eval (paren-expr-e e))]
        [(bin-expr? e) (eval-bin-expr e)] ; defer to a helper
        [(is0-expr? e)
         (if (= (eval (is0-expr-cond e)) 0)
             (eval (is0-expr-then e))
             (eval (is0-expr-else e)))]
        [else (error 'eval "unknown internal format?!: ~v" e)]))

(define (eval-bin-expr e)
  (let* {[left-value  (eval (bin-expr-left  e))]
         [right-value (eval (bin-expr-right e))]
         }
    (cond [(string=? (bin-expr-op e) "plus")
           (+ left-value right-value)]
          [(string=? (bin-expr-op e) "times")
           (* left-value right-value)]
          [(string=? (bin-expr-op e) "minus")
           (- left-value right-value)])))

              


;;;;;;;;;;;;;;;;;;; TEST CASES: N0 ;;;;;;;;;;;;;;;;
;;; The following gets used by 'N-test-helpers.ss':

(define tests
  ; Each entry in the list is either
  ; [str val] (where val is the result of interpreting the string str), or
  ; [str val expr] (as above, but expr is the internal (struct) representation).
  `{["7" 7 7]
    ["(3 plus 4)" 7 ,(make-bin-expr 3 "plus" 4)]
    ["(3 times   4)" 4 ,(make-bin-expr 3 "times" 4)]
    ["((3 plus 4) plus(  3  times 4 ))" 19]
    ["if 0 is0 then 1 else 2;" 1 ,(make-is0-expr 0 1 2)]
    ["if 1 is0 then 1 else 2 ;" 2 ,(make-is0-expr 1 1 2)]
    ["if (3 plus -3) is0 then 1 else 2;" 1 ,(make-is0-expr (make-bin-expr 3 "plus" -3) 1 2)]
    ["if (if if 0 is0 then 1 else 2; is0 then 3 else 4 ; plus -3) is0 then  1 else 2;" 
     2
     ,(make-is0-expr (make-bin-expr (make-is0-expr (make-is0-expr 0 1 2) 3 4) "plus" -3) 1 2)]
    })

; Some expressions to test in a non-automated way:
(define e0 "43")
(define e1 "(43)")
(define e2 "(4 plus 3)")
(define e3 "((((4 plus 3))))")
(define e4 "((43) plus    (  42 times 3))")


(check-expect (parse-string "39") 39)
(check-expect (parse-string "(4 plus 3)") (make-bin-expr 4 "plus" 3))
(check-expect (eval (parse-string "(4 plus 3)")) 7)

(check-expect (eval (parse-string e4)) 169)

(check-error (parse-string "()") "parse!: Unrecognized expr: \")\".")
(test)  ; This call actually *runs* the tests
        ; that have been previously registered via check-expect.