**Set-up: **For this assignment, edit a copy of mula.rkt, which is on the course website. In particular, replace occurrences of “CHANGE” to complete the problems. Do not use any mutation (set!, set-mcar!, etc.) anywhere in the assignment.

**Overview: **This project has to do with mul461 (a Made Up Language for CMPSC 461). mul461 programs are written directly in Racket by using the constructors defined by the structs defined at the beginning of mula.rkt. This is the definition of mul461’s syntax for Part A:

- If
*s*is a Racket string, then (mul461-var*s*) is a mul461 expression (a variable use). - If
*n*is a Racket integer, then (mul461-int*n*) is a mul461 expression (an integer constant). - If
*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461-+*e*_{1 }*e*_{2}) is a mul461 expression (an addition). - If
*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461–*e*_{1 }*e*_{2}) is a mul461 expression (a subtraction). If*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461-**e*_{1 }*e*_{2}) is a mul461 expression (a multiplication). - If
*b*is a Racket boolean, then (mul461-bool*b*) is a mul461 expression (a boolean constant). - If
*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461-and*e*_{1 }*e*_{2}) is a mul461*e*_{1 }and*e*_{2 }should both evaluate to mul461-bool values. - If
*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461-or*e*_{1 }*e*_{2}) is a mul461*e*_{1 }and*e*_{2 }should both evaluate to mul461-bool values. - If
*e*is a mul461 expression that evaluates to a mul461-bool value, then (mul461-not*e*) is a mul461 - If
*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461-<*e*_{1 }*e*_{2}) is a mul461 expression that evaluates to a mul461-bool value if*e*_{1 }and*e*_{2 }evaluate to mul461-int - If
*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461-=*e*_{1 }*e*_{2}) is a mul461 expression that evaluates to a mul461-bool value if*e*_{1 }and*e*_{2 }evaluate to mul461-int - If
*e*_{1},*e*_{2}, and*e*_{3 }are mul461 expressions, then (mul461-if*e*_{1 }*e*_{2 }*e*_{3}) is a mul461 It is a condition where the result is*e*_{2 }if*e*_{1 }is a boolean constant of true else the result is*e*_{3}. Only one of*e*_{2 }and*e*_{3 }is evaluated. - If
*s*is a Racket string and*e*_{1 }and*e*_{2 }are mul461 expressions, then (mul461-let*s e*_{1 }*e*_{2}) is a mul461 expression (a let expression where the value resulting from evaluating*e*_{1 }is bound to*s*in the evaluation of*e*_{2}).

In Part A, A mul461 *value *is a mul461 integer constant, a or a mul461 boolean constant.

You should assume mul461 programs are syntactically correct (e.g., do not worry about wrong things like (mul461-int “hi”) or (mul461-int (mul461-int 37)). But do *not *assume mul461 programs are free of type errors like (mul461-+ (mul461-bool #t) (mul461-int 7)) or (mul461-not (mul461-int 3)).

**Warning: **What makes this assignment challenging is that you have to understand mul461 well and debugging an interpreter is an acquired skill.

**Turn-in Instructions: **Turn in your modified mula.rkt to gradescope.

1

**Problems:**

**Implementing the**mul461**Language:**Write a mul461 interpreter, i.e., a Racket function eval-exp that takes a mul461 expression e and either returns the mul461 value that e evaluates to under the empty environment or calls Racket’s error if evaluation encounters a run-time mul461 type error or unbound mul461

A mul461 expression is evaluated under an environment (for evaluating variables, as usual). In your interpreter, use a Racket list of Racket pairs to represent this environment (which is initially empty) so that you can use *without modification *the provided envlookup function. Here is a description of the semantics of mul461 expressions:

- All values evaluate to themselves. For example, (eval-exp (mul461-int 17)) would return (mul461-int 17),
*not* - A variable evaluates to the value associated with it in the environment.(This case for var is done for you.)
- An addition/subtraction/multiplication evaluates its subexpressions and, assuming they both produce integers, produces the mul461-int
*n*that is their sum/difference/product. (Note the case for addition is done for you to get you pointed in the right direction.) - An
*<*or = comparison evaluates its subexpressions and, assuming they both produce integers, produces the mul461-bool*b*that is the result of comparing the two integer values. - An and/or evaluates its subexpressions and, assuming they both produce booleans, produces the mul461-bool
*b*that is their and/or boolean operation result. - A not evaluates its subexpression and, assuming it produces a boolean, produces the mul461-bool
*b*that is the logical negation of its subexpression result. - An if evaluates its first expression to a value
*v*_{1}. If it is a boolean, then if it is mul461-bool #t, then if evaluates to its second subexpression, else it evaluates its third subexpression. Only one of*e*_{2 }and*e*_{3 }should be evaluated. Do not evaluate both*e*_{2 }and*e*_{3}. - A let expression evaluates its first expression to a value
*v*. Then it evaluates the second expression to a value, in an environment extended to map the name in the let expression to*v*.

**Expanding the Language:**mul461 is a small language, but we can write Racket functions that act like mul461 macros so that users of these functions feel like mul461 is larger. The Racket functions produce mul461 expressions that could then be put inside larger mul461 expressions or passed to eval-exp. In implementing these Racket functions, do not use closure (which is used only internally in eval-exp). Also do not use eval-exp (we are creating a program, not running it).- Write a Racket function makelet* that takes a Racket list of Racket pairs ’((
*s*_{1 }.*e*_{1}) …(*s*._{i }*e*) …(_{i}*s*._{n }*e*)) and a final mul461 expression_{n}*e*_{n}_{+1}. In each pair, assume*s*is a Racket string and_{i }*e*is a mul461 makelet* returns a mul461 expression whose value is_{i }*e*_{n}_{+1 }evaluated in an environment where each*s*is a variable bound to the result of evaluating the corresponding_{i }*e*for 1 ≤_{i }*i*≤*n*. The bindings are done sequentially, so that each*e*is evaluated in an environment where_{i }*s*_{1 }through*s*_{i}_{−1 }have been previously bound to the values*e*_{1 }through*e*_{i}_{−1}.

- Write a Racket function makelet* that takes a Racket list of Racket pairs ’((
**Using the Language:**We can write mul461 expressions directly in Racket using the constructors for the structs and (for convenience) the functions we wrote in the previous problem.- Write a function makefactorial that gives a racket integer n, returns a mul461 expression that is similar to
*n*∗ ((*n*− 1) ∗ (*n*− 2)*…*∗ 1) using mul461 For example (makefactorial 3) should return this value:

- Write a function makefactorial that gives a racket integer n, returns a mul461 expression that is similar to

(mul461-* (mul461-int 3) (mul461-* (mul461-int 2) (mul461-int 1))).

2

## Reviews

There are no reviews yet.