Functions and Modules

This chapter is from the book

Computer Science: An Interdisciplinary Approach

Learn More Buy

This chapter is from the book

This chapter is from the book 

Computer Science: An Interdisciplinary Approach

Learn More Buy

THIS CHAPTER CENTERS ON A CONSTRUCT that has as profound an impact on control flow as do conditionals and loops: the function, which allows us to transfer control back and forth between different pieces of code. Functions (which are known as static methods in Java) are important because they allow us to clearly separate tasks within a program and because they provide a general mechanism that enables us to reuse code.

We group functions together in modules, which we can compile independently. We use modules to break a computational task into subtasks of a reasonable size. You will learn in this chapter how to build modules of your own and how to use them, in a style of programming known as modular programming.

Some modules are developed with the primary intent of providing code that can be reused later by many other programs. We refer to such modules as libraries. In particular, we consider in this chapter libraries for generating random numbers, analyzing data, and providing input/output for arrays. Libraries vastly extend the set of operations that we use in our programs.

We pay special attention to functions that transfer control to themselves—a process known as recursion. At first, recursion may seem counterintuitive, but it allows us to develop simple programs that can address complex tasks that would otherwise be much more difficult to carry out.

Whenever you can clearly separate tasks within programs, you should do so. We repeat this mantra throughout this chapter, and end the chapter with a case study showing how a complex programming task can be handled by breaking it into smaller subtasks, then independently developing modules that interact with one another to address the subtasks.

2.1 Defining Functions

THE JAVA CONSTRUCT FOR IMPLEMENTING A function is known as the static method. The modifier static distinguishes this kind of method from the kind discussed in CHAPTER 3—we will apply it consistently for now and discuss the difference then. You have actually been using static methods since the beginning of this book, from mathematical functions such as Math.abs() and Math.sqrt() to all of the methods in StdIn, StdOut, StdDraw, and StdAudio. Indeed, every Java program that you have written has a static method named main(). In this section, you will learn how to define your own static methods.

In mathematics, a function maps an input value of one type (the domain) to an output value of another type (the range). For example, the function f (x) = x² maps 2 to 4, 3 to 9, 4 to 16, and so forth. At first, we work with static methods that implement mathematical functions, because they are so familiar. Many standard mathematical functions are implemented in Java’s Math library, but scientists and engineers work with a broad variety of mathematical functions, which cannot all be included in the library. At the beginning of this section, you will learn how to implement such functions on your own.

Later, you will learn that we can do more with static methods than implement mathematical functions: static methods can have strings and other types as their range or domain, and they can produce side effects such as printing output. We also consider in this section how to use static methods to organize programs and thus to simplify complicated programming tasks.

Static methods support a key concept that will pervade your approach to programming from this point forward: whenever you can clearly separate tasks within programs, you should do so. We will be overemphasizing this point throughout this section and reinforcing it throughout this book. When you write an essay, you break it up into paragraphs; when you write a program, you will break it up into methods. Separating a larger task into smaller ones is much more important in programming than in writing, because it greatly facilitates debugging, maintenance, and reuse, which are all critical in developing good software.

Static methods

As you know from using Java’s Math library, the use of static methods is easy to understand. For example, when you write Math.abs(a-b) in a program, the effect is as if you were to replace that code with the return value that is produced by Java’s Math.abs() method when passed the expression a-b as an argument. This usage is so intuitive that we have hardly needed to comment on it. If you think about what the system has to do to create this effect, you will see that it involves changing a program’s control flow. The implications of being able to change the control flow in this way are as profound as doing so for conditionals and loops.

You can define static methods other than main() in a .java file by specifying a method signature, followed by a sequence of statements that constitute the method. We will consider the details shortly, but we begin with a simple example—Harmonic (PROGRAM 2.1.1)—that illustrates how methods affect control flow. It features a static method named harmonic() that takes an integer argument n and returns the nth harmonic number (see PROGRAM 1.3.5).

PROGRAM 2.1.1 is superior to our original implementation for computing harmonic numbers (PROGRAM 1.3.5) because it clearly separates the two primary tasks performed by the program: calculating harmonic numbers and interacting with the user. (For purposes of illustration, PROGRAM 2.1.1 takes several command-line arguments instead of just one.) Whenever you can clearly separate tasks within programs, you should do so.

Click to view larger image

Control flow

