Departments

We Have Mail

Dear Mr. Plauger,

I realize that you may be tiring of this subject, but I found myself intrigued by the problem posed first by Brian Tagg (Letters CUJ, April 1995) and then taken up again by Richard Howells (Letters CUJ, August 1995). The original example was as follows:

fgets(string, MAXLEN, stdin);
while (string[0] == '\n') {
   puts("Entering a blank line won't cut it.\n");
   fgets(string, MAXLEN, stdin);
   }
The problem lies in the repetition of the call to fgets. The repetition becomes a serious problem as the code undergoes maintenance. (You can see this if you add error-checking code after each fgets call, and perhaps an additional processing step.) Everything has to be repeated, and it is (unfortunately) all too easy to forget to replicate one of the changes.

The presented code is, of course, a prototype of a much more general situation. Typically, this involves carrying out a single action, with the requirement that the action must succeed, along with some steps to take to prepare for repeating the action. This calls for a loop with an exit in the middle, instead of at the top (while) or the bottom (do-while). So, here's my suggestion to capture the paradigm:

while (1) {
   perform_action();
   if (action_succeeds())
      break;
   prepare_to_repeat_action();
   }
I can't think of a better way to capture the idea of "n-and-a-half" loops. This solution is highly structured, providing a single entry and a single exit for this block of code. It is easy to maintain, since no code is duplicated. The while (1) tells you that you'll need to look carefully for the exit from the loop. The only potential danger that I foresee in maintenance is the possibility that someone will decide to add alternative exit points to the loop under some circumstances, thus destroying the loop invariant. Some circumstances remain beyond our control...

Thanks for listening, and thanks for continuing to provide a magazine that provokes thought.

Kevin R. Coombes
<krc@ math.umd.edu>

I read Richard Howells letter (CUJ August 1995) about the fgets problem and I'm not quite sure where's the problem :-)

Is it a feature that there is no puts in front of the first fgets? This looks not realistic to me. So if it's no feature, my solution would be:

do {
   puts("...");
   fgets(string, MAXLEN, stdin);
   /* error check */
   } while (string[0] != '\n');
If it's a feature another possible solution could be:

first = true;
do {
   if (!first) {
      puts("...");
      }
   else {
      first = true;
      }
   fgets(string, MAXLEN, stdin);
   /* error check */
} while (string[0] != '\n')
Well, not very elegant — but no duplicated code. Excuse me if I didn't get the point :-)

Stefan Braun
(100343.3266 @compuserve.com)

Dear Mr. Plauger,

Here's another approach to solving the problem described by Brian Tagg (Letters CUJ, April 1995). The problem is the repetition in constructs like this:

fgets(string, MAXLEN, stdin);
while (string[0] == '\n') {
   puts("Entering a blank line won't cut it.\n");
   fgets(string, MAXLEN, stdin);
   }
Tagg suggests eliminating the repetition with a clever use of the comma operator:

while (fgets(string,MAXLEN,stdin), string[0] == '\n')
   puts("Entering a blank line won't cut it.\n");
Richard Howells (Letters CUJ, August 1995) suggests solving the problem with a Common-Action Tail:

cat_01: fgets(string,MAXLEN,stdin);
while ( string[0] == '\n' ) {
   puts("Entering a blank line won't cut it.\n");
   goto cat_01;
   }
The basis of my solution is the idea that the while and do-while constructs of C are nothing more than syntactically distinct special cases of a more general view of loop control. A loop is simply a block of code, or group of statements, that is executed some number of times under control of some test condition. For instance, consider the following pseudo-code.

LOOP {
   WHILE (expression);
      statements
      more statements
}
In conventional C this would be expressed as

while (expression) {
   statements
   more statements
   }
The statements inside the loop are executed zero or more times, as long as the tested expression evaluates to a nonzero value. Either the LOOP-WHILE or the while form make this pretty clear, even to a programmer who has never seen either form.

But now consider what amounts to a fairly minor change in the program's requirements: how must we change the code to insure that the block of code inside the loop is executed at least once? Conceptually we just want to move the test from the top of the loop to the bottom. Our pseudo-code form would look like this.

LOOP {
   statements
   more statements
   WHILE (expression);
   }
In conventional C, however, this slight change in intent requires a rather major change in syntax.

do {
   statements
   more statements
   } while (expression);
In this case the LOOP-WHILE form presents a much clearer picture of the programmer's intent, as well as making it much easier to modify the code.

Now if we are willing to withstand the criticism of all those who hold that it isn't a loop if you exit it from someplace other than the top or bottom, we can also do things like this:

LOOP {
   statements
   WHILE (expression);
   more statements
   }
In particular, we can solve Tagg's problem this way:

LOOP {
   fgets(string,MAXLEN,stdin);
   WHILE ( string[0] =='\n' );
   puts("Entering a blank line won't cut it.\n");
   }
Consider now these simple macros:

#define LOOP whilc (1)
#define WHILE(c) if (!(c)) break
With these macros we can write loops in the style of the idealized pseudo-code above. We can now write a completely general loop with the exit test (or tests) at the top, the bottom, or anywhere in between.

