WingNews logo WingNews GitHub [2]
top | item 4180537

Higher-order programming in C

141 points| sthatipamala | 13 years ago |vedantk.tumblr.com | reply

45 comments

order
[+] caladri|13 years ago|reply
For the set of features you have, with most calling conventions on most platforms you don't need to synthesize all that. You could simply have your apply function be written in assembly and handle setting up the parameters fetching them from memory.

That also isn't higher-order programming as such. Can you create new functions from doing that? There are ways to compose functions in C by hand, but the distinction is that it cannot be done elegantly. (One could always just do higher-order programming in C by constructing an abstract syntax tree, after all.)

A good first effort in that you did correctly handle calling functions without requiring them to fetch their arguments in an unusual way, which is what most people would try at first. With a varargs apply function, you can handle the case of passing values larger than a register and passing pointers without having to cast them to a list, too. Consider the case of an apply function which takes an unsigned integer as the size of the following argument. If it's zero, then the argument list is finished. Otherwise, it then fetches an argument of that size from the va_list and goes on to the next one. So then your apply function is slightly uglier (int j = 42; apply(printf, sizeof (const char ), "Hello, %s! %u\n", sizeof (const char ), "world"), sizeof j, j, 0) but perhaps more flexible, and at least avoids relying on a few nasty implicit casts.

Also, function pointers should not necessarily be cast implicitly to void *, but on only a few architectures are function pointers so strange that you'll have any trouble with your approach.

As it is, you could even avoid writing or generating any assembly by just having the apply routine be a static inline function that does a switch on the argument count and then casts the function pointer to a function pointer that takes the right number of arguments. The compiler could do constant propagation for the number of arguments and you'd have little overhead in your function calls. You couldn't handle arbitrarily-large argument lists, but it would work pretty well.

Keep at it!

[+] huhtenberg|13 years ago|reply 

  +-----------------------------------------------------------+
  |                                                           |
  |  C has support for dynamic typing (in the form of void*)  |
  |                                                           |
  +-----------------------------------------------------------+
A quotable thinker.
[+] chrisohara|13 years ago|reply
Why are people so scared of void*? Are there any VM's that don't resort to some form of pointer tagging when implementing dynamic typing?
[+] Xcelerate|13 years ago|reply
Haha I can't stop cracking up! Although it reminds me of when I wrote a ray-tracer in high school. Every reflection distribution function took some kind of void* structure and did something unique with it.
[+] praptak|13 years ago|reply
Ok, so instead of "method not implemented" you get memory corruption. Big deal.
[+] ogoffart|13 years ago|reply
I made it simpler (and slightly more portable ;-) ) :

    typedef void* (*f)();
    extern void* apply(void* func, void** args, size_t argc) {
        switch (argc) {
            case 0: return  ((f)(func))();
            case 1: return  ((f)(func))(args[0]);
            case 2: return  ((f)(func))(args[0], args[1]);
            case 3: return  ((f)(func))(args[0], args[1], args[2]);
            case 4: return  ((f)(func))(args[0], args[1], args[2], args[3]);
            case 5: return  ((f)(func))(args[0], args[1], args[2], args[3], args[4]);
            case 6: return  ((f)(func))(args[0], args[1], args[2], args[3], args[4], args[5]);
            case 7: return  ((f)(func))(args[0], args[1], args[2], args[3], args[4], args[5], args[6]);
            case 8: return  ((f)(func))(args[0], args[1], args[2], args[3], args[4], args[5], args[6], args[7]);
            case 9: return  ((f)(func))(args[0], args[1], args[2], args[3], args[4], args[5], args[6], args[7], args[8]);
            /*...*/
        }
    }
[+] tspiteri|13 years ago|reply
I don't get the point. Why not use the generic function type?

    void *(*routine)(void *)
If you have a function already, just create a simple wrapper once. In the code shown, the wrapping has to be done by the caller of apply().

And this apply() doesn't work on all functions anyway. Casting an array of long into an array of void* makes quite a few assumptions and is very limited. What would you do if your original function takes a struct as an argument?

[+] mappu|13 years ago|reply
I'd quite like to use bind() in C / nasm for my current project. I think you can use a similar approach - create an executable area on the heap that pushes an extra parameter and jmps to the target function, then just return a function pointer to it.

EDIT: there might be a problem with arranging the stack parameters - if you use call on the target, then you're pushing a return address onto the stack, which messes up the arguments. But if you simply jmp, then neither the caller or callee know exactly how to clean up the stack when the function returns... hmm. I guess you could permanently reserve a register for this shimming but that's hardly an elegant solution.

[+] forgotusername|13 years ago|reply
The ability to cast a function pointer to a regular pointer is an implementation behavior (supported on every machine you'd want to use, but nonetheless it's not standard C)
[+] zvrba|13 years ago|reply
That's undefined behavior meaning that anything might happen, including appearing to work [most of the time]. C allows casts between two data pointers and between two function pointers, but not cast that cross the data/function boundary.

Any cast that crosses function/data boundary must go through suitably large integer type; UB results if you cast a pointer to a too-small integer type. See my other comment in this thread for a reference to the standard.

[+] MichaelGG|13 years ago|reply
That's interesting to know. Is there no general data type that's guaranteed to hold a function pointer?
[+] Daniel_Newby|13 years ago|reply
There are quite a few Harvard architecture microcontrollers and DSPs for which this is not true. (At least for some values of "want to use" ;-).
[+] crb3|13 years ago|reply
The blog's github interface is annoying: in order to save-to-disk more than just the opening paragraphs in Firefox, I had to bring up Web Developer's View Generated Source function and save the result of that. Not cool for anybody who prefers to study offline.
[+] drucken|13 years ago|reply
Strange. I had zero trouble saving the blog to disk with Firefox on a Windows PC.

- it works with both an old generation of Firefox (3.x) and a post 3.x version.

- it correctly opens with the code, in both FF versions as well as IE.

- NoScript also correctly blocks and unblocks the code depending on what access you give to github.com and tumblr.com.

So, not sure what you are seeing, but I am unable to replicate it. As you can probably guess, I am just as sensitive to these saving glitches when they occur as you are too... :)

[+] zvrba|13 years ago|reply
Sigh, if the program is relying on undefined behavior [like this one], it's not C. Plus, gcc has __builtin_apply as extension.
[+] daeken|13 years ago|reply
This is not undefined behavior. It's implementation specific behavior -- there's a huge difference. If you specify the calling convention for your functions, this is 100% deterministic and predictable. Nothing at all wrong with this approach.
[+] comex|13 years ago|reply
Incidentally, if you want "real" higher-order programming in C, take a look at blocks (Apple).
[+] dchest|13 years ago|reply
...if you want "real" higher-order programming in "C"...