While Harmonic appeals to our familiarity with mathematical functions, we will examine it in detail so that you can think carefully about what a static method is and how it operates. Harmonic comprises two static methods: harmonic() and main(). Even though harmonic() appears first in the code, the first statement that Java executes is, as usual, the first statement in main(). The next few statements operate as usual, except that the code harmonic(arg), which is known as a call on the static method harmonic(), causes a transfer of control to the first line of code in harmonic(), each time that it is encountered. Moreover, Java initializes the parameter variable n in harmonic() to the value of arg in main() at the time of the call. Then, Java executes the statements in harmonic() as usual, until it reaches a return statement, which transfers control back to the statement in main() containing the call on harmonic(). Moreover, the method call harmonic(arg) produces a value—the value specified by the return statement, which is the value of the variable sum in harmonic() at the time that the return statement is executed. Java then assigns this return value to the variable value. The end result exactly matches our intuition: The first value assigned to value and printed is 1.0—the value computed by code in harmonic() when the parameter variable n is initialized to 1. The next value assigned to value and printed is 1.5—the value computed by harmonic() when n is initialized to 2. The same process is repeated for each command-line argument, transferring control back and forth between harmonic() and main().

Program 2.1.1 Harmonic numbers (revisited)

public class Harmonic
{
   public static double harmonic(int n)
   {
      double sum = 0.0;
      for (int i = 1; i <= n; i++)
         sum += 1.0/i;
      return sum;
   }

   public static void main(String[] args)
   {
      for (int i = 0; i < args.length; i++)
      {
         int arg = Integer.parseInt(args[i]);
         double value = harmonic(arg);
         StdOut.println(value);
      }
   }
}

sum | cumulated sum

 arg  | argument
value | return value

This program defines two static methods, one named harmonic() that has integer argument n and computes the nth harmonic numbers (see PROGRAM 1.3.5) and one named main(), which tests harmonic() with integer arguments specified on the command line.

% java Harmonic 1 2 4
1.0
1.5
2.083333333333333

% java Harmonic 10 100 1000 10000
2.9289682539682538
5.187377517639621
7.485470860550343
9.787606036044348

Function-call trace

One simple approach to following the control flow through function calls is to imagine that each function prints its name and argument value(s) when it is called and its return value just before returning, with indentation added on calls and subtracted on returns. The result enhances the process of tracing a program by printing the values of its variables, which we have been using since SECTION 1.2. The added indentation exposes the flow of the control, and helps us check that each function has the effect that we expect. Generally, adding calls on StdOut.println() to trace any program’s control flow in this way is a fine way to begin to understand what it is doing. If the return values match our expectations, we need not trace the function code in detail, saving us a substantial amount of work.

i = 1
arg = 1
harmonic(1)
   sum = 0.0
   sum = 1.0
   return 1.0
value = 1.0
i = 2
arg = 2
harmonic(2)
   sum = 0.0
   sum = 1.0
   sum = 1.5
   return 1.5
value = 1.5
i = 3
arg = 4
harmonic(4)
   sum = 0.0
   sum = 1.0
   sum = 1.5
   sum = 1.8333333333333333
   sum = 2.083333333333333
   return 2.083333333333333
value = 2.083333333333333

Function-call trace for java Harmonic 1 2 4

FOR THE REST OF THIS CHAPTER, your programming will center on creating and using static methods, so it is worthwhile to consider in more detail their basic properties. Following that, we will study several examples of function implementations and applications.

Terminology

It is useful to draw a distinction between abstract concepts and Java mechanisms to implement them (the Java if statement implements the conditional, the while statement implements the loop, and so forth). Several concepts are rolled up in the idea of a mathematical function, and there are Java constructs corresponding to each, as summarized in the table at the top of the next page. While these formalisms have served mathematicians well for centuries (and have served programmers well for decades), we will refrain from considering in detail all of the implications of this correspondence and focus on those that will help you learn to program.

When we use a symbolic name in a formula that defines a mathematical function (such as f (x) = 1 + x + x²), the symbol x is a placeholder for some input value that will be substituted into the formula to determine the output value. In Java, we use a parameter variable as a symbolic placeholder and we refer to a particular input value where the function is to be evaluated as an argument.

Static method definition

The first line of a static method definition, known as the signature, gives a name to the method and to each parameter variable. It also specifies the type of each parameter variable and the return type of the method. The signature consists of the keyword public; the keyword static; the return type; the method name; and a sequence of zero or more parameter variable types and names, separated by commas and enclosed in parentheses. We will discuss the meaning of the public keyword in the next section and the meaning of the static keyword in CHAPTER 3. (Technically, the signature in Java includes only the method name and parameter types, but we leave that distinction for experts.) Following the signature is the body of the method, enclosed in curly braces. The body consists of the kinds of statements we discussed in CHAPTER 1. It also can contain a return statement, which transfers control back to the point where the static method was called and returns the result of the computation or return value. The body may declare local variables, which are variables that are available only inside the method in which they are declared.