LOOP {
   WHILE (someExpression);
      .
      statements
      .
   WHILE (someOtherExpression);
      .
   more statements
      .
   WHILE (stillAnotherExpression);
      .
   still more statements
      .
   WHILE (yetOneMoreExpression);
   }
It is interesting to note that the macros work their magic by simply sprinkling a little syntactic sugar on C's most inelegant, but also most general, control statement, the break statement! We could, of course, eliminate the macros and solve the problem with:

while (1) {
   fgets(string,MAXLEN,stdin);
   if (string[0] != '\n')
          break;
   puts("Entering a blank line won't cut it.\n");
   }
which does exactly the same thing (and probably generates very nearly the same code as Howells' Common Action Tail), but seems to fall short in expressing the programmer's intent.

The LOOP/WHILE macros seem to be the kind of idea that people are very passionate about; they ever love 'em or hate 'em.

I first came across the concept of reducing all loop operations to one generalized model in DASL, Datapoint's Advanced Systems Language, created in 1981 by Gene Hughes.

John A. Murphy
murf@perftech.com

There's certainly more than one way to skin this particular cat. I'm personally happy with a broad assortment of solutions, so long as the emphasis remains on readability. — pjp

Dear Mr. Plauger,

One of my greatest pleasures is reading the mail in The C/C++ Users Journal. That includes your responses which I think are a good example of knowledge and dry humor.

There are a few authors of computer literature who I think are especially valuable to read because of the unusual way they address computional problems (people like Jon Bentley and the old AT&T school, and of course you).

My only problem is that I feel like in the good old days when people still listened to drama on radio (yes, I remember these days): I have a certain imagination how these people look but I just do not know for sure. Now here it comes: Would it not be nice to always (or at least sometimes) publish a little picture of the authors?

Thank you for a very fine magazine.

Yours sincerely,

Detlef Engelbrecht
detlef@isys.net Hamburg, Germany

Pictures are an idea we've toyed with from time to time, even though our Managing Editor Marc Briand would begrudge the loss of hardwon editorial space. I'm afraid you would be a bit disappointed in some of our pictures, however. I always found that imagination makes people look more imposing than reality. — pjp

[I can attest to that. How about if we just offer a special issue with full-page color photos of all our colunmists? If we hurry we can make the Christmas coffee-table book rush. — mb]

Dear Mr Plauger:

John W. Ross ("Fast String Searching," CUJ, July 1995) mentioned that many strstr implementations are based on a locate-first-character algorithm. Perhaps we can attribute this choice to the fact that strstr's text parameter is a null-terminated string — if we're examining every character in the string without skipping, then we can check for the null character while we're at it. With the Boyer-Moore algorithm we couldn't do that; we'd have to call strlen first.

One simple way to get an improvement on the locate-first-character algorithm, without knowing the relative frequency of characters in the local language, is this: on each iteration, compare a 16-bit word instead of an 8-bit byte (though of course if the comparison fails we increment our text pointer by 1, not by 2). The point is, the frequency of a two-letter combination is always much smaller than the frequency of a single letter if values are random. If values are English characters then this remains true, although there are a few exceptions (for example "QU" is not much less frequent than "Q" alone). The "improvement" is not portable, but works with Intel 486s. I put an example of an improved strstr in our Optimizing C With Assembly Code book; the speedup over a regular strstr is between 32% and 93%, with caveats.

Very truly yours,

Peter Gulutzan

Thanks for the comments. And if we're going to shamelessly plug your book, let's do it right: Optimizing C With Assembly, by Peter Gulutzan and Trudy Pelzer. Publisher: R&D Technical books. 1601 W. 23rd St., Lawrence, KS., +1-913-841-1631. FAX: +1-913-841-2624. e-mail: rdorders@rdpub.com. ISBN: 0-13-234576-5. Price: $29.95. Disk included. — pjp

Editor,

I enjoyed "Fast String Searching" by John W. Ross. However, I would like to point out a problem in one of the code samples: Listing 5 refers to txt[k], where k is calculated in such a way that it can very reasonably be negative the first time through the loop. To fix this, you could replace the line:

cp = strchr(txt, pat[pos]);
with

cp = strchr(txt+pos, pat[pos]);
This will assure that cp-txt will at least equal pos. Admittedly, this presumes that txt has at least pos+1 members, but without that condition the whole exercise is moot.

Sincerely,

Lowell Palecek
pale@rsvl.unisys.com

Thanks. — pjp

Greetings;

I was reading the letters in the October 1994 issue about how CUJ was either too advanced or too elementary — and all I can say is, "Keep it up!" When I started reading CUJ over three years ago, 90 per cent of it went straight over my head. But I kept reading anyway, and little by little things started to make sense.

Now look at me — I'm programming sophisticated (if I dare say so myself) object-oriented relational databases from scratch. Still, there are things in some issues that continue to go over my head. Someday, maybe I'll understand those, too. And I like the fact that I can still find articles and columns on the absolute basics of C or C++. The basics can always use reinforcement — I never skip over a piece on pointers or inheritance just because I think I know everything (although the first time I found an article I could skip over because it was "too elementary" for me was quite a rush, I tell you).

Beginners just need to be patient and keep studying. And advanced programmers need to remember that they can never actually graduate — in this field, if you ain't still studying, you're a drop-out.

Thanks for being the single best source for continuing education in C/C++ programming.

Bruce V. Edwards
CIS: 102566,3363

It's nice to know that some people appreciate the dynamic range we strive for. Thanks. — pjp

Mr. Plauger,

I have been a subscriber to CUJ for two years now. I enjoy the publication for many reasons. It is informative, entertaining, and doesn't taste too bad with the right wine. I have a few responses to some letters from "We Have Mail" in the August 1995 issue. Maybe your readers will find them helpful, maybe not. If you'll print them, here they are:

To: Ken Onweller,

Mr. Plauger's book, The ANSI C Standard, is excellent, and mandatory for any C programmer. I also suggest that you read the entire contents for every .h file that came with your particular compiler.

To: James Scott,

Huh?

To: Marco Savard,

Works for me.

To: Richard Howells,

do {
   fgets(string, MAXLEN, stdin)
   if(string[0] =='\n')
      put("Entering a blank line won't cut it.\n");
   } while(string!=NULL);
To: Shyam Cherlopalle,

kill -9 Windoze;xinitrc
To: Robert L. Smith,

I like Borland for Windoze. I believe the box said something about Windows Application Frames, or something like that. Libraries I believe are from the Whitewater Group. You can't "dabble," you have to take time to learn the package. If you are a true "dabbler," get Clarion for Windows, or something along those lines.

Finally, to: Igor Siemienowicz

signal.h
In closing, Bill Gates has too much money. Ray Noorda should be our next president. And Linus Torvalds is my hero. That's all.

Russ Berry

That's enough. Looks like I've got competition for the job of answering letters. — pip

Dear CUJ,

The article by Jon Jagger about his exceptionally clever debug macro system really caught my interest (CUJ, October 1995). Having written some plain awful debug macros in the past, I was pleased to learn a few new tricks to add to my collection.

However, most of the way through the article I was climbing onto my high-horse about re-entrancy when finally it came: "This technique is not thread-safe?" Drat! My chance for a nasty letter evaporated :)

