Lecture 21, Discussion and Miscellaney
Part of
the notes for CS:4980:1
|
This class was structured around 5 brief student presentations giving status reports on the progress being made on the 5 group projects. During those discussions, some issues came up that led to brief micro-lectures that follow:
Inserting statements into code to produce debug output is a powerful debugging tool, but it has its weaknesses. Specifically, debug output that serves the needs of one developer working on one part of a large project can interfere with the work of another developer on another part of the project.
The first need this brings up is the need to easily strip the debug output out of a piece of code. If you just embed normal output instructions in the code to output your debug output, this makes stripping the debugging out difficult because some of the normal output instructions are part of the real program while others are there only for debugging.
So, one thing your group should agree on is a standard for flagging debug output. For example, every line that is there for debugging purposes should contain the text DEBUG in upper case. This lets someone strip out the debug code very quickly when it is time to strip it out. Consider these examples for three different ways of meeting this requirement:
/*DEBUG*/ putstr( "reached point a" );
putstr( "DEBUG reached point a" );
putstr( "reached point a" ); // DEBUG
One useful idea is to use a C/C++ define to handle debug output, for example:
#define DEBUG(s) putstr(s)
This lets you write code like this:
DEGUG( "reached point a" );
You could even define your macro like this:
#define DEBUG(s) s
This lets you write code like this:
DEGUG( putstr( "reached point a" ) );
DEGUG( int bugcount = 0 );
DEGUG( bugcount = bugcount + 1 ) );
This is not enough. Suppose two people are working on two different unrelated parts of the program, and each wants to use debug output, but each wants to suppress the debug output that the other person is working with. There are several ways to do this:
If you never commit code with debug output, other members of the group will never see your debug output, but you lose the benefit of being able to freely use Subversion. Each time you commit changes, you need to first strip out your debugging, and then you need to put it back in before you continue work on a persistent bug. This is awkward.
If you want to make changes that you don't commit, for example, stripping out all the debug code from some part of the program, do so freely, and then do not commit those changes.
pi@raspberrypi:cs4980/groupF $ svn update pi@raspberrypi:cs4980/groupF $ vi Hiscode.cpp -- delete the debug output pi@raspberrypi:cs4980/groupF $ vi Myparts.cpp -- play with my code pi@raspberrypi:cs4980/groupF $ make pi@raspberrypi:cs4980/groupF $ vi Myparts.cpp -- play with my code pi@raspberrypi:cs4980/groupF $ make pi@raspberrypi:cs4980/groupF $ kestrel testfile.kes pi@raspberrypi:cs4980/groupF $ svn revert Hiscode.cpp -- undo changes pi@raspberrypi:cs4980/groupF $ svn commit
The svn revert x command is equivalent to doing rm x followed by svn update x.
This works only if your debug output is in a different file from their debug output. It puts the burden on you to strip out their debug output when it gets in your way.
Consider a group where the members have the initials AB, CD and EF. If each group member has a their own file called DEBUG.h, where this file is never included in the Subversion archive, you can do some clever things. In any code where debug output is needed, include DEBUG.h.
If user CD wants to see some particular debug output, user CD writes this:
CDDEBUG( printf( "reached point a with x=%d\n", x ) );
If user AB needs some other debug output, user AB could write:
ABDEBUG( putchar( 'x' ) );
These completely unrelated debug outputs can coexist, even in the same source file. User AB will only see the effects of ABDEBUG if user AB has this DEBUG.h file:
#define ABDEBUG(s) s #define CDDEBUG(s) #define EFDEBUG(s)
Similarly, user CD will only see the effects of CDDEBUG if user AB has this DEBUG.h file:
#define ABDEBUG(s) #define CDDEBUG(s) s #define EFDEBUG(s)
You can see why the DEBUG.h file must not be part of the Subversion archive. Each user's copy is different. It must be there, in the development directory, but it must not be shared.
When it comes time to clean up the program, all the debugging code can be located with a single shell command:
pi@raspberrypi:cs4980/groupF $ grep DEBUG *.c *.h
If user EF wants to find just instances of EFDEBUG, then EF can type this command:
pi@raspberrypi:cs4980/groupF $ grep EFDEBUG *.c *.h
If you stick closely to the convention that all debuging code is on its own line and only debugging lines contain the text DEBUG and the text DEBUG occurs nowhere else, you can strip out all the debugging code from a file with one fast and simple command in the vi text editor:
:1,$g/DEBUG/.d
This globally searches the file for lines containing DEBUG and then deletes all lines that contained that string.
Fuzz testing is an extremely stupid yet useful debugging technique that is not as widely known as it should be. When people debug programs, their emphasis is usually on testing to see if the program operates correctly for correct input. Fuzz testing does the opposite, it asks how the program responds to random junk input.
Consider this little program written in C:
/* fuzz.c -- outputs an infinite stream of junk */
#include <stdio.h>
#include <stdlib.h>
int main() {
for (;;) { /* an infinite loop */
putchar( random() & 0xFF );
}
}
Now, suppose you wanted to fuzz test your Kestrel compiler. Try this:
pi@raspberrypi:cs4980/groupF $ ./fuzz | ./kestrel
This throws an infinite stream of effectively random text into your kestrel compiler. The compiler passes the test if it outputs error messages and exits in a sensible way, but if it terminates with an unhandled exception or some kind of system error, it fails.
Fuzz testing came to prominence when a group used it to compare the different commercial and open source implementations of the Unix operating system. AT&T Unix, IBM's AIX, Sun's Solaris, HP's HPUX, Linux, FreeBSD, etc. What they found when they fuzz tested the various shell utilities that allowed processing data from standard input was that the open-source versions were generally better, and that the more code from the original AT&T Unix had been rewritten, the better it survived.
This is not surprising. The original AT&T Unix code was the end product of a long evolution, the accretion of patches on top of patches as bugs were fixed, and the accretion of feature on feature. Reverse engineering this code to produce a new clean implementation created much more durable code.
Fuzz testing can be used for any part of a program that reads input in any form. Fuzz testers can be written that produce files of output in the form required by a program. Fuzz testers can be written to create random streams of mouse clicks and keypresses to test GUI-based code. For a compiler, a fuzz tester can be written that produces syntactically valid but semantically nonsensical code.
The grammar tools we have include a program that is almost good enough for Fuzz testing, gsample. This takes a BNF grammar as input and produces a random string of output from that grammar.
A serious weakness of this program is that, wherever there are alternatives in the grammar, it takes them with equal likelihood. Consider this example:
<a> ::= <b> | <c> | <d>
In this case, <b>, <c> and <d> will occur with equal frequency in the output. If you want to bias the selection to make some alternative more common than another, you can do it as follows:
<a> ::= <b> | <c> | <c> | <d> | <d> | <d>
Now, <c> is will be twice as common as <b> and <d> is will be three times as common as <b>.
If you run gsample on the current kestrel grammar, the equal distribution of probabilities leads to two serious symptoms: Half the time, it just produces <end of file> as its output, and when it does not do this, it tends to get lost in deep recursions that cause the stack to overflow. With some tuning of the BNF grammar, it is possible to make it tend to produce programs that are intermediate in length.
There are some other problems. If you run gsample on the Kestrel grammar, you get output that looks like this: as follows:
<identifier> ":" <identifier> ";" <end of file>
This is not particularly useful as compiler input. To use this for compiler input, you might need to add some production rules, for example, try adding:
<identifier> ::= <identifier> <letter> | <letter> <letter> ::= a | b | c | d | e | f | g | h | i | j | k
Now, you have given gsample rules for creating random identifiers, althought the above rules fall short of testing Kestrel's full range of legal identifiers, and it makes long identifiers vanishingly uncommon. To make long identifiers more common, you'd do this:
<identifier> ::= <identifier> <letter> | <letter>
| <identifier> <letter>
| <identifier> <letter>
The second problem we need to solve is eliminating the quotation marks from the grammar. To do this, we make some global changes to the grammar wherever quotation marks occur. For example, consider this quote from the EBNF grammar:
<declaration> ::= <identifier> ":" [ "private" | "restricted" ] <declarator>
We need to rewrite this as:
<declaration> ::= <identifier> : [ private | restricted ] <declarator>
The rules that the grammar tools use for reading BNF input files are flexible enough that it can handle this, except in the special cases of the symbols | and braces or parentheses. Solving the quotation mark problem without creating a brace and parenthesis problem is tricky.
The solution to this problem involves a bit of digging into how the grammar tools distinguish terminal and nonterminal symbols. It turns out that the tools do understand quotation marks and angle brackets in order to allow blanks in bracketed or quoted symbols, but otherwise, any sequence of nonblanks separated by blanks is interpreted as a symbol name. Terminal symbols are merely symbol names that do not occur on the lefthand side of rules. If we did not have to worry about the vertical bar symbol used to delimit BNF alternatives, we could simply delete all the quotation marks from the grammar.
To deal with BNF use of vertical bar and EBNF use of parentheses, brackets and braces, we need to do a bit of trickery, using an alternative quotation mark scheme. There are some punctuation marks that have no legal use in a Kestrel program (except within quoted strings). Underscore (_) is one of them. If we simply replace all the quotation marks in our grammar with underscore, the grammar tools will see "abc" replaced with _abc_ and "|" replaced with _|_. These will still be read as single terminal symbols. The following global substitution command will make this change to the grammar in the VI editor:
:1,$g/"/s//_/g -- replace all double quotes with underscores
If we use this modified grammar to drive the gsample utility, there will be lots of underscores in the result, but no quotation marks. Now, we simply need to strip out the underscores from the output. There is a stream editor called SED in the Unix/Linux environmet that can do this. A grammatically correct fuzz test of a kestrel compiler would look like this:
$ ./gsample kestrel.bnf | sed -e "s/_//g" | kestrel
A student reported that I made a mistake in designing Kestrel. He's right. Specifically, in declaraing an enumeration, there Kestrel does not, as defined at this point, require a keyword. This creates a problem. How can a compiler with one lexeme of lookahead distinguish between these two cases:
color: (red, blue, green); range: (a+1)/2 .. b;
Here, color is defined as an enumeration, while range is defined as a subrange. The obvious solution to this is to do what C and C++ do and introduce an enum keyword:
color: enum (red, blue, green); range: (a+1)/2 .. b;
So, we'll do that. It would have been nice if that could be avoided, but it's the easy way out.