Click to view larger image

Function calls

As you have already seen, a static method call in Java is nothing more than the method name followed by its arguments, separated by commas and enclosed in parentheses, in precisely the same form as is customary for mathematical functions. As noted in SECTION 1.2, a method call is an expression, so you can use it to build up more complicated expressions. Similarly, an argument is an expression—Java evaluates the expression and passes the resulting value to the method. So, you can write code like Math.exp(-x*x/2) / Math.sqrt(2*Math.PI) and Java knows what you mean.

Click to view larger image

Multiple arguments

Like a mathematical function, a Java static method can take on more than one argument, and therefore can have more than one parameter variable. For example, the following static method computes the length of the hypotenuse of a right triangle with sides of length a and b:

public static double hypotenuse(double a, double b)
{  return Math.sqrt(a*a + b*b); }

Although the parameter variables are of the same type in this case, in general they can be of different types. The type and the name of each parameter variable are declared in the function signature, with the declarations for each variable separated by commas.

Multiple methods

You can define as many static methods as you want in a .java file. Each method has a body that consists of a sequence of statements enclosed in curly braces. These methods are independent and can appear in any order in the file. A static method can call any other static method in the same file or any static method in a Java library such as Math, as illustrated with this pair of methods:

public static double square(double a)
{  return a*a;  }

public static double hypotenuse(double a, double b)
{  return Math.sqrt(square(a) + square(b));  }

Also, as we see in the next section, a static method can call static methods in other .java files (provided they are accessible to Java). In SECTION 2.3, we consider the ramifications of the idea that a static method can even call itself.

Overloading

Static methods with different signatures are different static methods. For example, we often want to define the same operation for values of different numeric types, as in the following static methods for computing absolute values:

public static int abs(int x)
{
   if (x < 0) return -x;
   else       return  x;
}

public static double abs(double x)
{
   if (x < 0.0) return -x;
   else         return  x;
}

These are two different methods, but are sufficiently similar so as to justify using the same name (abs). Using the same name for two static methods whose signatures differ is known as overloading, and is a common practice in Java programming. For example, the Java Math library uses this approach to provide implementations of Math.abs(), Math.min(), and Math.max() for all primitive numeric types. Another common use of overloading is to define two different versions of a method: one that takes an argument and another that uses a default value for that argument.

Multiple return statements

You can put return statements in a method wherever you need them: control goes back to the calling program as soon as the first return statement is reached. This primality-testing function is an example of a function that is natural to define using multiple return statements:

public static boolean isPrime(int n)
{
   if (n < 2) return false;
   for (int i = 2; i <= n/i; i++)
      if (n % i == 0) return false;
   return true;
}

Even though there may be multiple return statements, any static method returns a single value each time it is invoked: the value following the first return statement encountered. Some programmers insist on having only one return per method, but we are not so strict in this book.

Typical code for implementing functions (static methods)

public static int abs(int x)
{
      if (x < 0)  return -x;
      else          return x;
}

public static double abs(double x)
{
      if (x < 0.0)  return -x;
      else             return x;
}

public static boolean isPrime(int n)
{
      if (n < 2) return false;
      for (int i = 2; i <= n/i; i++)
          if (n % i == 0) return false;
      return true;
}

public static double hypotenuse(double a, double b)
{    return Math.sqrt(a*a + b*b);    }

public static double harmonic(int n)
{
      double sum = 0.0;
      for (int i = 1; i <= n; i++)
          sum += 1.0 / i;
      return sum;
}

public static int uniform(int n)
{    return (int) (Math.random() * n);    }

public static void drawTriangle(double x0, double y0,
                                double x1, double y1,
                                double x2, double y2 )
{
      StdDraw.line(x0, y0, x1, y1);
      StdDraw.line(x1, y1, x2, y2);
      StdDraw.line(x2, y2, x0, y0);
}

Single return value

A Java method provides only one return value to the caller, of the type declared in the method signature. This policy is not as restrictive as it might seem because Java data types can contain more information than the value of a single primitive type. For example, you will see later in this section that you can use arrays as return values.

Scope

