;; 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 Y0) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f))) #| ;; A Y0 implementation. @see http://www.radford.edu/itec380/2020fall-ibarland/Homeworks/Project/Y0.html @author ibarland@radford.edu @version 2021-Apr-01 @original-at http://www.radford.edu/itec380/2020fall-ibarland/Homeworks/Project/Y0.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 | Paren | BinOp | IfZero Paren ::= {= Expr =} Interpretation: a parenthesized expression BinOp ::= > Op Expr Expr < Interpretation: apply a binary operator Op ::= blam | swish | splat Interpretation: addition, subtraction, multiplication (resp.) IfZero ::= bliff Expr zok Expr nooo Expr ; Interpretation: if 1st expr is zero, answer is the 2nd expr, else use the 3rd expr |# ; datatype defn: ; An Expr is: ; - a number ; - (make-paren [Expr]) ; - (make-binop [Op] [Expr] [Expr]) ; - (make-if0 [Expr] [Expr] [Expr]) ; An Op is: (one-of "blam" "swish" "splat") (define-struct binop (op left right)) (define-struct paren (e)) (define-struct if0 (tst thn els)) ; Examples of Expr: 34 (make-paren 34) (make-binop "blam" 3 4) (make-binop "blam" (make-paren 34) (make-binop "splat" 3 4)) ; >blam {=34=} >splat 3 4<< (make-if0 3 7 9) (make-if0 (make-paren 1) (make-binop "blam" (make-paren 34) (make-binop 3 "splat" 4)) (make-if0 0 7 9)) (define OP-FUNCS (list (list "blam" +) (list "swish" -) (list "splat" *) )) (define OPS (map first OP-FUNCS)) ; An Op is: (one-of OPS) ; string->expr : string -> Expr ; given a string, return the parse-tree for the Y0 expression at its front. ; (define (string->expr prog) (parse! (create-scanner prog))) ; parse! : scanner -> Expr ; given a scanner, consume one Y0 expression off the front of it ; and ; return the corresponding parse-tree. ; (define (parse! s) ; Recursive-descent parsing: (cond [(number? (peek s)) (pop! s)] [(string=? "{" (peek s)) (let* {[_ (check-token= (pop! s) "{")] ; consume the '{' off the input-stream [_ (check-token= (pop! s) "=")] ; consume the '=' 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 '=' [_ (check-token= (pop! s) "}")] ; consume the trailing '}' } (make-paren the-inside-expr))] [(string=? ">" (peek s)) (let* {[_ (check-token= (pop! s) ">")] [op (pop! s)] [_ (if (not (member? op OPS)) (error 'parse! "Unknown op " op) 'keep-on-going)] [lefty (parse! s)] [righty (parse! s)] [_ (check-token= (pop! s) "<")] } (make-binop op lefty righty))] [(string=? "bliff" (peek s)) (let* {[_ (check-token= (pop! s) "bliff")] [the-test (parse! s)] [_ (check-token= (pop! s) "zok")] [the-then-ans (parse! s)] [_ (check-token= (pop! s) "nooo")] [the-else-ans (parse! s)] } (make-if0 the-test the-then-ans the-else-ans))] [else (error 'parse! (format "syntax error -- something has gone awry! Seeing " (peek s)))])) ; eval : Expr -> Num ; Return the value which this Expr evaluates to. ; In Y0, the only type of value is a Num. ; (define (eval e) (cond [(number? e) e] [(paren? e) (eval (paren-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))] [(if0? e) (if (zero? (eval (if0-tst e))) (eval (if0-thn e)) (eval (if0-els e)))] [else (error 'eval "unknown type of expr: " (expr->string e))])) ; eval-binop : op num num -> num ; Implement the binary operators. ; We just look up `op` in the list `OP-FUNCS`, and use the function that's in that list. (define (eval-binop op l r) (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 "blam") (+ l r)] [(string=? op "swish") (- l r)] [(string=? op "splat") (* l r)] [else (error 'eval "Unimplemented op " op)]) ; ; *** In your Y1 submission, DELETE whichever eval-binop approach you don't use. (check-expect (eval-binop "blam" 3 2) 5) (check-expect (eval-binop "swish" 3 2) 1) (check-expect (eval-binop "splat" 3 2) 6) ; expr->string : Expr -> string ; Return a string-representation of `e`. ; (define (expr->string e) (cond [(number? e) (number->string (if (integer? e) e (exact->inexact e)))] [(paren? e) (string-append "{=" (expr->string (paren-e e)) "=}")] [(binop? e) (string-append ">" (binop-op e) " " (expr->string (binop-left e)) " " (expr->string (binop-right e)) "<" )] [(if0? e) (string-append "bliff " (expr->string (if0-tst e)) " zok " (expr->string (if0-thn e)) " nooo " (expr->string (if0-els e)) )] [else (error 'expr->string "unknown type of expr: " e)])) ; check-token= : (or/c string? number?) (or/c string? number?) -> (or/c string? number?) ; Verify that `actual-token` equals `expected-token`; throw an error if not. ; IF they are equal, just return `actual-token` (as a convenience-value). ; (define (check-token= actual-token expected-token) (if (equal? actual-token expected-token) actual-token (error 'check-token= (format "Expected the token " expected-token ", but got " actual-token "."))))