Assignment 1:
Testing and Debugging
Due Date: Wednesday, January 22

Be sure to Reload this file periodically, because it may not be in its final form.

Save paper. Do not blindly print files. There are a number of files included with this assignment that you should not print.

Purpose:

NOTE: A copy of the cover page cover1.ps MUST be the first page of your document. (It can also be found in the a1 directory). If it does not appear as the VERY FIRST page of your document you will lose one full letter grade (e.g., A becomes B, C+ becomes D+, and D or lower becomes F). This means: NO BINDERS OR ENVELOPES.

You may work with a partner if you like. In this case you will hand in one jointly authored report. Each author will receive the same grade.

Readings:

Alternate Sources:

Overall Assignment

Task 1: Top Down Testing (Writing Stubs)

Top down testing starts with the main program to ensure that the upper level design and implementation is correct. In doing so it uses subprograms (called stubs or skeletons) to implement the lower level operations as place holders until the actual subprograms are completed. You'll begin by writing the stubs.

The implementation of the lower level module may be postponed until later or it may be done, in parallel, by another programmer. In this part of the assignment you are to write a skeleton Stack ADT (in a file called stack.tu) that provides stubs for each of the operations supported by the Stack (they are listed below). The stubs do not actually perform the operations, they just print a message saying which function or procedure was called and the parameters with which it was called. In the case of a function the returned value is usually a dummy value.

A Stack is an abstract data type that supports the following operations:

A detailed specification of the operations supported by the Stack abstract data type can be found on page 149 of the course text. Be sure that your implementation supports all of the operations and uses exactly the same names, parameters and return values as those specified in the text.

Your implementation must use elements of type "elementType". This will be used to control what type of elements can be used in the Stack. 

For example:
    type elementType : string     % if the elements used are strings
    type elementType : int        % if the elements used are integers

For now have your programs define elementType as an int. This stub implementation of the Stack ADT will be used in developing and testing higher level driver programs in Tasks 2 and 3.

TO HAND IN: a) stack.tu

Task 2: Top Down Testing (Writing an Interactive Test Driver)

A simple demonstration program can be found in stack.dem (it works with stackar.tu ). It is very limited in what it does and it does not adequately test all functions. Write a program (in a file called driver.dem) that will call each and every operation supported by the Stack ADT. It should read input from the keyboard and execute commands according to the input specified.

This test driver is designed to be used by someone to test the modules being called. The user must know which calls are supported and what functions each call should perform. It is then up to the user to ensure that the proper actions are taken.

Remember that at this stage we are designing and implementing the test driver (driver.dem). In order to ease this task we'll use the stub implementation of the Stack (stack.tu). The reason for using the stubs is that because of their simplicity they are not likely to have bugs themselves. Later you will use the test driver you develop to test two different implementations of Stack ADT and you should be able to do this without having to fix any bugs in your test driver.

The following characters are used to specify which command will be called. 

     P - Push
     p - pop
     q - quit
     e - is empty
     f - is full
     t - inspect top
     ? - print list of commands
     h - print list of commands

The operations that each of these commands are to perform are:

Remember to call Initialize before the Stack is used and Finalize when finished with the Stack.

You can find more details and a specification for the Stack abstract data type on page 149 of the course text.

Note that it is possible to use an input file with this program. See the file driver.in for an example of test input. (Note that driver.in is a small and incomplete example.) You should be able to run your driver program which uses your stub implementation of the Stack ADT using the file driver.in as input as follows: 

toot driver.dem < driver.in > driver.out

This will run the driver.dem program, using the contents of driver.in as input and place the output in driver.out.

Run an interactive test to show that your implementation of both stack.tu (the Stack stubs) and driver.dem (the interactive test driver) work correctly. Capture the output of this interactive session using the "script" command and hand in the output of this interactive session.

Create your own input file (called myinput.in) that is designed to exercise the different commands supported by driver.dem. (Remember driver.in is a small and incomplete example, your input file must clearly and precisely fully test the Stack ADT.) You should demonstrate that your program is robust by also using some commands that are not supported by the program (and your driver should not crash). Run your driver.dem using your newly created input file, capture the output in a file, print and hand in that file.

TO HAND IN: a) driver.dem, b) myinput.in, c) output of script and d) output from myinput.in (myinput.out)

Task 3: Testing Stack ADT Implementation

Now that you are convinced that your driver.dem program works correctly modify it to import the Stack implementation from another file (in this case stack1.tu). Note that stack1.tu and stack2.tu have been intentionally modified so they will be difficult for you to read and understand. (You are not required to test stack2.tu at this time, It will be tested in a later task.) Since you are unable to read and understand these files you will essentially be performing black box testing whenever you test their implementations. Black box testing is performed when you have only the specification of how a piece of software should behave without actually being able to see how the software is implemented (in this case it might be more like grey box testing because you can see the code but hopefully it is too difficult to understand).

One of the implementations of the Stack can only hold a limited number of elements. The other is limited only by the amount of virtual memory in the computer being used. You should be careful to ensure that your tests don't require large amounts of memory (by creating a Stack with large numbers of elements). Think about how to demonstrate that the implementation does or does not work without adding too many elements to the stack.