The scope of a variable is the part of the program that can refer to that variable by name. The general rule in Java is that the scope of the variables declared in a block of statements is limited to the statements in that block. In particular, the scope of a variable declared in a static method is limited to that method’s body. Therefore, you cannot refer to a variable in one static method that is declared in another. If the method includes smaller blocks—for example, the body of an if or a for statement—the scope of any variables declared in one of those blocks is limited to just the statements within that block. Indeed, it is common practice to use the same variable names in independent blocks of code. When we do so, we are declaring different independent variables. For example, we have been following this practice when we use an index i in two different for loops in the same program. A guiding principle when designing software is that each variable should be declared so that its scope is as small as possible. One of the important reasons that we use static methods is that they ease debugging by limiting variable scope.

Click to view larger image

Side effects

In mathematics, a function maps one or more input values to some output value. In computer programming, many functions fit that same model: they accept one or more arguments, and their only purpose is to return a value. A pure function is a function that, given the same arguments, always returns the same value, without producing any observable side effects, such as consuming input, producing output, or otherwise changing the state of the system. The functions harmonic(), abs(), isPrime(), and hypotenuse() are examples of pure functions.

However, in computer programming it is also useful to define functions that do produce side effects. In fact, we often define functions whose only purpose is to produce side effects. In Java, a static method may use the keyword void as its return type, to indicate that it has no return value. An explicit return is not necessary in a void static method: control returns to the caller after Java executes the method’s last statement.

For example, the static method StdOut.println() has the side effect of printing the given argument to standard output (and has no return value). Similarly, the following static method has the side effect of drawing a triangle to standard drawing (and has no specified return value):

public static void drawTriangle(double x0, double y0,
                                double x1, double y1,
                                double x2, double y2)
{
   StdDraw.line(x0, y0, x1, y1);
   StdDraw.line(x1, y1, x2, y2);
   StdDraw.line(x2, y2, x0, y0);
}

It is generally poor style to write a static method that both produces side effects and returns a value. One notable exception arises in functions that read input. For ex-ample, StdIn.readInt() both returns a value (an integer) and produces a side effect (consuming one integer from standard input). In this book, we use void static methods for two primary purposes:

• For I/O, using StdIn, StdOut, StdDraw, and StdAudio

• To manipulate the contents of arrays

You have been using void static methods for output since main() in HelloWorld, and we will discuss their use with arrays later in this section. It is possible in Java to write methods that have other side effects, but we will avoid doing so until CHAPTER 3, where we do so in a specific manner supported by Java.

Implementing mathematical functions

Why not just use the methods that are defined within Java, such as Math.sqrt()? The answer to this question is that we do use such implementations when they are present. Unfortunately, there are an unlimited number of mathematical functions that we may wish to use and only a small set of functions in the library. When you encounter a mathematical function that is not in the library, you need to implement a corresponding static method.

As an example, we consider the kind of code required for a familiar and important application that is of interest to many high school and college students in the United States. In a recent year, more than 1 million students took a standard college entrance examination. Scores range from 400 (lowest) to 1600 (highest) on the multiple-choice parts of the test. These scores play a role in making important decisions: for example, student athletes are required to have a score of at least 820, and the minimum eligibility requirement for certain academic scholarships is 1500. What percentage of test takers are ineligible for athletics? What percentage are eligible for the scholarships?

Two functions from statistics enable us to compute accurate answers to these questions. The Gaussian (normal) probability density function is characterized by the familiar bell-shaped curve and defined by the formula . The Gaussian cumulative distribution function Φ(z) is defined to be the area under the curve defined by ϕ(x) above the x-axis and to the left of the vertical line x = z. These functions play an important role in science, engineering, and finance because they arise as accurate models throughout the natural world and because they are essential in understanding experimental error.

In particular, these functions are known to accurately describe the distribution of test scores in our example, as a function of the mean (average value of the scores) and the standard deviation (square root of the average of the sum of the squares of the differences between each score and the mean), which are published each year. Given the mean μ and the standard deviation σ of the test scores, the percentage of students with scores less than a given value z is closely approximated by the function Φ((z – μ)/σ). Static methods to calculate ϕ and Φ are not available in Java’s Math library, so we need to develop our own implementations.

Program 2.1.2 Gaussian functions

public class Gaussian
{  // Implement Gaussian (normal) distribution functions.
   public static double pdf(double x)
   {
      return Math.exp(-x*x/2) / Math.sqrt(2*Math.PI);
   }

   public static double cdf(double z)
   {
      if (z < -8.0) return 0.0;
      if (z > 8.0) return 1.0;
      double sum = 0.0;
      double term = z;
      for (int i = 3; sum != sum + term; i += 2)
      {
         sum = sum + term;
         term = term * z * z / i;
      }
      return 0.5 + pdf(z) * sum;
   }

