The Way of the Java/Fruitful methods

Fruitful methods

Return values

Some of the built-in methods we have used, like the Math functions, have produced results. That is, the effect of invoking the method is to generate a new value, which we usually assign to a variable or use as part of an expression. For example:

 double e = Math.exp (1.0);
 double height = radius * Math.sin (angle);

But so far all the methods we have written have been void methods; that is, methods that return no value. When you invoke a void method, it is typically on a line by itself, with no assignment:

    nLines (3);
    g.drawOval (0, 0, width, height);

In this chapter, we are going to write methods that return things, which I will refer to as fruitful methods, for want of a better name. The first example is area, which takes a double as a parameter, and returns the area of a circle with the given radius:

 public static double area (double radius)
   double area = Math.PI * radius * radius;
   return area;

The first thing you should notice is that the beginning of the method definition is different. Instead of public static void, which indicates a void method, we see public static double, which indicates that the return value from this method will have type double. I still have not explained what public static means, but be patient.

static

Also, notice that the last line is an alternate form of the return statement that includes a return value. This statement means, return immediately from this method and use the following expression as a return value. The expression you provide can be arbitrarily complicated, so we could have written this method more concisely:

 public static double area (double radius)
   return Math.PI * radius * radius;

On the other hand, temporary variables like area often make debugging easier. In either case, the type of the expression in the return statement must match the return type of the method. In other words, when you declare that the return type is double, you are making a promise that this method will eventually produce a double. If you try to return with no expression, or an expression with the wrong type, the compiler will take you to task.

temporary variable

Sometimes it is useful to have multiple return statements, one in each branch of a conditional:

 public static double absoluteValue (double x)
   if (x < 0)
     return -x;
   else
     return x;

Since these return statements are in an alternative conditional, only one will be executed. Although it is legal to have more than one return statement in a method, you should keep in mind that as soon as one is executed, the method terminates without executing any subsequent statements.

Code that appears after a return statement, or any place elsewhere it can never be executed, is called dead code. Some compilers warn you if part of your code is dead.

Dead code

If you put return statements inside a conditional, then you have to guarantee that every possible path through the program hits a return statement. For example:

 public static double absoluteValue (double x)
   if (x < 0)
     return -x;
   else if (x > 0)
     return x;      // WRONG!!

This program is not legal because if x happens to be 0, then neither condition will be true and the method will end without hitting a return statement. A typical compiler message would be return statement required in absoluteValue, which is a confusing message considering that there are already two of them.

Program development

At this point you should be able to look at complete Java methods and tell what they do. But it may not be clear yet how to go about writing them. I am going to suggest one technique that I call incremental development.

incremental development

As an example, imagine you want to find the distance between two points, given by the coordinates. By the usual definition:

 distance = sqrt((x_2 - x_1)^2 + (y_2 - y_1)^2)

The first step is to consider what a distance method should look like in Java. In other words, what are the inputs (parameters) and what is the output (return value).

In this case, the two points are the parameters, and it is natural to represent them using four doubles, although we will see later that there is a Point object in Java that we could use. The return value is the distance, which will have type double.

Already we can write an outline of the method:

 public static double distance
              (double x1, double y1, double x2, double y2)
   return 0.0;

The statement return 0.0; is a place-keeper that is necessary in order to compile the program. Obviously, at this stage the program does not do anything useful, but it is worthwhile to try compiling it so we can identify any syntax errors before we make it more complicated.

In order to test the new method, we have to invoke it with sample values. Somewhere in main I would add:

 double dist = distance (1.0, 2.0, 4.0, 6.0);

I chose these values so that the horizontal distance is 3 and the vertical distance is 4; that way, the result will be 5 (the hypotenuse of a 3-4-5 triangle). When you are testing a method, it is useful to know the right answer.

Once we have checked the syntax of the method definition, we can start adding lines of code one at a time. After each incremental change, we recompile and run the program. That way, at any point we know exactly where the error must be—in the last line we added.

The next step in the computation is to find the differences between x_1 and x_2, and between y_1 and y_2. I will store those values in temporary variables named dx and dy.

 public static double distance
              (double x1, double y1, double x2, double y2)
   double dx = x2 - x1;
   double dy = y2 - y1;
   System.out.println ("dx is " + dx);
   System.out.println ("dy is " + dy);
   return 0.0;

