GOAL: Extend the WAE language to include multiply and divide operators (*, /) and a conditional expression:

 (if<0 expr val1 val2) 

which has the value val1 if expr is less than zero and val2 otherwise. So,

 {with {a 5} {if<0 a 77 99}} 

would have the value 99.

Implement the divide operator as an integer divide using quotient so that (/ 7 4) is 1 (not 1.75 or 1 3/4).

Also add a unary minus [ new tree (minus (operand CWAE?)) ]. For instance,

 {with {x -12} {- x}} 

has value 12.

In other words, you should write a parser and interpreter for the grammar:

 ::=  |  | {+  } | {-  } | {*  } | {/  } | {- } | {with { } } | {if<0   } 

Your parser should include error checking for illegal input.

METHOD: Work a little at a time. Don't try to do everything at once and then see if it runs (it almost surely won't). Also remember you need to be using #lang plai in order for define-type to work.

I would start by adding in multiplication and division. This is just like we did in class. Notice in this case that you're starting with the WAE language (in class we added the operations to the AE language). You'll need to modify the define-type to include the new tree variants, then change the parser to handle the new variants, and then update calc to compute with the new trees.

For the other additions (if<0 and unary -) you'll need to go through these same steps (adjust data type, parser, calc).

You can start including error checking at any point. For example, you could begin by just adding error checking to the WAE grammar. That means the parser should only accept input that matches the grammar. So, every input should be a number, a symbol, or a list starting with + or - or with. The lists starting with + and - should be length 3. Lists starting with with should have length 3 and the second entry should be a list of length 2 (where the first entry is just a symbol).

Notice once you add unary minus, then there are two legal possibilities for lists starting with -. They can be length 3 (and get parsed into a sub tree) or length 2 (and get parsed into a minus tree).

A sample program:

{with {x 9} ; you can change these vals, but the larger one should {with {y 3} ; always wind up at the left of the final number ; and the smaller one at the right {with {min {if<0 {- x y} x y}} {with {max {if<0 {- x y} y x}} {+ {* max 1000} min} ; output will be best if smaller is }}}} ; no more than two digits 

Some examples of illegal input (the parser should report syntax errors for these):

{+ 4 5 6} {+ 2} {with 6} {with 'x 6} {3 4 5} {- 6 5 2} {+} {with {x 32} {+ x 4} {+ x 10}}

Here is WAE language Code:

#lang plai ;; Abstract trees for "with" with arithmetic expressions (WAE) (define-type WAE [num (n number?)] [add (lhs WAE?) (rhs WAE?)] [sub (lhs WAE?) (rhs WAE?)] [with (name symbol?) (named-expr WAE?) (body WAE?)] [id (name symbol?)] ) ;; parse : sexp -> WAE ;; to convert s-expressions into WAEs (define (parse sexp) (cond [(number? sexp) (num sexp)] [(symbol? sexp) (id sexp)] [(list? sexp) (case (first sexp) [(+) (add (parse (second sexp)) (parse (third sexp)))] [(-) (sub (parse (second sexp)) (parse (third sexp)))] [(with) (with (first (second sexp)) (parse (second (second sexp))) (parse (third sexp)))] )] )) ;; subst : WAE symbol WAE --> WAE ;; substitutes second argument with third argument in first argument, ;; as per the rules of substitution; the resulting expression contains ;; no free instances of the second argument ;; (version p.26 of Krishnamurthi) (define(subst expr sub-id val) (type-case WAE expr [num (n) expr] [add (l r) (add (subst l sub-id val) (subst r sub-id val))] [sub (l r) (sub (subst l sub-id val) (subst r sub-id val))] [with (bound-id named-expr bound-body) (if (symbol=? bound-id sub-id) (with bound-id (subst named-expr sub-id val) bound-body) (with bound-id (subst named-expr sub-id val) (subst bound-body sub-id val)))] [id (v) (if (symbol=? v sub-id) val expr)] )) ;; calc : WAE --> number ;; evaluates WAE expressions by reducing them to numbers (define (calc expr) (type-case WAE expr [num (n) n] [add (l r) (+ (calc l) (calc r))] [sub (l r) (- (calc l) (calc r))] [with (bound-id named-expr bound-body) (calc (subst bound-body bound-id (num (calc named-expr))))] [id (v) (error 'calc "free identifier ~a" v)] )) (define e1 (with 'x (num 12) (sub (id 'x) (with 'x (num 2) (add (id 'x) (id 'x))))) ) (define e2 (with 'x (num 12) (sub (add (num 5) (id 'x)) (with 'y (num 2) (add (id 'x) (id 'y))))) ) (test (calc (parse '5)) 5) (test (calc (parse '{+ 5 5})) 10) (test (calc (parse '{with {x {+ 5 5}} {+ x x}})) 20) (test (calc (parse '{with {x 5} {+ x x}})) 10) (test (calc (parse '{with {x {+ 5 5}} {with{y{- x 3}}{+ y y}}})) 14) (test (calc (parse '{with {x 5} {with{y{- x 3}}{+ y y}}})) 4) (test (calc (parse '{with {x 5} {+ x{with{x 3}10}}})) 15) (test (calc (parse '{with {x 5} {+ x{with{x 3}x}}})) 8) (test (calc (parse '{with {x 5} {+ x{with{y 3}x}}})) 10) (test (calc (parse '{with {x 5} {with{y x}y}})) 5) (test (calc (parse '{with {x 5} {with{x x}x}})) 5)