The Science of Programming/Guzzintas and other Cipherin'

Although we now have a nifty way to represent constants, we are now left with a bigger problem: how to combine terms and constants. We can't use Sway's + operator, since it only works for numbers and strings.Later, we will learn how to override the + operator so that it can add terms and constants as well. Instead, we will create an object to hold the two items to be added.Why we are doing this is not obvious. As we proceed, we will see that the approach works, but it won't give us much insight on how to come up with such solutions in the first place. We are essentially going to delay the addition of the items until we really need to add them together (e.g., when we are trying to compute a specific y value). The idea of delaying is a powerful computer science concept. Knowing when to delay, however, is more art than science. Let's create a constructor named plus to remind us that it generates an object that holds the (potential) sum of two objects: function plus(p,q) //p and q are terms/constants { this; } We can't do much with plus objects, however, except extract the original items, bound to p and q. How should we enhance our plus constructor? Just like terms and constants, a plus object should be able to: * compute its value * compute its derivative * visualize itself Of course, the plus object doesn't know how to do any of these things, since it's just a container for holding two items. What it can do, however, is ask those items to perform computations and then combine the results in a meaningful way. There are two main kinds of relationships between objects. In this case, the relationship between the plus object and p (or q) is clientship. The object p (or q) is said to be a client of the plus object since p (or q) is a component. The other main relationship between objects in inheritance in which objects share traits. You can read more about in The Sway Reference Manual. Although explicit inheritance is not used in this case, one can think of terms and constants inheriting the idea of the three methods: value, diff, and toString. Now our questions become: how should the values of the items be combined? How should the differentials of the items be combined? How should the visualizations of the items be combined? For the value method, how should the value of p and the value of q be combined? Since the value of p is a number and the value of q is a number and since the plus object represents the additions of its items, we can simply add the item values together: function plus(p,q) //p and q are terms/constants { function value(x) { p . value(x) + q . value(x); } this; } Thus, to compute the y value of a two terms added together, we simply find the y values of the terms separately, then add the results together. Mathematically, Let's test: sway> var a = term(-5,2); sway> var b = term(7,0); sway> a . value(3) + b . value(3); INTEGER: -38 sway> var z = plus(a,b); sway> z . value(3); INTEGER: -38 Note that our plus constructor doesn't actually specify what kinds of objects the formal parameters p and q must be bound to; the only requirement is that those objects have a value method that takes a single argument. We will take advantage of this fact later and use plus objects to glue together terms, constants, and other plus objects, nilly willy. The Power Rule and Sums We now turn our attention to the second method plus objects need to implement, the diff method. Of course, the power rule won't work for sums, because the rule only works only for computing the derivative of a single term. It turns out the derivative of two things added together is the sum of the derivatives of each thing alone. Mathematically, Now here's the tricky part (well it will seem tricky now, but in a short time, you will think this is as easy as pie). We use a plus object to represent the addition of two terms, correct? The right-hand-side of the equation above involves an addition. What are being added? Two derivatives. If a and b are term objects, then what kinds of things are the derivatives of a and b. Both are terms! Thus the right-hand-side in this case is simply the sum of two terms. But what do we use to represent the sum of two terms......wait for it......a plus object. Wow! Then the derivative of a plus object, consisting of two terms, is another plus object containing the derivatives of those two terms. This is both amazingly powerful and amazingly simple at the same time. If the above explanation has confused you, perhaps looking at the code will help. Here is the revised powerRule: function powerRule(obj) { if (obj is :term) { var a = obj . a; var n = obj . n; term(a * n,n - 1); } else if (obj is :plus) { var dp/dx = powerRule(obj . p); var dq/dx = powerRule(obj . q); plus(dp/dx,dq/dx); } else { throw(:calculusError,"powerRule: unknown object"); } } Note that dp/dx is a variable name and is something entirely different from dp / dx, which is the variable dp divided by dx. For plus objects, we extract the two terms, p and q, take their derivatives using the power rule, and then combine them into a plus object. More than two terms Our plus constructor is fine for representing lines as a line is composed of two terms, one of them being a constant. What do we do for a sum of three or more terms? How about doing...nothing. Yes, nothing. It turns out that our design of plus is so fine it not only handles the sum of two terms but the sum of a plus object and a term.You will find these happy occurrences often if you write code that is simple and elegant.. Recall that the only requirement for the parameters p and q in a plus object are that they both be bound to objects that have a value method. Does a plus object have a value method? Yes, indeed! So that means p or q or both can be bound to plus objects. Let's see: var a = term(-5,0); var b = plus(term(3,1),a); var y = plus(term(4,2),b); The variable y now refers to the polynomial: or more simply: Now, just because we should (and can) be able to combine sums and terms nilly-willy with our plus constructor doesn't mean we can assume plus is completely correct as written. We need to testWhen you are a senior, rather than test some code to see if it appears correct, you might prove it correct. The advantage of proving code correct is that performing all possible tests is sometimes difficult or impossible. in order to convince ourselves thoroughly that the code works. Let's test a, b, and c at some value of x that is easy to verify, say x = 2: sway> a . value(2); INTEGER: -5 sway> b . value(2); INTEGER: 1 sway> y . value(2); INTEGER: 17 In this interaction, we see that a, which is , has a value of -5 when x has a value of 2. The object b, which is a plus object representing , has a value of 6 - 5 or 1. The object y, which is also a plus object and represents , has a value of 16 + 6 - 5 or 17. It is not surprising that the object a, which is just a term, and the object b, which is composed of two terms, both give the correct answer; we are using their constructors exactly in the manner they were intended. Less obvious is why y works, being composed of a term and a plus object. The next section will demonstrate visualization to help you understand 'why'. Visualizations A very good way to see why y works is to visualize the y object. We begin by modifying the term constructor to add a toString method. In general, a toString method is used to generate a string representing the current state of the object.The use of the name toString is just a convention. We are basing this convention on the Java Programming Language, which uses a toString method for this very purpose. Such a string is called a visualization. Before continuing, read up on strings. Here is the modified term function with its new toString method: function term(a,n) { function value(x) { a * (x ^ n); } function toString() { "" + a + "x^" + n; } this; } As always, we write a bit of code, and then test, test, test! sway> var t = term(3,2); sway> t . toString(); STRING: "3x^2" Given any term, we can quickly see the parts of our object in a way that is very easy to understand. Be aware that this representation uses the operator precedence you learned in grammar school, namely that the exponentiation operation is performed before the multiplication by the coefficient. This is unlike Sway, which would evaluate the expression 3 * x ^ 2 as (3 * x) ^ 2. To learn more about how Sway computes arithmetic expressions, see Precedence and Associativity in The Sway Reference Manual. This is the goal of visualization. We will also need to add a visualization to plus: function plus(p,q) //p and q are terms or plus objects { function value(x) { p . value(x) + q . value(x); } function toString() { p . toString() + " + " + q . toString(); } this; } Note that plus visualizes itself by using the visualizations of its component objects and adds a '+' sign to indicate addition. Now we remake a, b, and y with these new definitions of term and plus in force: var a = term(-5,0); var b = plus(term(3,1),a); var y = plus(term(4,2),b); Let's see what y looks like: sway> y . toString(); STRING: 4x^2 + 3x^1 + -5x^0 Looks exactly as intended. To see further why the visualization works, it is sometimes useful to look at the sequence of calls generating the result. These calls are organized into what is known as a 'call tree'. Actions within a call are indented one-level from the originating call. Leftward pointing arrows represent return values. Here is to call tree for ys toString method call: call y . toString() //object y is plus(term(4,2),b) call p . toString() //object p is term(4,2) <-- "4x^2" //return value " + " call q . toString() //object q is b, plus(term(3,1),a) call p . toString() //object p is term(3,1) <-- "3x^1" //return value " + " call q . toString() //object q is a, term(-5,0) <-- "-5x^0" //return value <-- 3x^1 + -5x^0 //return value <-- 4x^2 + 3x^1 + -5x^0 //return value Combining the strings from top to bottom at the first indentation level gives us the overall return value: 4x^2 + 3x^1 + -5x^0 We can construct a call tree determining the value of y when x = 2, as well: call y . value(2) call p . value(2) // p is 4x^2 <-- 16 + call q . value(2) // q is 3x^1 + -5x^0 call p . value(2) // p is 3x^1 <-- 6 + call q . value(2) // q is -5x^0 <-- -5 <-- 1 <-- 17 Summing the return values at the first indentation level yields 17, the overall return value. Visualization is an important technique. You should always include a visualization method for all your objects so that you can easily debug your program when things go awry. In such cases, your visualization will likely point out that an object does not appear as you expect it to, an important first step in solving your problem. Power Rule Modifications We have tested our powerRule function on sums of terms, but will it work for sums of sums? Let's examine the code: function powerRule(obj) { if (obj is :term) { var a = obj . a; var n = obj . n; term(a * n,n - 1); } else if (obj is :plus) { var dp/dx = powerRule(obj . p); var dq/dx = powerRule(obj . q); plus(dp/dx,dq/dx); } else { throw(:calculusError,"powerRule: unknown object"); } } If the formal parameter obj is bound to a sum of plus objects, the powerRule function is called recursively on the two objects making up the sum. As long as either of those two objects is a plus or term object, it appears if powerRule can handle it. In the case of a plus object, powerRule calls itself recursively again. Let's test the powerRule function on the polynomial bound to the variable y above. Recall y visualized as: 4x^2 + 3x^1 + -5x^0 We would expect the powerRule function to produce a polynomial that visualizes to something like: 8x + 3 Let's see. var dy/dx = powerRule(y); sway> dy/dx . toString(); STRING: 8x^1 + 3x^0 + 0x^-1 Looking at the last term of the result, we note that zero times anything is zero, so the result is equivalent to: 8x^1 + 3x^0 + 0 or 8x^1 + 3x^0 Noting, as before, that is equal to 1, the result becomes: 8x^1 + 3*1 or 8x^1 + 3 Finally, realizing that is simply x, the result becomes: 8x + 3 as desired. Some of the questions at the end of this chapter explore how to have the plus and term perform some of these simplifications automatically. Other mathematical combinations of terms What if we wish to subtract two terms, as in: y = 3x^2 - 4x We can write a function named minus to do this: function minus(p,q) { function value(x) { p . value(x) - q . value(x); } function toString() { p . toString() + " - " + q . toString(); } this; } This is just like plus, except that minus signs are used instead of plus signs in methods value and toString.A fine example of programming by analogy. Be aware, that making a new function by copying an existing function and making minor changes is usually a 'bad idea'. If you find yourself doing this, ask yourself how can the two functions be combined into a single function? There is a nice way to do this for plus and minus, but we'll skip that as to not impede the narrative flow. What is the power rule for the subtraction of terms? It is similar, but not quite the same as the power rule for the addition of terms: Thus powerRule, as written, cannot work for minus objects because there is no code in powerRule that subtracts or even produces a minus object. We will need to add a new clause to powerRule: function powerRule(obj) { if (obj is :term) { var a = obj . a; var n = obj . n; term(a * n,n - 1); } else if (obj is :plus) { var dp/dx = powerRule(obj . p); var dq/dx = powerRule(obj . q); plus(dp/dx,dq/dx); } else if (obj is :minus) { var dp/dx = powerRule(obj . p); var dq/dx = powerRule(obj . q); minus(dp/dx,dq/dx); } else { throw(:calculusError,"powerRule: unknown object"); } } While this will work, there is a clue that we are doing something wrong. Whenever you see a if-chain dealing with objects, it means you are not fully exploiting the power of objects and you should reorganize your code to remove the if-chain. The next section shows how. The Object Way The design of a program usually evolves over time. Some programmers feel very invested in the code they have written and will doggedly hang on to it even when a better way of doing things becomes apparent. In the words of the immortal Kenny Rogers, "you got to know when to hold 'em, know when to fold 'em". In this case, our powerRule function is threatening to get out of hand, so we are going to fold and get a new deal. Our new approach expands on the statement: An object should be able to ... In the case of our term and plus objects, we have already implemented the following versions of the above statement: A term object should be able to return its coefficient A term object should be able to return its exponent A term object should be able to compute a y value given an x value A term object should be able to be able to visualize itself A plus object should be able to return its components A plus object should be able to compute a y value given an x value A plus object should be able to be able to visualize itself To this list, we will add the following statements: A term object should be able to differentiate itself A plus object should be able to differentiate itself Other similar objects should be able to differentiate themselves Let's first update our term constructor so that terms can differentiate themselves. We do this by adding a diff (for differentiation) method: function term(a,n) { function value(x) { ... } function toString() { ... } function diff() { term(a * n,n - 1); } this; } The body of the diff method is simply a form of the term code found in the powerRule function. We can do the same for the plus constructor: function plus(p,q) { function value(x) { ... } function toString() { ... } function diff() { var dp/dx = p . diff(); var dq/dx = q . diff(); plus(dp/dx,dq/dx); } this; } To make plus a little shorter, we can replace the body of the diff method with a single line: function diff() { plus(p . diff(),q . diff()); } Using the fact that plus is a function of two arguments, we can use infix notation as well: function diff() { p . diff() plus q . diff(); } Modifying the minus constructor is similar. What about multiplying and dividing terms? According to CME, the mathematical rule for differentiating a product is: The rule for division is more complicated still: The implementations of the diff methods for times and div constructors are left as an exercise. After doing all this, the powerRule function becomes very simple: function powerRule(obj) { obj . diff(); } It is so simple, in fact, that it is longer doing any useful work and can be discarded. Questions All formulas are written using Grammar School Precedence.1. What happens if you pass a plus object to the original powerRule function? Explain what happens.2. Define and test a times constructor. Be sure to add toString and diff methods.3. Define and test a div constructor. Be sure to add toString and diff methods.4. Modify the toString method of term to use only the coefficient if the exponent is zero.5. Modify the toString method of term to ignore the coefficient and/or the exponent if it is 1. That is, term(3,1) should display as 3x, not 3x^1, and term(1,4) should display as x^4, not 1x^4.6. Modify the toString method of term to produce the empty string ""if the coefficient is zero.7. Modify the plus constructor to throw away terms if they have a coefficient of zero. How do you 'throw away' a term?8. Modify the plus constructor so that if the second argument is a term with a negative coefficient, it produces an appropriate minus object instead.9. Use Sway for Problem 6 on page 64 of CME.10. Use Sway to differentiate y = (x - 3/2) + (x^2 -5x) + (3x^3 + 7x^2 + 3x + 5) Define function y and11. Work exercises 1-5 on p. 64 of CME using pencil and paper.12'. Use pencil and paper to solve exercise 11 on p. 77. Footnotes Constant Worries Lather, Rinse, Repeat