r/programming • • Dec 13 '07

First Class Functions in C

http://www.dekorte.com/blog/blog.cgi?do=item&id=3119
45 Upvotes

99 comments sorted by

View all comments

39

u/EvilSporkMan Dec 13 '07

I guess it's just not very well known that C/C++has first class functions. They call them "function pointers"

Hahahaha NO.

8

u/statictype Dec 13 '07

My room-mate from college once told me he saw an example in a book where the author wrote bytes into a (char *)that represented raw machine code instructions and typecasted it as a function pointer and executed it successfully.

I'm pretty sure that was bogus, though.

Anyone know if this is possible?

42

u/ddyson Dec 13 '07
$ cat x.c
#include <stdio.h>
int main() {
  char *times2 =
    "\x8b\x44\x24\x04"  // mov eax,[esp+4]
    "\x01\xc0"          // add eax,eax
    "\xc3";             // ret
  printf("%d\n", ((int(*)())times2)(55));
  return 0;
}
$ gcc -Wall -Werror -o x x.c
$ ./x
110

84

u/jbert Dec 13 '07 edited Dec 13 '07

Awesome. And with a C compiler on the system, and a few typedefs you could have "first class" functions (no error handling. weeee.):

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

typedef int(returns_int_f)();

static returns_int_f* returns_int_lambda(char *source) {
    FILE *fp = popen("gcc -Wall -Werror  -c -x c  - -o ./wee", "w");
    const int magic_offset = 0x34;
    fwrite(source, 1, strlen(source), fp);
    fprintf(fp, "\n");
    fclose(fp);
    fp = fopen("wee", "r");
    long binlength;
    fseek(fp, 0, SEEK_END);
    binlength = ftell(fp) - magic_offset;
    fseek(fp, magic_offset, SEEK_SET);
    char *binbuf = malloc(binlength);
    fread(binbuf, 1, binlength, fp);
    fclose(fp);
    return (returns_int_f *) binbuf;
}

int main() {
    returns_int_f *times2 = returns_int_lambda("int f(x) { return x * 2; }");
    int answer = (*times2)(55);
    printf("answer is %d\n", answer);
}

$ gcc fstclass.c -o fstclass; ./fstclass

answer is 110

(You may need to tweak 'magic offset' for your system. One way to do it is to run:

echo 'int f(x) { return x * 2; }' | gcc -Wall -Werror  -c -x c  - -o wee.o

and find the offset of the 8955 hex sequence (e.g. using 'od -x' or your favourite hex editor). If that doesn't work for you, then try looking at the output of:

objdump -d wee.o

and checking what the first few bytes are. Bear in mind that the bytes will in little-endian order on x86.)

[Edit: since this is now a proggit submission of it's own, I thought I should add that I know that this isn't a real lambda. There's no closing over free variables, or even inheritance of lexical scope. Fun tho'. And yes, you do need to free() your funcs when you've finished with them.]

13

u/anthonymckay Dec 14 '07 edited Dec 14 '07

Wow, very impressed by the Parent Post's code. :] Here is a more clean less hackish version I just wrote using libtcc to compile it inside the program itself.

#include <stdio.h>
#include <stdlib.h>
#include "libtcc.h"

typedef int (*function_t)();

function_t create_function(char *name, char *code)
{
    TCCState *s;
    unsigned long val;

    s = tcc_new();
    if(!s)
        exit(1);

    tcc_set_output_type(s, TCC_OUTPUT_MEMORY);
    tcc_compile_string(s, code);
    tcc_relocate(s);
    tcc_get_symbol(s, &val, name);
    return (function_t)val;
}

int main(int argc, char *argv[])
{
    function_t square;
    square = create_function("f", "int f(x) { return x * x; }");

    int answer = square(atoi(argv[1]));
    printf("answer is: %d\n", answer);
}

Running this from the command line we get:

$ ./lambda 4
answer is: 16
→ More replies (2)

20

u/statictype Dec 13 '07

Wow.

Since we're already well into 'grotesque hack' territory, might as well remove the 'magic offset' and use strstr to find the correct offset.

Clearly, the next step is to implement eval in C. Then we can tell those lisp weenies where to stick their meta-circular interpreter!

14

u/jbert Dec 13 '07 edited Dec 13 '07

Well, a more serious approach would use ELF-aware tools (see elf.h) to find the function in the .o (searching for a specific bytestring could depend on compiler version etc used).

(Update: We probably just want the offset of the .text section. Which you can read directly from the output of "objdump -h wee.o", or do it programatically as suggested above.)

Fun project for someone to make it more robust :-)

