Chapter 5
Indefinite Loops and Program Logic

5.1 Introduction

The chapter begins by examining a new construct called a while loop that allows you to loop an indefinite number of times. Then it discusses the type boolean in greater detail. Then it explores what are known as assertions and their relationship to understanding the logic of programs. It ends with a discussion of other loop constructs available in Java.

5.2 While Loops

The loops we have looked at so far have been fairly simple loops that execute a predictable number of times. We call them "definite" loops because you know before the loop begins executing exactly how many times it will execute. Now we want to turn our attention to indefinite loops where you don't know how many times a loop will execute. These come up often in interactive programs and file processing. For example, you don't know in advance how many times a user might want to play a game and you won't know before you look at a file exactly how much data it stores.

The while loop is the first indefinite loop we will study. It has the following syntax:

Here is an example of a while loop.

    int number = 1;
    while (number <= 200)
	number *= 2;

    int number = 1;
    if (number <= 200)
	number *= 2;

The while loop tests its condition before executing the statement it controls. It performs its test at the top of the loop, as indicated in this pseudocode.

    loop
        evaluate test.
        if test returns false then exit.
        execute controlled statement.
    end of loop

Here is a while with two statements in the loop.

    int number = 1;
    while (number <= max) {
	System.out.println("Hi there");
	number++;
    }

    for (int number = 1; number <= max; number++)
	System.out.println("Hi there");

Here is a pseudocode description of how you might do this.

	start divisor at 2.
	while (the current value of divisor does not work)
	    increase divisor.

	start divisor at 2.
	while (the remainder of number/divisor is not 0)
	    increase divisor.

    int divisor = 2;
    while (number % divisor != 0)
	divisor++;

    int number = 1;
    while (number > 0)
	number++;

5.2.1 Fencepost Loops (aka loop and a half)

In programming we often find ourselves with a particular kind of loop known as a fencepost loop. To understand the concept, consider the following problem. You want to put up a fence that is 100 yards long and you want to have a post every 10 yards. How many posts do you need? If you do a quick division in your head, you might say that you need 10 posts, but actually you need 11 posts. That's because fences begin and end with posts. In other words, the fence looks like this:

    post, wire, post, wire, ..., post, wire, post

    for (the length of the fence) {
        plant a post.
        attach some wire.
    }

One solution is to plant one of the posts either before or after the loop. The usual solution is to do it before.

    plant a post.
    for (the length of the fence) {
        attach some wire.
        plant a post.
    }

As a simple example, consider the problem of writing out the integers between 1 and 10 separated by commas. In other words, we want to get this output:

    System.out.print(1);
    for (int i = 2; i <= 10; i++)
	System.out.print(", " + i);
    System.out.println();

5.2.2 Sentinel Loops

Suppose you want to read a series of numbers from the user and compute their sum. You could ask the user in advance how many numbers to read, but that isn't always convenient. What if the user has a long list of numbers to enter? One way around this is to pick some special input value that will signal the end of input. We call this a sentinel value.

For example, you could tell the user to enter the value -1 to stop entering numbers. But how do we structure our code to make use of this sentinel? In general, we want to do the following.

    sum = 0.
    while (we haven't seen the sentinel) {
	prompt & read.
	add it to the sum.
    }

    sum = 0.
    prompt & read.
    while (we haven't seen the sentinel) {
	add it to the sum.
	prompt & read.
    }

    sum = 0.
    prompt & read a value into n.
    while (n is not the sentinel) {
	add n to the sum.
        prompt & read a value into n.
    }

    Scanner console = new Scanner(System.in);

    int sum = 0;
    System.out.print("next integer (-1 to quit)? ");
    int number = console.nextInt();
    while (number != -1) {
        sum += number;
        System.out.print("next integer (-1 to quit)? ");
        number = console.nextInt();
    }
    System.out.println("sum = " + sum);

5.2.3 Checking for User Errors

In the last chapter we wrote programs that assumed that the user would type appropriate values. In general, you want to write programs that don't make such assumptions. We saw, for example, that the Scanner object can throw an exception if the user types the wrong kind of data. It's better to write programs that can deal with user errors. Such programs are referred to as being robust.

Consider the following code fragment:

    Scanner console = new Scanner(System.in);
    System.out.print("How old are you in years? ");
    int age = console.nextInt();

