handout #12

CSE341—Programming Languages

ML Programming Assignment #5

due 11 pm Thursday, 5/6/10

Please note that this assignment is worth half of the normal credit (50 points versus 100 points). You are to complete the definition of a structure that provides a type called expr that can be used to store a symbolic expression. Your structure will also provide utility functions called evaluate and toString that can be used to find the value of an expression and to see a text representation of the expression.

Your structure should be restricted to a signature known as EXPRESSION. By restricting the structure to the signature, we will hide any helper functions in your structure. To accomplish this, your solution will look like this:

signature EXPRESSION =

sig

datatype expr = Const of real | Var of string | Plus of expr * expr

| Minus of expr * expr | Times of expr * expr

| Div of expr * expr | Pow of expr * real

| Sin of expr | Cos of expr | Ln of expr | Exp of expr

exception NoSuchVariable

val evaluate : expr * (string * real) list -> real

val toString : expr -> string

end;

structure Expression :> EXPRESSION =

struct

datatype expr = Const of real | Var of string | Plus of expr * expr

| Minus of expr * expr | Times of expr * expr

| Div of expr * expr | Pow of expr * real

| Sin of expr | Cos of expr | Ln of expr | Exp of expr;

exception NoSuchVariable;

(* include your definitions of evaluate and toString here. *)

