Instructions: you will do this problem set by
yourself. You will modify the source files in ps2.zip
and submit the modified files. The submitted programs must
compile without warnings. Programs that do not compile
or compile with warnings will receive an automatic zero.
Beginning with
this project, you'll be using the SML Compilation Manager (CM) to compile all
of your files together. It will also let you get at some of the libraries that
were previously inaccessible. It's actually very easy, but the directions are a
bit complicated at first. There are several things to do:
· If you're using SML inside Emacs, this should occur by default. Simply launch Emacs, open any of the SML files in the right directory (say, part1.sml), then start SML.
¨
We will test
your code in this fashion, so you want to be sure it works (since failing to
compile, or compiling with warnings, is cause for getting a zero under course
policy).
¨ When you use CM, the compiler can give you better (sometimes much better!) error messages.
The file permutations.sml defines a structure that contains two functions. Modify these functions for the following exercises:
(a) Implement the function interleave that gets an integer newVal and
a list of integers myList and returns a list containing
the set of lists resulting from the insertion of newVal
in all possible positions of the original list.
Ex: interleave
4 [1, 2, 3] =
[[4, 1, 2, 3], [1, 4, 2, 3], [1, 2, 4, 3], [1, 2, 3, 4]]
Suggestion: Try thinking about this problem in steps. First
consider how a value would be interleaved in an empty list, then in a list with
only one element, then with two elements, and so on.
(Step 1 – Empty list) [[4]]
(Step 2 – Unit list) [[4,3],
[3,4]]
(Step 3 – List with 2 elements) [[4,2,3],
[2,4,3], [2,3,4]]
(Step 4 – List with 3 elements) [[4,1,2,3],
[1,4,2,3], [1,2,4,3], [1,2,3,4]]
Notice that in step 1 the function should return a list with
only one list [4].
In step 2 the function should return a new list [4, 3] and
prepend 3 to the one returned in step 1.
In step 3 the function should return a new list [4, 2, 3] and
prepend 2 to the ones returned in step 2.
In step 4 the function should return a new list [4, 1, 2, 3] and
prepend 1 to the ones returned in step 3.
Tip: The tricky part in this problem involves prepending the
values 1, 2, 3 in steps 2, 3 and 4. Think about how the map function can be used to solve this problem.
fun
interleave (newVal:int) (myList:int list):int list list = raise Fail “not
Implemented”
(b) Implement a function that, given
an integer n larger than 1, returns all lists
of possible permutations containing the integers 1 to n.
Ex:
permutation 3 =
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Suggestion:
Once again, try to work in a bottom up fashion. Think of the return value of
the function for n equal to 1, then 2, and so on. Figure out how the function interleave can be used in this case.
Tip:
look into the function concat – it can be used to convert a list of lists of any type
into a list of that same type.
fun permutation(n:int):int list list = raise Fail “not implemented”
A boolean
expression is an expression that evaluates to either true or false.
Boolean expressions are used extensively in programming language constructs
such as if-then-else commands and while
loops. A simplified rule for boolean expressions is:
bexp = VAR x | true | false | bexp AND bexp | bexp OR bexp | NOT bexp
File boolexp.sml defines a boolean expression
type according to the above rule:
datatype bexp = VAR of string | T | F | AND of (bexp * bexp) |
OR of (bexp *bexp) | NOT
of bexp
Ex: val myexp:bexp = OR ((AND (VAR “a”),(VAR “b”)),(Var “c”))
is equivalent to
myexp = (a AND b) OR c
(a) Given
a boolean expression bexp, and a list of pairs of variables and
boolean values (true or false), write the code for function evaluate
(in file boolexp.sml). It substitutes the variables
by their corresponding values and evaluates the expression, returning true or
false. Consider that all the needed variables are passed as argument to the
function.
Ex: evaluate (myexp) [(“a”,
true) (“b”, false) (“c”, true)]= true.
fun evaluate (myexp:bexp) (vl:(string*bool) list):bool = raise Fail
“Not implemented”
(b) Given a list
of strings, finish function removeDuplicates that returns the
same list of strings without duplications.
Ex: removeDuplicates [“c”,
“b”, “a”, “b”, “d”, “a”] =
[“c”,
“b”, “a”, “d”]
fun removeDuplicates(l:string list):string list = raise Fail “Not
implemented”
(c) Given
an expression of type bexp, implement function getVars
that returns the set of variables contained in it (without
duplications).
Ex: getVars myexp = [“a”,
“b”, “c”]
fun
getVars(exp:bexp):string list = raise Fail “Not implemented”
(d) A tautology
is a boolean expression that always evaluates to true, for all combinations of
values of its variables. A classical example is
x OR (NOT x)
Use the
functions previously implemented to finish function isTautology. This
function should return whether a given expression is a tautology or not.
Ex: isTautology(myexp)
= false
IsTautology(OR(T,F)) = true
isTautology (OR ((VAR “x”),NOT(“x”))) =
true
fun isTautology(exp:bexp):bool
= raise Fail “Not implemented”
Suggestion: First implement a function that creates a list containing all possible lists of (variable name , boolean value) pairs. For example, for myexp, the function should return:
[[(“a”, true), (“b”, true), (“c”, true)],
[(“a”,
true), (“b”, true), (“c”, false)], ...
[(“a”,
false), (“b”, false), (“c”, false)]]
In this problem you will
understand and modify a calculator for arithmetic expressions. After compiling
the source code using the CM.make()
command, you can start the calculator by typing the Calculator.run() command (do not forget the semicolon at the
end!). The calculator accepts the following special commands:
:h
- prints help messages;
:p
- prints the abstract syntax tree of the expression following the command;
:t
- determines whether the expression following the command typechecks;
:q
- terminates the execution of the calculator.
(Abstract
syntax trees are explained below, and will be covered in section.)
If a command is not special (it does not have
a colon as its first character), the command is assumed to be an arithmetic
expression, which is parsed and fully evaluated, but only if neither parsing,
nor type errors occur.
Here are some examples of the
calculator's output:
Exp >> 2 + 5 * (1
- 7)
~28 (integer)
Exp >> :p 2 + 5 *
(1 - 7)
Exp_t(
. Binop_e(
. .
Plus
. .
Int_c(2)
. .
Binop_e(
. .
. Times
. .
. Int_c(5)
. .
. Binop_e(
. .
. . Minus
. .
. . Int_c(1)
. .
. . Int_c(7)
. .
. )
. .
)
. )
)
Exp >> :t 2 +
true
typecheck failed
Exp >> :t 1 +
17.8
conversions needed
Exp >> :t (1.0 +
2.7) * if 2 = 3 then 7.0 else ~9.99
typecheck ok
Exp >> (1.0 +
2.7) * if 2 = 3 then 7.0 else ~9.99
~36.963 (real)
Exp
>> 3 = 3
true
(boolean)
Exp
>> 3.0 = 3.0
RUNTIME
ERROR: type error in argument of = operator.
Note that in the version of the
calculator included here typechecking does not work. The typechecking examples
are presented for illustrative purposes only.
The result of an expression is either a
number (integer or real), or a boolean value. Other languages (e.g. C/C++)
allow for implicit conversions between, say, integers, and real numbers; no
such conversions are performed in our calculator. This is similar to what SML
does.
To stress the approximate nature
of real values, SML does not allow for equality comparisons between such
values; our calculator does the same. Boolean values can be compared for
equality, but none of the other relational operators (<, >, <=, >=) can be applied to them. Again, in keeping with SML's
conventions, the interpreter distinguishes between unary minus (represented as ~) and the binary subtraction operator (-).
Before an expression is
typechecked and/or evaluated, the input string is parsed and broken up into
tokens. If no parse error is detected, these tokens are used to build a
hierarchical representation of the expression called an abstract syntax tree (AST). Being restricted to textual output, we
can not represent such a tree in the usual manner, but the :t
command tries to give you a good approximation by using indentation to
show the subordination relationship between the various components of the AST. Before you start answering the
questions below you should become thoroughly familiar with the AST representation. Use the interpreter to
generate many examples of ASTs, in
order to improve your understanding.
The only file you will need to
modify and submit for this assingment is evaluator.sml. You should not change, nor submit the other
files in the project. You should, however, become familiar with the contents of
(at least) the files abstractSyntax.sml,
printAST.sml, interpreter.sml, and error.sml.
The files expression.grm, and expression.lex contain the definition of the
lexical analyzer and the parser. While you are welcome to peruse these two
files, you will use them only as "black boxes," so you don't have to
understand them. A number of files are created when you run the CM.make() command - while these are
essential for the creation of the parser, you should feel free to ignore them
completely.
Numerical and boolean constants
are specified using the same rules SML uses. You can use the operators +, -, *, /, div, mod, =, >, <, <=, >=, andalso, orelse, which
have the same precedence and associativity as the corresponding operators in
SML. Round parantheses can be used to modify the default precedence of
operators.
In addition to the operators
above, the evaluator allows for named functions and for conditional
expressions.
A named function is specified by a string
followed by a possibly empty list of arguments in parantheses. If the function
is called with no arguments, the parantheses may be ommitted. Using
functions with no arguments we can define named numerical or boolean constants.
Functions in our calculator are
predefined, i.e. they are built into the calculator; it is not possible to
create user-defined functions. Here are a few examples:
Exp >> e
2.718281828
(real)
Exp >>
e()
2.718281828
(real)
Exp >>
pi
3.14159265359
(real)
Exp >>
sum(1, 2, 3, 4)
10 (integer)
Exp >>
sum(1.1, 2.2, 1.1 * 3.0, 4.4)
11.0 (real)
Exp >>
sum(1, 1.2)
RUNTIME ERROR:
wrong type mix in 'sum' function.
Exp >>
sum
RUNTIME ERROR:
function 'sum' must have at least one argument.
Exp >>
sum(1, true)
RUNTIME ERROR:
wrong type mix in 'sum' function.
The function sum requires a non-empty
list of numerical arguments and computes their sum. Note that this function
signals an error if its arguments are not all of the same type, which must be
integer or real.
A conditional expression is of
the form if <condition> then
<expression 1> else <expression 2>. The condition must
evaluate to a boolean value; if it is true, then the result of <expression 1> is returned as the
value of the entire expression. Otherwise, the result of evaluating <expression 2> is returned.
Exp >>
if 3 = 3 then 312 else 314
312 (integer)
Exp >>
(5 + 4) * if true = (5 = 7) then 9 else 11
99 (integer)
To avoid error messages while
evaluating an expression, we can typecheck it first. Typechecking is performed
in the function checkType in file evaluator.sml, which returns a pair of type
(check * typ). The corresponding type
definitions are as follows:
datatype check
= OK | FAIL | CONVERSIONS
datatype typ =
INT_t | REAL_t | BOOL_t | NONE_t
A value of type check specifies whether the expressions
typecheck or not, or whether it typechecks, but only assuming that automatic
conversions from integers to reals and/or viceversa are possible. Type typ ("type" can not be used
because it is a keyword in SML) conveys the type of the result if the
expression typechecks. If type checking fails, NONE_t indicates that the type
of the result is undefined.
Exp >> :t true = false
typecheck ok
Exp >> :t 1 + 2.3
conversions needed
Exp >> :t (5 = 4) * (if true = (5 = 7) then 9 else 11)
typecheck failed
Questions:
(a)
Modify
the implementation of the equality operator so that two real numbers a and b are considered equal if
they differ by strictly less than 0.000001 of max(abs(a), abs(b)), where abs() denotes the absolute
value function.
(b)
Implement
constants e
and pi using exactly the
values we have provided in the example above. Also implement sum so that its behavior
matches exactly the examples above. Implement the conversion function toReal so that it takes
exactly one integer argument and converts it to the appropriate real value.
Implement toInt
to perform conversions from reals to integers. Given a real number r, toInt(r) is the greatest integer
ri such that ri <= r. Make sure that you
signal all relevant error cases for all the functions you implement. All the
code necessary to answer this question must go into the defintion of the funEvaluate function in file evaluator.sml.
(c)
Type
expression false andalso 3
into the calculator, and you will trigger an error message. This is because the
andalso operator evaluates both
its arguments before deciding the answer. The orelse operator behaves
similarly, while if
evaluates its condition and both its branches before returning the answer. This
is unlike the behavior of these operators in SML, where only the minimal number
of evaluations is performed in order to produce the result. In the case of the false andalso
true
expression, for example, evaluating the left side of the expression is enough
to determine that the result will be false. This approach is called
"short-circuiting" the evaluation of the expression. Change the
implementation of the andalso, orelse, and if operators so they use short-circuiting. In the context of
our calculator this will mean that non-type checking expressions like false andalso 3 will be evaluated as if
the error never existed.
(d)
The
version of the calculator you have received does not perform type checking.
Modify the function typeCheck to include typechecking for all operators.
Modify the function funType to add typechecking for all functions specified
in question (b) above (note: "constants" like e and pi are functions in our
world).