In Part III, we have explored means to generate test data, and in Chapter 11, we have discussed ways to generate test oracles; in this chapter, we discuss how to compose test data and test oracles to develop a test driver.

12.1 SELECTING A SPECIFICATION

In Chapter 11, we have discussed how to map a specification against which we want to test a program into a test oracle; in this section, we discuss how to choose a specification. One may argue that the question of what specification to test a program against is moot, since we do not get to choose the specification. We argue that while we do not in general have the luxury of deciding what specification we must test a program against, we do have some latitude in choosing how to deploy different verification methods against different components of a complex, compound specification. Indeed, each family of verification methods (fault avoidance, fault removal, fault tolerance) works best for some type of specifications and works much less for others; the law of diminishing returns advocates that we use a wide range of methods, where each method is deployed against the specification components that are best adapted to it. We consider each broad family of methods and briefly characterize the properties of the specifications that are best adapted to it:

• Fault Avoidance/Static Analysis of Program/Static Verification of Program Correctness. We argue that specifications that are reflexive and transitive are very well adapted to static verification methods. Imagine that one has to prove the correctness of a complex program g with respect to a specification R that is represented by a reflexive transitive relation. If g is structured as a sequence of two subprograms, say , then to prove that G refines R, it suffices to prove that G₁ and G₂ refine R (since R is transitive). Likewise, we find that if g is an if-then statement, then to prove that G refines R, it suffices to prove that the then-branch of g refines R; and that if g is an if-then-else statement, then to prove that G refines R, it suffices to prove that each branch of the statement refines R; and finally that if g is a while statement, then in order for G to refine R, it suffices that the loop body of g refines R. More generally, the reflexivity and transitivity of R greatly simplify the inductive arguments that are at the heart of many algorithms, whereby reflexivity supports the basis of induction and transitivity supports the inductive step.

  As far as axiomatic program proofs are concerned (using Hoare’s logic), it is well known that the most difficult aspects of such proofs (and the main obstacle to their automation) is the need to generate intermediate assertions and invariant assertions. When the specification at hand is reflexive and transitive, these assertions often take the simple form

  
  where s₀ is the initial state and s is the current state. A small illustration of this situation is given in Chapter 6, where a reflexive transitive relation (prm(s0,s)) is uniformly used as an intermediate assertion and as an invariant assertion throughout the program, and all the verification conditions have the same assertion as precondition and postcondition.
• Fault Removal/Software Testing. The main criterion that a specification must satisfy to be an adequate choice for testing is the criterion of reliability: It must produce an oracle that can be implemented reliably, as a faulty oracle may throw the whole test off-balance and may insert faults into the software product, rather than remove existing faults.
• Fault Tolerance. In order to be an adequate specification for fault tolerance, a specification has to meet the following criteria: first, lend itself to a simple, reliable oracle (the same criterion as for testing, for the same rationale); second, it has to lend itself to an efficient run-time execution (since it may have to be checked at run-time to detect errors); third, and most importantly, it has to refer to current states rather than current and past states. In practice, this third requirement means that the specification is represented by an inverse vector, that is, a relation R such that . Such relations refer to the current state but not to any previous state; they offer the advantage that they can be checked by looking exclusively at the current state and spare us from the burden of storing previous states at designated checkpoints and from checking complex binary relations; hence they represent a savings in terms of memory space and processing time.

To illustrate the kind of rationale that governs the mapping of sub-specification to methods, we consider the following examples:

• We consider the example of the sorting routine discussed in Chapter 6, where we showed that such a program is difficult to prove using static methods, and difficult to test, but that that it is easy to prove its correctness with respect to some part of the specification and very easy and efficient to test it against the other part of the specification.
• We consider the specification of a program to perform a Gaussian elimination of a system of linear equations defined by a square matrix of size N and a column vector of size N. The specification that we consider for this program has the form:
  
  where Eq means that the original system of equations has the same set of solutions as the final system of equations and Tri means that the final system of equations is triangular. It is difficult to prove the correctness of the program with respect to specification Gauss (since this requires that we deal with several nested loops, we check the start and end values of several index variables, we worry about the logic for finding optimal pivots, etc.); it is very complex, inefficient, and unreliable to test the program using an oracle derived from specification Gauss (due to the difficulty and inefficiency of ensuring that two systems of equations have the same set of solutions); it gives us a great return on investment (in terms of required effort vs. achieved impact) to verify the correctness of a candidate program with respect to specification Eq (since that can be done by merely checking that the system of equations is never modified except by replacing an equation by a linear combination of the equation with others) and to test it using an oracle derived from specification Tri (since this can be done by a simple scan of the lower half of the current matrix, without reference to any previously saved data). Note that as an equivalence relation, Eq is reflexive and transitive (hence satisfies the properties we have identified as making a specification adequate for proving correctness).

Hence when we say that the first step in designing a test driver is to decide what specification we want to test the program against, we mean it. The foregoing discussions illustrate in what sense and to what extent the software engineer does have some latitude in making this decision.

12.2 SELECTING A PROCESS

The structure of the test driver depends on the following (inter-dependent) parameters:

• The Goal of the Test. If the goal of the test is to certify the product or to rule on acceptance, then it is driven by the mandated test data; if the goal of the test is to find and remove faults, then it is driven by the observation of failures.
• Whether the Test Data is Extracted from a Prepared Set or Generated by a Random Data Generator. If the test data is extracted from a prepared test data set, then it runs until the set is exhausted; if the test data is generated at random (according to some law of probability) by a test data generator, then some other criterion must be used to determine when the test terminates.
• Whether the Test Must Stop at Each Failure or Merely Record the Failure and Continue. Depending on the process of testing, we may have to stop the test whenever the program fails; this applies in particular if the test cycle includes a repair phase, which takes place off-line.
• Whether Test Outcomes Are Recorded for Postmortem Analysis. In some cases, such as certification testing or acceptance testing, the only relevant outcome of the test is whether the candidate program has passed the test successfully; in other cases, such as cases where the test results are used to identify and remove faults, each test execution (or perhaps each execution that leads to failure) must be documented for postmortem analysis.

As an example, a certification test based on a predefined test set may look like this:

bool certified ()
  {bool c=true;  stateType s, init_s;
    while !(testSet.empty())
    {testSet.remove(s);  init_s=s; 
   g;  //  program under test; manipulates s, preserves init_s;
   c = c && oracle(init_s, s);}
    return c;}

This function returns true if and only if the candidate program runs successfully on all the test data in testSet. If the same test data set is used for debugging purposes, then the test driver may look as follows:

void testReport()
   {stateType s, init_s;
     while !(testSet.empty())
       {testSet.remove(s);  init_s=s;  
       g;  //  program under test; manipulates s, preserves init_s;
       if (oracle(init_s, s)) {successfulTest(init_s,s);}
       else {unsuccessfulTest(init_s,s);};}
     }

If we have a test data generator that can produce data indefinitely, and we are interested in running the test until the next failure (hopefully, the program will fail eventually, if not we have an infinite loop), then the test driver may look as follows:

void testUntilFailure()
  {stateType s, init_s;
     repeat
       {generateTestData(s);  init_s=s;  
       g;  //  program under test; manipulates s, preserves init_s;
       }
     until !oracle(init_s,s);
  unsuccessfulTest(init_s, s);}

12.3 SELECTING A SPECIFICATION MODEL

For simple input/output programs, the test driver templates we have presented in the previous section can be used virtually verbatim; all we need to do is instantiate the functions that generate test data and execute the oracle. But for software products that have an internal state, such as abstract data types (ADT’s), two complications arise:

• First, the oracle is not a closed form Boolean function, since the specification is represented by axioms and rules rather than by a closed form logic formula.
• Second, test data does not take the form of values assigned to variables but rather takes the form of method calls.

In this section, we discuss the design of test drivers for software products that carry an internal state; we cover, in turn, the case where test data is generated randomly, then the case where test data is pre-generated according to some criterion (such as those discussed in Chapter 9).

#include <iostream>
#include “stack.cpp”
#include “rand.cpp”

using namespace std;

typedef int boolean;
typedef int itemtype;

const int testsize = 10000;
const int hlength = 9;
const int Xsize = 5;
const itemtype paramrange=7;  // drawing parameter to push()

// random number generators
int randnat(int rangemax);  int gt0randnat(int rangemax);

// rule testers
void initrule();  void initpoprule();  void pushpoprule();
void sizerule(); void emptyrulea();  void emptyruleb();
void vopruletop(); void voprulesize(); void vopruleempty();
// history generator
void historygenerator
   (int hl, int hop[hlength], itemtype hparam[hlength]);

/*  State Variables    */
stack s; // test object
int nbf; // number of failures

int main ()
   {
  /*  initialization  */
  nbf=0;            // counting the number of failures
  SetSeed (825);    // random number generator 

  for (int i=0; i<testsize; i++)
    {switch(i%9)
    {case 0: initrule(); break;
                case 1:  initpoprule(); break; 
    case 2: pushpoprule(); break;
                case 3:  sizerule(); break;
    case 4: emptyrulea(); break;
                case 5:  emptyruleb(); break;
    case 6: vopruletop(); break;
                case 7:  voprulesize(); break;
    case 8: vopruleempty(); break;}
    }
   cout << “failure rate: ” << nbf << “ out of ” << testsize << endl;
   }

void pushpoprule() 
  {
  // stack(init.h.push(a).pop.h+) = stack(init.h.h+)

  int hl, hop[hlength]; itemtype hparam[hlength];  // storing h
  int hplusl, hplusop[hlength]; itemtype hplusparam[hlength]; // storing h+
  int storesize;      // size in LHS
  boolean storeempty; // empty in LHS
  itemtype storetop;  // top in LHS
  boolean successfultest; // successful test

  // drawing h and h+ at random, storing them in hop, hplusop
  hl = randnat(hlength); 
  for (int k=0; k<hl-1; k++) 
    {hop[k]=gt0randnat(Xsize);
       if (hop[k]==1) {hparam[k]=randnat(paramrange);}}

  hplusl = gt0randnat(hlength);
  for (int k=0; k<hplusl-1; k++) 
    {hplusop[k]=gt0randnat(Xsize);  
        if (hplusop[k]==1) {hplusparam[k]=randnat(paramrange);}}

  // left hand side of rule
  s.sinit(); historygenerator(hl,hop,hparam);
  itemtype a=randnat(paramrange); s.push(a); s.pop();
  historygenerator(hplusl,hplusop,hplusparam);
  // store resulting state
  storesize = s.size(); storeempty=s.empty();
      storetop=s.top();

  // right hand side of rule
  s.sinit(); historygenerator(hl,hop,hparam);
  historygenerator(hplusl,hplusop,hplusparam);
  // compare current state with stored state
  successfultest = 
   (storesize==s.size()) && (storeempty==s.empty()) && (storetop==s.top());
  if (! successfultest) {nbf++;}
  }

void historygenerator (int hl, int hop[hlength], itemtype hparam[hlength])
  {int dumsize; boolean dumempty; itemtype dumtop;
  for (int k=0; k<hl-1; k++)
    {switch (hop[k])
        {case 1:  {itemtype a=hparam[k]; s.push(a);} break; 
         case 2:  s.pop(); break;
         case 3:  dumsize=s.size(); break;
         case 4:  dumempty=s.empty(); break;
         case 5:  dumtop=s.top(); break;
        }
      }
  }

  int randnat(int rangemax)
    {//  returns a random value between 0 and rangemax
    return (int) (rangemax+1)*NextRand();
    }

  int gt0randnat(int rangemax)
    {//  returns a random value between 1 and rangemax
    return 1 + randnat(rangemax-1);
    }

  void sizerule() 
  {// stack(init.h.push(a).size) = 1+stack(init.h.size)
  int hl, hop[hlength]; itemtype hparam[hlength];  // storing h
  int storesize;      // size in LHS
  boolean successfultest; // successful test

  // drawing h and h+ at random,
  // storing them in hop, hplusop

  hl = randnat(hlength); 
  for (int k=0; k<hl-1; k++) 
    {hop[k]=gt0randnat(Xsize);  
       if (hop[k]==1) {hparam[k]=randnat(paramrange);}}

  // left hand side of rule
  s.sinit(); historygenerator(hl,hop,hparam);
  itemtype a=randnat(paramrange); s.push(a); 
  // store resulting state
  storesize = s.size();  // size value on the left hand side

  // right hand side of rule
  s.sinit(); historygenerator(hl,hop,hparam);
  // compare current state with stored state
  successfultest =(storesize==1+s.size());
  if (! successfultest) {nbf++;}
  }

failure rate: 0 out of 10000

#include <iostream>
#include <cassert>
#include “stack.cpp”
#include “rand.cpp”


using namespace std;

typedef int boolean;
typedef int itemtype;

const int Xsize = 5;
const itemtype paramrange=8;  // drawing parameter to push()

// random number generators
int randnat(int rangemax);  int gt0randnat(int rangemax);
/*  State Variables    */
stack s; // test object
int nbtest, nbf; // number of tests, failures
itemtype a, b, c; //  push() parameters

bool storeempty;
itemtype storetop;
int storesize;

int main ()
  {
  /*  initialization  */
  nbf=0; nbtest=0;  // counting the number of tests and failures
  SetSeed (825);    // random number generator 
  a=randnat(paramrange); b=randnat(paramrange);
  c=randnat(paramrange);

  //  first test case:  init.push(a).init.top.  
  //  Init Rule
  nbtest++;
  s.sinit(); s.push(a); s.sinit(); storetop=s.top();
  s.sinit();
  if (!(s.top()==storetop)) {nbf++;}

  //  second test case:  init.push().push().push(a).size.  
  //  Size Rule
  nbtest++;
  s.sinit(); s.push(c); s.push(b); s.push(a); storesize = s.size();
  s.sinit(); s.push(c); s.push(b); 
  if (!(storesize==1+s.size())) {nbf++;}

  //  third test case:  init.push().push(a).push(b).empty.  

  //  Empty Rule
  nbtest++;
  s.sinit(); s.push(c); s.push(a); s.push(b); storeempty=s.empty();
  s.sinit(); s.push(c); s.push(a);
  if (!(!(s.empty()) || storeempty)) {nbf++;}

  //  fourth test case:  init.push().push().push(a).pop.top
  //  Push Pop Rule
  nbtest++;
  s.sinit(); s.push(c); s.push(b); s.push(a); s.pop(); storetop=s.top();
  s.sinit(); s.push(c); s.push(b);
  if (!(s.top()==storetop)) {nbf++;}

  cout << “failure rate: ” << nbf << “ out of ” << nbtest << endl;
  }

failure rate: 0 out of 4.

********************************************************
//  Array based C++ implementation for the stack ADT.
//  file stack.cpp, refers to header file stack.h.
//******************************************************

#include “stack.h”  
   
stack :: stack ()
   {
   };

void stack :: sinit ()
   {sindex =0;};

bool stack :: empty ()  const
   {return (sindex==0);}

void stack :: push (itemtype sitem)
   {sindex++;
     sarray[sindex]=sitem;}

void stack :: pop ()
   {if (sindex>0)
        { // stack is not empty
     sindex--;}
   }

itemtype stack :: top ()
   {int error = -9999;
    if (sindex>0)
         {return sarray[sindex];}
    else
         {return error;}
   }


int stack :: size ()
   {return sindex;}

********************************************************
//  Scalar based C++ implementation for the stack ADT.
//  file stack.cpp, refers to header file stack.h.
//   base is declared as a constant in the header file, =8.
//******************************************************

#include “stack.h”  
#include <math.h>

stack :: stack ()
   {
   };

void stack :: sinit ()
   {n=1;};

bool stack :: empty ()  const
   {return (n==1);}

void stack :: push (itemtype sitem)
   {n = n*base + sitem;}

void stack :: pop ()
   {if (n>1) { // stack is not empty 
           n = n / base;}
   }

itemtype stack :: top ()
   {int error = -9999;
     if (n>1)
       {return n % base;}
    else
       {return error;}
   }

int stack :: size ()
   {return (int) (log(n)/log(base));}

