Containers, Templates, Lambda Expressions in C

by bysin on 2010-10-12
Programming

Not many people know this, but the C language (with the help of gcc extensions) can support templates and lambda expressions.

I know I’m going to get emails / comments about how I butchered the C language. So let me start out with a word of caution, this is for educational use only, and is not intended to be used in production code.

We start off with a little known gcc extension that allows functions to be declared inside of functions. These functions are normally only accessible from inside the scope in which it was declared.

void parent() {
    int child() {
        return 42;
    }
    printf("%d\n", child());
}

Theres also a gcc extension that allows you to nest instructions inside of scope operators, where the instructions are evaluated and returned.

void parent() {
    int a = ({ int n = 17; n += 25; n; });
    printf("%d\n", a);
}

If we were to combine these two examples we can have a scope operator return a function pointer to a nested function. The result would look very similar to a lambda expression, but in C! FYI: You can use the dollar sign as a symbol name.

#include <stdio.h>

void eval(int (*func)(char*)) {
	func("lambda");
	func("expression");
}

void main() {
	int (*func)(char*);
	func = ({ int $(char *str){ printf("Test: %s\n", str); } $; });
	eval(func);
}

And here is the expected output:

Test: lambda
Test: expression

So here’s where it gets tricky. You can create a template class in C if you combine lambda expressions with structures and an incredibly large macro (what Mat Anger likes to call Uber-Macros ©2010).

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

typedef struct stack {
    int (*push)(struct stack*, ...);
    void *(*pop)(struct stack*);
    void *ptr;
    int length;
} *stack;

#define stack_new(T)                                                        \
    ({                                                                      \
        stack __n;                                                          \
        if ((__n = calloc(sizeof(struct stack), 1))) {                      \
                                                                            \
            __n->push = (void*)({int $(stack n, T p) {                      \
                T *np;                                                      \
                if (!(np = realloc(n->ptr, sizeof(*np) * (n->length + 1)))) \
                    return 0;                                               \
                np[n->length++] = p;                                        \
                n->ptr = np;                                                \
                return 1;                                                   \
            }$;});                                                          \
                                                                            \
            __n->pop = (void*)({T *$(stack n){                              \
                T *np;                                                      \
                if (!n->length)                                             \
                    return (T*) 0;                                          \
                np = n->ptr;                                                \
                return &np[--n->length];                                    \
            }$;});                                                          \
                                                                            \
        }                                                                   \
        __n;                                                                \
    })

void main() {
    stack p;
    int *num;
    char **str;

    p = stack_new(int);
    p->push(p, 42);
    p->push(p, 666);
    printf("%d\n", *(num = p->pop(p)));
    printf("%d\n", *(num = p->pop(p)));

    p = stack_new(char*);
    p->push(p, "template");
    p->push(p, "class");
    printf("%s\n", *(str = p->pop(p)));
    printf("%s\n", *(str = p->pop(p)));

}

As you can see, we created a pseudo-template that took a type, and it generated function pointers based upon the type. Here is the expected output:

666
42
class
template

Using those techniques I was able to create a small container library for C. It has map, list, and array objects that can be used in a syntax almost as easy as its C++ counterpart:

c_object n;

n = c_array_new(int);
c_insert(n, 5);
c_insert(n, 512);
c_insert(n, -125);
c_foreach(n, t_int) {
	printf("%d\n", t_int);
}
c_free(n);
c_object n;
c_pair(char*, int) t_map;

n = c_map_new(char*, int);
c_append(n, "test", 4);
c_append(n, "foo", 12345);
c_append(n, "bar", -423);
printf("foo is most definitely %d\n", c_at(n, "foo"));
c_erase(n, "foo");
c_foreach(n, t_map) {
	printf("%s = %d\n", t_map.left, t_map.right);
}
c_free(n);

Click here to download the Container Source Code

{ 5 comments }

Love4Boobies October 12, 2010 at 23:26

main returns int.

Ed October 13, 2010 at 13:34

Ritchie is just retired, not dead!

cgp October 13, 2010 at 18:41

He’s not dead yet!

cgp October 13, 2010 at 18:41

That’s the joke.

cgp October 13, 2010 at 18:42

Doh.

Comments on this entry are closed.

{ 1 trackback }

Next post: