7.4 Data Structures: The Boolean Type

We introduced the Boolean data type in Chapter 4. We have used Boolean expressions (expressions that evaluate to True or False) to control loop repetition and to select one of the alternatives in an IF statement. Some examples of Boolean expressions are

    Gross > TaxBracket
    Item /= Sentinel
    TranType = 'C'

    TYPE Boolean IS ( False, True);

The simplest Boolean expression is a Boolean variable or constant. A Boolean variable or constant can be set to either of the Boolean values, False or True. The statement

    Debug : CONSTANT Boolean := True;

    Switch : Boolean; 
    Flag : Boolean;  

Boolean Operators

There are four Boolean operators: AND, OR, XOR, and NOT. These operators are used with operands that are Boolean expressions:

    ( Salary < Minsal) OR ( NumDepend > 5) 
    ( Temp > 90.0) AND ( Humidity > 0.90) 
    Athlete AND ( NOT Failing)
    Married XOR CollegeGraduate

The first expression can be used to determine whether an employee pays income tax. It evaluates to True if either condition in parentheses is true. The second expression can be used to describe an unbearable summer day: temperature and humidity both above 90. The expression evaluates to True only when both conditions are true. The third expression has two Boolean variables (Athlete and Failing) as its operands. Any individual for whom this expression is true is eligible for intercollegiate sports. The fourth expression evaluates to True if the individual is either married or a college graduate but not both. It might be useful to a public opinion pollster.

The Boolean operators can be used with Boolean expressions only. The Boolean operators are summarized in Table 7.4, which shows that the AND operator yields a true result only when both its operands are true, that the OR operator yields a false result only when both its operands are false, and that the XOR operator yields a true result only when exactly one of its operands is true. The NOT operator has a single operand and yields the logical complement, or negation, of its operand.

Table 7.4
Boolean Operators

op1   op2    NOT op1   op1 AND op2   op1 OR op2   op1 XOR op2

false false  true      false         false        false
false true   true      false         true         true
true  false  false     false         true         true
true  true   false     true          true         false	

Operator Precedence

Table 7.5
Operator Precedence

Operator 	Precedence

**, NOT, ABS 	highest ( evaluated first)
*, /, REM	multiplying operators
+, -	monadic adding operators
+, -, &	dyadic adding operators
	( & is concatenation, coming in Chapter 9)
<, <=, =, /=, >=, >	relational operators
AND, OR, XOR	dyadic logical operators ( evaluated last)

Example 7.14

The expression

X < Y + Z 

X < ( Y + Z)   

X < Y OR Z < Y 

( X < Y) OR ( Z < Y) 

because OR has lower precedence than <. The expression

NOT Sunny OR Warm

( NOT Sunny) OR Warm

As is clear from Table 7.5 and Example 7.14, Ada has many operators, and their relative precedences are often difficult to remember. It is therefore advisable to keep expressions relatively simple and to use parentheses to make clear what you mean.

Example 7.16

The following are all legal Boolean expressions if X, Y, and Z are type Float and Flag is type Boolean. The value of each expression is shown in brackets assuming that X is 3.0, Y is 4.0, Z is 2.0, and Flag is True.

1. ( X > Z) AND ( Y > Z)			[True]
2. ( X + Y / Z) <= 3.5			[False]
3. ( Y > X) XOR ( Y > Z)			[False]
4. NOT Flag				[False]
5. ( X = 1.0) OR ( X = 3.0)		[True]
6. ( 0.0 < X) AND ( X < 3.5)		[True]
7. ( X <= Y) AND ( Y <= Z)			[False]
8. NOT Flag OR (( Y + Z) >= ( X - Z)) 	[True]
9. NOT ( Flag OR (( Y + Z) >= ( X - Z)))	[False]

Expression 1 gives the Ada form of the relationship "X and Y are greater than Z." It is often tempting to write this as

    X AND Y > Z

However, this is an illegal Boolean expression because the float variable X cannot be an operand of the Boolean operator AND. Similarly, expression 5 shows the correct way to express the relationship "X is equal to 1.0 or to 3.0."

