The Science of Programming/Working on the Chain Gang

From Wikibooks, open books for an open world
Jump to: navigation, search

Sometimes, as SPT in CME, Chapter IX, points out, you find yourself puzzling over how to differentiate something complicated like:

    y = 3 (x^2 + 17)^2 

The approach is to make the expression simpler by abstracting away the detail. Let a be the polynomial:

     a = x^2 + 17 
   

We can represent this using a sum of terms:

Now, y can be rewritten as:

  y = 3 a^2 

To find the derivative of y with respect to x, we use the chain rule:

    \frac{dy}{dx} = \frac{dy}{da} * \frac{da}{dx} 

In other words, the differential of y with respect to x is equal to the differential of (the rewritten) y with respect to (the new) a multiplied by the differential of (the new) a with respect to x.

Programmatically, we have:

   var a = term(1,:x,2) plus term(17,:x,0);
   var y = term(3,:a,2);
   var dy/dx = y . diff(:a) times  a . diff(:x);

Looking at what dy/dx represents, we have:

   sway> a . toString();
   STRING: x^2 + 17
   sway> y . toString();
   STRING: 3x^2
   sway> dy/dx . toString();
   STRING: 6a * 2x

Doing the final substitution by hand (a = x^2 + 17), we get the final answer for dx/dy:

    dy/dx = 6 * (x^2 + 17) * 2x
          = (6x^2 + 102) * 2x
          = 12x^3 + 204x

Implementing the chain rule[edit]

It would be nice to have the chain rule substitution step automatically done for us, but doing so requires a bit of work, both conceptually and programmatically. We begin by extending the idea of abstracting the variable of a term. Recall that, at first, we hard-wired the term variable as x. Next, we allowed the caller of the term constructor to pass in the independent variable as a Sway symbol. The next step in the abstraction is to allow the term variable to be a term (or sum of terms or whatever) itself. If we did so, then a term's diff method would become the chain rule:

   function diff(wrtv)
       {
       term(a * n,iv,n - 1) times iv . diff(wrtv);
       }

Obviously, the independent variable iv can no longer be a symbol, but must be instead an object with a diff method. So, to represent a term of the form:

    a x^b 

we would need to use an object to represent the variable x. The constructor for such a variable object would look similar to term and plus constructors. That is, it must have value, toString, and diff methods[1]:

   function variable(name)
       {
       function value(x) { x; }
       function toString() { "" + name; }
       function diff(wrtv)
           {
           if (wrtv == name)
               {
               constant(1);
               }
           else
               {
               constant(0);
               }
           }
       this;
       }

The rule for finding the derivative of a simple variable is: if the with-respect-to variable matches, the result is one. If not, the result is zero. We will use constants to represent the numbers zero and one; in this way, every item in our system, including numbers, has toString, value, and diff methods.

To make our lives simpler, we can add the following logic to the body of the term constructor. If a symbol is passed in as the independent variable, we will convert it into a variable object.[2] In this way, we can pass in a symbol as before. Here is a mock-up of the new term constructor:

   function term(a,iv,n)
       {
       function value(x) { ... }
       function toString() { ... }
       function diff(wrtv)
           {
           if (n == 0)
               {
               constant(0);
               }
           else
               {
               term(a * n,iv,n - 1) times iv . diff(wrtv);
               }
           }
       
       if (iv is :SYMBOL, iv = variable(iv));
       this;
       }

We will also need to modify term's toString method to call iv's visualization. Here is the new non-simplifying version:

   function toString()
       {
       "" + a + iv . toString() + "^" + n;
       }

Let's test our modified system:

   var t = term(4,:x,3);
   var t' = t . diff(:x);
   sway> t . toString();
   STRING: 4x^3
   sway> t . iv;
   OBJECT: <OBJECT 1958>
   sway> t' . toString();
   STRING: 12x^2

It seems to be working so far for simple variables. Now let's try our original problem:

    y = 3 (x^2 + 17)^2 

First, we make our polynomial:

   var a = term(1,:x,2) plus term(17,:x,0);
   var y = term(3,a,2);                     // not :a 

Now, we visualize it:

   sway> y . toString();
   STRING: 31x^2 + 17x^0^2

Ouch! What did we do wrong? We need to parenthesize the visualization of iv:

   function toString()
       {
       "" + a + "(" + iv . toString() + ")" +  "^" + n;
       }

Remaking a and y with term's new visualization yields:

   var a = term(1,:x,2) plus term(17,:x,0);
   var y = term(3,a,2);
   sway> y . toString();
   STRING: 3(1x^2 + 17x^0)^2

If you use a simplifying toString method for terms, you should get:

   3(x^2 + 17)^2

exactly as desired! Now let's differentiate y (you will need your times constructor up and running):

   var y' = y . diff();
   sway> y' . toString();
   STRING: 6(x^2 + 17) * 2x

Nice!

We still have two little problems. The first is that the above result is not in its simplest form. Unfortunately, producing the simplest form is rather a complex process (compounded by the fact that is is not always clear which form is the simplest). So we will stop at this point and be happy.

The other little problem occurs when we visualize a:

   sway> a . toString();
   STRING: (x)^2 + 17

We've gone overboard with the parentheses. Clearly, when the independent variable is a complex object, we want to use parens. When it is a simple variable, however, we should eschew parens. This task is left as an exercise.

Questions[edit]

1. Explain why the diff method for terms no longer needs to test whether or not the with-respect-to variable matches the independent variable.

2. Implement the one function.

3. Modify the simplifying toString method for terms to print out parentheses only when the independent variable is complex and ether the coefficient or the exponent is not equal to one. Hint: Create a term method that adds parentheses around iv's visualization if it is complex but simply returns iv's visualization if it is not. Call this method from toString where appropriate.

4. CME p. 100, 1, 8 using sway

5. CME p. 100, 2, 3, 5, 8 using pencil and paper

Footnotes[edit]

  1. This is the heart of the object-oriented approach to programming: related objects have the same methods, but the methods are customized for the particular object.
  2. This little trick illustrates an important principle in the design of the computer programs: do as much for the user of your code as possible. We could force the user to pass in a variable object or we could allow the user to pass in a symbol, as before, and do the work ourselves.


As Time Goes By · Slippery Slopes