As much of the code I write needs to be reentrant, I started thinking about how I might improve it. Which led me to another small problem in the technique: storing the __LINE__ and __FILE__ values when the call is made to the Ptr_printf routine only works if that expression is evaluated after the evaluation of the function arguments. Consider:

printf("%d\n", a());
If the function a also calls printf and the function designator is evaluated before the argument list, then the technique breaks. This is because the printf call inside a will clobber the __LINE__ and __FILE__ values saved by the outermost call. My reading of the C Standard does not give an order, so this might be a problem with some implementations.

The extension I would propose solves the problem above, and makes the technique thread-safe. I would add a small stack allocated as static near where the struct Func func is allocated, Then the Ptr_xxxxx routine pushes the __LINE__ and __FILE__ values onto this stack, and the DB_printf pops them from it,

Maximum stack depth could be controlled by the DB_DEFN macro, or all debug macros could share a common stack. In either case, re-entrancy interlocks and over/under flow of the push and pop operation can be added if needed.

This does not solve all problems, but it does help. There is still the problem with incorrect reporting in situations that Jon described in "Disadvantages" point 3. In that example with my stack, the details are popped off the stack in the incorrect order. Sigh.

Thanks Jon for an interesting article — hope my comments add value.

David Brown
brown@falam.ch

P.S. From the same issue: the only true indent style is Allman. Repent!

Making code thread-safe gives me a headache, but I have to admit it's an important exercise. — pjp

Mr. Plauger,

As an experienced C developer, and apprentice C++ journeyman, I enjoyed your article in The C/C++ Users Journal, July 95; however I have some questions.

My primary focus for the past ten years has been with user interfaces, and as such I am routinely searching strings with regular expressions. I saw nothing in your discussion about a method for regular expressions. Is this addressed by the proposed standard? Would I, and my colegues, have to create a subordinate class to the standard string class and add this method?

Also the basic sprintf functionality appears to have fallen into the bit bucket. I would have loved to see a method of the following form:

string x0;   //place args into x0
             //according to the format
             //x0.sprintf(format, vargs,..);
Why were these two very common methods left out of the standard? I suspect that in the real world sprintf and regex are used far more often than find_first_not_of.

Thanks for any information you can provide,

Richard Decker LCC, L.L.C.
2300 Clarendon Blvd, Ste 800,
Arlington, VA 22201
rdecker@lccinc.com

There was some loose talk about adding regular expressions to the Standard C++ library, but it never happened. The Posix (X/Open) standard includes such machinery, however. Your second request is met by the header <sstream>, which I discussed in my March 1995 "Standard C/C++" Column. — pip