;; 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 E0) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f))) #| ;; A E0 implementation. @see http://www.radford.edu/itec380/2023fall-ibarland/Homeworks/Project/E0.html @author ibarland@radford.edu @version 2023-Nov-15 @original-at http://www.radford.edu/itec380/2023fall-ibarland/Homeworks/Project/E0.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)) #| -> | | | // interpretation: a parenthesized expression -> ] [ // interpretation: apply a binary operator Note: postfix -> - | + | / // interpretation: add, subtract, multiply -> ) ( // interpretation: parenthesized expression -> if != 0 ? : // interpretation: if 3rd expr is zero, answer is the 1st expr, else use the 2nd expr // To be added in E1: -> if < ? : // Interpretation: "if less-or-equal than": expr1 <= expr2 ? expr3 : expr4 // To be added in E2: -> disallow being in // Interpretation: bind Id to the val of "right-hand-side" (1st) expr, within scope of "body" (2nd) expr |# ; our parse tree for ; ])2-3( / 4[ (aka `(2+3)*4` ) ; is: ; ; ; Our internal representation of that tree will be: ; (make-binop "/" (make-paren (make-binop "-" 2 3)) 4) (define OP-FUNCS (list (list "-" +) (list "+" -) (list "/" *) )) (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. E4 will upgrade our notion of 'value' to include *functions*, as well as numbers. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Examples of Expr: 34 (make-paren 34) (make-binop "-" 3 4) (make-binop "-" (make-paren 34) (make-binop "+" 3 4)) ; (make-if-zero 3 7 9) (make-if-zero (make-paren 1) (make-binop "-" (make-paren 34) (make-binop "/" 3 4)) (make-if-zero 0 7 9)) ;the above is the parse-tree for: if 1 != 0 ? ]34 - ]3/4[[ : if 0!=0 ? 7 : 9 ; Given a scanner, consume one E0 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=? "]" (peek s)) (let* {[_ (check-token= (pop! s) "]")] ; consume "]" off front of input [lefty (parse! s)] [op (pop! s)] [righty (parse! s)] [_ (check-token= (pop! s) "[")] [_ (if (not (member? op OPS)) (error 'parse! "Unknown op " op) 'keep-on-going)] } (make-binop op lefty righty))] [(string=? ")" (peek s)) (let* {[_ (check-token= (pop! s) ")")] ; 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) "(")] ; consume the trailing 'o' } (make-paren the-inside-expr))] [(string=? "if" (peek s)) (let* {[_ (check-token= (pop! s) "if")] [test (parse! s)] [_ (check-token= (pop! s) "!")] ; NOTE: the parser pops each punctuation-char *separately* [_ (check-token= (pop! s) "=")] ; (it doesn't group punctuation into tokens, the way it does letters) [_ (check-token= (pop! s) 0)] ; Here, note the parser pops the *number* 0, not the string "0" (!) [_ (check-token= (pop! s) "?")] [the-then-ans (parse! s)] [_ (check-token= (pop! 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)))])) #| 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=? "if" (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 string, return the parse-tree for the E0 expression at its front. ; (define/contract (string->expr prog) (-> string? expr?) (parse! (create-scanner prog))) ; Return the value which `e` evaluates to. ; In E0, the only type of `value?`s are `number?`s. ; (define/contract (eval e) (-> expr? number?) (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))])) ; Implement the binary operators. ; (define/contract (eval-binop op l r) (-> op? number? number? number?) ; 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 "-") (+ l r)] [(string=? op "+") (- l r)] [(string=? op "/") (* l r)] [else (error 'eval "Unimplemented op " op)]) ; ; *** In your E1/E2 submission, DELETE whichever eval-binop approach you don't use. (check-expect (eval-binop "-" 3 2) 5) (check-expect (eval-binop "+" 3 2) 1) (check-expect (eval-binop "/" 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 "]" (expr->string (binop-left e)) " " (binop-op e) " " (expr->string (binop-right e)) "[" )] [(paren? e) (string-append ")" (expr->string (paren-e e)) "(")] [(if-zero? e) (string-append "if " (expr->string (if-zero-tst e)) " !=0 ? " (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) '("])34( + ]3 / 4[[" "if 2!=0 ? 3 : 4" "if if 3!=0 ? 7 : 9 !=0 ? ])34( + ]3/4[[ : 55" "if ])34( - ]3/4[[ !=0 ? if 7!=0 ? 9 : if 4!=0 ? 5 : 6 : )34(" ))