Problem Set 2: Symbolic Differentiation and Folding

Due September 18, 2008, 11:59 pm.


Objectives

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.

Updates/Corrections

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..

Part 1: A Language for Symbolic Differentiation

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.)" 

Part 1a: Contains Variable

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.

Part 1b: Evaluation

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.

Part 1c: Symbolic Differentiation

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.

Part 1d: Zero Finding

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.

Part 1e: Simplification (Karma Problem)

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:

  1. All arithmetic on constants should be carried out
  2. 0 + f = f
  3. f + 0 = f
  4. 0 − f = ~f
  5. f − 0 = f
  6. 0 / f = 0
  7. f / 1 = f
  8. 1 * f = f
  9. f * 1 = f
  10. 0 * f = 0
  11. f * 0 = 0
  12. f ^ 0 = 1
  13. 0 ^ f = 0 (other than 0 ^ 0, which is defined as 1)
  14. f ^ 1 = f
  15. ln(1) = 0
  16. sin(0) = 0
  17. cos(0) = 1
  18. ~0 = 0
  19. f + f = 2 * f
  20. f * f = f ^ 2
  21. ff = 0
  22. f / f = 1

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:

  1. n = ~n
  2. ~~f = f
  3. ~f + g = gf
  4. f + (~g) = fg
  5. f − (~g) = f + g
  6. ~fg = ~(f + g)
  7. (~f) * g = ~(f * g)
  8. f * (~g) = ~(f * g)
  9. (f/g) * h = (f * h) / g
  10. f * (g/h) = (f * g) / h
  11. (~f) / g = ~(f / g)
  12. f / (~g) = ~(f / g)
  13. (f / g) / h = f / (g * h)
  14. f / (g / h) = (f * h) / g
  15. f ^ (~g) = 1 / (f ^ g)
  16. (f ^ g) ^ h = f ^ (g * h)

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.


Part 2: Folding

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:

  1. Writing one or more helper functions
  2. Calling fold with one of those functions, some initial accumulator, and the input list
  3. Doing a single pattern-matching to extract the answer from the tuple that fold returned

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:

  1. listProduct: int list -> int. Returns the product of the elements of the list.
  2. listReverse: 'a list -> 'a list. Returns the given list in reverse order. Do not use List.rev.
  3. highestPos: int list -> int option. Returns the highest positive element in the list, or None if all elements are negative.
  4. 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).
  5. 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]].
  6. 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.