First provide a test plan of precisely how and what you are testing, what input is used to test, what output is expected and whether or not the output produced matches the output expected.

Then capture an interactive session using "script" where you follow the test plan you've described to fully test the implementation stack1.tu .

TO HAND IN: a) Test plan and results, b) output from your interactive test session testing stack1.tu

Task 4: Bottom Up Testing (Writing a Test Driver)

Bottom up testing involves writing the lowest level of subprograms first and then using test drivers to test those subprograms. That is, you work up to higher levels. In this case, the lowest level of subprograms are the provided for you in the form of two different implementations of a Stack ADT. These are provided in files named stack1.tu and stack2.tu .

You are required to implement a test driver that requires no user intervention (in a file called tester.dem) and assumes that the lower level operations are implemented and are correct. This program should run on it's own (it requires NO user input) and should rely heavily on the use of the "assert" statement to detect errors in the implementation of the Stack. This program will serve no purpose other than testing if the implementation of the Stack ADT is correct. In this case, if the Stack ADT being tested works correctly only the words "Test Succeeds" should be printed. The program should demonstrate that if the words "Test Succeeds" are printed then the Stack ADT is clearly implemented correctly. In other words, this test program could be used reliably by someone who is implementing (or has implemented) a Stack ADT, for the purposes of testing that module. If there is something wrong with the Stack ADT then a message should be produced as a result of an assertion failing. It is perfectly acceptable to have the program fail due to the first assertion (that is not all errors have to be detected, only the first). For this test ANY other output generated by the test program is unacceptable!

One small and incomplete example of a program that might test a function that returns a string representation of pi to N decimal places (where N <=5) might be tested as follows: 

assert(pi(1) = "3.1")
assert(pi(2) = "3.14")
assert(pi(3) = "3.141")
assert(pi(4) = "3.1415")
assert(pi(5) = "3.14159")
put "Test Succeeds"

Clearly the assertion will fail if the correct result is not returned in each of the tests performed. The words "Test Succeeds" can only be printed if all of the preceding assertions are correct and therefore, the implementation of the function "pi" is correct as defined. You should use assertions in a similar fashion in your test program (tester.dem).

Once you have implemented a "tester.dem" that you believe demonstrates that the implementation of the Stack ADT is correct if the test succeeds use it to test the implementation of the Stack ADT provided in "stack1.tu" (and just tested using the interactive test driver). Use the "script" command to show the execution of this test.

Then use the same test program to test the implementation of the Stack ADT provided in stack2.tu . Use the "script" command to show the execution of this test.

Describe any problems, bugs and/or difference between these two implementations that you have found by running your test program on these two different implementations.

TO HAND IN: a) tester.dem b) output of running tester.dem to test stack1.tu, c) output of running tester.dem to test stack2.tu d) Description of problems, bugs, difference in implementations.

Task 5: Using Debugging Statements

The file stackar.tu implements a Stack ADT using an array. Copy this file to a file named debug.tu and modify debug.tu so that the stack can be used to store integers rather than strings. Also modify the implementation in file debug.tu so that it contains a number of useful debugging statements that can easily be turned on and off. Define a boolean const "DEBUG". When DEBUG := true the debugging statements will be executed and when DEBUG := false the debugging statements will not be executed. For example: 

if DEBUG then
    put "In function Push: Pushing ", element, " top now = ", top
end if
Also add a new operation to the Stack ADT called Show, that when called will print the contents of the entire stack (which is also useful for debugging purposes). Modify driver.dem to call the Stack "Show" operation using the letter command 's', for show (Print is a reserved word and can not be used.)

Modify your interactive test driver (driver.dem) so that it uses the debug.tu implementation of the Stack ADT. With the added debugging features turned on (in debug.tu) execute an interactive test that demonstrates that your implementation is correct and that the debugging statements produce output that would be helpful in understanding how the program is executing and in finding bugs.

Now run modify tester.dem so that it uses the debug.tu implementation of the Stack ADT and execute this test to test debug.tu (with the debugging statements turned on).

Now modify debug.tu so that it does not produce the debugging output and execute tester.dem.

TO HAND IN: a) modified debug.tu containing debugging statements, b) script output using the modified driver.dem with debugging turned on, c) output using tester.dem and debug.tu with debugging turned on, d) output using tester.dem and debug.tu with debugging turned off

DO NOT HAND IN: modified driver.dem.

Information and Privacy:

To think about, but not to hand in.

The advent of computers has meant that it is has become increasingly easy to keep track of vast amounts of information about people. This information can be used to develop sophisticated consumer profiles, allowing companies to directly market to people who are likely to be interested in their products. Arguably, this would allow companies to more effectively target their advertising, reducing their costs, ultimately reducing the costs of the company's products. Do you believe it is reasonable for credit card companies to sell this information to other companies, or would it be a violation of privacy? Do you think people are appropriately informed that this information is being collected and sold? The Ontario government collects and sells information from driver's licenses. Do you think this is reasonable?