(* any helper functions you define won't be visible outside *)

(* the structure (like private methods in Java). *)

end;

This code will be provided to you as a skeleton file called hw4.sml from the class web page. Your task is to implement two functions: evaluate and toString. Each will be worth 25 points.

The datatype expr can be used to store symbolic expressions or equations. The type includes:

· simple numbers as in Const(4.8)

· named variables as in Var(“x”)

· arithmetic expressions involving addition, subtraction, multiplication and division, as in Plus(Const(2.5), Const(3.4)), which represents the expression 2.5 + 3.4

· exponentiation using a real number as the exponent, as in Pow(Const(8.7), 3.4) which represents 8.7^3.4

· expressions involving standard mathematical functions for sin, cos, natural log (ln), and e to some power (exp), as in Exp(Var(“y”)) which represents e^y

Because this is a recursive type, you can combine these operations to form more complex expressions. For example, we know from math that the distance between two points (x₁, y₁) and (x₂, y₂) is given by the following equation:

We can describe this using our expr type as follows:

val dist = Pow(Plus(Pow(Minus(Var("x1"), Var("x2")), 2.0),

Pow(Minus(Var("y1"), Var("y2")), 2.0)), 0.5);

We could then pass this value to the toString function:

- toString(dist);

val it = "((x1 - x2) ^ 2.0 + (y1 - y2) ^ 2.0) ^ 0.5" : string

To evaluate an expression like this, we would need to know the values of the variables. Notice that the evaluate function takes an expression and a list of tuples of type (string * real). This should be a list of variable bindings (a named variable and its value). For example, if we were computing the distance between the points (3.4, 4.7) and (9.8, 7.4), we’d ask for:

- evaluate(dist, [("x1", 3.4), ("y1", 4.7), ("x2", 9.8), ("y2", 7.4)]);

val it = 6.94622199472 : real

It is worth noting that all of these examples assume that the structure has been opened first:

- open Expression;

We could still do the same things without opening the structure, but then we’d need to say Expression.Pow, Expression.Plus, Expression.Minus, Expression.Const, Expression.Var, etc.

In writing the evaluate function, you will need to replace each named variable with the value of the variable in the list of bindings. If one of the variables included in the expression is not in the list of bindings, your function should raise a NoSuchVariable exception (included in the structure). You may assume that any given variable appears at most once in the list of bindings. The list of bindings could be empty (e.g., when evaluating an expression that doesn’t have variables in it) and it could contain variables that are not part of the expression you are asked to evaluate.

Writing evaluate basically involves enumerating all of the different cases and including appropriate expressions for each. For example, if you were writing a function f that will operate on an expression, you can use pattern matching to mention each case:

fun f(Const(n)) = ...

| f(Var(name)) = ...

| f(Plus(x, y)) = ...

...

Obviously you will need to call functions like Math.sin, Math.cos, Math.pow, Math.ln and Math.exp.

The toString function should return a textual equivalent of the given expression. Your function should convert each kind of expression to its customary format and should not include extraneous spaces or parentheses. Below are a few particular rules to keep in mind:

· For constants, you can use the function Real.toString to convert the value to a string.

· For arithmetic operators like addition, subtraction, multiplication and division you should include a single space on either side of the operator character, as in “2.2 + 3.4”.

· Mathematical functions should have the function name followed by its argument contained in parentheses, as in “sin(3.4)”.

· For exponentiation, you should use the up-arrow character as an operator and format it like the other arithmetic operators with exactly one space on each side of the up-arrow, as in “3.4 ^ 7.8”.

· You are required to include parentheses when the expression would otherwise be ambiguous, but you should not include parentheses when there is no potential ambiguity. This is a tricky requirement and will probably take you a while to work out. For example, consider the following expressions:

val a = Plus(Plus(Var("x"), Var("y")), Var("z"));

val b = Plus(Var("x"), Plus(Var("y"), Var("z")));

You can’t simply convert these expressions to “x + y + z” because then these two different expressions would have the same textual form. Instead, we need to include parentheses:

- toString(a);

val it = "(x + y) + z" : string

- toString(b);

val it = "x + (y + z)" : string

Notice, however, that we don’t need an outer set of parentheses for either expression because we don’t need those parentheses to know the form of the original expression.

· As with the other binary operators, you won’t need parentheses for a simple function call carried to an exponent:

- val a = Pow(Exp(Var("n")), 0.5);

val a = Pow (Exp (Var "n"),0.5) : expr

- toString(a);

val it = "exp(n) ^ 0.5" : string

In this case, we don’t need parentheses to see that the value carried to the 0.5 power is the result of the call on exp(n). But exponentiation is very different from the other binary operators like addition, subtraction and multiplication. We will adopt the convention that exponentiation has a higher level of precedence than addition, subtraction, multiplication and division and that it evaluates left to right. That means that we don’t need nearly as many parentheses to eliminate ambiguity.

For example, if we want to compute x/y², we don’t need any parentheses because we recognize that exponentiation has higher precendence than division:

- val b = Div(Var("x"), Pow(Var("y"), 2.0));

val b = Div (Var "x",Pow (Var "y",2.0)) : expr

- toString(b);

val it = "x / y ^ 2.0" : string

We would only have needed parentheses if we were computing (x/y)²:

- val c = Pow(Div(Var("x"), Var("y")), 2.0);

val c = Pow (Div (Var "x",Var "y"),2.0) : expr

- toString(c);

val it = "(x / y) ^ 2.0" : string

Similarly, if we want to compute (x²)³, we don’t need parentheses:

- val d = Pow(Pow(Var("x"), 2.0), 3.0);

val d = Pow (Pow (Var "x",2.0),3.0) : expr

- toString(d);

val it = "x ^ 2.0 ^ 3.0" : string

This is unambiguous because the exponentiation operator is evaluated left to right. Again, you would need parentheses only to make it clear what is to be carried to the given power, as in:

- val e = Pow(Pow(Plus(Const(2.0), Var("x")), 2.0), 3.0);

val e = Pow (Pow (Plus (Const 2.0,Var "x"),2.0),3.0) : expr

- toString(e);

val it = "(2.0 + x) ^ 2.0 ^ 3.0" : string

· Even though we are taking into account precedence to reduce parentheses for exponentiation, we are not taking into account the normal precedence rules for addition and subtraction versus multiplication and division. For example, in Java we would understand how to group x + y * z, but for our purposes we will produce more explicit output:

- val f = Plus(Var("x"), Times(Var("y"), Var("z")));

val f = Plus (Var "x",Times (Var "y",Var "z")) : expr

- toString(f);

val it = "x + (y * z)" : string

In other words, the only binary operator that has special rules is exponentiation.

We could get some rather odd output from the toString function if someone introduces variable names like “x + 2.3”, but we’ll assume that variables have reasonable names, as in the rules used by Java and ML for identifiers.

You should copy the skeleton file hw5.sml to your account and fill in your definitions for evaluate, toString and any helper functions you want to include. You are not allowed to use references or arrays, but otherwise you can use all of ML to solve this problem, including the standard libraries. When you are finished, submit your hw5.sml file electronically using the catalyst esubmit link on the class web page