12.4 TESTING BY SYMBOLIC EXECUTION

When we deploy a test driver on some test data and the oracle is satisfied, the only evidence of correct behavior that we have collected pertains to the precise test data on which the candidate program was tested; whether the test driver relies on randomly generated test data, or on targeted, pre-generated test data, the space covered by test data is typically a very small fraction of the domain of the specification. To overcome this limitation, it is possible to simulate the execution of a program without committing to a particular value of the input; to this effect, we represent the input values by symbolic names, rather than actual concrete values and analyze the effect of executing the program on these values, so as to compare them with the requirements imposed by the specification. For all intents and purposes, this is essentially a static verification method, but it is considered as part of the toolbox of the software tester; we refer to this technique as symbolic testing because it consists in effect in testing a program by executing it symbolically (rather than actually) on symbolic data (rather than actual concrete data). Whereas actual program execution produces an actual output for a specific actual input value, symbolic execution produces a symbolic expression of the output as a function of a symbolic representation of the input; this amounts, in effect, to computing the function of the program. In Chapter 5, we had talked about program functions without discussing how these are derived; in this section, we briefly discuss how this can be done in a bottom-up stepwise process, which proceeds inductively on the program structure.

We can think of a program function as mapping inputs (from an input stream, say) onto outputs (stored in an output stream); but very often, it is more interesting and more convenient to think of a program function as mapping initial states to final states. To accommodate these two perspectives without too much complexity overhead, we generally focus on state transformation, but we may sometimes (especially when we discuss I/O operations) assume that we have a default input stream (is) and a default output stream (os) as part of the state space. We consider a simple C-like programming language, and we consider, in turn, its elementary statements and then its compound statements.

Elementary statements include assignment statements and input/output statements (which we denote respectively by read()and write()). We denote by S the space of the program (whose function we are computing), and by s and s′ arbitrary states of the program.

• Assignment Statement. Let x be a variable of some type T, let E be an expression on S that returns a value of type T, and let def(E) be the set of states on which expression E is defined (can be computed). Then
  

  where (respectively ) designates all the variable names in s (respectively s′) other than x.

• Read Statement. Let x be a variable of type T, and let is (the default input stream) be structured as a sequence of T-type values. Then,
  

  where (respectively ) designates all the variable names in s (respectively s′) other than x and is.

• Write Statement. Let x be a variable of type T, and let os be the default output stream of the program. Then,
  
  where (respectively ) designates all the variable names in s (respectively s′) other than os and designates concatenation.

Compound statements include the structured control constructs of imperative programming languages, most notably:

• The Sequence Statement, whose rule is defined as follows:
  

  where · designates the relational product.

• The Conditional Statement, whose rule is defined as follows:
  

  where .

• The Alternative Statement, whose rule is defined as follows:
  
• The Iterative Statement, whose rule is defined as follows:
  

Because the formula of the while rule is difficult to apply in practice, we have a theorem that characterizes such functions.

In order to apply this theorem, we need to derive function W based on our understanding of what the loop does, then check that W verifies the conditions set forth above. We illustrate this theorem with two simple examples.

Let S be defined by variables x and y of type integer and let w be the following loop on S:

w:  while (y!=0) {x=x+1; y=y-1;}.

We consider the following function W:

The first condition of the theorem is satisfied, since the domain of W is the set of states for which y is nonnegative, and that is exactly the set of states for which the loop terminates. As for the next two conditions, we check them briefly below:

= {substitution}

= {pre-restriction}

= {simplification}

= {substitution}

As for the third condition, we write

= {substitution, pre-restriction}

= {relational product}

= {simplification}

= {pre-restriction}

= {substitution}

As a second example, we let S be defined by natural variables n, f, k, and we consider the following loop on space S:

w:  while(k!=n+1) {f=f*k; k=k+1;}.

We let W be the function on S efined by:

The domain of W is the set of states such that , which is precisely the set of states on which the loop terminates. We check in turn the two remaining conditions of the theorem, as follows:

= {substitution}

= {pre-restriction}

= {simplification}

= {substitution}

As for the third condition, we write

= {substitution, pre-restriction}

