Programming Languages Racket

Implement MUWAE which deals with multiple values. Begin with the WAE-implementation.rkt to serve as the basis of your work. As a first step, replace all of the ''WAE''s with ''MUWAE''.

Multiple Values Extend the language so that instead of only plain numeric values we actually deal with multiple values. Thus, a single number and a list of numbers are both valid WAE expressions. As a representation for this, we replace the number in the output of eval (and run) with (listof number).

Fixing the with The next that requires fixing is the one used in the evaluation of with. The problem there is that were still wrapping the numeric result of eval in a num so we can use it with subst, and num expects a single number. One way to resolve this would be to add a new variant called nums to our AST definition. But this would require reworking new cases for it in a few places. So instead, we will choose an easier solution: just change the existing num so instead of holding a single number it will hold a (listof number). Once you do that, you will have three easy fixes to do. First, the code that parses numbers should put a list with the number in the num. Next, there are two small fixes left in the eval function, and everything will work fine with it. Dont forget to add tests that demonstrate that this works: that using with to bind a name to a multi- valued expression works as expected.

(test (run "{+ 3 7}") '(10)) (test (run "{- 10 {3 5}}") '(7 5)) (test (run "{with {x {+ 5 5}} {+ x x}}") '(20))

Adding More Arithmetic Operators Finally, add two arithmetic operators, muwae-min and muwae-max that take three expressions evaluating to integers and return the minimum and the maximum number, respectively, to MUWAE:

(test (run "{muwae-min 3 4 5}") '(3)) (test (run "{muwae-max {+ 1 2} 4 5}") '(5)) (test (run "{+ {muwae-min 9 3 7} {muwae-max 6 2 20}}") '(23))

Racket Code I've done so far (but mine have some errors, Please help me modify it):

#lang plai (require (for-syntax racket/base) racket/match racket/list racket/string (only-in mzlib/string read-from-string-all))

;build a regexp that matches restricted character expressions, can use only ;{}s for lists, and limited strings that use '...' (normal racket escapes ;like , and '' for a single ') (define good-char "(?:[ \t a-zA-Z0-9_{}!?*/<=>:+-]|[.][.][.])") ;this would make it awkward for students to use \" for strings ;(define good-string "\"[^\"\\]*(?:\\\\.[^\"\\]*)*\"") (define good-string "[^\"\\']*(?:''[^\"\\']*)*") (define expr-re (regexp (string-append "^" good-char"*" "(?:'"good-string"'"good-char"*)*" "$"))) (define string-re (regexp (string-append "'("good-string")'")))

(define (string->sexpr str) (unless (string? str) (error 'string->sexpr "expects argument of type ")) (unless (regexp-match expr-re str) (error 'string->sexpr "syntax error (bad contents)")) (let ([sexprs (read-from-string-all (regexp-replace* "''" (regexp-replace* string-re str "\"\\1\"") "'"))]) (if (= 1 (length sexprs)) (car sexprs) (error 'string->sexpr "bad syntax (multiple expressions)"))))

;; MUWAE abstract syntax trees (define-type MUWAE [num (n (and number? list?))] [add (left MUWAE?)(right MUWAE?)] [sub (left MUWAE?)(right MUWAE?)] [with (name symbol?)(init MUWAE?)(body MUWAE?)] [id (name symbol?)] [muwae-min (expr1 MUWAE?) (expr2 MUWAE?) (expr3 MUWAE?)] [muwae-max (expr1 MUWAE?) (expr2 MUWAE?) (expr3 MUWAE?)])

;parse-sexpr : sexpr -> MUWAE ;to convert s-expressions into MUWAEs (define (parse-sexpr sexp) (match sexp [(? number?) (num (list sexp))] [(list '+ l r) (add (parse-sexpr l)(parse-sexpr r))] [(list '- l r) (sub (parse-sexpr l)(parse-sexpr r))] [(list 'with (list x i) b) (with x (parse-sexpr i) (parse-sexpr b))] [(? symbol?) (id sexp)] [(list 'muwae-min e1 e2 e3) (muwae-min (parse-sexpr e1) (parse-sexpr e2) (parse-sexpr e3))] [(list 'muwae-max e1 e2 e3) (muwae-max (parse-sexpr e1) (parse-sexpr e2) (parse-sexpr e3))] [else (error 'parse "bad syntax: ~a" sexp)]))

;parses a string containing a ;MUWAE expression to a MUWAE AST (define (parse string) (parse-sexpr (string->sexpr string)))

;subst: arg2 arg3 -> arg1 ;substitutes the second argument with the third argument in the ;first argument, as per the rules of substitution ;the resulting expression contains no free instances of the second argument (define (subst expr from to) (type-case MUWAE expr [num (n) expr] [add (l r) (add (subst l from to)(subst r from to))] [sub (l r) (sub (subst l from to)(subst r from to))] [with (bound-id named-expr bound-body) (with bound-id (subst named-expr from to) (if (symbol=? bound-id from) bound-body (subst bound-body from to)))] [id (name) (if (symbol=? name from)(num to) expr)] [muwae-min (e1 e2 e3) (muwae-min (subst e1 from to) (subst e2 from to) (subst e3 from to))] [muwae-max (e1 e2 e3) (muwae-max (subst e1 from to) (subst e2 from to) (subst e3 from to))]))

;eval: muwae -> numbers ;evaluates MUWAE expressions ;by reducing them to numbers (define (eval expr) (type-case MUWAE expr [num (n) n] [add (l r) (bin-op + (eval l)(eval r))] [sub (l r) (bin-op - (eval l)(eval r))] [with (bound-id named-expr bound-body) (eval (subst bound-body bound-id (eval named-expr)))] [id (name) (error 'eval "free-ids: ~s" name)] [muwae-min (e1 e2 e3) (car (sort (list (eval e1) (eval e2) (eval e3)) <))] [muwae-max (e1 e2 e3) (cdr (sort (list (eval e1) (eval e2) (eval e3)) >))] ))

;run: string->listof number ;evaluate a MUWAE program contained in a string (define (run string) (eval (parse string)))

;bin-op : (number number -> number) (listof number) (listof number) -> (listof number) ;applies a binary numeric function on all combinations of numbers from ;the two input lists, and return the list of all of the results (define (bin-op op ls rs) (define (helper l rs) ;; f : number -> number (define (f num) (op l num)) (map f rs)) (if (null? ls) null (append (helper (first ls) rs) (bin-op op (rest ls) rs))))