Expression 6 is the Ada form of the relationship 0.0 < X < 3.5 (i.e., "X is in the range 0.0 to 3.5"). Similarly, expression 7 shows the Ada form of the relationship X <= Y <= Z; that is, "Y is in the range X to Z, inclusive."

Finally, expression 8 is evaluated in Fig. 7.6; the values given at the beginning of this example are shown above the expression. The expression in Fig. 7.6 is rewritten below with parentheses enclosing the term NOT Flag. Although these parentheses are not required, they do clarify the meaning of the expression and we recommend their use:

    ( NOT Flag) OR (( Y + Z) >= ( X - Z))

Figure 7.6
Evaluation Tree for Boolean Expression

Short-Circuit Boolean Operators

When evaluating Boolean expressions, Ada evaluates both sides of the expression, but in an order not defined by the language. This is not usually a problem; generally we are interested only in the final result of the evaluation. Circumstances do arise, however, when it is desirable to evaluate the right side of an AND only if the left side is true, or the right side of an OR only if the left side is false. Ada provides for this purpose two additional operators, AND THEN and OR ELSE. These are called short-circuit operators: The evaluation of the right operand is skipped if evaluating the left operand determines the result of the expression.

Example 7.16

Both sides are always evaluated in the expression

    Flag OR (( Y + Z) /= ( X - Z))

but in the expression

    Flag OR ELSE (( Y + Z) /= ( X - Z))

Short-circuit evaluation has important applications. Sometimes it is necessary to omit evaluation of the right operand, lest a run-time error arise.

Example 7.17

If X is 0, the expression

    ( X /= 0.0) AND ( Y / X > 5.0)

is False because ( X /= 0.0) is False and False AND ... must always be False. Not only is there no need to evaluate the subexpression ( Y / X > 5.0) when X is zero, it is an error to do so: Numeric_Error would be raised because the divisor X is zero. An expression like this must be written

    ( X /= 0.0) AND THEN ( Y / X > 5.0)

to prevent the right side from being evaluated whenever X is zero.

Boolean Assignment Statements

    Same := X = Y;

    IF X = Y THEN
    	Same := True;
    ELSE
    	Same := False;
    END IF;       

Example 7.18

The assignment statement below assigns the value True to Even if N is an even number:

    Even := ( N REM 2) = 0;

This statement assigns a value of True to Even when the remainder of N divided by 2 is 0. (All even numbers are divisible by 2.)

Using Boolean Variables as Program Flags

Example 7.19