   public static void main(String[] args)
   {
      double z     = Double.parseDouble(args[0]);
      double mu    = Double.parseDouble(args[1]);
      double sigma = Double.parseDouble(args[2]);
      StdOut.printf("%.3f\n", cdf((z - mu) / sigma));
   }
}

 sum | cumulated sum
term | current term

This code implements the Gaussian probability density function (pdf) and Gaussian cumulative distribution function (cdf), which are not implemented in Java’s Math library. The pdf() implementation follows directly from its definition, and the cdf() implementation uses a Taylor series and also calls pdf() (see accompanying text and EXERCISE 1.3.38).

% java Gaussian 820 1019 209
0.171
% java Gaussian 1500 1019 209
0.989
% java Gaussian 1500 1025 231
0.980

Closed form

In the simplest situation, we have a closed-form mathematical formula defining our function in terms of functions that are implemented in the library. This situation is the case for ϕ—the Java Math library includes methods to compute the exponential and the square root functions (and a constant value for π), so a static method pdf() corresponding to the mathematical definition is easy to implement (see PROGRAM 2.1.2).

No closed form

Otherwise, we may need a more complicated algorithm to compute function values. This situation is the case for Φ—no closed-form expression exists for this function. Such algorithms sometimes follow immediately from Taylor series approximations, but developing reliably accurate implementations of mathematical functions is an art that needs to be addressed carefully, taking advantage of the knowledge built up in mathematics over the past several centuries. Many different approaches have been studied for evaluating Φ. For example, a Taylor series approximation to the ratio of Φ and ϕ turns out to be an effective basis for evaluating the function:

Φ(z) = 1/2 + ϕ(z) (z + z³ / 3 + z⁵ / (3·5) + z⁷ / (3·5·7) +. . .)

This formula readily translates to the Java code for the static method cdf() in PROGRAM 2.1.2. For small (respectively large) z, the value is extremely close to 0 (respectively 1), so the code directly returns 0 (respectively 1); otherwise, it uses the Taylor series to add terms until the sum converges.

Running Gaussian with the appropriate arguments on the command line tells us that about 17% of the test takers were ineligible for athletics and that only about 1% qualified for the scholarship. In a year when the mean was 1025 and the standard deviation 231, about 2% qualified for the scholarship.

COMPUTING WITH MATHEMATICAL FUNCTIONS OF ALL kinds has always played a central role in science and engineering. In a great many applications, the functions that you need are expressed in terms of the functions in Java’s Math library, as we have just seen with pdf(), or in terms of Taylor series approximations that are easy to compute, as we have just seen with cdf(). Indeed, support for such computations has played a central role throughout the evolution of computing systems and programming languages. You will find many examples on the booksite and throughout this book.

Using static methods to organize code

Beyond evaluating mathematical functions, the process of calculating an output value on the basis of an input value is important as a general technique for organizing control flow in any computation. Doing so is a simple example of an extremely important principle that is a prime guiding force for any good programmer: whenever you can clearly separate tasks within programs, you should do so.

Functions are natural and universal for expressing computational tasks. Indeed, the “bird’s-eye view” of a Java program that we began with in SECTION 1.1 was equivalent to a function: we began by thinking of a Java program as a function that transforms command-line arguments into an output string. This view expresses itself at many different levels of computation. In particular, it is generally the case that a long program is more naturally expressed in terms of functions instead of as a sequence of Java assignment, conditional, and loop statements. With the ability to define functions, we can better organize our programs by defining functions within them when appropriate.

For example, Coupon (PROGRAM 2.1.3) is a version of CouponCollector (PROGRAM 1.4.2) that better separates the individual components of the computation. If you study PROGRAM 1.4.2, you will identify three separate tasks:

• Given n, compute a random coupon value.

• Given n, do the coupon collection experiment.

• Get n from the command line, and then compute and print the result.

Coupon rearranges the code in CouponCollector to reflect the reality that these three functions underlie the computation. With this organization, we could change getCoupon() (for example, we might want to draw the random numbers from a different distribution) or main() (for example, we might want to take multiple inputs or run multiple experiments) without worrying about the effect of any changes in collectCoupons().

Using static methods isolates the implementation of each component of the collection experiment from others, or encapsulates them. Typically, programs have many independent components, which magnifies the benefits of separating them into different static methods. We will discuss these benefits in further detail after we have seen several other examples, but you certainly can appreciate that it is better to express a computation in a program by breaking it up into functions, just as it is better to express an idea in an essay by breaking it up into paragraphs. Whenever you can clearly separate tasks within programs, you should do so.

