Symbolic Differentiation

Please write the programs directly into the section programs at the end of this notebook!

The Problem

In the lecture notes we show the first steps towards a program that calculates the first derivative of a function w.r.t. some variable. As we know, differentiation is a recursive process, and the program in the lecture notes uses repeated application of transformation rules with //. in order to implement recursion.
Based on the transformation rules given in the lecture notes develop a program Differentiation, which calculates the first derivative of a function w.r.t. a given variable. Assume the function to be given by its defining term. Develop the program in rule based programming style, i.e. implement the rules for differentiation as separate definitions that differ in the patterns of the parameters. Of course, recursion must be implemented through explicit recursive function calls. Note, that the rules in the lecture notes are not complete!
The program should not apply any simplification rules for functions before it applies the rules for differentiation, i.e. is the user wants to differentiate 3  x + 4  x w.r.t. x, then the program should apply the sum rule and differentiate 3  x and 4  x, respectively, rather than simplifying the term first to 7  x and then apply some rule for differentiation.
The chain rule needs special care: (e^(3  x + Sin[x])) is a "different" composition of functions compared to (((Sin[x] + 3  x))^4)although the two functions look almost the same. However, there is only one chain rule for computing the derivative of a composition of functions, namely g[h[x]]' = g'[h[x]]*h'[x]. The two cases above (and several others) only differ in how to interpret the given function as a composition of "appropriate g and h". This should be reflected in the program, meaning that there should only be one implementation of the chain rule but several variants that reflect how certain terms must be interpreted for the chain rule to be applicable. As an example, in order to differentiate (e^(3  x + Sin[x])) by the chain rule, we must realize that this term stands for (λ x . (e^x))[
        3  x + Sin[x]] and when we differentiate (((Sin[x] + 3  x))^4) by the chain rule, we need to read this term as (λ x . (x^4))[Sin[x] + 3  x].

Programs

Test Examples

Differentiation[3  x + 4  x, x] // Trace

Differentiation[((x^3) + 2 x + 4) ((x^2) + 1), x]

Differentiation[(q^x) ((x^2) + 1), x]

Differentiation[((E^x)/((x^2) + 1)), x]

Differentiation[(E^x) Sin[x], x]

Differentiation[(x^(1/3)), x]

Differentiation[(Sqrt[(x^2) + 1]), x]

Differentiation[Sin[Cos[x]], x]

Differentiation[(Sqrt[Sin[(x^2) + 1] + (q^x) (3 x - 2)]), 
      x]

Differentiation[(Sqrt[Cos])[3 x - 2]/Log[3 (x^2) - 1], x]

Differentiation[(E^((x^2) + 1)), x]

Differentiation[(x^x), x]

Differentiation[(((3 x))^((x^2) - Sin[x])), x]