= {relational product}

= {simplification}

= {pre-restriction}

= {substitution}

12.5 CHAPTER SUMMARY

In this chapter, we gather the artifacts we have collected in previous chapters to develop a test driver, which is responsible for running tests on a candidate software product and delivering a report from these tests. Specifically, we explore the following issues:

• In what sense and to what extent we have latitude in choosing the specification against which we can test a software product (whence the oracle that we derive for the test).
• How we can derive a test driver using a specific oracle (computed from a selected specification) and a specific test generation technique, for simple input/output programs and for software products that have an internal state.
• How we can overcome some of the limitations of software testing by means of symbolic execution, whereby we represent inputs by symbolic names (rather than concrete input values) and we represent outputs by symbolic expressions (rather than concrete output values).

12.6 EXERCISES

• 12.1 Consider the following C++ program:

  void selectionSort ()  //  given an array a of size N
   {indexType i, j, smallest;
    itemType t;
    for (i=N-1; i>0; i--)
     {smallest=0; 
      for (j=1;  j<=i; j++)
       {if (a[j]<a[smallest]) smallest=j;}
     t=a[smallest]; a[smallest]=a[i]; a[i]=t;}
   }
  

  1. Prove the correctness of this program with respect to specification Sort.
  2. Derive an oracle for this program from specification Sort.
  3. Prove the correctness of this program with respect to specification Prm.
  4. Derive an oracle for this program from specification Ord.
  5. Conclude.
• 12.2 Same as Exercise 1, for a Gaussian elimination program, using the specification: .
• 12.3 Consider the sort program of Exercise 1 and the specification Ord.
  1. Derive a test oracle from specification Ord.
  2. Consider the following test set (giving values for N and a), build a set datatype that has the relevant methods (empty, insert, remove), and load the test data therein:

     N	a[]
     1	[6]
     2	[6, 9]
     2	[9, 6]
     8	[32, 28, 24, 20, 16, 12, 8, 4]
     8	[32, 8, 24, 16, 4, 12, 20, 28]

  3. Develop a test driver according to the pattern shown in Section 12.2 for certification testing.
• 12.4 Consider the sort program of Exercise 1 and the specification Ord.
  1. Derive a test oracle from specification Ord.
  2. Consider the following test set (giving values for N and a), build a set datatype that has the relevant methods (empty, insert, remove), and load the test data therein:

     N	a[]
     1	[6]
     2	[6, 9]
     2	[9, 6]
     8	[32, 28, 24, 20, 16, 12, 8, 4]
     8	[32, 8, 24, 16, 4, 12, 20, 28]

  3. Develop a test driver according to the pattern shown in Section 12.2 for a test intended to record the outcome of each execution for subsequent analysis.
• 12.5 Consider the sort program of Exercise 1 and the specification Ord.
  1. Derive a test oracle from specification Ord.
  2. Alter the program in such a way as to make it incorrect.
  3. Develop a random test data generator that produces random values for N and a.
  4. Use the test data generator and the test oracle to develop a test driver that iterates until the first failure.
  5. How many executions did it take to cause the first failure?
