Ramblings on Lambdas

Before reading, note that I have no idea what I’m talking about and go read ThePhD’s post. Perhaps because of how little idea I have of what I’m talking about, I’m using the terms “closure” and “lambda” interchangeably. (See how the <title> uses one term and the <h1> the other?) See also Jens Gustedt’s proposals for lambdas in C:

A lambda consists of a function and the captures.

int
compute_with(int x, int (*f)(int, void *), void *aux)
{
        int completed_work = (x + 2) * 3;
        return f(completed_work, aux);
}

int
main()
{
        int x = 1;
        auto f = [x](int y) {
                return x + y;
        };
        return compute_with(1, &f, &f);
}

could be desugared to

int
compute_with(int x, int (*f)(int, void *), void *aux)
{
        int completed_work = (x + 2) * 3;
        return f(completed_work, aux);
}

struct __lambda_captures {
        int x;
};

int
__lambda_function(int y, void *__aux)
{
        struct __lambda_captures *__captures = __aux;
        return __captures->x + y;
}

int
main()
{
        int x = 1;
        struct __lambda_captures f = {x};
        return compute_with(1, __lambda_function, &f);
}

That is to say, a pointer to a lambda type (which stores the captures) can be converted implicitly to a pointer to the lambda function.

To have even more fun, make the lambda type explicit.

/* mirroring the syntax for structs and unions, just adding a parameter list before the brace */
lambda f(int y) {
        int x;
};

lambda f f = [x](int y){
        return x + y;
}

I don’t yet see much of a reason to do that. Maybe it’s useful for talking about the memory somehow. Whatever. What you might want to do, though, is make it easier for the callee to accept and call a lambda.

int
compute_with(int x, int ([*]*f)(int))
{
        int completed_work = (x + 2) * 3;
        return f(completed_work);
}

int
main()
{
        int x = 1;
        auto f = [x](int y) {
                return x + y;
        };
        return compute_with(1, &f);
}

Here, the type int ([*]*f)(int) is a pointer to a lambda with unspecified captures and one int parameter returning int. Desugaring would get you:

struct __lambda_pointer {
        int (*__f)(int y, void *);
        void *__captures;
};

int
compute_with(int x, __lambda_pointer f)
{
        int completed_work = (x + 2) * 3;
        return f.__f(completed_work, f.__captures);
}

struct __lambda_captures {
        int x;
};

int
__lambda_function(int y, void *__aux)
{
        struct __lambda_captures *__captures = __aux;
        return __captures->x + y;
}

int
main()
{
        int x = 1;
        struct __lambda_captures f = {x};
        return compute_with(1, (struct __lambda_pointer){__lambda_function, &f});
}

What if I want to pass a simple function?

int
compute_with(int x, int ([*]*f)(int))
{
        int completed_work = (x + 2) * 3;
        return f(completed_work);
}

int
f(int y)
{
        return 42 + y;
}

int
main()
{
        int x = 1;
        return compute_with(1, f);
}

Desugared:

struct __lambda_pointer {
        int (*__f)(int y, void *);
        void *__captures;
};

int
compute_with(int x, __lambda_pointer f)
{
        int completed_work = (x + 2) * 3;
        return f.__f(completed_work, f.__captures);
}

int
f(int y)
{
        return 42 + y;
}

int
main()
{
        int x = 1;
        return compute_with(1, (struct __lambda_pointer){(int (*)(int, void *))f, 0});
}

Huh‽ You see, the System V AMD64 psABI allows you to call functions with more arguments than parameters. For ABIs for which that is not the case:

struct __lambda_pointer {
        int (*__f)(int y, void *);
        void *__captures;
};

int
compute_with(int x, __lambda_pointer f)
{
        int completed_work = (x + 2) * 3;
        return f.__f(completed_work, f.__captures);
}

int
f(int y)
{
        return 42 + y;
}

int
__f_wrapper(int y, void *)
{
        return f(y);
}

int
main()
{
        int x = 1;
        return compute_with(1, (struct __lambda_pointer){__f_wrapper, 0});
}

For all of these, we’d need to define the ABI to be able to interoperate with C and the like. (“With C? This is C!” No, this is Hare. I just used C syntax.)

Frequently asked-about quarrels

How do I allocate memory for the captures?

However you want. The captures of a lambda aren’t all that different from other objects you might want to allocate space for. Store the captures in an automatic variable, store them in dynamically allocated storage. Store them in static storage. Whatever you want.

How are lambdas integrated with the type system?

Pointers to lambdas can be converted to a pointer to the underlying function, with an additional pointer to void as parameter. You can invoke the lambda by calling that function and passing the pointer to the lambda as last argument.

What about C ABI compat?

If a C function takes a function pointer and a pointer to void and passes the pointer to void as last argument to the pointed-to function, you can simply pass the lambda. Trying to make libraries work that have the user-pointer as not-last parameter would make this stuff more complex.

If a Hare function takes a function pointer and an opaque pointer, you can use that function like usual from C.

If a Hare function calls a C function with a pointer to a lambda with unspecified captures, the C function should have as parameter, for lambda return type R and parameters params, the type struct {R (*f)(params, void *); void *c;}.

Similarly, if a Hare function takes a pointer to a lambda with unspecified captures, when calling from C, you should pass a struct {R (*f)(params, void *); void *c;}.