In Section 6.7 we developed, for package Robust_Input, a procedure for reading an integer value Item between the values MinVal and MaxVal. That procedure used Ada exception handling to determine whether the input value was in range. Suppose Ada did not have an exception-handling capability (many languages don't)? Here is a loop for reading input within range that has similar behavior but does not use exception handling.

-- Keep reading until a valid number is read.
  Between := False;   -- Assume a valid number is not read
  WHILE NOT Between LOOP
    -- invariant:
    --   All prior values of Item are outside the range MinVal to MaxVal

    Ada.Text_IO.Put(Item => "Enter an integer between ");
    Ada.Integer_Ada.Text_IO.Put(Item => MinVal, Width => 0);
    Ada.Text_IO.Put(Item => " and ");
    Ada.Integer_Ada.Text_IO.Put(Item => MaxVal, Width => 0);
    Ada.Text_IO.Put(Item => " > ");
    Ada.Integer_Ada.Text_IO.Get(Item => Item);
    Between := (Item >= MinVal) AND (Item <= MaxVal);

  END LOOP;
  -- assert: Item is in the range MinVal to MaxVal 

This loop continues to read integer values until a value between its two input parameters, MinVal and MaxVal, is entered. The first data value within range is returned as the procedure result. The Boolean variable Between is used as a program flag to signal whether or not the event "data entry of an integer between MinVal and MaxVal" has occurred. The variable Between is initialized to False before the WHILE loop. Inside the WHILE loop, the assignment statement

    Between := (Item >= MinVal) AND (Item <= MaxVal) 

resets Between to True when a value between MinVal and MaxVal is read into N. The loop is repeated as long as Between is still False. Finally, we could write the last statement equally well as

    Between := Item IN MinVal .. MaxVal;

    WITH Ada.Text_IO;
    PACKAGE Boolean_IO IS NEW Ada.Text_IO.Enumeration_IO (Enum => Boolean);

    WITH Boolean_IO;

Example 7.20

Two well-known laws of logic are called DeMorgan's laws after their discoverer. These two laws state that, for two Boolean variables X and Y, for any combination of values of X and Y

    NOT( X OR Y)  = ( NOT X) AND ( NOT Y)
    NOT( X AND Y) = ( NOT X) OR  ( NOT Y)

Program 7.8 illustrates the validity of these laws, the use of a Boolean flag to control an input loop, and also the use of Boolean_IO.

Program 7.8
Demonstration of DeMorgan's Laws and Boolean_IO

WITH Ada.Text_IO;
WITH Boolean_IO;
PROCEDURE Show_DeMorgan IS
------------------------------------------------------------------------
--| Demonstrates the validity of DeMorgan's Laws, and also Boolean_IO
--| a Boolean flag is also used to control the input loop
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: July 1995                                     
------------------------------------------------------------------------

  X         : Boolean;
  Y         : Boolean;
  MoreInput : Boolean;

BEGIN -- Show_DeMorgan

  MoreInput := True;
  WHILE MoreInput LOOP

    Ada.Text_IO.Put
      ( Item => "Please enter True or False value for X > ");
    Boolean_IO.Get ( Item => X);
    Ada.Text_IO.Put
      ( Item => "Please enter True or False value for Y > ");
    Boolean_IO.Get ( Item => Y);

    Ada.Text_IO.Put( "NOT( X OR Y)         = ");
    Boolean_IO.Put( Item => NOT( X OR Y), Width => 1);
    Ada.Text_IO.New_Line;

    Ada.Text_IO.Put( "( NOT X) AND ( NOT Y) = ");
    Boolean_IO.Put( Item => ( NOT X) AND ( NOT Y), Width => 1);
    Ada.Text_IO.New_Line;
    Ada.Text_IO.New_Line;

    Ada.Text_IO.Put("NOT( X AND Y)        = ");
    Boolean_IO.Put( Item => NOT( X AND Y), Width => 1);
    Ada.Text_IO.New_Line;

    Ada.Text_IO.Put("( NOT X) OR ( NOT Y)  = ");
    Boolean_IO.Put( Item => ( NOT X) OR ( NOT Y), Width => 1);
    Ada.Text_IO.New_Line;
    Ada.Text_IO.New_Line;

    Ada.Text_IO.Put
      ( Item=>"Do you wish to try another combination ( True/False)? ");
    Boolean_IO.Get ( Item => MoreInput);

  END LOOP;

END Show_DeMorgan;

Please enter True or False value for X > false
Please enter True or False value for Y > false
NOT( X OR Y)         = TRUE
( NOT X) AND ( NOT Y) = TRUE

NOT( X AND Y)        = TRUE
( NOT X) OR ( NOT Y)  = TRUE

Do you wish to try another combination ( True/False)? true
Please enter True or False value for X > false
Please enter True or False value for Y > true
NOT( X OR Y)         = FALSE
( NOT X) AND ( NOT Y) = FALSE

NOT( X AND Y)        = TRUE
( NOT X) OR ( NOT Y)  = TRUE

Do you wish to try another combination ( True/False)? false

Using a Global Boolean Constant for Debugging

We mentioned earlier that the programmer should plan for debugging by including diagnostic print statements in the original code. One way to prevent the diagnostic print statements from executing during production runs is to declare a global Boolean constant (say, Debugging) whose value is True during debugging and False during production runs. The declaration part of the main program will contain the constant declaration

    Debugging : CONSTANT Boolean := True; -- turn diagnostics on

    Debugging : CONSTANT Boolean := False; -- turn diagnostics off

    IF Debugging THEN
        Ada.Text_IO.Put ( Item => "Procedure ProcessGoods entered");  
        Ada.Text_IO.New_Line;
        Ada.Text_IO.Put ( Item => "Input parameter Salary is ");
        Ada.Float_Text_IO.Put ( Item => Salary, Fore => 6, Aft => 2, Exp => 0);  
        Ada.Text_IO.New_Line;
    END IF; 

This case study involves the manipulation of type Natural data. It also illustrates the use of Boolean variables as program flags.

PROBLEM SPECIFICATION

Write a program that tests a positive integer to determine whether or not it is a prime number. A prime number is an integer that has no divisors other than 1 and itself. Examples of prime numbers are the integers 2, 3, 5, 7, and 11.

ANALYSIS

Our program will either display a message indicating that its data value is a prime number, or it will display the smallest divisor of the number if it is not prime.

Data Requirements

Problem Inputs

the number to be tested for a prime number (N : Positive)

Problem Outputs

the smallest divisor if N is not prime (FirstDiv : Positive)

DESIGN

Initial Algorithm

1. Read in the number to be tested for a prime number.

2. Find the smallest divisor > 1 or determine that the number is prime.

3. Display a message that the number is prime or print its smallest divisor.

We will use the Boolean variable Prime as a program flag to indicate the result of step 2 as described below. A structure chart is shown in Fig. 7.7.

Figure 7.7
Structure Chart for Prime-Testing Program

Additional Program Variables

program flag that will be set to True if N is prime, False otherwise (Prime : Boolean)

We can dispose of Step 3 very simply with the following refinement:

Step 3 Refinement

3.1. IF N is prime THEN

     Display a message that N is prime

ELSE

     Display the first divisor of N

END IF;

Let us consider step 2. Define a subtype SmallPos to include the positive numbers from 2 to MaxN (1000). Variable FirstDiv (the first divisor) is type SmallPos, and we need to compute the values of FirstDiv and Prime by determining whether or not N has any divisors other than 1 and itself.

If N is an even integer, it is divisible by 2. Therefore, 2 is the only even integer that can be prime, and 2 is the smallest divisor of all other even integers.

If N is an odd integer, its only possible divisors are the odd integers less than N. In fact, it can be proved that a number is prime if it is not divisible by any odd integer less than or equal to its square root. These considerations form the basis for the algorithm shown next.

Step 2 Refinement

2.1.IF N = 2 THEN

     2.2. N is a prime number

ELSIF N is even then

     2.3. 2 is the smallest divisor and N is not prime

ELSE

     2.4. Test each odd integer between 3 and N to see whether it is a divisor of N

END IF;

Step 2.4 must test each odd integer as a possible divisor of N until a divisor is found. This we do with a WHILE loop that has the following loop invariant:

    -- invariant:
    -- FirstDiv during pass i is 1 + 2 * i (3, 5, 7, ... ) and
    -- No prior value of FirstDiv is a divisor of N and
    -- FirstDiv is less than or equal to the square root of N

Step 2.4 refinement

2.4.1. Assume N is a prime number (i.e., set Prime to True)

2.4.2. Initialize FirstDiv to 3

2.4.3. WHILE Prime is still True and FirstDiv < SQRT( N) LOOP

     2.4.4. IF FirstDiv is a divisor of N THEN

     2.4.5. Set Prime to False (N is not prime)

     ELSE

     2.4.6. Set FirstDiv to the next odd number

     END IF;

END LOOP;

IMPLEMENTATION

The implementation and testing is left as an exercise.

Exercises for Section 7.4

Self-Check

1. Draw the evaluation tree for expression 9 of Example 7.16.
2. Write the following Boolean assignment statements:

   a. Assign a value of True to Between if the value of N lies between -K and +K, inclusive; otherwise, assign a value of False.

   b. Assign a value of True to UpCase if Ch is an uppercase letter; otherwise, assign a value of False.

   c. Assign a value of True to Divisor if M is a divisor of N; otherwise, assign a value of False.

Programming

1. Write a function that returns a Boolean value indicating whether or not its first parameter is divisible by its second parameter.

Copyright © 1996 by Addison-Wesley Publishing Company, Inc.