mcdaniel@uicsrd.csrd.uiuc.edu (05/05/88)
I just got the Second Edition of "The C Programming Language" by
Kernighan & Richie. (The "New Testament"? :-) )
I'm puzzled by the example in section 5.11, "Pointers to Functions",
pp. 119--120. It's a generic quicksort which sorts using an array of
void pointers to the data. This "qsort" is passed a comparison
function.
void qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void*));
"lineptr" is an array of lines to sort. "strcmp" is the normal string
comparison function, and "numcmp" compares strings numerically (the
results of atof() are compared):
char *lineptr[MAXLINES];
int numcmp(char *, char *);
The problem is that "qsort" is called thus:
qsort((void **) lineptr, 0, nlines-1,
(int (*)(void*,void*))(numeric ? numcmp : strcmp));
Are those two casts portable---is it guaranteed that "void *" and
"char *" have the same internal representation? Is it likely that
they would under any "reasonable" implementation (whatever THAT
means)?
Whether or not it's legal, the type punning above is obscene. I would
use the following declarations:
void *lineptr[MAXLINES];
int numcmp(void *, void *);
int my_strcmp(void *, void *);
If I'm careful to store them as "void *"s and use them as "char *"s,
there are no storage or use type problems.
--
Tim, the Bizarre and Oddly-Dressed Enchanter
Center for Supercomputing Research and Development
at the University of Illinois at Urbana-Champaign
Internet, BITNET: mcdaniel@uicsrd.csrd.uiuc.edu
UUCP: {ihnp4,uunet,convex}!uiucuxc!uicsrd!mcdaniel
ARPANET: mcdaniel%uicsrd@uxc.cso.uiuc.edu
CSNET: mcdaniel%uicsrd@uiuc.csnetchris@mimsy.UUCP (Chris Torek) (05/07/88)
In article <44200009@uicsrd.csrd.uiuc.edu> mcdaniel@uicsrd.csrd.uiuc.edu asks: >Are those two casts portable---is it guaranteed that "void *" and >"char *" have the same internal representation? It is so guaranteed, according to the most recent public draft review standard. In the dpANS, `void *' is simply a notational convenience for `char * but_never_complain_about_mixed_pointer_types'. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
gwyn@brl-smoke.ARPA (Doug Gwyn ) (05/08/88)
In article <44200009@uicsrd.csrd.uiuc.edu> mcdaniel@uicsrd.csrd.uiuc.edu writes: > qsort((void **) lineptr, 0, nlines-1, > (int (*)(void*,void*))(numeric ? numcmp : strcmp)); >Are those two casts portable---is it guaranteed that "void *" and >"char *" have the same internal representation? Yes, the proposed C standard requires that. >Whether or not it's legal, the type punning above is obscene. You won't get any argument from me there! numcmp and strcmp are pointers to what in ANSI C parlance are termed "compatible types", so there is not a type mismatch between the operands of the ?: operator, as one might think at first. It takes some degree of language lawyer virtuosity to unravel the constraints in the proposed standard to discover that this usage is in fact legal. The reason for the cast is that it does not appear to be specified what the "composite type" is when a char * and a void * collide, so the cast ensures that whatever the type is, it is turned into the right thing to feed to qsort(). Presumably this oversight is one of the things that will be fixed in the next draft of the standard. The more usual solution is to define numcmp() with void * parameters and apply explicit casts at the beginning of its function body.
henry@utzoo.uucp (Henry Spencer) (05/08/88)
> Are those two casts portable---is it guaranteed that "void *" and > "char *" have the same internal representation? ... Yes. X3J11 decided to require this. If for no other reason, because making them different will break thousands of old programs that pass "char *" to library functions that are now officially defined to take parameters of type "void *". -- NASA is to spaceflight as | Henry Spencer @ U of Toronto Zoology the Post Office is to mail. | {ihnp4,decvax,uunet!mnetor}!utzoo!henry
dmr@alice.UUCP (05/09/88)
Tim, the Bizarre and Oddly-Dressed Enchanter, questions (44200009@uicsrd.csrd.uiuc.edu) the call to qsort in K&R 2, p. 119. The call is qsort((void **) lineptr, 0, nlines-1, (int (*)(void*,void*))(numeric ? numcmp : strcmp)); and the thing in question is that messy second line. He's right to remain suspicious, even though we seem to have passed the Gwyn, Torek, and Spencer tests with no more than minor cuts and abrasions. The intent of the example is to show how to deal with function pointers. Arrays of lines are being compared either numerically or lexically, and either the numeric or string comparison function is being passed to qsort. I suspect the example should have been simplified; it raises too many issues. Here are some of the problems with it. I leave aside the question of whether it would be better to rewrite the call without the ?: or otherwise fiddle it to make it more readable; the question is whether it is correct. First: is `numeric? numcmp: strcmp' legal? We declared numcmp above as `int numcmp(char *, char *)' while letting strcmp come from the standard header; it is (as of Jan 11, but dropping the `noalias') `int strcmp(const char *, const char *).' The relevant question is whether the two arms of the conditional are `pointers to compatible types,' and the answer, I'm afraid, is no, because the parameters are not identically qualified [3.5.3; p. 66, line 11 of the Jan 11 draft]. Second: [easy] is the cast (int (*)(void*,void*)) legal? Yes; essentially all vaguely sensible casts are legal. Third: is the argument to qsort legal? Yes, with the declaration for qsort given on p. 119 of the text; the types of the parameter and the argument agree. But observe that the library qsort routine (which is declared in <stdlib.h>) takes a third argument of type int (*)(const void*, const void*) and the Standard warns that you are on your own if you write your own version of library functions, and here the parameter types are not even identical. Fourth: Is it well-defined what happens when qsort calls the comparison function? Perhaps not, according to the standard. `A pointer to a function may be converted to a pointer to another type.... If a converted pointer is used to call a function that is not compatible with the type of the called function, the behavior is undefined' [3.3.4]. So it depends on whether a function of type (*)(void*, void*) which is the one our qsort uses, will work when it calls a comparison routine declared with either of (*)(const char*, const char*) (*)(char*, char*) which are the types of the pointer versions of strcmp and numcmp. In spite of the fact that the type void* is now guaranteed to have the same representation as char*, I don't think that the type rules of the dpANS guarantee this will work. In our defense, given that the representation of char* is the same as that of void*, it is reasonable to expect that you would be safe in reproducing the book example provided your compiler accepted it. However, at least as I read the last-issued version of the standard, the compiler might well reject it. A lot of people are going to be surprised when ANSI compilers become common. As I have argued before, type qualifiers are not an unmixed blessing. Dennis Ritchie research!dmr dmr@research.att.com
gwyn@brl-smoke.ARPA (Doug Gwyn ) (05/10/88)
In article <7861@alice.UUCP> dmr@alice.UUCP writes: > qsort((void **) lineptr, 0, nlines-1, > (int (*)(void*,void*))(numeric ? numcmp : strcmp)); >The relevant question is whether the two arms of the conditional are >`pointers to compatible types,' and the answer, I'm afraid, is no, >because the parameters are not identically qualified ... I believe the Committee agreed that our intent was not properly expressed in the wording in the January 1988 draft, and that this is being revised for the next draft so that the operands of this ?: operator will have compatible types regardless of qualifiers. (I haven't seen the revised wording in context yet.) I don't think that there is a composite type assigned for the result of this function- type meeting, though, which would be the real reason that a cast would still be necessary. I'm discussing this with the draft Redactor. (So far he says that char * and void * are not compatible types, just assignment compatible, to which my response is that given the identity of representation that seems like an oversight.) >In our defense, given that the representation of char* is the same >as that of void*, it is reasonable to expect that you would be safe >in reproducing the book example provided your compiler accepted it. >However, at least as I read the last-issued version of the standard, >the compiler might well reject it. Yes, that is the essential question. If it makes it through the compiler, I think it is guaranteed to work, but we need to know whether it is guaranteed to make it through the compiler without a possibly fatal diagnostic. Personally I wouldn't have tried writing code that explores the dark corners of the language like that but would have made my comparison function arguments have precisely the same type as qsort expects, with (trivial) conversion at the beginning of the comparison function. I know THAT is supposed to work portably.
henry@utzoo.uucp (Henry Spencer) (05/10/88)
> ... we seem to have passed the > Gwyn, Torek, and Spencer tests with no more than minor cuts and > abrasions. Actually, you've only passed the first two; the Spencer test wasn't being given that day... :-) Once in a while I decide I'm just not going to get involved in a discussion, particularly if Chris or Doug has already waded in, and PARTICULARLY if the debate turns on some fine point of type qualifiers and type compatibility! Talk about swamps... -- NASA is to spaceflight as | Henry Spencer @ U of Toronto Zoology the Post Office is to mail. | {ihnp4,decvax,uunet!mnetor}!utzoo!henry
nather@ut-sally.UUCP (Ed Nather) (05/10/88)
In article <7861@alice.UUCP>, dmr@alice.UUCP writes: > > A lot of people are going to be surprised when ANSI compilers become > common. > > Dennis Ritchie Hmmm. I thought ANSI was supposed to standardize the C language, not fill the description with surprises ... -- Ed Nather Astronomy Dept, U of Texas @ Austin {allegra,ihnp4}!{noao,ut-sally}!utastro!nather nather@astro.AS.UTEXAS.EDU
sjs@spectral.ctt.bellcore.com (Stan Switzer) (05/11/88)
In article <7861@alice.UUCP> dmr@alice.UUCP writes: > qsort((void **) lineptr, 0, nlines-1, > (int (*)(void*,void*))(numeric ? numcmp : strcmp)); > > The relevant question is whether the two arms of the conditional are > `pointers to compatible types,' and the answer, I'm afraid, is no, > because the parameters are not identically qualified ... And after a good bit of exposition concludes that many people will be surprised at the number of different languages recognized (and rejected) by "conforming" C compilers. In defense of ANSI, gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: > Yes, that is the essential question. If it makes it through the > compiler, I think it is guaranteed to work, but we need to know > whether it is guaranteed to make it through the compiler without > a possibly fatal diagnostic. > > Personally I wouldn't have tried writing code that explores the dark > corners of the language like that but would have made my comparison > function arguments have precisely the same type as qsort expects, > with (trivial) conversion at the beginning of the comparison function. > I know THAT is supposed to work portably. To this I can only ask: "Why are there STILL dark corners?" I know unambiguous specification is dark art (and formal approaches have been none too successful), but it really isn't fair to defend a standard by calling a reasonable construction a "dark corner" of the language. Basically, I recognize the need for a C standard, and I sympathize that one should avoid "obscure" constructions (a judgement call in any case), but I can't help but be nostalgic for the days when "pcc" itself was the "standard" against which C compilers were compared (syntacticly speaking) and when the only sensible measure of a C compiler other than recognizing pcc's language was that it ran code that ran on VAXes (modulo byte order and char signedness). As a cautious customer, I have learned to interpret specfications perversely in order to anticipate the worst case implementations. It would be fun to postulate perverse but conforming interpretations of the ANSI C language. Perhaps a contest is in order. This is no small concern, because as C expands into new markets and environments, there is good reason to fear that a lot of houey will be sold under the banner "standard conforming" and we might very well find ourselves living with a new and unfortunate mutatation of "C". I know all about the "quality-of- implementation" argument, and I am not impressed: just look how many people think "char *far foo;" is proper C. Stan Switzer
gwyn@brl-smoke.ARPA (Doug Gwyn ) (05/11/88)
In article <7288@bellcore.bellcore.com> sjs@spectral.UUCP (Stan Switzer) writes: >To this I can only ask: "Why are there STILL dark corners?" That has a simple answer. C's type system has dark corners because of the way it evolved. There are too many cases where types are "sort of the same", but not identical. The proposed ANSI C standard has managed to bring some semblance of order to this mess, but it cannot just change to a clean, rigorous type system, since one of its main goals is to accommodate existing practice rather than to totally supplant it. >... but it really isn't fair to defend a standard by calling a >reasonable construction a "dark corner" of the language. I don't know how you read that into what I had said: "Personally I wouldn't have tried writing code that explores the dark corners of the language like that ..." How does my personal C usage style relate to a "defense of the standard"? Dark corners are dark corners whether or not they are theoretically well defined, just as dark alleys may be unsafe even though the law says thou shalt not be mugged in one. >... I can't help but be nostalgic for the days when "pcc" >itself was the "standard" against which C compilers were compared >(syntacticly speaking) and when the only sensible measure of a C >compiler other than recognizing pcc's language was that it ran >code that ran on VAXes (modulo byte order and char signedness). You must have moved in different circles than I did. Far from being a correctness criterion, it has been well-known that PCC did several things wrong. One would also think that Ritchie's compiler would have precedence over Johnson's. In any case, there always was a problem with the exact definition of C, just that people who used nothing but PCC never noticed the problem. >...there is good reason to fear that a lot of houey will be sold under >the banner "standard conforming" ... I know of two ANSI C validation suites in progress and I suspect there may be others. There will therefore be tools for C compiler customers to check that vendor offerings are indeed standard conforming. Whether or not a conforming implementation will be widely useful or will have obnoxious limitations is something that the marketplace will have to shake out.
dhesi@bsu-cs.UUCP (Rahul Dhesi) (05/12/88)
In article <7288@bellcore.bellcore.com> sjs@spectral.UUCP (Stan Switzer) writes: >To this I can only ask: "Why are there STILL dark corners?" Knowing what we do by observing the standardization process for Pascal and Ada, I think we can reasonably conclude that it is a tremendously difficult task to unambiguously define a nontrivial programming language in less than 5 years. Since ANSI C is not just a fixed K&R C, but is actually an evolutionary step (some say up, some say down) away from it, it clearly hasn't had enough time yet. -- Rahul Dhesi UUCP: <backbones>!{iuvax,pur-ee,uunet}!bsu-cs!dhesi
hugh@dgp.toronto.edu ("D. Hugh Redelmeier") (05/12/88)
In article <7861@alice.UUCP> dmr@alice.UUCP writes: >In spite of the fact that the type void* is now guaranteed to have >the same representation as char*, I don't think that the type >rules of the dpANS guarantee this will work. > >In our defense, given that the representation of char* is the same >as that of void*, it is reasonable to expect that you would be safe >in reproducing the book example provided your compiler accepted it. >However, at least as I read the last-issued version of the standard, >the compiler might well reject it. > >A lot of people are going to be surprised when ANSI compilers become >common. As I have argued before, type qualifiers are not an unmixed >blessing. Here is an extract from my public comment to X3J11. References to the draft (X3J11/88-001) look like page/line chapter.section.subsection I don't think that any action resulted from this. 24/5 3.1.2.5 overlapping values of signed and unsigned have same rep 25/5 3.1.2.5 void * has same rep as char * 39/18 3.3 accessing an object with type different from declaration 131/25 4.9.6.1 fprintf There seems to be some partial compatibility presumed between unsigned, signed, and plain types of the same width. There also seems to be some unspecified compatibility between char * and void *: why else decree that their representations match? In fprintf and its variants, d, i, o, u, x, and X conversion specifiers work only with signed int arguments (or signed long int, if preceded by l) (see 132/44 4.9.6.1). But many existing programs pass unsigned int (or unsigned long) arguments. Surely these must not be deemed wrong. And I suspect that the effort of casting all unsigned arguments will seem so silly that it won't even be done for new programs (prototypes don't change this: they are matched by elipsis). Especially for the u conversion -- it would seem downright wrong on a one's complement machine (unsigned max would probably have to print as zero). okOld programs, written under the "unsignedness sticks" rules might well pass an unsigned short argument to an unsigned int parameter. Under the current default argument promotions, the argument will be promoted to signed int if sizeof(int) is greater than sizeof(short). Thus, the program will silently fail (i.e. violate a rule in the standard). Of course, on most implementations, these programs will continue to work IN SPITE OF the standard. The similar thing can happen to unsigned char arguments. Issue 1: extended parameter/argument compatibility A new kind of type compatibility is required, say "congruence". Two types are congruent if they are compatible. In addition, two integer types are congruent if their sizes are the same. Furthermore, two pointer types are congruent if one is compatible with pointer to char and the other is compatible with pointer to void. The agreement of parameters with arguments must be changed. Argument and parameter types, if either was produced by the default argument promotions, must at least be congruent. If they are congruent, but not compatible, the parameter passing will work when the value is representable in both types, and both representations are identical (note: in one's complement, -0 has a distinct representation from +0). Even though passing parameters to congruent types will sometimes work, it should be considered an error so that it may be diagnosed. This is wishy-washy, but existing programs have not carefully distinguished signed versus unsigned, and certainly have not passed void * parameters to library functions that now require them. It is to be admitted that the distinction between "working" and "correct" is questionable. Making this code work is important to the mandate of X3J11: existing code is important. I infer that this is what some of the referenced passages of the draft standard are trying to get at, but fail to accomplish. Issue 2: fprintf parameter should be unsigned for o, u, x, and X Draft 132/44: "The int argument is converted to signed decimal (d or i), unsigned octal (o), unsigned decimal (u), or unsigned hexadecimal notation (x or X); ..." Since o, u, x, and X conversion specifiers do not generate signs, it would seem most natural that they should take unsigned numbers to format. In fact, they take a signed number. This should be changed. Note that fscanf gets these conversion specifiers right: for them it expects the argument to be a pointer to unsigned int. Proposed replacement: "The int (d or i) or unsigned int (o, u, x, or X) argument is converted to signed decimal (d or i), unsigned octal (o), unsigned decimal (u), or unsigned hexadecimal notation (x or X); ..." This still leaves a problem: old programs have often printed signed ints with these conversion specifiers. Unless the first issue is addressed, some programs are bound to be broken. Hugh Redelmeier {utcsri, utzoo, yunexus, hcr}!redvax!hugh In desperation: hugh@csri.toronto.edu +1 416 482 8253
henry@utzoo.uucp (Henry Spencer) (05/12/88)
> Hmmm. I thought ANSI was supposed to standardize the C language, not > fill the description with surprises ... Standards committees tend to do the latter even when they are only supposed to do the former. X3J11 has not been too bad about this, compared to some of the things that have happened in other standards efforts. -- NASA is to spaceflight as | Henry Spencer @ U of Toronto Zoology the Post Office is to mail. | {ihnp4,decvax,uunet!mnetor}!utzoo!henry
nather@ut-sally.UUCP (Ed Nather) (05/14/88)
In article <2990@bsu-cs.UUCP>, dhesi@bsu-cs.UUCP (Rahul Dhesi) writes: > > Since ANSI C is not just a fixed K&R C, but is actually an evolutionary > step (some say up, some say down) away from it, It makes me nervous to realize this evolutionary step was made by a committee. -- Ed Nather Astronomy Dept, U of Texas @ Austin {allegra,ihnp4}!{noao,ut-sally}!utastro!nather nather@astro.AS.UTEXAS.EDU
gwyn@brl-smoke.ARPA (Doug Gwyn ) (05/15/88)
In article <11593@ut-sally.UUCP> nather@ut-sally.UUCP (Ed Nather) writes: >It makes me nervous to realize this evolutionary step was made by a >committee. Whoopie do. What are the alternatives? 1) stagnation at a functionally inadequate level 2) evolution by one individual's fiat (who?) 3) evolution by cooperating individuals (e.g. committee) 4) evolution by battling individuals Pick one. I think I would be MORE nervous with the other alternatives.
wes@obie.UUCP (Barnacle Wes) (05/16/88)
In article <1988May12.163809.16998@utzoo.uucp>, henry@utzoo.uucp (Henry Spencer) writes: > > Hmmm. I thought ANSI was supposed to standardize the C language, not > > fill the description with surprises ... > > Standards committees tend to do the latter even when they are only supposed > to do the former. X3J11 has not been too bad about this, compared to some > of the things that have happened in other standards efforts. Like, for instance, the Fortran-88 committee? It strikes me that a new Fortran standard will be hard to push when IBM, DEC, and Harris are all dead-set against it. -- /|\ Barnacle Wes @ Great Salt Lake Yacht Club, north branch / | \ @ J/22 #49, _d_J_i_n_n_i /__|__\ ___|____ "If I could just be sick, I'd be fine." ( / -- Joe Housely, owner of _E_p_i_d_e_m_i_c -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mouse@mcgill-vision.UUCP (der Mouse) (05/18/88)
In article <7890@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes: > In article <11593@ut-sally.UUCP> nather@ut-sally.UUCP (Ed Nather) writes: >> It makes me nervous to realize this evolutionary step was made by a >> committee. Me too. > Whoopie do. What are the alternatives? > 1) stagnation at a functionally inadequate level > 2) evolution by one individual's fiat (who?) > 3) evolution by cooperating individuals (e.g. committee) > 4) evolution by battling individuals > Pick one. I think I would be MORE nervous with the other > alternatives. We did okay with alternative 2 when C was designed, and the same person is available today (not to say he's interested in actually making the next step in the evolution of C). ...And isn't X3J11 really somewhere between 3 and 4? der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu
daveb@geac.UUCP (David Collier-Brown) (05/18/88)
>In article <11593@ut-sally.UUCP> nather@ut-sally.UUCP (Ed Nather) writes: >>It makes me nervous to realize this evolutionary step was made by a >>committee. In article <7890@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >Whoopie do. What are the alternatives? > 1) stagnation at a functionally inadequate level > 2) evolution by one individual's fiat (who?) > 3) evolution by cooperating individuals (e.g. committee) > 4) evolution by battling individuals >Pick one. I think I would be MORE nervous with the other alternatives. 2a) evolution by a respected author's proposal and committee vetting & acceptance (K&R II?) 2b) evolution by a respected author's proposal and independant, individual acceptance (K&R II?) 4a) evolution into a different, translatable form (specifically C++) 5) replacement by an upwards-compatible low- or medium-level language (C++ perhaps, but its a weak example) 6) replacement in particular problem domains by VHLLs (usually under the guise of 4GLs) In other words, the problem space is larger than the language... --dave (I like 2a and 3) c-b -- David Collier-Brown. {mnetor yunexus utgpu}!geac!daveb Geac Computers Ltd., | "His Majesty made you a major 350 Steelcase Road, | because he believed you would Markham, Ontario. | know when not to obey his orders"
reggie@pdn.UUCP (George W. Leach) (05/19/88)
In article <1110@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) writes: >We did okay with alternative 2 when C was designed, and the same person >is available today (not to say he's interested in actually making the >next step in the evolution of C). ...And isn't X3J11 really somewhere >between 3 and 4? Ah, but Bjarne Stroustrup has with C++!!! -- George W. Leach Paradyne Corporation ..!uunet!pdn!reggie Mail stop LF-207 Phone: (813) 530-2376 P.O. Box 2826 Largo, FL 34649-2826