Program 2.1.3 Coupon collector (revisited)

public class Coupon
{
   public static int getCoupon(int n)
   {  // Return a random integer between 0 and n-1.
      return (int) (Math.random() * n);
   }

   public static int collectCoupons(int n)
   {  // Collect coupons until getting one of each value
      // and return the number of coupons collected.
      boolean[] isCollected = new boolean[n];
      int count = 0, distinct = 0;
      while (distinct < n)
      {
         int r = getCoupon(n);
         count++;
         if (!isCollected[r])
            distinct++;
         isCollected[r] = true;
      }
      return count;
   }

   public static void main(String[] args)
   {  // Collect n different coupons.
      int n = Integer.parseInt(args[0]);
      int count = collectCoupons(n);
      StdOut.println(count);
   }
}

      n       | # coupon values (0 to n-1)
isCollected[i]| has coupon i been collected?
     count    | # coupons collected
   distinct   | # distinct coupons collected
      r       | random coupon

This version of PROGRAM 1.4.2 illustrates the style of encapsulating computations in static methods. This code has the same effect as CouponCollector, but better separates the code into its three constituent pieces: generating a random integer between 0 and n-1, running a coupon collection experiment, and managing the I/O.

% java Coupon 1000
6522
% java Coupon 1000
6481

% java Coupon 10000
105798
% java Coupon 1000000
12783771

Passing arguments and returning values

Next, we examine the specifics of Java’s mechanisms for passing arguments to and returning values from functions. These mechanisms are conceptually very simple, but it is worthwhile to take the time to understand them fully, as the effects are actually profound. Understanding argument-passing and return-value mechanisms is key to learning any new programming language.

Pass by value

You can use parameter variables anywhere in the code in the body of the function in the same way you use local variables. The only difference between a parameter variable and a local variable is that Java evaluates the argument provided by the calling code and initializes the parameter variable with the resulting value. This approach is known as pass by value. The method works with the value of its arguments, not the arguments themselves. One consequence of this approach is that changing the value of a parameter variable within a static method has no effect on the calling code. (For clarity, we do not change parameter variables in the code in this book.) An alternative approach known as pass by reference, where the method works directly with the calling code’s arguments, is favored in some programming environments.

A STATIC METHOD CAN TAKE AN array as an argument or return an array to the caller. This capability is a special case of Java’s object orientation, which is the subject of CHAPTER 3. We consider it in the present context because the basic mechanisms are easy to understand and to use, leading us to compact solutions to a number of problems that naturally arise when we use arrays to help us process large amounts of data.

Arrays as arguments

When a static method takes an array as an argument, it implements a function that operates on an arbitrary number of values of the same type. For example, the following static method computes the mean (average) of an array of double values:

public static double mean(double[] a)
{
   double sum = 0.0;
   for (int i = 0; i < a.length; i++)
      sum += a[i];
   return sum / a.length;
}

We have been using arrays as arguments since our first program. The code

public static void main(String[] args)

defines main() as a static method that takes an array of strings as an argument and returns nothing. By convention, the Java system collects the strings that you type after the program name in the java command into an array and calls main() with that array as argument. (Most programmers use the name args for the parameter variable, even though any name at all would do.) Within main(), we can manipulate that array just like any other array.

Side effects with arrays

It is often the case that the purpose of a static method that takes an array as argument is to produce a side effect (change values of array elements). A prototypical example of such a method is one that exchanges the values at two given indices in a given array. We can adapt the code that we examined at the beginning of SECTION 1.4:

public static void exchange(String[] a, int i, int j)
{
   String temp = a[i];
   a[i] = a[j];
   a[j] = temp;
}

This implementation stems naturally from the Java array representation. The parameter variable in exchange() is a reference to the array, not a copy of the array values: when you pass an array as an argument to a method, the method has an opportunity to reassign values to the elements in that array. A second prototypical example of a static method that takes an array argument and produces side effects is one that randomly shuffles the values in the array, using this version of the algorithm that we examined in SECTION 1.4 (and the exchange() and uniform() methods considered earlier in this section):

public static void shuffle(String[] a)
{
   int n = a.length;
   for (int i = 0; i < n; i++)
      exchange(a, i, i + uniform(n-i));
}

Typical code for implementing functions with array arguments or return values

public static double max(double[] a)
{
      double max = Double.NEGATIVE_INFINITY;
      for (int i = 0; i < a.length; i++)
          if (a[i] > max) max = a[i];
      return max;
}