What if the user types something other than an integer? Then we'd want to discard the input, print out some kind of error message and prompt for a second input. We'd want this in a loop so that we'd keep discarding input and generating error messages until the user gives us legal input. Here is a first attempt at a solution in pseudocode:

    while (user hasn't given us an integer) {
        prompt.
        discard input.
        generate an error message.
    }
    read the integer.

    prompt.
    while (user hasn't given us an integer) {
        discard input.
        generate an error message.
        prompt.
    }
    read the integer.

    Scanner console = new Scanner(System.in);
    System.out.print("How old are you in years? ");
    while (!console.hasNextInt()) {
        console.next();  // to discard the input
        System.out.println("That is not an integer.  Please try again.");
        System.out.print("How old are you in years? ");
    }
    int age = console.nextInt();

    public static int getInt(Scanner console, String prompt) {
	System.out.print(prompt);
	while (!console.hasNextInt()) {
	    console.next();
	    System.out.println("That is not an integer.  Please try again.");
	    System.out.print(prompt);
	}
	return console.nextInt();
    }

    Scanner console = new Scanner(System.in);
    int age = getInt(console, "How old are you in years? ");

5.2.4 A loop with priming and pseudorandom numbers

We often want our programs to exhibit apparently random behavior. This often comes up in game playing programs where we need our program to make up a number for the user to guess or to shuffle a deck of cards or to pick a word from a list of words for the user to guess. Programs are, by their very nature, predictable and non-random. But we can produce values that seem to be random. Such values are called pseudorandom because they are produced algorithmically.

Java provides several mechanisms for obtaining pseudorandom numbers. You can call the method Math.random() from the Math class to obtain a random floating point value that has the property that:

Let's look at a simple program that picks numbers between 1 and 10 until a particular number comes up. Let's use the Random class to construct an object for generating our pseudorandom numbers:

	Random r = new Random();

        int result;
	while (result != number) {
	    result = r.nextInt(10) + 1;
	    System.out.println("next number = " + result);
	}

We want to set the variable result to something that will cause us to enter the loop, but in some sense we don't care what value we set it to as long as it gets us into the loop. We would want to be careful not to set it to the value the user wants us to generate. We are dealing with values between 1 and 10, so we could set result to a value like -1 that is clearly outside the range of numbers we are working with. We sometimes refer to this as a "dummy" value because we don't actually process it. Later in this chapter we will see a variation of the while loop that wouldn't require this kind of priming.

Below is the complete program solution.

5.3 Type boolean

George Boole was such a good logician that a type has been named for him. You use the Java type boolean to describe logical true/false relationships. Recall that boolean is one of the primitive types like int, double and char.

Without realizing it, you have already used booleans. if/else statements and while loops are controlled by expressions that specify tests. The following expression:

	number % 2 == 0

To understand this better, remember what these terms mean for type int. The The literals of type int include 0, 1, 2, and so on. Because these are literals of type int, you can do things like the following:

    int number1 = 1;
    int number2 = 0;

    boolean test1 = true;
    boolean test2 = false;

    test1 = test2;

    number1 = 2 + 2;

    test1 = (2 + 2 == 4);
    test2 = (3 * 100 < 250);

Many beginners don't understand these assignment statements and write code like the following.

	if (x < y)
	    less = true;
	else
	    less = false;
	END;

	less = (first < second);

You form complicated boolean expressions using what are known as the logical operators.

The not operator ("!") reverses the truth value of its operand. If an expression evaluates to true, its negation evaluates to false and vice versa. You can express this using a truth table. The following truth table has two columns, one for a variable and one for its negation. The table shows for each value of the variable, the corresponding value of the negation.

In addition to the negation operator, there are two logical connectives you will use, and ("&&") and or ("||"). You use these connectives to tie two boolean expressions together, creating a new boolean expression. The truth table below shows that the and operator returns true only when both of its individual operands are true:

The truth table below shows that the or operator returns true except when both operands are false.

The Java or operator has a slightly different meaning than the English "or." In English you say, "I'll study tonight or I'll go to a movie." One or the other will be true, but not both. The or operator behaves differently. If both operands are true, the overall proposition is true.

