In article <11************ **********@i42g 2000cwa.googleg roups.com>,
ballpointpenthi ef <ba************ ***@yahoo.co.uk wrote:
>[Thanks Dave Vandervies, that was the most useful piece of information
I've ever read on USENET.]
There is only one conclusion that can be drawn from that: You have
obviously not read anything by Chris Torek.
>I've studied your answer, and I now understand one way of setting this
up. I've chucked some simple code below.
....and I have a few comments on it that I'll throw in inline.
>One thing: What if we needed to play with an arbritrary number of
base_types?
Then you have to be a bit more clever.
The obvious ways to handle that are to use generics (like C++ templates)
or to have dynamic typing (like in Scheme or Smalltalk). Unfortunately,
C has neither of those, and trying to re-create them is usually (but
not always) the wrong solution.
(One of the big benefits of C is that you *can* build any high-level
abstraction you want to use[1]; one of the big problems of C is that
you *need* to build any high-level abstraction you want to use.)
A slightly less obvious way, but one that's probably more general and
better-suited to C in general, is to give the type-agnostic code a void
pointer that points at your data along with the size of the data, and let
the callback functions (which know what they're working with) convert the
void pointer they get back to a pointer to the appropriate type of data.
qsort and bsearch use this; the prototype for qsort is
--------
void qsort(void *base, size_t nmemb, size_t size,
int(*compar)(co nst void *, const void *));
--------
and the implementation will do something equivalent to this:
--------
void qsort(void *base, size_t nmemb, size_t size,
int(*compar)(co nst void *, const void *))
{
/*Get a pointer we can do arithmetic on*/
char *base_c=base;
/*...do sort stuff, including...*/
if((*compar)(ba se_c+i*size,bas e_c+j*size) 0)
__swap_memory(b ase_c+i*size,ba se_c+j*size,siz e);
}
--------
(so the type-agnostic code only needs to be told how big the data
elements are so it can throw them around, and lets caller-provided code
do everything else with them).
A fully type-agnostic map with this type of interface would look something
like this:
--------
void map(const void *vfrom,size_t from_size,void *vto,size_t to_size,
size_t nelem,
void (*trans_func)(c onst void *from,void *to,void *cookie),
void *cookie)
{
const char *from=vfrom;
unsigned char *to=vto;
size_t i;
for(i=0;i<nelem ;i++)
{
trans_func(from +i*from_size,to +i*to_size,cook ie);
}
}
--------
and the transform function would look like this:
--------
void frob(const void *vfrom,void *to,void *vcookie)
{
const type1 *from=vfrom;
type2 *to=vto;
cookie_type *cookie=vcookie ;
/*Now do stuff with *from (and optionally *cookie) and
stuff the results into *to
*/
}
--------
Note that to do things this way you'd still need a different transform
function for each type you use, even if you're doing the same operations
on them - an add-seventeen-to-int function would probably not give you
the results you want if you ask map to invoke it on your array of doubles.
Note also that this doesn't do any type-checking on the callback you
give it. If you're careful and know what you're doing, that's probably
not a major lack, but it does mean that if you get it wrong the compiler
will happily generate code that will silently corrupt your data (or,
if you're lucky, crash your program) instead of complaining that you've
gotten something wrong. (Of course, if you're not careful or don't
know what you're doing, you probably shouldn't be trying to program a
computer at all, but that doesn't seem to stop a lot of people.)
There seems to be no 'means of combination' (which I have
learnt is important off of those online MIT lectures.)
I'm not quite sure what you mean by "means of combination".
If you mean being able to use different aggregate types, you do that
the same way as you'd do it with different basic types - either by
writing one version for every type or by applying some cleverness to
avoid having to do all that work (either by getting a code generator to
do it for you or by avoiding it altogether).
If you mean composing functions, you can do that with fake-closures the
same way you'd do it with real closures; the equivalent of this:
--------
(define (anti-filter lis pred)
(filter lis (lambda (x) (not (pred x)))))
--------
would be something like this:
--------
struct not_cookie
{
void *orig_cookie;
_Bool (*orig_pred)(ba sic_type *in,void *cookie);
};
static _Bool not(basic_type *in, void *vcookie)
{
struct not_cookie *cookie=vcookie ;
return !(*(cookie->orig_pred))(in ,cookie->orig_cookie) ;
}
size_t anti_filter(con st basic_type *src, basic_type *dst, void *ext_var,
_Bool (*pred_func)(ba sic_type *, void *), size_t arr_len)
{
struct not_cookie nc;
nc.orig_cookie= ext_var;
nc.orig_pred=pr ed_func;
return filter(src,dst, &nc,not,arr_len );
}
--------
(and the relative length of these two examples is why some people will
try to tell you you need closures and anonymous functions to usefully
use higher-order functions. They're wrong, but they do have a point
that's worth paying attention to.)
>It's probably easy to guess that I've got zero real-world programming
experience.
For having zero real-world programming experience, your code is Rather
Good. I assume you have at least some non-real-world experience?
(The differences aren't always as big as big as a lot of people will
try to tell you they are.)
>Here's proof that I read the code:
[most code snipped, leaving only the parts I have comments on]
>#include <stdbool.h>
Note that <stdbool.hand _Bool are new in C99. It's worth keeping in
mind that C99 implementations are still rather rare in the wild, so for
maximal portability you probably still want to avoid C99isms.
(Whether or not this is a disgraceful state of affairs for a standard
that's been around for seven years is a discussion that I try to avoid
getting into, but the pragmatic consequences aren't affected by your
position on that.)
If you use int for values with boolean meaning, most C programmers will
have no trouble figuring out that that's what you meant, and they'll
also be able to compile it with their C90 compilers (which is generaly
considered a Good Thing).
>void map(const basic_type *src, basic_type *dst, void *ext_var,
basic_type (*trans_func)(b asic_type *, void *), size_t arr_len)
There's not really any reason to give the callback function a pointer to
its input instead of just the data object (unless your basic_data type
is big, in which case you might be better off just passing a pointer,
but then you probably want to do something comparable for dst).
If you are passing the pointer, you should probably make it const.
So the type of trans_func is probably wrong here, and should either be
basic_type (*trans_func)(b asic_type,void *)
or
basic_type (*trans_func)(c onst basic_type *,void *)
depending on whether you really want to pass a pointer or not.
>{
for (int i=0; i<arr_len; i++)
{
dst[i] = trans_func(&src[i], ext_var);
}
}
Not all newsreaders play nicely with tabs, and not all the ones that do
handle them sensibly use the same width, so if you want your code lined
up nicely (especially for anything other than indents at the beginning
of the line) you're probably better off converting them to spaces before
you post.
>size_t filter(const basic_type *src, basic_type *dst, void *ext_var,
_Bool (*pred_func)(ba sic_type *, void *), size_t arr_len)
{
basic_type *node_in = src;
basic_type *node_out = dst;
Since you're not using these for anything, there's not much point
keeping them around. (The caller probably needs the original values,
but it has its own copy.)
> size_t count = 0;
for (int i=0; i<arr_len; i++)
{
if (pred_func(src, ext_var))
{
*dst++ = *src++;
count++;
}
else src++;
}
return count;
}
It seems clearer to me to do this as array indexing instead of walking
the pointers through. Array indexing lets you keep the output count
and the dst-position in the same place, and also the iteration count
and the src-position.
(That's a matter of taste and style, though; a moderately clever optimizer
should produce equivalent output either way. A C++ programmer would
probably find your version easier to understand, too, since it more
closely matches the C++ iterator idioms.)
dave
[1] Well, some of them are hard enough that it ends up being less
painful to just do without. (Sometime when you're feeling
masochistic, try implementing fully general coroutines without
invoking implementation-specific knowledge. But even that *can*
be done if you don't mind explicitly managing your call-stack frames
(and if you do it right you even get first-class continuations out
of the deal).)
--
Dave Vandervies
dj******@csclub .uwaterloo.ca
There are two kinds of program structures: Those that I can easily handle
in my head without the use of paper, and those that wouldn't fit on any
kind of paper anyway. --Christian Bau in comp.lang.c
