rfg@NCD.COM (Ron Guilmette) (12/22/90)
In article <1990Dec20.114821@roadster.bellcore.com> garnett@thumper.bellcore.com writes: + +I'm P***ed! (excuse the language!) Grrrr.... + +This is one stupid thing: +char *bsearch (const char*, char*, unsigned, int, int (*)(...)) ); + +It should be like this: +void *bsearch(const void *, void *, unsigned, unsigned, + int(*)(const void *, const void *)); + +Do they mean to tell me that I really have to deal with stdargs/varargs when +I want to write a quick compare routine for my data type!? + +Does anyone else see this is a VERY STUPID move on Sun's Part? + +HEY SUN: LISTENING? + DON'T RESIST THE ANSI C SPEC! void*s are NICE. You're 'cc' even + supports them (but does not use them). How about fixing these + header files?? huh?? I think that you are blaming Sun for a problem in the language which is not their fault. (Actually, I think that this is an outstanding problem in both C++ and in ANSI C.) The problem arises for all sorts of functions designed to accept function pointers. I seem to recall asking Bjarne about this problem some long time ago with respect to the UNIX(tm) qsort() function. Both qsort() and bsearch() have a similar need to be fed a pointer to a function which itself takes two parameters of type pointer-to-T, where the type T is the same for both of the two parameters (but is never actually the type `void'). For ANSI C, your proposed soultion would just about work, but not quite. Here is the problem. I have some existing ANSI C code which looks like: #include <some_include.h> typedef /* ??? */ T; int compar (const T* left, const T* right); ... bsearch (key, base, nel, sizeof (*key), compar) ... int compar (const T* left, const T* right) { /* ... */ } Now if we put the declaration of bsearch() that you have suggested into <some_include.h> then my code (which used to compile cleanly) would cease compiling. That would make me get mad, and then I'd be cursing you instead of you cursing Sun. Now I know what you are going to tell me. You are going to suggest that I start to get *really* type-safe, and that I re-write my compar() routine to look like: int compar (const void *__left, const void*__right) { const T* left = (T*) __left; const T* right = (T*) __right; /* ... */ } But what if that compare routine is stashed away in a precompiled library? In other words, what if I just plain don't have the option of changing it? Now I'm REALLY going to get mad at you! In C++ the situation is even worse because in C++ I don't even have the option of rewriting my compar() function as shown above! Why? Well, in C++ it is always legal to cast any pointer-to-T to a void* however for some T's it is illegal to cast backwards from a void* to a T*. Thus, in cases like qsort() and bsearch() the ultimate effect of all of C++'s rules (intended to enforce type-safety) is to force us to totally abandon type-safety for the pointer-to-function argument(s)!!! There are two possible solution to this problem. The first is to leave things just as they are. That means that there will be no cross-checking whatsoever on the types of the parameters which the (user-supplied) compar() function accepts (or even on the number of parameters which it expects). The second solution is more radical. It involves enhancing the language so that we can express the idea of a type which has a name but which is otherwise undefined (and undefinable). One possibility would be: typedef ? T; // a generic unknown/unknowable type void *bsearch(const void *, const T *, unsigned, unsigned, int(*)(const T *, const T *)); In this case, the argument matching rules would have to be made smart enough to insist on proper matching all the way down to the point where we hit the mystery type T. In this case, the benefit (relative to the current loose-typing situation) would be that: comparison functions would be forced to take exactly two parameters each parameter of each comparison function would be forced to be of some pointer type each parameter of each comparison function would be forced to be of some pointer-to-CONST type both parameters of any given compare function would be forced to be of the same type the type of the second argument to bsearch would be forced to be the same as the type of the parameters to the comparison function (and vise-versa) Obviously, we could add one hell of a lot of type-safety (for situations like these) with only a very minor enhancement to the language. But wait! Before you rush off to phone your local implementor to demand the addition of this feature, be advised that even this (cute?) idea will not entirely solve the problems associated with functions like qsort() and bsearch(). To understand the *REAL* problem, just try writing your own implementation of qsort() entirely in ANSI C (or C++). Now try porting it to some machine for which there is more than one representation for pointer values (e.g. DG Eclipse, HP 3000). Keep in mind that on machine like this there is actually some shifting involved when you assign a void* to an int* (and vise-versa). In short, IT IS IMPOSSIBLE TO WRITE QSORT() ENTIRELY IN ANSI C OR IN C++ IN SUCH A WAY THAT IT IS COMPLETELY PORTABLE. This is the *real* problem. Perhaps the only truly clean solution (in C++) is to recognize qsort() and bsearch() for what they really are (i.e. generic functions) and to implement them accordingly (as templates). Any volunteers? -- // Ron Guilmette - C++ Entomologist // Internet: rfg@ncd.com uucp: ...uunet!lupine!rfg // Motto: If it sticks, force it. If it breaks, it needed replacing anyway.
rfg@NCD.COM (Ron Guilmette) (12/25/90)
In article <246@salt.bellcore.com> garnett@shera.UUCP (Michael Garnett) writes: +In article <3069@lupine.NCD.COM> rfg@NCD.COM (Ron Guilmette) writes: +>In article <1990Dec20.114821@roadster.bellcore.com> garnett@thumper.bellcore.com writes: +>+This is one stupid thing: +>+char *bsearch (const char*, char*, unsigned, int, int (*)(...)) ); +>+ +>+It should be like this: +>+void *bsearch(const void *, void *, unsigned, unsigned, +>+ int(*)(const void *, const void *)); +>+ +> +> +>For ANSI C, your proposed soultion would just about work, but not quite. +>Here is the problem. +>I have some existing ANSI C code which looks like: +> #include <some_include.h> +> typedef /* ??? */ T; +> int compar (const T* left, const T* right); +> ... bsearch (key, base, nel, sizeof (*key), compar) ... +> int compar (const T* left, const T* right) +> { +> /* ... */ +> } +Q: I have used a "fully ANSI compliant" C compiler (I uassumed they were not + lying). The ANSI C prototype for bsearch looks just like the one I + suggested (and verifyed from the ObjectWorks\C++ search.h). ANSI C + will accept the compar function as is -- C++ will not. For C++ I *must* + accept const void*'s. This means that strcmp is not a valid compare + function for bsearch in C++, but it *IS* in ANSI C. (Hers's the Q): + Is my ANSI C compiler lenient? Am I correct that C++ will NOT accept + compare (const T*, const T*) ? Yes. Your "ANSI" C compiler is being too lenient. This would be unacceptable to most C++ compilers. +Q: If is is "always legal to cast any pointer-to-T to a void*" then why + won't C++ accept compar(const T*, const T*)? (Assuming that my compiler + was correct in telling me that it wouldn't) Why does C++ allow + a call of the form 'free(T*)' when free has a parameter profile of + 'free(void*)'? I see no difference in these 2 cases. Both involve + accepting T* where a void* is wanted. You ask "why?" The answer is "Because those are the rules". There are important differences in the two cases you cite. +I have not checked this further, but SUN C++ will not accept a compar +function with any other prototype than 'int compar(...)'. If the '...' in +the compar prototype is meant to keep C++ from checking the type(s) of the +parameters to compar, SUN C++ is wrong. Right? Hummm... I guess that you have a good point there. In fact, now that you've forced me to think about it, I'd have to say that there simply is no 100% correct way to declare qsort() and/or bsearch() in C++. I guess that given C++'s current (very strict) rules regarding type- matching for formal parameters of "pointer-to-function" types, the closest approximation that you could get that might possibly work for C++ (without causing all sorts of compile-time errors) would be: void *bsearch(const void *, void *, unsigned, unsigned, const void *); In this case we are avoiding the problem of getting the types to perfectly match on the final ("pointer-to-function" type) argument altogether. Unfortunately, the only way that we can do this is to fake out the compiler and to tell it that the final argument is a void* rather than a pointer-to-function. Now for the bad news... even this (cruddy?) solution may not work because in both ANSI C and C++ it is illegal to convert (either explicitly or implicitly) a pointer-to-function type value to a void* type value. So we are back to square one. As I said, you simply cannot correctly declare qsort() and bsearch() in C++. I hope the the x3j16 Library Working Group takes note of this problem and that either (a) they mandate template versions of these (generic) functions, or else (b) that they at least encourage implementors to avoid the mistake of putting (bogus) declarations of these sorts of things into the header files that they ship with their products. +I changed the prototype in SUN'c search.h to the one that I suggested, +and (as I expected) my code compiled again. My compar must accept +2 const void*'s, but I'm used to this from 2 other compilers. That solution is probably the best stop-gap available, but there are two problems: 1) Your code may cease to work if you ever try to port it to certain kinds of machines which have multiple flavors of pointers, and 2) You are now forced to declare all of your comparison routines to accept a pair of void* parameters. Then, within each of these comparison functions, you must convert each of these two void* pointers to some other (useful) type of pointer. At the very least this is an annoyance, but at the very worst, it will not even be legal to do that for some pointer types in C++! +SUMMARY: + is 't1 (*)(...)' supposed to suspend the type-checking of parameter type + matching in pointer-to-function parameters? OR should the compiler + force the actual parameter to have a 't1 (*)(...)' parameter profile? I believe that it's the latter. It is my understanding that the following two types are NOT compatible in C++: typedef void (*elipsis_function_pointer_type) (...); typedef void (*two_arg_function_pointer_type) (void *, void*); I believe that this is a good and necessary rule (i.e. that these must be treated as being INCOMPATIBLE TYPES) and that it should stay in the langauge. + If the 't1 (*)(...)' is forced, then what about ANSI's stdargs where + one needs at least one parameter to find the beginning of the variable + arguments? Good question. C++ (unlike ANSI C) allows both regular (non-member) functions and member functions to be declared with only an ellipsis as the formal argument list. I'm not sure that this was such a hot idea (because it can make stdarg usage problematic) but I believe that this was permitted in C++ in order to help people to transition from (and to interface to) old C programs. + I like the idea of a pointer to an unknown/undeterminable type, but why + can't void* serve this purpose? It can't because void* is an honest to goodness actual type as far as the C++ (and ANSI C) type matching rules are concerned. In particular, the following is REQUIRED to get an error in both C++ and in ANSI C: void (*p1) (void*, void*); void (*p2) (int*, int*); ... p1 = p2; /* must get a type-mismatch error */ What I suggested was allowing: typedef ? T; void (*p3) (T*, T*); ... p3 = p2; /* OK - matches as far as possible */ After some consideration however, I think that I should retract that suggestion and just hope that the really *BEST* solution (i.e. template definitions for qsort and bsearch) gets implemented someday. -- // Ron Guilmette - C++ Entomologist // Internet: rfg@ncd.com uucp: ...uunet!lupine!rfg // Motto: If it sticks, force it. If it breaks, it needed replacing anyway.
shankar@hpclscu.cup.hp.com (Shankar Unni) (01/22/91)
Ron Guilmette writes: > +P.S. regarding the "laxness" of ANSI C compilers: many such compilers, > +recognizing the need for such a usage, are deliberately permissive > +on a mismatch of function pointer arguments, if the mismatch is between > +a "T *" and a "void *". > > Oh, yea?!?!?! Name two! I dare you! Who makes these sloppy implementations? Sorry to duplicate my reply, but my notesposter does not allow me to cross-post anything.. As I replied in comp.lang.c++, this was slightly sloppy wording on my part. Of course, ANSI C implementations are required to "diagnose" such mismatches. What's left up to the compiler is the severity of the messages for such transgressions. That's where the "usability factor" comes in.. ----- Shankar Unni E-Mail: Hewlett-Packard California Language Lab. Internet: shankar@hpda.hp.com Phone : (408) 447-5797 UUCP: ...!hplabs!hpda!shankar