public static double dot(double[] a, double[] b)
{
      double sum = 0.0;
      for (int i = 0; i < a.length; i++)
          sum += a[i] * b[i];
      return sum;
}

public static void exchange(String[] a, int i, int j)
{
      String temp = a[i];
      a[i] = a[j];
      a[j] = temp;
}

public static void print(double[] a)
{
      StdOut.println(a.length);
     for (int i = 0; i < a.length; i++)
          StdOut.println(a[i]);
}

public static double[][] readDouble2D()
{
      int m = StdIn.readInt();
      int n = StdIn.readInt();
      double[][] a = new double[m][n];
      for (int i = 0; i < m; i++)
          for (int j = 0; j < n; j++)
                a[i][j] = StdIn.readDouble();
      return a;
}

Similarly, we will consider in SECTION 4.2 methods that sort an array (rearrange its values so that they are in order). All of these examples highlight the basic fact that the mechanism for passing arrays in Java is call by value with respect to the array reference but call by reference with respect to the array elements. Unlike primitive-type arguments, the changes that a method makes to the elements of an array are reflected in the client program. A method that takes an array as its argument cannot change the array itself—the memory location, length, and type of the array are the same as they were when the array was created—but a method can assign different values to the elements in the array.

Arrays as return values

A method that sorts, shuffles, or otherwise modifies an array taken as an argument does not have to return a reference to that array, because it is changing the elements of a client array, not a copy. But there are many situations where it is useful for a static method to provide an array as a return value. Chief among these are static methods that create arrays for the purpose of returning multiple values of the same type to a client. For example, the following static method creates and returns an array of the kind used by StdAudio (see PROGRAM 1.5.7): it contains values sampled from a sine wave of a given frequency (in hertz) and duration (in seconds), sampled at the standard 44,100 samples per second.

public static double[] tone(double hz, double t)
{
   int SAMPLING_RATE = 44100;
   int n = (int) (SAMPLING_RATE * t);
   double[] a = new double[n+1];
   for (int i = 0; i <= n; i++)
      a[i] = Math.sin(2 * Math.PI * i * hz / SAMPLING_RATE);
   return a;
}

In this code, the length of the array returned depends on the duration: if the given duration is t, the length of the array is about 44100*t. With static methods like this one, we can write code that treats a sound wave as a single entity (an array containing sampled values), as we will see next in PROGRAM 2.1.4.

Example: superposition of sound waves

As discussed in SECTION 1.5, the simple audio model that we studied there needs to be embellished to create sound that resembles the sound produced by a musical instrument. Many different embellishments are possible; with static methods we can systematically apply them to produce sound waves that are far more complicated than the simple sine waves that we produced in SECTION 1.5. As an illustration of the effective use of static methods to solve an interesting computational problem, we consider a program that has essentially the same functionality as PlayThatTune (PROGRAM 1.5.7), but adds harmonic tones one octave above and one octave below each note to produce a more realistic sound.

Chords and harmonics

Notes like concert A have a pure sound that is not very musical, because the sounds that you are accustomed to hearing have many other components. The sound from the guitar string echoes off the wooden part of the instrument, the walls of the room that you are in, and so forth. You may think of such effects as modifying the basic sine wave. For example, most musical instruments produce harmonics (the same note in different octaves and not as loud), or you might play chords (multiple notes at the same time). To combine multiple sounds, we use superposition: simply add the waves together and rescale to make sure that all values stay between –1 and +1. As it turns out, when we superpose sine waves of different frequencies in this way, we can get arbitrarily complicated waves. Indeed, one of the triumphs of 19th-century mathematics was the development of the idea that any smooth periodic function can be expressed as a sum of sine and cosine waves, known as a Fourier series. This mathematical idea corresponds to the notion that we can create a large range of sounds with musical instruments or our vocal cords and that all sound consists of a composition of various oscillating curves. Any sound corresponds to a curve and any curve corresponds to a sound, and we can create arbitrarily complex curves with superposition.

Click to view larger image

Weighted superposition

Since we represent sound waves by arrays of numbers that represent their values at the same sample points, superposition is simple to implement: we add together the values at each sample point to produce the combined result and then rescale. For greater control, we specify a relative weight for each of the two waves to be added, with the property that the weights are positive and sum to 1. For example, if we want the first sound to have three times the effect of the second, we would assign the first a weight of 0.75 and the second a weight of 0.25. Now, if one wave is in an array a[] with relative weight awt and the other is in an array b[] with relative weight bwt, we compute their weighted sum with the following code:

