Assignment 1:
Testing and Debugging
Due Date: Wednesday, January 21, 1998 -- 10:30 am
Save paper. Do not blindly print files. There are a number of files included with this assignment that you should not print. Also you should consider using the enscript command to print to pages per page. The first example below paginates and prints the files adbook.tu driver.dem and tester.dem using two logical pages per physical page. Note that the pr command is useful for avoiding blank pages in the enscript output. The second example prints the file named document using two logical pages per physical page.
pr -f adbook.tu driver.dem tester.dem | enscript -2rG
enscript -2rG document
For more information on the pr and enscript commands see:
man pr
man enscript
NOTE: A copy of the cover page cover1.ps MUST be the first page of your document. It is a postscript file (basically postscript is a page description language for printers) and can be viewed and printed on the systems in ARIEL. It is unlikely that you'll be able to view or print this on your system at home unless you've installed special software for dealing with postscript. 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.
ALSO NOTE: You can hand in no more than 28 single spaced logical pages total. Any assignments using more than 28 single spaced logical pages will be assigned a grade of F.
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.
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 for the AddressBook ADT.
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 AddressBook ADT (in a file called adbook.tu) that provides stubs for each of the operations supported by the AddressBook (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.
An AddressBook is an abstract data type that supports the following operations:
A detailed specification of the operations supported by the AddressBook abstract data type can be found on pages 121-122 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. Note that you should also add Initialize and Finalize (which should be supported by all module implementations).
This stub implementation of the AddressBook ADT will be used in developing and testing higher level driver programs in Tasks 2 and 3.
TO HAND IN: a) adbook.tu
A simple demonstration program adbook.dem can be found in the text on paged 125-128. (it works with adbookar.tu). It is limited in what it does. In addition it may not adequately test all functions. Write a program (in a file called driver.dem) that will call each and every operation supported by the AddressBook 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 procedures 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. This can still be considered top down testing because we are actually implementing the main program which uses the lower layer AddressBook module.
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 AddressBook (adbook.tu) that you implemented in Task 1. 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 the AddressBook 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.
e - Enter a name and associated address
(prompt the user for the name and address to add to the book)
d - Delete a specified name
(prompt the user for the name then delete that name and address)
q - quit
c - change the address associated with a specified name
(prompt the user for the name and then the new address)
i - initialize the address book
f - finalize the address book
l - lookup a name in the address book
(prompt the user for a name to lookup)
p - print the contents of the address book
S - save the contents of the address book to a file
(only one file is used adbook.dat)
L - load the contents of the address book from a file
(only one file is used adbook.dat)
? - print list of commands
h - print list of commands
Remember to call Initialize before the AddressBook is used and Finalize when finished with the AddressBook. The driver program should only load or store the data to/from the data file if the load or store operations are used.
You can find more details and a specification for the AddressBook abstract data type on pages 121-122 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 AddressBook 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 adbook.tu (the AddressBook 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 AddressBook ADT.)
Also note that too much testing output clearly makes it more difficult to tell if the program is working correctly or not. You must use your judgment to use the minimal amount of testing required to convincingly show that the code being tested does or does not work correctly.
You should also 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)
Now that you are convinced that your driver.dem program works correctly modify it to import the AddressBook implementation from another file (in this case adbook1.tu).
Note that adbook1.tu and adbook2.tu have been intentionally modified so they will be difficult for you to read and understand. (You are not required to test adbook2.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 AddressBook 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 an AddressBook 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 address book.
First provide a test plan of precisely how and what you are testing, what input is used to perform the 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 adbook1.tu .
TO HAND IN: a) Test plan and results, b) output from your interactive test session testing adbook1.tu
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. The assumption is that the higher level will be implemented correctly and has been tested using Top Down testing. In this task, the lowest level of subprograms are the provided for you in the form of two different implementations of an AddressBook ADT. These are provided in files named adbook1.tu and adbook2.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 its 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 AddressBook. This program will serve no purpose other than testing if the implementation of the AddressBook ADT is correct. In this case, if the AddressBook 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 AddressBook ADT is clearly implemented correctly. In other words, this test program could be used reliably by someone who is implementing (or has implemented) an AddressBook ADT, for the purposes of testing that module. If there is something wrong with the AddressBook 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). The idea is that someone who is implementing the AddressBook ADT should be able to rely on tester.dem to test the ADT. If the tester.dem program fails due to an assertion the implementor of the ADT should fix the bug and rerun the tests. This would continue until no errors are found by the test program. Additionally, this testing program should be rerun any time any modifications are made to the ADT, to ensure that no bugs have been introduced.
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 is less than or equal to 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 AddressBook ADT is correct if the test succeeds, use it to test the implementation of the AddressBook ADT provided in "adbook1.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 AddressBook ADT provided in adbook2.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 adbook1.tu, c) output of running tester.dem to test adbook2.tu d) Description of problems, bugs, difference in implementations.
The file adbookar.tu implements an AddressBook module using an array. Copy this file to a file named debug.tu and modify 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 Lookup: Searching for ", name
end if
In this way debugging statements are added at the time of initial implementation and left in the program forever. Before shipping the product they can simply be turned off. If bugs are reported, debugging can be easily turned back on to help find and fix bugs.
Also add a new operation to the AddressBook ADT called Reverse, that when called will reverse the contents of the entire address book. Be sure to include useful debugging statements in this new routine. Modify driver.dem to call the AddressBook "Reverse" operation using the letter command 'r', for reverse.
Modify your interactive test driver (driver.dem) so that it uses the debug.tu implementation of the AddressBook 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 AddressBook 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 and the new Reverse operation, 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.
Write a very brief description of how you will apply what you've been doing and learning in this assignment to future assignments. Also explain the difference between the two programs driver.dem and tester.dem and when it would be appropriate to use each program.
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? What about grocery stores? 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?