I added print statements that will let me check the intermediate values before proceeding. As I mentioned, I already know that they should be 3.0 and 4.0.

scaffolding

When the method is finished I will remove the print statements. Code like that is called scaffolding, because it is helpful for building the program, but it is not part of the final product. Sometimes it is a good idea to keep the scaffolding around, but comment it out, just in case you need it later.

The next step in the development is to square dx and dy. We could use the Math.pow method, but it is simpler and faster to just multiply each term by itself.

 public static double distance
              (double x1, double y1, double x2, double y2)
   double dx = x2 - x1;
   double dy = y2 - y1;
   double dsquared = dx*dx + dy*dy;
   System.out.println ("dsquared is " + dsquared);
   return 0.0;

Again, I would compile and run the program at this stage and check the intermediate value (which should be 25.0).

Finally, we can use the Math.sqrt method to compute and return the result.

 public static double distance
              (double x1, double y1, double x2, double y2)
   double dx = x2 - x1;
   double dy = y2 - y1;
   double dsquared = dx*dx + dy*dy;
   double result = Math.sqrt (dsquared);
   return result;

Then in main, we should print and check the value of the result.

As you gain more experience programming, you might find yourself writing and debugging more than one line at a time. Nevertheless, this incremental development process can save you a lot of debugging time.

The key aspects of the process are:

• Start with a working program and make small, incremental changes. At any point, if there is an error, you will know exactly where it is.
• Use temporary variables to hold intermediate values so you can print and check them.
• Once the program is working, you might want to remove some of the scaffolding or consolidate multiple statements into compound expressions, but only if it does not make the program difficult to read.

Composition

As you should expect by now, once you define a new method, you can use it as part of an expression, and you can build new methods using existing methods. For example, what if someone gave you two points, the center of the circle and a point on the perimeter, and asked for the area of the circle?

Let's say the center point is stored in the variables xc and yc, and the perimeter point is in xp and yp. The first step is to find the radius of the circle, which is the distance between the two points. Fortunately, we have a method, distance that does that.

 double radius = distance (xc, yc, xp, yp);

The second step is to find the area of a circle with that radius, and return it.

 double area = area (radius);
 return area;

Wrapping that all up in a method, we get:

 public static double fred
              (double xc, double yc, double xp, double yp)
   double radius = distance (xc, yc, xp, yp);
   double area = area (radius);
   return area;

The name of this method is fred, which may seem odd. I will explain why in the next section.

The temporary variables radius and area are useful for development and debugging, but once the program is working we can make it more concise by composing the method invocations:

 public static double fred (double xc, double yc, double xp, double yp)
   return area (distance (xc, yc, xp, yp));

Overloading

In the previous section you might have noticed that fred and area perform similar functions—finding the area of a circle—but take different parameters. For area, we have to provide the radius; for fred we provide two points.

If two methods do the same thing, it is natural to give them the same name. In other words, it would make more sense if fred were called area.

Having more than one method with the same name, which is called overloading, is legal in Java as long as each version takes different parameters. So we can go ahead and rename fred:

 public static double area (double x1, double y1, double x2, double y2)
   return area (distance (xc, yc, xp, yp));

When you invoke an overloaded method, Java knows which version you want by looking at the arguments that you provide. If you write:

 double x = area (3.0);

Java goes looking for a method named area that takes a single double as an argument, and so it uses the first version, which interprets the argument as a radius. If you write:

 double x = area (1.0, 2.0, 4.0, 6.0);

Java uses the second version of area. More amazing still, the second version of area actually invokes the first.

Many of the built-in Java commands are overloaded, meaning that there are different versions that accept different numbers or types of parameters. For example, there are versions of print and println that accept a single parameter of any type. In the Math class, there is a version of abs that works on doubles, and there is also a version for ints.

Although overloading is a useful feature, it should be used with caution. You might get yourself nicely confused if you are trying to debug one version of a method while accidentally invoking a different one.

Actually, that reminds me of one of the cardinal rules of debugging: make sure that the version of the program you are looking at is the version of the program that is running! Some time you may find yourself making one change after another in your program, and seeing the same thing every time you run it. This is a warning sign that for one reason or another you are not running the version of the program you think you are. To check, stick in a print statement (it does not matter what you print) and make sure the behavior of the program changes accordingly.

Boolean expressions

Most of the operations we have seen produce results that are the same type as their operands. For example, the + operator takes two ints and produces an int, or two doubles and produces a double, etc.