double[] c = new double[a.length];
for (int i = 0; i < a.length; i++)
  c[i] = a[i]*awt + b[i]*bwt;

The conditions that the weights are positive and sum to 1 ensure that this operation preserves our convention of keeping the values of all of our waves between –1 and +1.

Click to view larger image

Program 2.1.4 Play that tune (revisited)

public class PlayThatTuneDeluxe
{
   public static double[] superpose(double[] a, double[] b,
                                    double awt, double bwt)
   {  // Weighted superposition of a and b.
      double[] c = new double[a.length];
      for (int i = 0; i < a.length; i++)
         c[i] = a[i]*awt + b[i]*bwt;
      return c;
   }

   public static double[] tone(double hz, double t)
   {  /* see text */ }

   public static double[] note(int pitch, double t)
   {  // Play note of given pitch, with harmonics.
      double hz = 440.0 * Math.pow(2, pitch / 12.0);
      double[] a = tone(hz, t);
      double[] hi = tone(2*hz, t);
      double[] lo = tone(hz/2, t);
      double[] h = superpose(hi, lo, 0.5, 0.5);
      return superpose(a, h, 0.5, 0.5);
   }

   public static void main(String[] args)
   {  // Read and play a tune, with harmonics.
      while (!StdIn.isEmpty())
      {  // Read and play a note, with harmonics.
         int pitch = StdIn.readInt();
         double duration = StdIn.readDouble();
         double[] a = note(pitch, duration);
         StdAudio.play(a);
      }
   }
}

  hz | frequency
 a[] | pure tone
hi[] | upper harmonic
lo[] | lower harmonic
 h[] | tone with harmonics

This code embellishes the sounds produced by PROGRAM 1.5.7 by using static methods to create harmonics, which results in a more realistic sound than the pure tone.

% more elise.txt
7 0.25
6 0.25
7 0.25
6 0.25
...

Click to view larger image

PROGRAM 2.1.4 IS AN IMPLEMENTATION THAT applies these concepts to produce a more realistic sound than that produced by PROGRAM 1.5.7. To do so, it makes use of functions to divide the computation into four parts:

• Given a frequency and duration, create a pure tone.

• Given two sound waves and relative weights, superpose them.

• Given a pitch and duration, create a note with harmonics.

• Read and play a sequence of pitch/duration pairs from standard input.

These tasks are each amenable to implementation as a function, with all of the functions then depending on one another. Each function is well defined and straightforward to implement. All of them (and StdAudio) represent sound as a sequence of floating-point numbers kept in an array, corresponding to sampling a sound wave at 44,100 samples per second.

Click to view larger image

Up to this point, the use of functions has been somewhat of a notational convenience. For example, the control flow in PROGRAM 2.1.1–2.1.3 is simple—each function is called in just one place in the code. By contrast, PlayThatTuneDeluxe (PROGRAM 2.1.4) is a convincing example of the effectiveness of defining functions to organize a computation because the functions are each called multiple times. For example, the function note() calls the function tone() three times and the function sum() twice. Without functions methods, we would need multiple copies of the code in tone() and sum(); with functions, we can deal directly with concepts close to the application. Like loops, functions have a simple but profound effect: one sequence of statements (those in the method definition) is executed multiple times during the execution of our program—once for each time the function is called in the control flow in main().

FUNCTIONS (STATIC METHODS) ARE IMPORTANT BECAUSE they give us the ability to extend the Java language within a program. Having implemented and debugged functions such as harmonic(), pdf(), cdf(), mean(), abs(), exchange(), shuffle(), isPrime(), uniform(), superpose(), note(), and tone(), we can use them almost as if they were built into Java. The flexibility to do so opens up a whole new world of programming. Before, you were safe in thinking about a Java program as a sequence of statements. Now you need to think of a Java program as a set of static methods that can call one another. The statement-to-statement control flow to which you have been accustomed is still present within static methods, but programs have a higher-level control flow defined by static method calls and returns. This ability enables you to think in terms of operations called for by the application, not just the simple arithmetic operations on primitive types that are built into Java.

Whenever you can clearly separate tasks within programs, you should do so. The examples in this section (and the programs throughout the rest of the book) clearly illustrate the benefits of adhering to this maxim. With static methods, we can

• Divide a long sequence of statements into independent parts.

• Reuse code without having to copy it.

• Work with higher-level concepts (such as sound waves).

This produces code that is easier to understand, maintain, and debug than a long program composed solely of Java assignment, conditional, and loop statements. In the next section, we discuss the idea of using static methods defined in other programs, which again takes us to another level of programming.