Reference no: EM132231825

Assignment -

This is a programming assignment in F#, with some additional non-programming questions. You can do it alone or in a team of two people. In the latter case, you are responsible for contacting other students and form a team.

Download the accompanying F# source file hw.fsx and enter your solutions in it where indicated. When you are done, submit it as instructed on Piazza.

Each of your answers must be free of static errors. You may receive no credit for problems whose code contains syntax or type errors.

In the following problems do not use any mutable variables (i.e., variables declared with let mutable) or any mutable predefined types such as references, mutable records, arrays, and so on. Define your functions recursively as needed and take advantage of the match operator.

1. Extending the expression language and its interpreter

File hw2.fsx contains the datatype expr

type  expr  =

| Const of int

| Op of string * expr * expr

| IfElse of expr * expr * expr

meant to encode the abstract syntax of a simple expression language like the one discussed in class. A datatype value of the form (Const n) encodes the integer constant n, while a datatype value of the form Op ("+", t₁, t₂), say, encodes the expression e₁ + e₂ if each t_i in turn encodes the expression e_i.

1. Define an eval function similar to the one discussed in class that evaluates expr values to an integer value as expected and supports the binary operator names "+", "-", "*", "max", "min", "=" and ">", respectively with the following behavior:

• "+", "-", "*" are as seen in class;
• "max" denotes the function that returns the largest of its arguments;
• "min" denotes the function that returns the smallest of its arguments;
• "=" denotes the function that returns 1 when its arguments have the same value, and returns 0 otherwise;
• ">" denotes the function that returns 1 when the value of its first argument is greater than the value of its second argument, and returns 0 otherwise.

The function eval fails with failwith in case of unrecognized binary operators and (for now) with expressions of the form IfElse(e, e₁, e₂).

2. Now we would like to extend our interpreter to conditional expressions of the form IfElse(e, e₁, e₂), giving them the same semantics as the corresponding Java expression e ? e₁ : e₂ or F#'s expression if e then e₁ else e₂.

Extend eval into a new function eval2 that behaves like eval except that it handles IfElse expressions as follows: IfElse(e, e₁, e₂) evaluates to the value of e1 if e evaluates to a non-zero value, and to the value of e₂ otherwise. Your extension should be such that e₁ and e₂ are evaluated only as needed, after e has been evaluated.

3. Using pattern matching, define a recursive function normAdd : expr -> expr that normalizes additions in the input expression by returning an equivalent one where any nested applications of "+" are right-associated.

2. An expression language with variables

In this problem we will consider a variation of the datatype expr where we represent operators with an enumeration type instead of the string type and we add support for variables, to represent arithmetic expressions with variables.

type oper1 = Neg | Not

type oper2 = Add | Mul | Sub | Gt | Eq | Or

type aexpr =

| C of int

| V of string

| Op1 of oper1 * aexpr

| Op2 of oper2 * aexpr * aexpr

With the two datatypes above, an expression like x * (y + 3), say, is represented as

Op2(Mul, Op1(Neg, Var "x"), Op2(Add, Var "y", C 3)) .

Similarly, an expression like :(x > 4 y), say, is represented as

Op1(Not, Op2(Gt, Var "x", Op2(Sub, C 4, Var "y"))) .

1. Assuming the usual precedence rules between operators and treating '+' and binary ' ' as left-associative operators, define three F# variables e1, e2 and e3 of type aepr whose value corresponds to the expressions z (v + w), 4 * (z - 2 * w - v), and x + y + v + w * z, respectively.

2. Write an interpreter aeval: env -> aexpr -> int for programs written as aexpr expressions. Function aeval takes an environment e and an expression a as input and returns the value of a in that environment.

The function should evaluate variables in a as specified in e, failing with failwith if a contains a variable that is undefined in e. It should interpret Neg, Add, Mul, and Sub respectively as integer negation, addition, multiplication and subtraction. It should interpret the remaining operators as the Boolean operators in C. Namely,

• Op2(Gt, e₁, e₂) evaluates to 1 if e1 evaluates to a number greater than the number e₂ evaluates to, and it evaluates to 0 otherwise.
• Op1(Not, e) evaluates to 1 if e evaluates to 0 and evaluates to 1 otherwise;
• Op2(Eq, e₁, e₂) evaluates to 1 if e₁ and e₂ evaluate to the same number, and evaluates to 0 otherwise;
• Op2(Or, e₁, e₂) evaluates to 1 if e₁ or e₂ evaluates to 1, and evaluates to 0 otherwise.

You can use the provided function lookup to lookup the value of a variable in an environment.

3. Write an F# function simplify: aexpr -> aexpr to perform some simple expression simplifications. Such simplifications are applied for instance in optimizing compilers. The simplify function relies on standard properties of arithmetic to reduce an expression to a simpler, but equivalent, one and to eliminate some of the Boolean operators. In particular, it should use the following simplification rules for an arbitrary expressions e, where V is logical disjunction (or) and ¬ is logical negation (not):

0 + e → e

e + 0 → e

e - 0 → e

1 * e → e

e * 1 → e

0 * e → 0

e * 0 → 0

e - e → 0

-(-e) → e

e V e → e

¬(¬e) → e

This means, for instance, that it should reduce x + 0, 1 * x, and (1 + 0) * (x + 0) all to x.

Your implementation should be such that the result of simplify is an expression that cannot be simplified further by it. That is, it should be such that, for all expressions e, (simplify (simplify e)) = (simplify e).

Notes: Pattern matching is your friend. Don't forget cases where you cannot simplify anything. Repeated (recursive) passes of simplify might be needed to produce an expression that cannot be simplified further.

4. Write an F# function toString: aexpr -> string to format expressions as strings, with the binary operators written in infix format. For instance, it may format Sub(V "x", C 34) as the string "x - 34". For simplicity, you may put parentheses around any subexpressions, even when they are superfluous according to the standard precedence rules for arithmetic operators. Use the predefined function string to convert an integer value to its string representation.

Hint: toString has very much the same structure as an eval function, although it needs no environment argument because it uses variables names, not variable values.

Attachment:- Assignment Files.rar