Higher-order programming in C

http://vedantk.tumblr.com/post/26182854460/higher-order-programming-in-c

by sthatipamala • 14 years ago

141 45 14 years ago

vedantk.tumblr.com

ori_b• 14 years ago

If you ever want to do this in the real world, look at libffi: http://sourceware.org/libffi/

aklofas• 14 years ago

There is a macro way to do this. It involves lots of magic and beating the preprocessor with a two-by-four: https://groups.google.com/forum/?fromgroups#!topic/comp.lang...

Go down this hole with caution.

bowyakka• 14 years ago

I often want to beat the pre-processor with a two-by-four

caladri2• 14 years ago

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!

davvid• 14 years ago

Like this? https://github.com/davvid/libapply

unittest.c shows how it can be used: https://github.com/davvid/libapply/blob/master/unittest.c

mappu2• 14 years ago

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.

vedantk• 14 years ago

I think the callee expects the return address in %rbp, and by System V convention will pull certain arguments from above %ebp on the stack.

This might not help, but it's an interesting article on stack frames for all interested: http://eli.thegreenplace.net/2011/09/06/stack-frame-layout-o...

mappu2• 14 years ago

Looks like fastcall, or any convention on x86_64.

I think you can do bound functions if you do callee-cleanup, then your intermediate bound trampolines can just jmp and you don't end up with (too many) weird problems. But it means that the final return address ends up at the bottom of the stack, rather than at the top, like it would with a conventional push/call system.

In any case it looks like cdecl is out of the question.

Some further discussion in a slightly different context, if you're interested: http://stackoverflow.com/questions/11271848/implementing-bou...

maybird• 14 years ago

This makes me wish I could use "PROT_WRITE | PROT_EXEC" with mmap() on iOS.

buzzert• 14 years ago

You actually can by exploiting a bug in the code signing check in the kernel! http://books.google.com/books?id=1kDcjKcz9GwC&lpg=PT92&#...

huhtenberg2• 14 years ago

  +-----------------------------------------------------------+
  |                                                           |
  |  C has support for dynamic typing (in the form of void*)  |
  |                                                           |
  +-----------------------------------------------------------+

A quotable thinker.

Xcelerate• 14 years ago

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.

bengl3rt• 14 years ago

Funny, mine was the exact same.

chrisohara• 14 years ago

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?

pmelendez• 14 years ago

I don't think people is scared of void*. However, it is pretty easy to introduce memory corruption bugs when it is used in big projects.

I find very wise to avoid it when it is not necessary or when there is an equivalent safer alternative (e.g C++ templates if available and applicable).

In this case however, is not only completely fine but I don't think there is a better way to do it.

BTW, my favourite phrase of the article:

"“… Why do this?” Because I can, of course."

The truly spirit of a hacker :)

huhtenberg2• 14 years ago

Who are these "people" exactly?

praptak• 14 years ago

Ok, so instead of "method not implemented" you get memory corruption. Big deal.

zvrba5• 14 years ago

Sigh, if the program is relying on undefined behavior [like this one], it's not C. Plus, gcc has __builtin_apply as extension.

daeken2• 14 years ago

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.

zvrba5• 14 years ago

Not undefined behavior, really? Run it on a 64-bit SPARC system and see if it works. Not to mention that this implementation is dog-slow (two rather slow syscalls [mmap/munmap] for each apply-invocation).

tspiteri• 14 years ago

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?

crb33• 14 years ago

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.

dbaupp• 14 years ago

Does something like instapaper help?

http://www.instapaper.com/text?u=http://vedantk.tumblr.com/p...

crb33• 14 years ago

Apparently not; sorry.

drucken• 14 years ago

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... :)

crb33• 14 years ago

Firefox 3.5.6 on Mepis Linux 8.0 here; NoScript permissions open to github and tumbler otherwise I wouldn't see code onscreen fwiw, tnx for feedback

forgotusername2• 14 years ago

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)

Daniel_Newby2• 14 years ago

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" ;-).

forgotusername2• 14 years ago

I've never written code for these architectures, but my assumption was that a modern GCC will happily bodge this for you in software, so its probably only super ancient/exotic stuff for which the lack of ability to cast applies

MichaelGG• 14 years ago

That's interesting to know. Is there no general data type that's guaranteed to hold a function pointer?

caladri2• 14 years ago

Only function pointer types. An indirect function call on some architecture, for example, could require that when one makes an indirect call one sets up several registers in addition to jumping to a particular location in memory, and none of the registers that need to be set up can be derived from the jump target. So in practice your function pointers would need to actually be structures containing those register values and the jump target. Or you might need to pass around a tuple of target and calling convention, although the C standard limits the ways you could implement that (namely by requiring that function pointers cast to and from other function pointer types will compare as equal, and will still work when they are cast to the correct type.)

zvrba5• 14 years ago

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.

comex• 14 years ago

Incidentally, if you want "real" higher-order programming in C, take a look at blocks (Apple).

dchest• 14 years ago

...if you want "real" higher-order programming in "C"...

SoftwareMaven• 14 years ago

You're just not looking at the problem objectively...

Seriously, though, is there a reason the Objective C blocks wouldn't work in C, just substituting functions for methods?

ogoffart• 14 years ago

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]);
            /*...*/
        }
    }

Higher-order programming in C

Related Stories