relational operator

The exceptions we have seen are the relational operators, which compare ints and floats and return either true or false. true and false are special values in Java, and together they make up a type called boolean. You might recall that when I defined a type, I said it was a set of values. In the case of ints, doubles and Strings, those sets are pretty big. For booleans, not so big.

Boolean expressions and variables work just like other types of expressions and variables:

 boolean fred;
 fred = true;
 boolean testResult = false;

The first example is a simple variable declaration; the second example is an assignment, and the third example is a combination of a declaration and an assignment, sometimes called an initialization. The values true and false are keywords in Java, so they may appear in a different color, depending on your development environment.

initialization

As I mentioned, the result of a conditional operator is a boolean, so you can store the result of a comparison in a variable:

 boolean evenFlag = (n
 boolean positiveFlag = (x > 0);    // true if x is positive

and then use it as part of a conditional statement later:

 if (evenFlag)
   System.out.println ("n was even when I checked it");

A variable used in this way is frequently called a flag, since it flags the presence or absence of some condition.

Logical operators

There are three logical operators in Java: AND, OR and NOT, which are denoted by the symbols &&, || and !. The semantics (meaning) of these operators is similar to their meaning in English. For example (x > 0) && (x < 10) is true only if x is greater than zero AND less than 10.

semantics

evenFlag n3 == 0 is true if either of the conditions is true, that is, if evenFlag is true OR the number is divisible by 3.

Finally, the NOT operator has the effect of negating or inverting a boolean expression, so !evenFlag is true if evenFlag is false—if the number is odd.

nested structure

Logical operators often provide a way to simplify nested conditional statements. For example, how would you write the following code using a single conditional?

 if (x > 0)
   if (x < 10)
     System.out.println ("x is a positive single digit.");

Boolean methods

Methods can return boolean values just like any other type, which is often convenient for hiding complicated tests inside methods. For example:

 public static boolean isSingleDigit (int x)
   if (x >= 0 && x < 10)
     return true;
   else
     return false;

The name of this method is isSingleDigit. It is common to give boolean methods names that sound like yes/no questions. The return type is boolean, which means that every return statement has to provide a boolean expression.

The code itself is straightforward, although it is a bit longer than it needs to be. Remember that the expression x >= 0 && x < 10 has type boolean, so there is nothing wrong with returning it directly, and avoiding the if statement altogether:

 public static boolean isSingleDigit (int x)
   return (x >= 0 && x < 10);

In main you can invoke this method in the usual ways:

 boolean bigFlag = !isSingleDigit (17);
 System.out.println (isSingleDigit (2));

The first line assigns the value true to bigFlag only if 17 is not a single-digit number. The second line prints true because 2 is a single-digit number. Yes, println is overloaded to handle booleans, too.

The most common use of boolean methods is inside conditional statements:

 if (isSingleDigit (x))
   System.out.println ("x is little");
 else
   System.out.println ("x is big");

More recursion

Now that we have methods that return values, you might be interested to know that we have a complete programming language, by which I mean that anything that can be computed can be expressed in this language. Any program ever written could be rewritten using only the language features we have used so far (actually, we would need a few commands to control devices like the keyboard, mouse, disks, evil robots, etc., but that is all).

Turing, Alan

Proving this claim is a non-trivial exercise first accomplished by Alan Turing, one of the first computer scientists (well, some would argue that he was a mathematician, but a lot of the early computer scientists started as mathematicians). Accordingly, it is known as the Turing thesis. If you take a course on the Theory of Computation, you will have a chance to see the proof.

To give you an idea of what you can do with the tools we have learned so far, let's look at some methods for evaluating recursively-defined mathematical functions. A recursive definition is similar to a circular definition, in the sense that the definition contains a reference to the thing being defined. A truly circular definition is typically not very useful:

description

frabjuous: an adjective used to describe something that is frabjous.

If you saw that definition in the dictionary, you might be annoyed. On the other hand, if you looked up the definition of the mathematical function factorial, you might get something like:

eqnarray*
&&  0! = 1
&&  n! = n (n-1)!
eqnarray*

(Factorial is usually denoted with the symbol , which is not to be confused with the Java logical operator ! which means NOT.) This definition says that the factorial of 0 is 1, and the factorial of any other value, , is multiplied by the factorial of . So is 3 times , which is 2 times , which is 1 times . Putting it all together, we get equal to 3 times 2 times 1 times 1, which is 6.

If you can write a recursive definition of something, you can usually write a Java program to evaluate it. The first step is to decide what the parameters are for this function, and what the return type is. With a little thought, you should conclude that factorial takes an integer as a parameter and returns an integer:

  public static int factorial (int n)

If the argument happens to be zero, all we have to do is return 1:

 public static int factorial (int n)
   if (n == 0)
     return 1;

Otherwise, and this is the interesting part, we have to make a recursive call to find the factorial of , and then multiply it by .

 public static int factorial (int n)
   if (n == 0)
     return 1;
   else
     int recurse = factorial (n-1);
     int result = n * recurse;
     return result;

If we look at the flow of execution for this program, it is similar to nLines from the previous chapter. If we invoke factorial with the value 3:

Process:

• Since 3 is not zero, we take the second branch and calculate the factorial of ...
• Since 2 is not zero, we take the second branch and calculatethe factorial of ...
• Since 1 is not zero, we take the second branch and calculate the factorial of ...
• Since 0 is zero, we take the first branch and return the value 1 immediately without making any more recursive calls.
• The return value (1) gets multiplied by n, which is 1, and the result is returned.
• The return value (1) gets multiplied by n, which is 2, and the result is returned.
• The return value (2) gets multiplied by n, which is 3, and the result, 6, is returned to main, or whoever invoked factorial (3).

Notice that in the last instance of factorial, the local variables recurse and result do not exist because when n=0 the branch that creates them does not execute.

Leap of faith

Following the flow of execution is one way to read programs, but as you saw in the previous section, it can quickly become labarynthine. An alternative is what I call the leap of faith. When you come to a method invocation, instead of following the flow of execution, you assume that the method works correctly and returns the appropriate value.

In fact, you are already practicing this leap of faith when you use built-in methods. When you invoke Math.cos or drawOval, you do not examine the implementations of those methods. You just assume that they work, because the people who wrote the built-in classes were good programmers.

Well, the same is true when you invoke one of your own methods. For example, in Section boolean we wrote a method called isSingleDigit that determines whether a number is between 0 and 9. Once we have convinced ourselves that this method is correct—by testing and examination of the code—we can use the method without ever looking at the code again.

The same is true of recursive programs. When you get to the recursive invocation, instead of following the flow of execution, you should assume that the recursive invocation works (yields the correct result), and then ask yourself, Assuming that I can find the factorial of , can I compute the factorial of ? In this case, it is clear that you can, by multiplying by .

Of course, it is a bit strange to assume that the method works correctly when you have not even finished writing it, but that is why it is called a leap of faith!

One more example

In the previous example I used temporary variables to spell out the steps, and to make the code easier to debug, but I could have saved a few lines:

 public static int factorial (int n)
   if (n == 0)
     return 1;
   else
     return n * factorial (n-1);

From now on I will tend to use the more concise version, but I recommend that you use the more explicit version while you are developing code. When you have it working, you can tighten it up, if you are feeling inspired.

After factorial, the classic example of a recursively-defined mathematical function is fibonacci, which has the following definition:

eqnarray*
&& fibonacci(0) = 1
&& fibonacci(1) = 1
&& fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);
eqnarray*

Translated into Java, this is:

 public static int fibonacci (int n)
   if (n == 0 || n == 1)
     return 1;
   else
     return fibonacci (n-1) + fibonacci (n-2);

If you try to follow the flow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if we assume that the two recursive calls (yes, you can make two recursive calls) work correctly, then it is clear that we get the right result by adding them together.

Glossary

• return type The part of a method declaration that indicates what type of value the method returns.
• return value The value provided as the result of a method invocation.
• dead code Part of a program that can never be executed, often because it appears after a return statement.
• scaffolding Code that is used during program development but is not part of the final version.
• void A special return type that indicates a void method; that is, one that does not return a value.
• overloading Having more than one method with the same name but different parameters. When you invoke an overloaded method, Java knows which version to use by looking at the arguments you provide.
• boolean A type of variable that can contain only the two values true and false.
• flag A variable (usually boolean) that records a condition or status information.
• conditional operator An operator that compares two values and produces a boolean that indicates the relationship between the operands.
• logical operator An operator that combines boolean values and produces boolean values.
• initialization A statement that declares a new variable and assigns a value to it at the same time.