'dynamic' functions

[Gibby Koldenhof]

Hiya,

Terrible subject but I haven't got a better term at the moment.

I've been building up my own library of functionality (all nice conforming
ISO C) for over 6 years and decided to adopt a more OO approach to fit my
needs. Altough I used an OO approach previously for some subparts of the
library it became somewhat difficult to maintain all those parts since they
really are the same thing coded for each part (code duplication). So what I
am coding up is this: a binary tree which in each node contains 2 additional
binary trees, one for data and for functions (methods). Each 'class' defines
a couple of basic methods such as ctor() and dtor() (constructor,
destructor) and a clone() function. Data is nicely abstracted and has all
kinds of flags (hidden, protected, etc) and includes the size, offset in the
structure, additional help, default values, etc. Anyway, nothing new -
people already did this (see for example
http://www.planetpdf.com/mainpage.asp?WebPageID=620
for a nice introduction). So my classes can inherent each other, overload
functions, do some logic on given parameters, it can generate documentation
on it's self, build a gui framework from the parameters, etc. Essentially
your basic OO functionality wich is fairly fast (the tree helps a lot) and
forces me into modular thinking and gives me a flexible way to extend my
library in the future (essentially all algorithms are now in a 'plugin'
format and even dynamicly loaded objects are simple addition)

And now the problem ...

imagine I have a 'image' class - i.e. a class that allocated a bitmap/pixmap
object and return a pointer to that class:

void * image = new("image", 320, 200, 10);

the new() call will parse the parameters and convert them to variadic list
(e.g. the "image" object is found in the tree and ctor() is called with the
va_list) - this is nice since it allows me to use different parameters
depending on the type of object returned from the class.

The problem arises when I would want to call a get_pixel() routine. I could
code it up just as the new() call i.e. using variable argument lists. The
problem that this is way too slow for a function that is called a lot. I
timed it and wrote a little program to compare one getpixel() with variable
arguments and one with non-variable arguments (i.e. int get_pixel(void *
object, int x, int y)) and the va_list version was about twice as slow
(which is natural due to the overhead of the argument parsing of va_arg() in
the function)).

I guess there is no real solution to my problem (but I'm hoping some bright
mind has a good idea!) but what I would want is some way to abstract
functions while still be able to use them in a fast way. There are a couple
of solutions I thought up:

1. just create a function:

int get_pixel(void * object, int x, int y)

e.g.

void * image = new("image", 320, 200, 8);

int the_pixel = get_pixel(image, 100, 100);

Problem: This works but is not very nice from an API point of view. It is
not obvious that get_pixel() belongs to the image class. Of course if the
object is not of type 'image' the function will bail out but that is not
elegant enough for me. Essentially; there is no real relation between
get_pixel() and the image class (the image class doesn't know there is a
get_pixel)

2. create the variable argument list function - this means that *all*
functions (in the whole library which conform to this type of calling)
should be in the same format, say:

void * do_something(void * self, const char * what, va_list * args)

and I would call it (through a wrapper) something like:

do_something(image, "get_pixel", x, y, &result)

Problem: I guess this would work but as mentioned earlier this is way to
slow for functions that get called a lot. The nice things is that I can ask
the class what type of functions it has and therefore automagically create
documentation for each class which helps in preserving the API. Another nice
thing is that overloading these types of functions becomes easy.
Essentially; there now *is* a relation between the class and the function.

3. I could create some pointers to the 'x' and 'y' elements in the class
data structure and loop over them and call do_something(image, "get_pixel")
and retrieve the result with another pointer.

Problem: this is just way nasty - very error prone and it would mean I'd be
adjusting all my loops which would now use the pointer instead of just
integers - it would certainly become more unreadable and hard to change in
the future.

4. Use C++

C++ is not an option. it's a silly language IMHO (please: no flame war)

5. Maybe, just maybe it would be possible to generate a faster function when
needed ... ?

something like:

int (*func)(void * object, int x, int y) = generate_function(image,
"get_pixel");

and then just use func(), e.g.:

int the_pixel = func(image, 100, 100);

But I guess this can't be done (how in the hell should generate_function be
able to return a function that can contain any kind of parameters)

So this is where I'm stuck - I would really like to get some input on
this... maybe there is some way that I didn't think of that will give me an
elegant solution to the problem at hand. The solution should be portable (as
in ISO C89).