You generally use the logical operators when what you have to say does not reduce to one test. For example, suppose you want to do something if a number is between 1 and 10. You might say:

	if (number >= 1)
	    if (number <= 10)
		doSomething();

	if (number >= 1 && number <= 10)
            doSomething();

	if (x == 1 || 2 || 3)
	    doSomething();

	if (x == 1 || x == 2 || x == 3)
	    doSomething();

        if (!first && second || third)
            doSomething();

5.3.1 Flags and Other boolean Variables

if/else statements are controlled by a boolean test. The test can be a boolean variable as well as a boolean expression. Consider, for example, the following code.

    if (number > 0)
        System.out.println("positive");
    else
        System.out.println("negative");

    boolean positive = (number > 0);
    if (positive)
        System.out.println("positive");
    else
        System.out.println("negative");

    boolean cute = (looks >= 9);
    boolean smart = (IQ > 125);
    boolean rich = (income > 100000);
    boolean available = (snothers == 0);
    boolean awesome = cute && smart && rich && available;

        for (each step taken by a team member)
	    if (this step puts the player over the scrimmage line)
		set offsides to true.
	    else
		set offsides to false.
        if (offsides)
            impose penalty.

        for (each step taken by a team member)
	    if (this step puts the player over the scrimmage line)
		set offsides to true.
        if (offsides)
            impose penalty.

        set offsides to false.
        for (each step taken by a team member)
	    if (this step puts the player over the scrimmage line)
		set offsides to true.
        if (offsides)
            impose penalty.

	double sum = 0;
	for (int i = 1; i <= totalNumber; i++) {
	    System.out.print("    next--> ");
	    double next = console.nextDouble();
	    sum += next;
	}
	System.out.println("Sum = " + sum);

	double sum = 0;
	boolean negative = false;
	for (int i = 1; i <= totalNumber; i++) {
	    System.out.print("    next--> ");
	    double next = console.nextDouble();
	    sum += next;
	    if (sum < 0)
		negative = true;
	}
	System.out.println("Sum = " + sum);
	if (negative)
	    System.out.println("Sum went negative");
	else
	    System.out.println("Sum never went negative");

5.4 Other Indefinite Loops

As we have seen, the while loop tests at the "top" of the loop before it executes its controlled statement. Java has an alternative known as the do/while loop that tests at the "bottom" of the loop. It has the following syntax:

	int number = 1;
	do
	    number *= 2;
	while (number <= 200);

Recall that the while loop operates like this, testing before executing the controlled statement:

    loop
        evaluate test.
        if test returns false then exit.
        execute controlled statement.
    end of loop

    loop
        execute controlled statement.
        evaluate test.
        if test returns false then exit.
    end of loop

We saw a situation like this earlier with the program that picked pseudorandom numbers between 1 and 10 until a certain number is picked. You know you have to pick at least once, so a do/while is appropriate. The while loop version required priming, which involved initializing a variable before the loop. With the do/while version, we don't need to initialize because we know the loop will execute at least once:

5.4.1 Break and "forever" loops

The while loop has its test at the top of the loop and the do/while has its test at the bottom of the loop. That should lead you to wonder whether it might be desirable to have the test in the middle of the loop. There is a way to accomplish this in Java, although it requires some odd looking loops.

Java has a special statement called "break" that will exit a loop. You can use it to break out of any of the loops we have seen (while, do/while, for). Loops with break statements can be difficult to understand, so the practice is generally discouraged. But there is an interesting application of break to form a loop where the test occurs in the middle. The problem is that we still need to choose one of the standard loop constructs (while, do/while, for). One common choice is to form what appears to be an infinite loop with a while loop:

    Scanner console = new Scanner(System.in);

    int sum = 0;
    System.out.print("next integer (-1 to quit)? ");
    int number = console.nextInt();
    while (number != -1) {
        sum += number;
        System.out.print("next integer (-1 to quit)? ");
        number = console.nextInt();
    }
    System.out.println("sum = " + sum);

    Scanner console = new Scanner(System.in);

    int sum = 0;
    while (true) {
        System.out.print("next integer (-1 to quit)? ");
        int number = console.nextInt();
        if (number == -1)
            break;
        sum += number;
    }
    System.out.println("sum = " + sum);

