Write and test a Miranda function to do symbolic differentiation of arbitrary expressions involving variables, constants, and the operators + - and *. Your function should take two strings as input -- the expression and a variable -- and return a new string that is an expression representing the derivative of the expression with respect to the variable. I suggest using Scheme syntax for the input and output expressions. (You can use C or Java Syntax if you prefer but it will be much harder to parse the input.)
Your result should be at least minimally simplified, using the following rules:
0 + expr --> expr expr + 0 --> expr num + num --> their sum 0 * expr --> 0 expr * 0 --> 0 1 * expr --> expr expr * 1 --> expr num * num --> their productExamples:
deriv "(+ x 3)" "x" => "1" deriv "(* x y)" "x" => "y" deriv "3" "x" => "0" deriv "(+ (* x 3) (* x 2))" "x" => "5" deriv "(* (* x y) (+ x 3))" "x" => "(+ (* x y) (* y (+ x 3)))"Hints:
Think modular! I would write several functions:
tokens -- takes a string and returns a list of tokens. (Tokens in this case represent variables, constants, left paren, right paren, plus, and times. Define a type token, as follows:
token ::= VariableToken [char] | ConstantToken num | LeftParen ...parse -- takes a list of tokens and returns an expression. Define a type expression:
expression ::= Variable [char] | Plus expression expression | ...basic_deriv -- takes an expression and a variable, and returns a new expression (not simplified).
simplify -- takes an expression and returns a simplified version of it.
expr_to_string -- takes an expression and returns a string representation of it.
Test these functions separately, then define deriv in terms of them. For testing define some helper functions, e.g.
test1 = deriv "(* (* x y) (+ x 3))" "x"Symbolic differentiation is a classic Scheme example -- see Chapter 2 of the Scheme book, or the program ~borning/scheme/ch2-deriv.scm on orcas. (The program is much simpler in Scheme because Scheme takes care of the parsing and printing for you.)
You might also want to look at sample solutions for assignment 7 from the Spring 1998 offering of 341 -- this was a Miranda project to multiply two polynomials, and some of the same parsing issues come up in that problem.
If you do want to use C/Java syntax for the input expressions, you will want to write a little recursive descent parser -- consult a compiler textbook (or ask Alan).
turnin -c cse341 hw7.mYour homework should include the function:
deriv ::= [char]->[char]->[char]Which when called as deriv func var computes the symbolic derivative of the function func with respect to variable var (as in the above examples).
You may write any other helper functions that you need. However, if you take an approach vastly different from that outlined in these instructions, please take care to explain your method.
As usual, your paper turnin should include complete source code. Please make sure that your print out does not wrap lines that are not wrapped in your program. It makes Miranda code very hard to read. Also, as usual, you should include output that demonstrates that your code works. This should not be extra work for you, you should just print out whatever tests that you run to make sure that your code works. You can show me output from your helper functions. It would be wise of you to debug them as you go, anyway. If any portion of your code does not work as requested by this assignment specification, you should document that in your paper turnin.