Due: Wed, Oct 30
Types are used for many purposes, including encapsulation of the representation of information. This is an exercise in the use of types with multiple constructors.
The derivative of an expression is a concept from calculus. The derivative of x (with respect to x) is 1, and the derivative of expression x^2 is 2x. If you are unfamiliar with derivatives, the general rules that are needed here are given below.
Symbolic mathematics packages such as Mathematica and Maple will take derivatives for you. They do so symbolically, in the same way as you do when you are doing it by hand. They require the concept of an expression, such as 2*x. That concept can be captured in a type called Expression.
For this assignment, you will write a program to compute the derivative of an expression. Do so by modifying the starting point file. It provides a function called deriv that takes an expression and produces another expression. deriv(E) is the derivative of E. Function deriv computes derivatives of expressions involving only a single independent variable, with respect to that variable. (The variable is called xx in the program just because it is probably a bad idea to have a global constant called x.) In addition to the independent variable, the current version handles constants and addition.
Your assignment is to extend the given program so that it can handle subtraction, multiplication and constant powers. Add more cases to the definition of type Expression. So that everybody uses the same names (making programs easier for me to test) use operator - for subtraction, operator * for multiplication and operator ^ for exponentation. Design your program so that each of these operators takes two expressions as parameters.
The rules for taking the derivative a' of an expression a (with respect to x) are as follows. Here, c is a constant and x is the independent variable (called xx in the program.)
| c' | = | 0 |
| x' | = | 1 |
| (a+b)' | = | a' + b' |
| (a - b)' | = | a' - b' |
| (ab)' | = | ab' + a'b |
| (ac)' | = | cac-1a' |
Be careful about types. When I present these facts to you, I write them using ordinary mathematical notation. When I write 0, I might be talking about the number 0 or the expression that consists only of the number 0. In mathematics, we do not distinguish between the two. But your program needs to pay attention to types. One type that your program must use is Real, the type of a real number. Another type is Expression. They are not the same. Constant 0 can have type Real. (It is polymorphic, and can have other numeric types.) But constant 0 cannot have type Expression. To make the expression 0, you must convert from type Real to type Expression. Function constant does that. So constant(0) is the number 0, as an expression.
The derivative rules can lead to some rather silly looking expressions. If you apply them exactly as stated, you find that the derivative of 2+3*x is 0 + 3*1 + 0*x. It is nice to do some simplifications. A simplification function is provided. You should extend the simplifier as well, to get simplifications involving subtractions, multiplication and constant powers. Do at least the following simplifications.
| y-0 | = | y |
| 0*y | = | 0 |
| y*0 | = | 0 |
| 1*y | = | y |
| y*1 | = | y |
| y^1 | = | y |
| 1^y | = | 1 |
Also perform constant arithmetic. For example, your expression should not contain subexpressions that contain only constants, except for simple constants. Expression 3*4 should be simplified to 12. Expression 3^4 should be simpified to 81.
Note. The program is broken into two parts. deriv.ast implements expressions and derivatives. File testderiv.ast contains a tester. Extend it to do more tests. Be sure to test your new code!
Note. You are only supposed to deal with constant powers. The equation given for the derivative of a power does not work when c is a general expression. If your deriv function is asked to produce the derivative of an expression where the exponent is not constant, it should fail. Use expression {false} to indicate a failure. So just make the result of deriv be {false} when your rule does not work. Do not leave off the braces. {false} is not the same as false. You will lose points if your program uses that rule inappropriately.
Note. Internal documentation is important in any program, and it is important that it be correct. When you make modifications, keep the documentation up to date. Failure to do so will cause you to lose points.
Note. Pay attention to what you are writing. I have received submissions for this assignment containing "facts" such as 0*x = x, x0 = x, x0 = 0, 0-x = x and assorted other goodies. (By the way, 00 is undefined. It is not terribly important how your program handles that little problem. If you treat x0 as 1, that is ok. But in unusual cases, it can lead to some problems.)
Note. To compute a real number to a real power, use operator ^~. It computes powers using logarithms and exponentials. (x^~y = exp(y ln(x)).) You can call your expression exponentiation operator ^.
Submit both of your programs, the derivative finder and the tester, in the usual way, using the handin program. Be sure to indicate that the assignment number is 5.