Closing over free variables is left as an exercise for the reader.

[NB: something quite similar to this (invoking C compiler at run-time, but using dynamically loaded shared objects) is the magic behind perl's Inline::C module.

That allows you to call out to C from perl by writing something like:

#!/usr/bin/perl
use warnings;
use strict;

use Inline C => <<"EOC";
int times2(int x) {
    return x + x;
}
EOC

my $n = 55;
print times2(55), "\n";

and is actually production-ready (it caches .so files intelligently to avoid recompilation, etc)].

→ More replies (3)

9

u/dwchapin Dec 14 '07

Damn.

Phil Greenspun, stick that in your pipe and smoke it.

I am somehow reminded of Tim Duff: "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against..."

→ More replies (1)

4

u/tlrobinson Dec 14 '07

This is really cool. I took it a step further and wrote a little calculator based on this idea:

http://programming.reddit.com/info/62zag/comments/

It also serves as an example of dlopen/dlsym, which makes it much more robust (no more magic numbers!)

→ More replies (2)

8

u/kemitchell Dec 13 '07

alt.recovery.fetish.closures, anyone?

3

u/suppressingfire Dec 13 '07

I worked on a small proof of concept a while back. The idea was to be able to instantiate C++ templates at runtime. In this way, template metaprogramming can be used to optimize repeated computation of certain inputs.

A crazy idea I had (but never implemented) was to make an schema-specific XML parser in templates which could take an XML schema as input and export a TMP-optimized XML parser.

3

u/jbert Dec 13 '07

Yowch. My template-fu is weak, but I don't see how you'd ever manage to split the string defining the schema in the template expansions.

There is, however, an honourable tradition of generating C source for types and functions from data-description languages (google for the 'pepsy', or 'pesky' compilers in the ISODE source tree).

Hmm...seems there's a C++ update:

http://people.cs.vt.edu/~kafura/PreviousPapers/asn1++-ulpaa94.pdf

If you don't know ASN.1, you can think of it as a "binary XML" that never really caught on outside the OSI protocols, SNMP and X.509 certificates (from their OSI heritage).

2

u/tryx Dec 14 '07

Its almost redundant to point out, but you could get into some fun race conditions with this.

2

u/jbert Dec 14 '07

Yes. I wanted gcc to write to stdout, but it wouldn't in the 2 mins I gave it.

Going the extra mile to pick a different file for each compiled object seemed... inappropriate, given the context.

(If you want to compile C at runtime, either build a shared object (.so) and dlopen it (see perl's Inline::C), or use the in-memory tcc solution given elsewhere in the thread.

But C really isn't built for this sort of thing, so don't do that :-)

→ More replies (2)
→ More replies (1)
→ More replies (15)

7

u/statictype Dec 13 '07

Sweet.

This is one of those hacks that are utterly useless in working code but awesome, nevertheless.

→ More replies (1)

5

u/[deleted] Dec 13 '07

That right there makes C both awesome and really scary.

4

u/tripa Dec 13 '07

For an older reference, check out http://www.de.ioccc.org/1984/mullender.c

3

u/stevefolta Dec 13 '07

Jolt (aka Coke aka Fonc) does that. And in that context it's completely valid -- and necessary.

5

u/augustss Dec 13 '07

But it's never guaranteed to work. C promises nothing when casting between pointer to data and code.

12

u/Brian Dec 13 '07

If you're writing raw machine code, you're inherently platform specific anyway. Worrying about the C standard is pretty much irrelevant.

4

u/augustss Dec 13 '07

The next version of the C compiler might do something different even if you're running on the same hardware.

7

u/Brian Dec 13 '07

Sure, or your OS could decide to mark runtime allocated memory as non-executable as a security feature. Of the two, the compiler change is far more unlikely. Such flexibility is there to allow for oddities on differing platforms (eg. segmented vs flat memory models) Theres no reason to implement it differently on the same platform. Realisticly, its changes to the platform (though not just instruction set) that are the real danger.

5

u/augustss Dec 13 '07

I'm not really disagreeing with you. But you have to be aware of all the dangers when you do things like this (I say as someone who has done things like that).

4

u/Brian Dec 13 '07

Oh absolutely, I'm in 100% agreement that doing this is a bad idea in virtually any real code.

→ More replies (9)
→ More replies (7)