Another form of this loop is to use a for loop that has none of the usual initialization, test and update code. The for loop still needs the parentheses and semicolons, but the rest can be empty. This leads to the following rather odd looking code:

    Scanner console = new Scanner(System.in);

    int sum = 0;
    for (;;) {
        System.out.print("next integer (-1 to quit)? ");
        int number = console.nextInt();
        if (number == -1)
            break;
        sum += number;
    }
    System.out.println("sum = " + sum);

People tend to either love or hate this version of the for loop and for the same reason. The people who hate it say, "This looks too strange." The people who love it say, "I'm glad it looks strange because it makes it clear that the real loop test is somewhere else." Some people read the "for (;;)" as "forever" and refer to these as "forever loops."

Many advocates of structured programming argue that neither of these loops is a reasonable alternative. They argue that the break statement is like the "goto" construct that many computer scientists have argued leads to unstructured "spaghetti" code. Obviously different programmers will make up their own minds about whether they like this construct or not.

5.5 Assertions and Program Logic

Logicians concern themselves with assertions.

The following are all assertions.

	2 + 2 = 4
	The sun is larger than the earth.
	x > 45
	It was raining.
	The rain in Spain falls mainly on the plain.

	How much do you weigh?
	Please take me home.

	x > 45			This depends on x.
	It was raining.		This depends on when and where.

	when x = 13, x > 45
	On July 4, 1776 in Philadelphia, it was raining.

    System.out.print("Please input a nonnegative number--> ");
    double number = console.nextDouble();
    // Is number nonnegative here?

Using a loop we can guarantee that the number we get is nonnegative.

    double number;
    do {
        System.out.print("Please input a nonnegative number--> ");
        number = console.nextDouble();
    } while (number < 0.0);
    // Is number nonnegative here?

This doesn't mean that the number "should be nonnegative" after the loop. It means the number "will be nonnegative." By working through the logic of the program, you can see that this is a certainty. It is an assertion of which you are sure. You could even prove it if need be. Such an assertion is called a provable assertion.

Provable assertions help to identify unnecessary bits of code. Consider these statements:

	int x = 0;
	if (x == 0)
            System.out.println("This is what I expect.");
	else
            System.out.println("how can that be?");

	int x = 0;
        System.out.println("This is what I expect.");

5.6 Preconditions and Postconditions

You can formally describe the workings of a method using assertions. For example, you can give a series of assertions that describe what will be true when a method is done executing. Such assertions are called postconditions of a method. For example, to describe the job of a person on an auto assembly line, you might use a postcondition like, "The bolts that secure the left front tire are on the car and tight."

Postconditions are not the whole story. Employees on an assembly line depend on each other. A line worker can't add bolts and tighten them if the left tire isn't there or if there are no bolts. You specify conditions like these by using preconditions, assertions that must be true before a task is performed. The assembly line worker might have preconditions like, "the left tire is mounted properly on the car; there are at least 8 bolts in the supply box; and a working wrench is available." You describe the task fully, then, by saying that the worker can make the postconditions true if the preconditions are true before starting.

Methods, like workers on an assembly line, need to work together, each solving its portion of the task, in order to solve the overall task. The preconditions and postconditions describe the dependencies between methods. To understand this better, consider this nonprogramming example with the following methods and their conditions.

        makeBatter
                pre : bowl is clean.
                post: bowl has batter in it; bowl is dirty.
        bakeCake
                pre : bowl has batter in it; pan is clean.
                post: cake is baked; pan is dirty.
        washDishes
                pre : none.
                post: bowl and pan are clean.

        makeBatter.
        bakeCake.

        --> bowl and pan are clean.
        makeBatter.
        --> bowl has batter in it; bowl is dirty; pan is clean.
        bakeCake.
        --> cake is baked; bowl and pan are dirty.

        for (many cakes) {
            makeBatter.
            bakeCake.
        }

        --> bowl and pan are clean.
        makeBatter.
        --> bowl has batter in it; bowl is dirty; pan is clean.
        bakeCake.
        --> cake is baked; bowl and pan are dirty.
        makeBatter.

        for (many cakes) {
            makeBatter.
            bakeCake.
            washDishes.
        }

5.7 Programming Problems

1. Write an interactive program that prompts for an integer and displays the same number in binary. How would you modify the program to make it display in base 3 rather than base 2?