Any tips/hints welcome...

Cheers,
Gibby

 

[Malcolm]

imagine I have a 'image' class - i.e. a class that allocated a
bitmap/pixmap object and return a pointer to that class:

Don't call it a "class", to avoid confusion, also don't use C++ keywords as
C identifiers, for the same reason.

void * image = new("image", 320, 200, 10);

The problem arises when I would want to call a get_pixel() routine. > I

could code it up just as the new() call i.e. using variable argument

lists. The problem that this is way too slow for a function that is
called a lot.

There is often a tension between design goals and performance. If you look
at the assembler you will probably find that C functions have a fairly
simple calling convention, and that you can implement signature polymorphism
in assembly code much more efficiently than by using variadic functions.Have you considered calling the get_pixel function via a function pointer?
This would allow to you encapsulate the function in your OO scheme, and only
have a minor performace penalty (probably).

 

[Gibby Koldenhof]

Hi Malcolm,

Thanks for the reply,

Don't call it a "class", to avoid confusion, also don't use C++ keywords as
C identifiers, for the same reason.

I'm still looking for a good term that wasn't sniped by some other OO
language ;-)

could code it up just as the new() call i.e. using variable argument
There is often a tension between design goals and performance. If you look
at the assembler you will probably find that C functions have a fairly
simple calling convention, and that you can implement signature polymorphism
in assembly code much more efficiently than by using variadic functions.

Agreed - there is tradeoff between performance and elagance. I'm just hoping
I can combine the two somehow ...

P.s. I really need to keep the code as portable as possible (it needs to run
on everything from HPUX to windows) - so assembly is not really an option.

Have you considered calling the get_pixel function via a function pointer?
This would allow to you encapsulate the function in your OO scheme, and only
have a minor performace penalty (probably).

Not sure if I follow you here. All functions that are generic for each
'object' are already implemented as a function pointer, e.g. the previously
mentioned ctor() and dtor() for example are in the form of:

typedef struct {

const char * name ;
const char * help ;

void *(*ctor)(void * self, va_list * args);

void * next ; /* overload */

} method_t ;

And then the each method is linked into the binary tree of the
object/class/OO-thing

The question is how should I call the get_pixel() given I get the image
object like this:

void * image = new("image", 320, 200, 8);

Given that abstraction has higher precedence in my design (e.g. the void
*) - indeed I could create a different structure for each object something
like:

image_t * image = new("image", 320, 200, 8);

and then call

image -> get_pixel(100, 100);

This would indeed be fast (I'd guess the same speed as calling a normal
function) but it isn't abstract and would litter my code with all kinds of
structs (which is one of the reasons why I'm now stepping into a more
abstract way of dealing with the functionality - I want to define the
interface to the functionality through a generic object without exposing the
object structure itself).

Is this what you mean? or maybe I've misunderstood you ...?

Cheers,
Gibby

 

[jacob navia]

You can just cache the pointer.

Write a new method that when invoked returns a function pointer to the
given method.

You do

typedef (*void)() FNPTR;

FNPTR GetMethodAddress(object,"get_pixel");

Your method should return a FNPTR, that can be later casted to
anything you want.

typedef int (*pGetPixel)(int,int);

pGetPixel fnptr = (GetPixel)GetMethodAddress(object,"get_pixel");

Then you just use it.
Pixel pix = fnptr(300,200);

This is method caching, something fairly common in
Objective C.

 

[Gibby Koldenhof]

Hi Jacob,

You can just cache the pointer.

Write a new method that when invoked returns a function pointer to the
given method.

You do

typedef (*void)() FNPTR;

FNPTR GetMethodAddress(object,"get_pixel");

Your method should return a FNPTR, that can be later casted to
anything you want.

typedef int (*pGetPixel)(int,int);

pGetPixel fnptr = (GetPixel)GetMethodAddress(object,"get_pixel");

Then you just use it.
Pixel pix = fnptr(300,200);

This is method caching, something fairly common in
Objective C.

Nice. Indeed I didn't think of this - if I'm correct C89 allows me to cast a
function pointer to any [other defined] function pointer in a portable
fashion. Given that when the function is called it is cast back to the
original definition.

