In this assignment, you will be given the opportunity to write your own language for symbolic differentiation using OCaml and learn more about folding. Through this practice you will exercise important features of this functional language, such as recursion, pattern matching, datatypes, list processing, etc., not to mention the ability to design your own mini-language.
As in the previous assignment, all of your programs must compile. Programs that do not compile will receive an automatic zero. Make sure that the functions you are asked to write have the correct names and the number and type of arguments specified in the assignment. Finally, please pay attention to style and follow the style guidelines posted on the course web site. Think carefully before writing the code, and try to come up with simpler, elegant solutions.
Sept 14: The toStringSmart function was corrected. It has been updated on CMS.
Sept 15: Clarification for isPalindrome, and karma problem added relating to it.
Sept 16: Another clarification for isPalindrome..
In the Summer of 1958, John McCarthy (recipient of the Turing Award in 1971) made a major contribution to the field of programming languages. With the objective of writing a program that performed symbolic differentiation of algebraic expressions in a effective way, he noticed that some features that would have helped him to accomplish this task were absent in the programming languages of that time. This led him to the invention of LISP (published in Communications of the ACM in 1960) and other ideas, such as list processing (the name Lisp derives from "List Processing"), recursion and garbage collection, which are essential to modern programming languages, including Java. Nowadays, symbolic differentiation of algebraic expressions is a task that can be conveniently accomplished on modern mathematical packages, such as Mathematica and Maple.
The objective of this part is to build a language that can differentiate and evaluate symbolically represented mathematical expressions that are functions of a single variable. Symbolic expressions consist of numbers, variables, and standard math functions (plus, minus, times, divide, sin, cos, etc). To get you started, we have provided the datatype that defines the abstract syntax for such expressions; download the file "expression.ml" from CMS.
Instructions: Change to the directory where you saved the "expression.ml" file. In the OCaml environment type:
#use "expression.ml";; open Expression;
to start using the datatype.
(* abstract syntax tree *) (* Binary Operators *) type bop = Add | Sub | Mul | Div | Pow (* Unary Operators *) type uop = Sin | Cos | Ln | Neg type expression = Num of float | Var | BinOp of bop * expression * expression | UnOp of uop * expression
Var
represents an occurrence of the single variable,
which we usually call "x". UnOp(Ln, Var)
represents the natural logarithm of x
.
Neg
is negation, and is denoted by the "~" symbol
("-" is only used for subtraction). The rest should be
clear what they refer to.
Mathematical expressions can be constructed using the
constructors in the above datatype definition. For example, the expression
"x^2 + sin(~x)"
can be
represented as:
BinOp(Add, BinOp(Pow, Var, Num(2.0)), UnOp(Sin, UnOp(Neg, Var)))
This represents a tree where nodes are the type constructors
and the children of each node are the specific operator to use and the arguments of that
constructor. Such a tree is called an abstract syntax tree (or AST for short). For
your convenience, we have provided a function parseString
which
translates a string in infix form (such as "x^2 +
sin(~x)"
) into an expression
(treating
"x" as the variable). The parseString
function parses
according to the standard order of operations - so
"5+x*8"
will be read as
"5+(x*8)"
.
We have also provided functions toString
and toStringSmart
that print
expressions in a readable form, using infix
notation. The function toString
adds parentheses
around every binary operation so
that the output is completely unambiguous — however, that output
is often hard to read. The function toStringSmart
only adds parentheses when there may be ambiguity.
let e = BinOp(Add,BinOp(Pow,Var,Num 2.0),UnOp(Sin,BinOp(Div,Var,Num 5.0))) toString(e) = "((x^2.)+(sin((x/5.))))" toStringSmart(e) = "x^2.+sin(x/5.)"
First, we want to be able to test whether an
expression contains a variable. This will be useful later. Your task is to implement a
function containsVar
that takes an expression
e
and returns true
if there is a Var
anywhere
in e
, and false
otherwise. The type of this function is expression -> bool
.
Second, we want to be able to evaluate expressions for
specific values of x. For example, suppose we wanted to evaluate
e = x^2 + 3.0*x +2.0
with x = 5.0
. Then the result of the
evaluation of e at x is 5.0^2 + 3.0*5.0 + 2.0 = 42.0
.
Your task is to implement an evaluation
function evaluate
that takes an expression
e
and a float x
,
representing the value of the single variable, and evaluates
e
to a floating point number. The type of
this function is expression -> float -> float
.
Next, we want to develop a
function that takes an expression
e
as its argument and returns an expression
e'
representing the derivative of the expression with
respect to x. This process is referred to as symbolic differentiation.
When implementing this function, recall the chain rule from your freshman Calculus course:
And recall how, using that, we can write the derivatives for the other functions in our language:
Note that there two cases provided for calculating the derivative of f(x) ^ g(x)
,
one for where g(x) = h
does not contain any variables, and one for the general case.
The first is a special case of the second, but it is useful to treat them separately, because when the first case applies, the second case produces
unnecessarily complicated expressions.
Your task is to implement the derivative
function.
The type of this function is expression -> expression
.
The result of
your function must be correct, but need not be expressed in the simplest form.
Take advantage of this in order to keep the code in this part as short
as possible. You can implement this function in as little
as 20–30 lines of code.
One application of the derivative of a function is to find zeros of a function. One way to do so is Newton's method. The function should take an expression, a starting guess for the zero, a precision requirement, and a limit on the number of times to repeat the process. It should return None
if no zero was found within the desired precision by the time the limit was reached, and Some r
if a zero was found at r
within the desired precision.
Your task is to implement the find_zero:expression ->
float -> float -> int -> float option
function. Note that there are
cases where Newton's method will fail to produce a zero, such as for
the function x1/3. You are not
responsible for finding a zero in those cases,
but just for the correct implementation of Newton's method.
This part is a karma problem that is not required for the problem set. It is included as a avenue for students to further explore issues associated with symbolic differentiation and the representation of expressions. We will grade it if you do it; you will receive no points but good karma if you do well.
Consider the application of the derivative
function to the expression x^2+sin(2*x)
and the corresponding output:
toStringSmart(derivative(parseString "x^2+sin(2*x)")) = "2.*1.*x^(2.-1.)+cos(2.*x)*(2.*1.+0.*x)"This expression appears very complicated. However, it can be greatly simplified to "
2*x+cos(2*x)*2
". We can
reduce this using various elementary
simplifications.
Two basic types of reductions can be performed. The first and more obvious is to carry out operations that we have a simplified form for. One such simplification is carrying out arithmetic on constants: if we have two constants that are being added, multiplied, etc., we can reduce them to the result. Additionally, some operations have predefined results for certain constants, or when the operands are equal. We could perform reductions for other values of ln, sin, and cos, but it is not advisable to do so, as there can be a loss of precision. We expect you to implement the following simplifying reductions:
The second type of reduction is to group similar operations, and move negations
to the outside (as there are few real simplifications we can do when negation is involved,
but many we can do with the other operations). In and of themselves, these reductions
don't do very much; their true power is allowing us to apply other reductions. One of these
reductions is to transform all negative constants into the unary operator negation applied
to a positive constant. For example, consider (-1)*f
.
With the above reduction, it
will be converted to (~1)*f
, and then other reductions will
will convert it to ~(1*f)
and then ~f
. Note that we write -n for an actual negative
constant (i.e., Num(-5.0)
,
and ~n for the unary operator negation applied to something (i.e., UnOp(Neg,Num(5.0))
).
We expect you to implement the following reductions:
It is worth noting that applying one reduction to an expression may
result in being able to apply another. One implication of this is that subexpressions
must be reduced first. For example, to fully reduce
x + (sin(x)−sin(x))
, you must first reduce sin(x)−sin(x)
to 0,
transforming the expression to x+0
, then reduce x + 0
to x
.
Further, note that as in the (~1)*f
example above, you may need to apply multiple
reduction rules in sequence to an expression.
Your task is to implement a function reduce
that
performs all these reductions. The type of this function is expression
-> expression
.
Folding is an important technique in function languages that allows the programmer
to abstract out the details of traversing a list. With folding, many tasks can be
accomplished by writing very little. In this part, you will use folding to write a
number of functions. Folding is implemented in OCaml by the function
List.fold_left
, which begins at the left end of the list and proceeds to the right.
There is also a version (List.fold_right
) which begins at the right, but in most cases
List.fold_left
is preferred, due to its tail-recursive nature.
Each of these functions should be implemented entirely by:
You may also use List.rev
— though you should only do so when necessary,
because it takes time linear in the length of the list being reversed.
Note that not all these steps are needed for each function. Step 1 may be omitted if you pass an anonymous function to fold,
and step 3 may be omitted if your accumulator is not a tuple.
Your task is to implement the following functions in this manner, in
folding.ml:
listProduct: int list -> int
.
Returns the product of the elements of the list.
listReverse: 'a list -> 'a list
.
Returns the given list in reverse order. Do not use List.rev
.
highestPos: int list -> int option
.
Returns the highest positive element in the list, or None
if all elements are negative.
isPalindrome: int list -> bool
.
Returns true
if the given list is a palindrome,
false
otherwise. You are allowed to use List.rev. You are NOT allowed
to use the OCaml equality test (ie, =) on lists. As a karma problem,
try to implement isPalindrome only iterating through the list once (ie, List.rev is not allowed since that
would count as your one iteration).
allPrefixes: 'a list -> 'a list list
.
Returns a list of all the non-empty prefixes of the given list, ordered from shortest prefix to longest prefix.
For example, allPrefixes [1;2;3;4] = [[1]; [1;2]; [1;2;3]; [1;2;3;4]]
.
allSuffixes: 'a list -> 'a list list
.
Returns a list of all the non-empty suffixes of the given list, ordered from longest suffix to shortest suffix.