• 12.6 In Section 12.3.1, we have shown the code for the push-pop rule. Taking inspiration from this code, write code for the init rule; run the resulting test driver on a candidate implementation of the stack.
• 12.7 In Section 12.3.1, we have shown the code for the push-pop rule. Taking inspiration from this code, write code for the init-pop rule; run the resulting test driver on a candidate implementation of the stack.
• 12.8 In Section 12.3.1, we have shown the code for the push-pop rule. Taking inspiration from this code, write code for the VX rules; run the resulting test driver on a candidate implementation of the stack.
• 12.9 In Section 12.3.1, we have shown the code for the size rule. Taking inspiration from this code, write code for the empty rule; run the resulting test driver on a candidate implementation of the stack.
• 12.10 In Section 12.3.1, we have shown the code for the size rule. Taking inspiration from this code, write code for the top rule; run the resulting test driver on a candidate implementation of the stack.
• 12.11 Consider the test data shown in the following table for the stack ADT. Select two test cases from each of the tables below and develop a test driver accordingly, following the pattern of Section 12.3.2 Deploy your test driver on the stack implementations given in Section 12.3.3.
  
  

  		(X */E)
  		init	init.push(_)	init.push(_). push(_)	init.push(_). push(_). push(_)
  VX	top	init.top	init.push(a).top	init.push(_).push(a).top	init.push(_).push(_).push(a).top
  	size	init.size	init.push(a).size	init.push(_).push(a).size	init.push(_).push(_).push(a).size
  	empty	init.empty	init.push(a).empty	init.push(_).push(a).empty	init.push(_).push(_).push(a).empty

  AX	VX	(X */E)
  				init	init.push(_)	init.push(_). push(_)	init.push(_). push(_). push(_)
  init	top	init.init.top	init.push(a).init.top	init.push(_).push(a).init.top	init.push(_).push(_).push(a).init.top
  	size	init.init.size	init.push(a).init.size	init.push(_).push(a).init.size	init.push(_).push(_).push(a).init.size
  	empty	init.init.empty	init.push(a).init.empty	init.push(_).push(a).init.empty	init.push(_).push(_).push(a).init.empty
  push	top	init.push(b).top	init.push(a).push(b).top	init.push(_).push(a).push(b).top	init.push(_).push(_).push(a).push(b).top
  	size	init. push(b).size	init.push(a).push(b).size	init.push(_).push(a).push(b).size	init.push(_).push(_).push(a).push(b).size
  	empty	init. push(b).empty	init.push(a).push(b).empty	init.push(_).push(a).push(b).empty	init.push(_).push(_).push(a).push(b).empty
  pop	top	init.pop.top	init.push(a).pop.top	init.push(_).push(a).pop.top	init.push(_).push(_).push(a).pop.top
  	size	init.pop.size	init.push(a).pop.size	init.push(_).push(a).pop.size	init.push(_).push(_).push(a).pop.size
  	empty	init.pop.empty	init.push(a).pop.empty	init.push(_).push(a).pop.empty	init.push(_).push(_).push(a).pop.empty

• 12.12 Use the technique discussed in Section 12.3.1 to write a test driver for a queue implementation of the queue ADT. Write an array-based queue implementation and a scalar based queue implementation and deploy the test driver to test them.
• 12.13 Use the technique discussed in Section 12.3.2 to write a test driver for a queue implementation of the queue ADT. Write an array-based queue implementation and a scalar-based queue implementation and deploy the test driver to test them.
• 12.14 Let x and y be integer variables and let MaxInt and MinInt be (respectively) the largest (smallest) integer that can be represented in a given programming language. Compute (by symbolic execution) the function of the following statements.
  1. x=x+1;
  2. y=y-1;
  3. x=x+1; x=x-1;
  4. x=x-1; x=x+1;
  5. x=x+1; y=y-1;
• 12.15 Let S be the space defined by variables x, y, z of type integer, and let w be the following while loop:

  w: while (y!=0) {y=y-1; z=z+x;}
  

  And let W be the following function on S:

  

  Prove that W is the function of w.

• 12.16 Let S be the space defined by integer variables x, y and z, and let w be the following while loop:

  
  w: while (y!=0)
        {if (y%2==) {y=y/2; x=2*x;} else {y=y-1; z=z+x;}}
  

    and let W be the following function on S:

  

  Prove that W is the function of w.

• 12.17 Let S be the space defined by integer variables x, y and z, and let w be the following while loop:

  w: while (y>0)
        {if (y%2==) {y=y/2; x=2*x;} else {y=y-1; z=z+x;}}

  and let W be the following function on S:

  

  Prove that W is the function of w.

12.7 BIBLIOGRAPHIC NOTES

The theorem that captures the function of a program is due to H.D. Mills (1972). Because it requires a great deal of creativity (to derive a candidate function W), practitioners often replace it with an approximation of the loop function, whereby they do not compute the function of the loop for an arbitrary number of iterations (which is what this theorem does), but rather limit the number of iterations to a specific value and evaluate the function of the loop under these conditions; this produces an approximation of the program function, but still delivers much more information than a single execution of the program over a single input value.