I kinda like this way of doing it, there are a couple of downsides though I
guess: here's an example of how I think you intended the example:

/* test.c - compile with gcc -ansi -pedantic -Wall */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef void (*fptr_t)(void);

typedef struct {
const char * name ;
fptr_t func;
} foo_t ;

static int get_pixel(int x, int y)
{
return x+y; /* whatever */
}

static void * wacky_function(const void * const a, double b[23], char **
v[33])
{
return 0;
}

static foo_t foo[] = {
{ "get_pixel", get_pixel },
{ "wacky", wacky_function }
};

/* extern */

fptr_t get_method(const char * name)
{
int i = sizeof foo / sizeof foo[0];

while(i--)
if(0 == strcmp(name, foo.name))
return foo.func;

return NULL ;
}

int main(void)
{
int (*my_get_pixel1)(int x, int y) = get_method("get_pixel");
int (*my_get_pixel2)(int x, int y) = get_method("wacky_function");

printf("%d\n", my_get_pixel1(1,2));

/* the next one will crash */

printf("%d\n", my_get_pixel2(1,2));

return 0;
}


When compiled it gives me:

$ gcc -Wall -pedantic -ansi test.c
test.c:23: warning: initialization from incompatible pointer type
test.c:24: warning: initialization from incompatible pointer type
test.c: In function `main':
test.c:42: warning: initialization from incompatible pointer type
test.c:43: warning: initialization from incompatible pointer type

Which is obvious since I didn't cast anything - anyway, the problem lies in
the wacky_function which will obviously crash. The problem being that
get_method() has no way of telling me what type it is being cast to (C just
doesn't support such constructs) - so it is a tad error prone. Another
(small) problem is the user is required to know the function parameters
before he/she can cast it (and a little typing mistake is likely) - yet I
guess I could fix that by forcing the user to also include the parameters in
the get_method() function as a string to check if they are correct (yet,
this still is a little dangerous).

Anyway, interresting ... I'm going to think about this a little more.
Thanks!

Cheers,
Gibby

 

[Chris Torek]

Nice. Indeed I didn't think of this - if I'm correct C89 allows me to cast a
function pointer to any [other defined] function pointer in a portable
fashion. Given that when the function is called it is cast back to the
original definition.

Yes.

[stripped down from the original example]

typedef void (*fptr_t)(void);

typedef struct {
const char * name ;
fptr_t func;
} foo_t ;

static int get_pixel(int x, int y)
{
return x+y; /* whatever */
}

static void * wacky_function(const void * const a, double b[23], char **
v[33])
{
return 0;
}

static foo_t foo[] = {
{ "get_pixel", get_pixel },
{ "wacky", wacky_function }
};

The two initializations need casts, to change the pointer values
from "int (*)(int, int)" to "void (*)(void)" (for get_pixel()) and
"void *(*)(const void *, double *, char ***)" to "void (*)(void)"
(for wacky_function()).

The changed pointers must then be changed back to their original
types before calling the target functions:

int (*my_get_pixel1)(int x, int y) = get_method("get_pixel");
int (*my_get_pixel2)(int x, int y) = get_method("wacky_function");

These need to become:

int (*my_get_pixel1)(int, int) =
(int (*)(int, int))get_method("get_pixel");
void *(*my_get_pixel2)(const void *, double *, char ***) =
(void *(*)(const void *, double *, char ***)
get_method("wacky_function");

Where do the types come from? Magic, of course.

Ultimately, what you are doing here is choosing between "late" and
"early" binding. Looking up "method names" (functions to call) at
run-time is (very) late binding, while compiling function calls to
direct machine code, as C compilers typically do, is (very) early
binding.

By looking up the method once, and then using the result many times,
you get to compromise: you can defer the lookup until runtime, but
avoid repeating it.

Naturally, the longer you put off the binding, the longer you must
keep any type-checking information around in order to determine
whether my_get_pixel1 and my_get_pixel2 really have types that are
compatible with the actual implementation methods. C compilers
typically discard the all type information between the "compilation"
and "link" phases, and C++ compilers may discard (some of) it but
leave "trace records" in "mangled" link-level names, which can be
used to reconstruct the original type information.

... The problem being that get_method() has no way of telling me
what type it is being cast to (C just doesn't support such
constructs) - so it is a tad error prone. Another
(small) problem is the user is required to know the function parameters
before he/she can cast it (and a little typing mistake is likely) - yet I
guess I could fix that by forcing the user to also include the parameters in
the get_method() function as a string to check if they are correct (yet,
this still is a little dangerous).

This is precisely what you must do: squirrel away the "actual
implementation" type information in some place so that get_method()
can retrieve it, and provide "desired match" type information in
calls to get_method(). You can then even have overloaded methods
-- more than one with the same "function name" -- and match by
type-compatibility. In languages less primitive than C (e.g., Lisp
or Objective-C), you could get the compiler to do this for you
automatically -- but in those languages you would not even have to
implement get_method(), as the languages do it already. Of course,
these abilities come at a price....

(C++ attempts to squirrel away type information at compile time --
via the forementioned "name mangling" -- and in older C++ systems,
this is *all* you got. Fundamentally, however, this is "less
powerful" than full-blown dynamic typing -- and sure enough, today's
C++ has RTTI to implement dynamic typing. This, however, is rather
off-topic for comp.lang.c; comp.programming is probably the place
to go to compare costs and benefits of various language strategies.)

 

[Joona I Palaste]

Don't call it a "class", to avoid confusion, also don't use C++ keywords as
C identifiers, for the same reason.

What is different between that and ERT saying that all C code should be
written so that it would also compile as C++?

--
/-- Joona Palaste ([email protected]) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"A friend of mine is into Voodoo Acupuncture. You don't have to go into her
office. You'll just be walking down the street and... ohh, that's much better!"
- Stephen Wright

 

[Martin Dickopp]

What is different between that and ERT saying that all C code should be
written so that it would also compile as C++?

FWIW, I don't agree with Malcolm here. Although I write both C and C++
code (but never "common subset of both" code), I regularly use `old' and
`new' as variable names in C, and have never been confused by that.

As an example of popular software, the X Window System uses `class' as
an identifier for a structure member (although this usage probably
predates the invention of C++).

