Q8 starter for CS 145

;; 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-beginner-abbr-reader.ss" "lang")((modname Q8-starter) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
(require racket/match)

(define-struct bin (op fst snd))

;; grammar for Faux-Racket (FR) so far:
;;
;; exp = number
;;     | (op exp exp)
;;
;; op  = + | * | - | /
;;
;; An sexp is a quoted exp.
;;
;; An AST is either a number or (make-bin opr x y),
;; where opr is a symbol and x and y are ASTs.

;; parse: sexp -> AST
;; structurally recursive in the grammar for sexps

(define (parse sx)
  (match sx
    [`(+ ,x ,y) (make-bin '+ (parse x) (parse y))]
    [`(* ,x ,y) (make-bin '* (parse x) (parse y))]
    [`(- ,x ,y) (make-bin '- (parse x) (parse y))]
    [`(/ ,x ,y) (make-bin '/ (parse x) (parse y))]
    [x x]))

;; interp: AST -> number
;; structurally recursive in definition of AST

(define (interp ast)
  (match ast
    [(struct bin ('+ x y)) (+ (interp x) (interp y))]
    [(struct bin ('* x y)) (* (interp x) (interp y))]
    [(struct bin ('- x y)) (- (interp x) (interp y))]
    [(struct bin ('/ x y)) (/ (interp x) (interp y))]
    [x (if (number? x)
           x
           (error 'interp "undefined variable " x))]))

;; tests using check-expect and check-error for parse and interp removed
;; build your own set and keep adding to it as the interpreter grows
;; the set below is not adequate!

(check-expect (parse 1) 1)
(check-expect (interp (parse 1)) 1)

;; To be added for Q8:
;;
;; exp      = (id exp)
;;          | (if0 exp exp exp)
;; defn     = (def (id id) exp)
;; def-list = (defn ...)
;;
;; An id is a symbol.

(define-struct app (fn arg))
(define-struct ifzero (test tex fex))

;; An AST can be (make-app rand rator),
;; where rand is a symbol, and rator is an AST.
;; It can also be (make-ifzero b t f),
;; where b, t, and f are ASTs.

(define-struct fundef (name param body))

;; A definition is a (make-fundef nm par bdy)),
;; where nm and par are symbols and bdy is an AST.
;;
;; parse-fundefs: sexp -> (listof fundef)
;; parses an sexp satisfying the grammar rule for def-list
;;
;; (define (parse-fundefs sx) ...)
;;
;; interp now has a new contract:
;; interp: AST (listof fundef) -> number
;;
;; (define (interp ast defs) ...)
;;
;; As a helper for interp, for function application:
;;
;; subst: symbol number AST -> AST
;;
;; (define (subst var val ast) ...)
;;
;; Note that the recursive applications of interp needed
;; to handle function application make interp no longer
;; structurally recursive.