;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname D0) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f)))
#|
;; A D0 implementation.
@see http://www.radford.edu/itec380/2022fall-ibarland/Homeworks/Project/D0.html

@author ibarland@radford.edu
@version 2023-Apr-06
@original-at http://www.radford.edu/itec380/2022fall-ibarland/Homeworks/Project/D0.rkt

@license CC-BY -- share/adapt this file freely, but include attribution, thx.
    https://creativecommons.org/licenses/by/4.0/ 
    https://creativecommons.org/licenses/by/4.0/legalcode 
Including a link to the *original* file satisifies "appropriate attribution".
|#

(require "student-extras.rkt")
(require "scanner.rkt")
(provide (all-defined-out))

#|
<Expr>      ->  <Num> | <BinOp> | <ParenExpr> | <IfZero> // interpretation: a parenthesized expression
<BinOp>     ->  ring  <Expr> bearer <Expr> <Op>          // interpretation: apply a binary operator  Note: postfix
<Op>        ->  frodo | gollum | samwise                 // interpretation: add, subtract, multiply  
<ParenExpr> ->  o <Expr> o                               // interpretation: parenthesized expression
<IfZero>    ->  for <Expr> gondor <Expr> <Expr>          // interpretation: if 3rd expr is zero, answer is the 1st expr, else use the 2nd expr



// To be added in D1:
<IfLE>      ->  you <Expr> shall <Expr> not <Expr> pass <Expr> // Interpretation: "if less-or-equal than": expr1 < expr2  ?  expr3  : expr4

// To be added in D2:
<LetExpr>   ->  bind <Id> to <Expr> in <Expr>  // Interpretation: bind Id to the val of "right-hand-side" (1st) expr, within scope of "body" (2nd) expr
|#


; our parse tree for
;     ring o ring 2 bearer 3 frodo o bearer 4 samwise        (aka  `(2+3)*4` )
; is:
;     <draw on board in class>
;
; Our internal representation of that tree will be:
;   (make-binop "samwise" (make-paren (make-binop "frodo" 2 3)) 4)



(define OP-FUNCS (list (list "frodo" +)
                       (list "gollum" -)
                       (list "samwise" *)
                       ))
(define OPS (map first OP-FUNCS))

; datatype defn:
(define (op? val) (member val OPS))


; datatype defn
(define (expr? v)
  (or (number? v)
      (binop? v)
      (paren? v)
      (if-zero? v)))


(define-struct/c binop ([op op?] [left expr?] [right expr?]))   ; NOTE: `op` is our *first* field, despite our postfix syntax.
(define-struct/c paren ([e expr?]))
(define-struct/c if-zero ([tst expr?] [thn expr?] [els expr?]))

;(define (value? val) (number? val))  ; N.B.  D4 will upgrade our notion of 'value' to include *functions*, as well as numbers.




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


; Examples of Expr:
34
(make-paren 34)
(make-binop "frodo" 3 4)
(make-binop "frodo" (make-paren 34) (make-binop "gollum" 3 4))  ; 
(make-if-zero 3 7 9)
(make-if-zero (make-paren 1)
              (make-binop "frodo" (make-paren 34) (make-binop "samwise" 3 4))
              (make-if-zero 0 7 9))
;the above is the parse-tree for:






; An Op is: (one-of OPS)

(define/contract (string->expr prog)
  (-> string? expr?)
  ; given a string, return the parse-tree for the D0 expression at its front.
  ;
  (parse! (create-scanner prog)))




#| Our java version of `parse` corresponds more to:
(define/contract (parse! s)
  (-> scanner? expr?)
  (cond [(number? (peek s)) (parse-number s)]
        [(string=? "/" (peek s)) (parse-paren s)]
        [(string=? "~" (peek s)) (parse-binop s)]
        [(string=? "zro" (peek s))) (parse-if-zero s)]))

 And then `parse-binop` etc are each in their own class.
 (They simply need to be sure to recur on `Expr.parse`;
  if they just write `parse` they'll get, say, `Binop.parse`
  which is not general enough.)
|#





