New K&R2 exercise: fix getint
Tim Hagan
Language" by Kernighan & Ritchie:
Exercise 5-0. As written, getint sucks. Fix it.
Has anyone else noticed that the getint function in K&R2 (Section 5.2,
page 97) does not work? It is not mentioned in the K&R2 Errata
(http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html), nor do Steve Summit's
excellent notes (http://www.eskimo.com/~scs/cclass/krnotes/sx8b.html)
point this out, although he does say that it is "somewhat complicated".
Here it is:
#include <ctype.h>
int getch(void);
void ungetch(int);
/* getint: get next integer from input into *pn */
int getint(int *pn)
{
int c, sign;
while (isspace(c = getch())) /* skip white space */
;
if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
ungetch(c); /* it's not a number */
return 0;
}
sign = (c == '-') ? -1 : 1;
if (c == '+' || c == '-')
c = getch();
for (*pn = 0; isdigit(c); c = getch())
*pn = 10 * *pn + (c - '0');
*pn *= sign;
if (c != EOF)
ungetch(c);
return c;
}
Notice what happens when the character c is not a number. ungetch(c)
pushes the character back onto the input and the function returns 0.
On the next call to getint it will be the first character read in.
Well, it's still not a number, so it gets pushed back onto the input
and the function returns 0. On the next call to getint it will be
the first character read in. Well, it's *still* not a number, so ...
we're stuck in an infinite loop. (The trivial fix is left as an
exercise for the reader.)
But there's another problem. Look at that awful example on page 96:
int n, array[SIZE], getint(int *);
for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
;
If getint runs across a non-digit character, it returns 0, array[n]
retains whatever it contained (probably garbage) and n is incremented.
On the next call to getint ... oops, there it goes again. That pesky
"infinite" loop kicks in and won't stop until n reaches SIZE. So, the
loop should not increment n unless a valid number has been placed in
array[n], which is indicated when the return status of getint is
greater than zero.
--
Tim Hagan
Arthur J. O'Dwyer
On Wed, 18 Jun 2003, Tim Hagan wrote:
>
> I would like to propose a new exercise for "The C Programming
> Language" by Kernighan & Ritchie:
>
> Exercise 5-0. As written, getint sucks. Fix it.
>
> Has anyone else noticed that the getint function in K&R2 (Section 5.2,
> page 97) does not work? It is not mentioned in the K&R2 Errata
> (http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html), nor do Steve Summit's
> excellent notes (http://www.eskimo.com/~scs/cclass/krnotes/sx8b.html)
> point this out, although he does say that it is "somewhat complicated".
The function works fine as written.
> Here it is:
>
> #include <ctype.h>
>
> int getch(void);
> void ungetch(int);
>
> /* getint: get next integer from input into *pn */
> int getint(int *pn)
> {
> int c, sign;
>
> while (isspace(c = getch())) /* skip white space */
> ;
(The extra whitespace is not ungetch()ed on failure, but that's
acceptable. Debugging without a spec again. :)
> if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
> ungetch(c); /* it's not a number */
> return 0;
> }
If no number is found, we restore all non-whitespace characters
(i.e., the last character read) and return 0 (i.e., failure).
> sign = (c == '-') ? -1 : 1;
> if (c == '+' || c == '-')
> c = getch();
Skip over any sign that may be present.
> for (*pn = 0; isdigit(c); c = getch())
> *pn = 10 * *pn + (c - '0');
Store the number itself. N.B: isdigit(EOF) is always false; thus
no check for EOF is necessary in the loop condition.
> *pn *= sign;
Might better be handled by "if (sign==-1) pn = -pn;", but whatever.
> if (c != EOF)
> ungetch(c);
Push back the last non-digit character.
> return c;
Also return the last non-digit character. Here is a slight "bug",
in that if a null character ends up on the input stream following
a number, getint() will return 0 rather than some positive value
upon reading that number. I'd change this line to
return 1 - 2*(c == EOF);
or the equivalent.
> }
>
> Notice what happens when the character c is not a number. ungetch(c)
> pushes the character back onto the input and the function returns 0.
> On the next call to getint it will be the first character read in.
> Well, it's still not a number, so it gets pushed back onto the input
> and the function returns 0. On the next call to getint it will be
> the first character read in. Well, it's *still* not a number, so ...
> we're stuck in an infinite loop.
Only if the thing controlling your loop is "do this forever", rather
than "do this until getint() fails or until we have read N numbers",
or something sensible. fscanf("%d") behaves the exact same way.
> (The trivial fix is left as an
> exercise for the reader.)
while (getint(&n) > 0) {
...
}
> But there's another problem. Look at that awful example on page 96:
>
> int n, array[SIZE], getint(int *);
>
> for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
> ;
This does seem to be incorrect usage of the getint() function, from a
c.l.c point of view. K&R probably assumed that the reader would
understand the lack of error-checking was a pedagogical quirk.
It's not really a "bug" unless the book says something that isn't
correct. Here, you have an example program that uses a library
function in a not-very-safe fashion. My K&R1 is full of those, and
I expect the second edition has its share. K&R doesn't really try
to teach absolute safety -- it teaches the C language.
-Arthur
Tim Hagan
>
> On Wed, 18 Jun 2003, Tim Hagan wrote:
> >
> > I would like to propose a new exercise for "The C Programming
> > Language" by Kernighan & Ritchie:
> >
> > Exercise 5-0. As written, getint sucks. Fix it.
> >
> > Has anyone else noticed that the getint function in K&R2 (Section 5.2,
> > page 97) does not work? It is not mentioned in the K&R2 Errata
> > (http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html), nor do Steve Summit's
> > excellent notes (http://www.eskimo.com/~scs/cclass/krnotes/sx8b.html)
> > point this out, although he does say that it is "somewhat complicated".
>
> The function works fine as written.
I guess it depends on how one uses it. :-)
Thanks for the annotations. I was only remarking on the seeminly odd
behavior of getint when it encountered a non-digit.
> > Notice what happens when the character c is not a number. ungetch(c)
> > pushes the character back onto the input and the function returns 0.
> > On the next call to getint it will be the first character read in.
> > Well, it's still not a number, so it gets pushed back onto the input
> > and the function returns 0. On the next call to getint it will be
> > the first character read in. Well, it's *still* not a number, so ...
> > we're stuck in an infinite loop.
>
> Only if the thing controlling your loop is "do this forever", rather
> than "do this until getint() fails or until we have read N numbers",
> or something sensible. fscanf("%d") behaves the exact same way.
>
> > (The trivial fix is left as an
> > exercise for the reader.)
>
> while (getint(&n) > 0) {
> ...
> }
I was thinking of "fixing" the function itself by removing the first
ungetch call, which would cause non-digits to be ignored, effectively
treating them as delimiting white space.
> > But there's another problem. Look at that awful example on page 96:
> >
> > int n, array[SIZE], getint(int *);
> >
> > for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
> > ;
>
> This does seem to be incorrect usage of the getint() function, from a
> c.l.c point of view. K&R probably assumed that the reader would
> understand the lack of error-checking was a pedagogical quirk.
Maybe a better example would be:
int i, n, array[SIZE], getint(int *), status;
n = 0;
while (n < SIZE && (status = getint(&array[n])) != EOF)
if (status > 0)
n++;
> It's not really a "bug" unless the book says something that isn't
> correct.
True. However, the text accompanying their example says: "Each call
sets array[n] to the next integer found in the input and increments
n." Either the example or the text is incorrect. Their function works
fine until a non-digit is entered.
> Here, you have an example program that uses a library
> function in a not-very-safe fashion. My K&R1 is full of those, and
> I expect the second edition has its share. K&R doesn't really try
> to teach absolute safety -- it teaches the C language.
From the preface to the first edition: "Besides showing how to make
effective use of the language, we have also tried where possible to
illustrate useful algorithms and principles of good style and sound
design." IMHO, getint does not demonstrate good style and sound design.
BTW, I think K&R is great. It is an excellent text book and reference.
I just think the getint example is a bit goofy. :-p
--
Tim Hagan
Arthur J. O'Dwyer
On Wed, 18 Jun 2003, Tim Hagan wrote:
>
> "Arthur J. O'Dwyer" wrote:
> > On Wed, 18 Jun 2003, Tim Hagan wrote:
> > >
> > > Has anyone else noticed that the getint function in K&R2 (Section 5.2,
> > > page 97) does not work? It is not mentioned in the K&R2 Errata
> > > (http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html), nor do Steve Summit's
> > > excellent notes (http://www.eskimo.com/~scs/cclass/krnotes/sx8b.html)
> > > point this out, although he does say that it is "somewhat complicated".
> >
> > The function works fine as written.
>
> I guess it depends on how one uses it. :-)
As I said, same as the *scanf family. Invalid data is not read, and
the programmer has to handle such cases by himself. If the function
silently threw away the invalid data, the programmer would be in a
much worse position to recover from the user's error.
> > > Notice what happens when the character c is not a number. ungetch(c)
> > > pushes the character back onto the input and the function returns 0.
> > > On the next call to getint it will be the first character read in.
> > > Well, it's still not a number, so it gets pushed back onto the input
> > > and the function returns 0. On the next call to getint it will be
> > > the first character read in. Well, it's *still* not a number, so ...
> > > we're stuck in an infinite loop.
> >
> > Only if the thing controlling your loop is "do this forever", rather
> > than "do this until getint() fails or until we have read N numbers",
> > or something sensible. fscanf("%d") behaves the exact same way.
> >
> > > (The trivial fix is left as an
> > > exercise for the reader.)
> >
> > while (getint(&n) > 0) {
> > ...
> > }
>
> I was thinking of "fixing" the function itself by removing the first
> ungetch call, which would cause non-digits to be ignored, effectively
> treating them as delimiting white space.
That would break the function, in that the function would be eating
possibly valuable data without warning the programmer that it was
doing so.
> > > But there's another problem. Look at that awful example on page 96:
> > >
> > > int n, array[SIZE], getint(int *);
> > >
> > > for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
> > > ;
> >
> > This does seem to be incorrect usage of the getint() function, from a
> > c.l.c point of view. K&R probably assumed that the reader would
> > understand the lack of error-checking was a pedagogical quirk.
>
> Maybe a better example would be:
>
> int i, n, array[SIZE], getint(int *), status;
>
> n = 0;
> while (n < SIZE && (status = getint(&array[n])) != EOF)
> if (status > 0)
> n++;
No; that doesn't fix the bug. Try a variation on what I already
posted:
int array[SIZE];
int n;
for (n=0; n < SIZE && getint(&array[n]) > 0; ++n) ;
if (n < SIZE && !feof(stdin)) {
printf("You entered something that was not a number.");
}
> > It's not really a "bug" unless the book says something that isn't
> > correct.
>
> True. However, the text accompanying their example says: "Each call
> sets array[n] to the next integer found in the input and increments
> n." Either the example or the text is incorrect. Their function works
> fine until a non-digit is entered.
I think it's pretty clearly implied that the input stream contains *only*
integers. After all, that's the purpose of the program -- to get some
integers from stdin. It's not trying to somehow separate the integers
from the non-digits in the stream, or anything like that.
> > Here, you have an example program that uses a library
> > function in a not-very-safe fashion. My K&R1 is full of those, and
> > I expect the second edition has its share. K&R doesn't really try
> > to teach absolute safety -- it teaches the C language.
>
> From the preface to the first edition: "Besides showing how to make
> effective use of the language, we have also tried where possible to
> illustrate useful algorithms and principles of good style and sound
> design." IMHO, getint does not demonstrate good style and sound design.
getint() is fine. It's just the example program that could be more
robust.
-Arthur
Tim Hagan
>
[snip]
> getint() is fine.
You're right. I was expecting too much from it. As the name implies,
I thought getint should get *all* integers from the input stream,
ignoring any extraneous characters until EOF was reached.
> It's just the example program that could be more robust.
Yes! That was the source of my confusion.
--
Tim Hagan