handout #10
CS341—Programming Languages
ML Programming
Assignment #5
due 11 pm Wednesday, 2/7/07
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.
Although we didn’t
discuss signatures in Friday’s lecture, 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. This is discussed in the
book and will be described in more detail in Monday’s lecture. For now, you just need to know that 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.73.4
·
expressions involving standard
mathematical functions for sin, cos, natural log (ln), and e to some power
(exp), as in Ln(Var(“y”)) which represents ey
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 (x1, y1) and (x2,
y2) is given by the following equation:
We can describe this
using our expr type. We’ll have to settle
for variable names x1, y1, x2, and y2, but can fully describe the expression 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. You
might want to use a case expression described in section 5.1.4 of the Ullman
book starting on page 130. 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 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.
·
Exponentiation deserves some special
comment. You won’t need parentheses for
a simple function call carried to an exponent:
- val c =
Pow(Exp(Var("n")), 0.5);
val c = Pow (Exp (Var
"n"),0.5) : expr
- toString(c);
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). Similarly, if we
want to compute (x2)3, 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 we don’t allow expressions where the exponent is itself an expression,
as in “x ^ (2.0 ^ 3.0)”. But you will
sometimes need to introduce parentheses for exponentiation 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
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