; Given a scanner, consume one D0 expression off the front of it
; and return the corresponding parse-tree.
;
(define/contract (parse! s)
  (-> scanner? expr?)
  ; Recursive-descent parsing:
  (cond [(number? (peek s)) (pop! s)]
        
        [(string=? "ring" (peek s))
         (let* {[_ (check-token= (pop! s) "ring")]  ; consume "ring" off front of input
                [lefty  (parse! s)]
                [_ (check-token= (pop! s) "bearer")]
                [righty (parse! s)]
                [op (pop! s)]
                [_ (if (not (member? op OPS))
                       (error 'parse! "Unknown op " op)
                       'keep-on-going)]
                }
           (make-binop op lefty righty))]
        
        [(string=? "o" (peek s))
         (let* {[_ (check-token= (pop! s) "o")]   ; consume the 'o' off the input-stream
                [the-inside-expr (parse! s)]      ; recursively consume one whole Expr (no matter how long) 
                [_ (check-token= (pop! s) "o")]   ; consume the trailing 'o'
                }
           (make-paren the-inside-expr))]

        [(string=? "for" (peek s))
         (let* {[_ (check-token= (pop! s) "for")] 
                [test (parse! s)]
                [_ (check-token= (pop! s) "gondor")]
                [the-then-ans (parse! s)]
                [the-else-ans (parse! s)]
                }
           (make-if-zero test the-then-ans the-else-ans))]
        
        [else (error 'parse! (format "syntax error -- something has gone awry!  Seeing ~v." (peek s)))]))


(define/contract (eval e)
  (-> expr? number?)
  ; Return the value which `e` evaluates to.
  ; In D0, the only type of `value?`s are `number?`s.
  ;
  (cond [(number? e) e]
        [(binop? e) (let* {[the-op    (binop-op e)]
                           [left-val  (eval (binop-left  e))]
                           [right-val (eval (binop-right e))]
                           }
                      (eval-binop the-op left-val right-val))]
        [(paren? e) (eval (paren-e e))]
        [(if-zero? e) (if (zero? (eval (if-zero-tst e)))
                          (eval (if-zero-thn e))
                          (eval (if-zero-els e)))]
        [else (error 'eval "unknown type of expr: " (expr->string e))]))


(define/contract (eval-binop op l r)
  (-> op? number? number?  number?)  
  ; Implement the binary operators.
  ;
  ; We just look up `op` in the list `OP-FUNCS`, and use the function that's in that list.
  (let* {[ops-entry (assoc op OP-FUNCS)]}
         ; OPS is a list of list-of-string-and-func;
         ; so `(second ops-entry)` is a function (if ops-entry is found at all).
    (cond [(cons? ops-entry) ((second ops-entry) l r)]
          [else (error 'eval-binop "Unimplemented op " op "; most be one of: " OPS)])))

   ; An alternate implementation -- forces us to repeat
   ; the string-constants already in OPS:
   #;(cond [(string=? op "frodo") (+ l r)]
           [(string=? op "gollum") (- l r)]
           [(string=? op "samwise") (* l r)]
           [else (error 'eval "Unimplemented op " op)])
   ;
   ; *** In your D1/D2 submission, DELETE whichever eval-binop approach you don't use.


(check-expect (eval-binop "frodo" 3 2) 5)
(check-expect (eval-binop "gollum" 3 2) 1)
(check-expect (eval-binop "samwise" 3 2) 6)


; Return a string-representation of `e`.
;
(define/contract (expr->string e)
  (-> expr? string?)
  (cond [(number? e) (number->string (if (integer? e) e (exact->inexact e)))]
        [(binop? e) (string-append "ring "
                                   (expr->string (binop-left e))
                                   " bearer "
                                   (expr->string (binop-right e))
                                   " "
                                   (binop-op e)
                                   )]
        [(paren? e) (string-append "o" " " (expr->string (paren-e e)) " " "o")]
        [(if-zero? e) (string-append "for "
                                     (expr->string (if-zero-tst e))
                                     " gondor "
                                     (expr->string (if-zero-thn e))
                                     " "
                                     (expr->string (if-zero-els e))
                                     )]
        [else (error 'expr->string "unknown type of expr: " e)]))




; datatype definition:
(define token? (or/c string? number?))

(define/contract (check-token= actual-token expected-token)
  (-> token? token? token?)
  ; Verify that `actual-token` equals `expected-token`; throw an error if not.
  ; IF they are equal, just return `actual-token` (as a convenience-value).
  ;
  (if (equal? actual-token expected-token)
      actual-token
      (error 'check-token= (format "Expected the token ~v, but got ~v." expected-token actual-token))))

(map (compose expr->string string->expr)
     '("ring o 34 o bearer ring 3 bearer 4 samwise frodo"
       "for for 3 gondor 7 9 gondor o 99 o ring o 34 o bearer ring 3 bearer 4 samwise frodo"
       "for    ring o 34 o
               bearer ring 3 bearer 4 samwise
               frodo
        gondor for 7
               gondor 9
                      for 4 gondor 5 6
               o 34 o"
       ))