+1-415-670-9189
info@expertsmind.com
Define a recursive function normAdd
Course:- Programming Languages
Reference No.:- EM132231825




Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Programming Languages

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 ("+", t1, t2), say, encodes the expression e1 + e2 if each ti in turn encodes the expression ei.

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, e1, e2).

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

Extend eval into a new function eval2 that behaves like eval except that it handles IfElse expressions as follows: IfElse(e, e1, e2) evaluates to the value of e1 if e evaluates to a non-zero value, and to the value of e2 otherwise. Your extension should be such that e1 and e2 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, e1, e2) evaluates to 1 if e1 evaluates to a number greater than the number e2 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, e1, e2) evaluates to 1 if e1 and e2 evaluate to the same number, and evaluates to 0 otherwise;
  • Op2(Or, e1, e2) evaluates to 1 if e1 or e2 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




Put your comment
 
View Conversion
Minimize
  1. user image
    len2231825

    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. Pay close attention to the specification of each problem and the restrictions imposed on its solution.

  2. user image
    len2231825

    Solutions ignoring the restrictions may receive only partial credit or no credit at all. 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. You do not need, and should not use, any F# library functions unless instructed otherwise. However, you can use your own auxiliary functions if you prefer. Do not worry about the efficiency of your solution. Strive instead for cleanness and simplicity. Unnecessarily complicated code may not receive full credit. Do the assigned readings before starting attempting this assignment. If you do not, you might find the assignment exceedingly hard. Be sure to review the syllabus for details about this course's cheating policy.



Ask Question & Get Answers from Experts
Browse some more (Programming Languages) Materials
Your final document should contain a "hierarchy chart" of phases, flowcharts, pseudo code, data dictionary, and seven UML diagrams as developed in Visio and Word. Your docum
Develop the C++ function which needs one integer parameter and returns the integer value. Function will double the value passed to it and return doubled value.
Create the program which uses two arrays: one to hold employee names and one to hold employee salaries (standard US currency, two decimal points). The program must prompt us
Identify input, process and output to solves each problem. Compute and print the annual salary of employee. suppose the employee receive 6% increase in pay.
A colleague of yours frequently takes small amounts of office supplies, noting that the loss to the company is minimal. Your rationale expresses which historical principle?
Deleting and Recovering the Shell PATH Variable, uppose a CIS255 student was experimenting with shell variables and accidentally deleted his / her PATH variable. The student
Write a RainFall program that stores the total rainfall for each of 12 months into an array of doubles. Demonstrate program. Input Validation should not allow negative numbers
What will the code output when run - What are individualScores, bonusScore, baseScore, and teamScore? What do you think the difference is between the keywords let and var?