Martin

 

[Dan Pop]

As an example of popular software, the X Window System uses `class' as
an identifier for a structure member (although this usage probably
predates the invention of C++).

It's C++ that predates the X Window System.

Dan

 

[Gibby Koldenhof]

Hi Chris,

sorry for my late reply (newserver went down for some reason - thank
god for Google

Nice. Indeed I didn't think of this - if I'm correct C89 allows me to cast a
function pointer to any [other defined] function pointer in a portable
fashion. Given that when the function is called it is cast back to the
original definition.

[snip]

This is precisely what you must do: squirrel away the "actual
implementation" type information in some place so that get_method()
can retrieve it, and provide "desired match" type information in
calls to get_method(). You can then even have overloaded methods
-- more than one with the same "function name" -- and match by
type-compatibility. In languages less primitive than C (e.g., Lisp
or Objective-C), you could get the compiler to do this for you
automatically -- but in those languages you would not even have to
implement get_method(), as the languages do it already. Of course,
these abilities come at a price....

(C++ attempts to squirrel away type information at compile time --
via the forementioned "name mangling" -- and in older C++ systems,
this is *all* you got. Fundamentally, however, this is "less
powerful" than full-blown dynamic typing -- and sure enough, today's
C++ has RTTI to implement dynamic typing. This, however, is rather
off-topic for comp.lang.c; comp.programming is probably the place
to go to compare costs and benefits of various language strategies.)

Thanks for the excellent comments - I've been looking more closely
into Objective C and it seems I'm essentially recoding it but this
time without the strange (which is subjective I guess) syntax of ObjC.

What would be a good place to learn some more about 'parameter
type/name' passing? I looked at comp.programming but that doesn't
really seems to be the place. comp.object seems somewhat more in my
direction. I've been trying to find some decent information on RTTI
(just to understand how that system works) but haven't been able to
google much usefull on it.

Anyway, sorry that this is off-topic but does anybody know a system in
ISO C that already implemented something like this? (I guess that
through some macro's some of the problems can already be fixed - eg. a
macro that expands the function pointer along with a string of it to
be checked) - somebody else must have though about this already. Or
some good docs on how RTTI or an alike system works would be great.

Any tips or urls to material related to parameter type passing would
be great.

Cheer,
Gibby