Pippijn - Projects / Lang / Safe / Ideas / Language / Lambda

Lambda and closures

Syntactically, nested functions are supported, but they are emitted as such and thus depend on the C compiler supporting them. I would like to lift local functions to the global scope and construct closures if necessary. These closures cannot be passed as function pointers to C, but a helper function could be implemented that calls the C function with the closure as environment and a stub invoking the closure as function.

Closures

Normal code calculating the sum of the numbers between from and to, each multiplied by num, thus requiring a closure:

int sum (int from, int to, int (@func) (int i)) {
   int result = 0;
   int inc = from > to ? 1 : -1;
   while (from != to) {
      result += func (from);
      from += inc;
   }
   return result;
}

int sum_of_muls (int from, int to, int num) {
   int mul (int i) { return i * num; }
   return sum (from, to, mul);
}

Would roughly (the names would be mangled somehow) be compiled to:

struct sum_clos1 {
   void *env;
   int (*func) (void *env, int i);
};
int sum (int from, int to, struct sum_clos1 func) {
   int result = 0;
   int inc = from < to ? 1 : -1;
   while (from != to) {
      result += func.func (func.env, from);
      from += inc;
   }
   return result;
}

struct mul_env {
   int num;
};
int mul (void *venv, int i) {
   struct mul_env *env = venv;
   return i * env->num;
}

int sum_of_muls (int from, int to, int num) {
   struct mul_env env;
   struct sum_clos1 clos;

   /* initialise the environment for the function */
   env.num = num;

   /* initialise the closure */
   clos.env = &env;
   clos.func = mul;

   return sum (from, to, clos);
}

This must be done even for simple, non-capturing and global functions, as the called function (in this case sum) cannot know whether it gets a closure or a normal function. It is, however, unfeasible to add a parameter void *env to every function, so passing normal functions as function pointer requires the generation of stubs:

int identity (int i) { return i; }
int identity_sum (int from, int to) {
   return sum (from, to, identity);
}

Has to be translated to:

int identity (int i) { return i; }
int identity_stub (void *env, int i) { return identity (i); }
int identity_sum (int from, int to) {
   struct sum_clos1 clos;

   clos.env = NULL; // could be left out, since it is provably unused
   clos.func = identity_stub;

   return sum (from, to, clos);
}

This will cause a performance hit, but has to be done for uniform handling of global and nested functions.

Passing closures to C

Another problem is that we can no longer trivially pass functions to C.

Use libffi

The libffi library provides a relatively portable way to create dynamically allocated closures. In order to pass a closure to C, we would need to generate a libffi closure wrapper.

// Same as above, but somewhere else, implemented in regular C
extern "C" int sum (int from, int to, int (@func) (int i));

int sum_of_muls (int from, int to, int num) {
   int mul (int i) { return i * num; }
   return sum (from, to, {mul}); // or some other syntax
}

The above code would be compiled to the following:

#include <ffi.h>
#include <sys/mman.h>

extern int sum (int from, int to, int (*func) (int i));

struct mul_env {
   int num;
};
int mul (void *venv, int i) {
   struct mul_env *env = venv;
   return i * env->num;
}

static void
mul_closure_wrapper (ffi_cif *cif, void *rval,
                     void **avals, void *data) {
   *(ffi_arg *)rval = mul (data
      , *(int *)avals[0]
   );
}

int sum_of_muls (int from, int to, int num) {
   struct mul_env env;

   /* initialise the environment for the function */
   env.num = num;

   /* initialise closure */
   {
      ffi_cif cif;
      union {
         ffi_closure *cl;
         int (*fn) (int);
      } clos;

      /* argument types of the generated function */
      ffi_type *arg_types[2] = {
         &ffi_type_sint,
         NULL,
      };

      /* return type of the generated function */
      ffi_type *ret_type = &ffi_type_sint;

      /* allocate executable memory for the closure */
      clos.cl = ffi_closure_alloc ();

      if (ffi_prep_cif (&cif, FFI_DEFAULT_ABI,
                        sizeof arg_types / sizeof *arg_types - 1,
                        ret_type, arg_types) != FFI_OK)
         perror ("ffi_prep_cif");
      if (ffi_prep_closure (clos.cl, &cif, mul_closure_wrapper, &env)
          != FFI_OK)
         perror ("ffi_prep_closure");

      return sum (from, to, clos.fn);
   }
}

All the complexity is handled by libffi. However, the memory allocated by libffi would leak by default, so the garbage collector needs to be aware of that memory and free it using ffi_closure_free. Alternatively, the closure could be placed on the stack on platforms where the stack can be made executable. That way, however, it would become impossible to return closures from functions, which would be quite a substantial loss. On systems where global data is executable, the closure could be put there, but this would make the function non-reentrant (inacceptable) and calling the function would invalidate previously generated closures. The best way to solve this is probably to place closures on the stack and heap-allocate returned closures. This would limit portability to platforms where the stack can be marked executable. The implications of this need to be evaluated.

The question is, do we want to generate FFI closures only for external C interoperability or also for all our own functions. It's probably best to do the latter, as it would immensely simplify C interop (think of passing pointers to functions taking pointers to functions to C). For normal functions and non-capturing lambda expressions, no closures need to be generated, so there is no performance hit for those.

Expect calling convention from the C API

The problem can also be solved by changing the calling convention from closures to plain function pointers when calling C. When we want to pass actual closures to C, it is a little more complicated. The idea presented only works with C functions that take both an environment and a callback. Most sane C APIs luckily do this. Basically, the idea is to just pass the real function along with a generated env pointer.

// Expect C API to allow for user data to be passed.
extern "C" int sum (int from, int to, `t env,
                    int (@func) (`t env, int i));

int sum_of_muls (int from, int to, int num) {
   int mul (int i) { return i * num; }
   return sum (from, to, mul);
}

Passing the mul function would expand to two arguments: the env and the function pointer. It would thus be compiled to:

extern int sum (int from, int to, void *env,
                int (*func) (void *env, int i));

/* compile to mul_env + mul like in the first example */
[...]

int sum_of_muls (int from, int to, int num) {
   /* construct env like in the first example */
   [...]
   return sum (from, to, &env, mul);
}

Lambda expressions

I really don't like the syntax of C++ lambda expressions. I much prefer the C# way, providing type inference and a prettier syntax. Also, why would we have to tell it what variables we're going to use? Oh yeah, because C++ has references. Well, we don't and we're not going to have them, so the proposed syntax is very similar to the C# syntax.

int sum_of_muls (int from, int to, int num) {
   // syntax 1:
   return sum (from, to, i => i * num);
   // syntax 2 (works for multiple arguments):
   return sum (from, to, (i) => i * num;);
   // syntax 3:
   return sum (from, to, i => { return i * num; });
   // syntax 4 (also for multiple arguments):
   return sum (from, to, (i) => { return i * num; });
}

The type of i can easily be inferred with the already implemented type inference engine. The expression is first compiled to a nested function and then handled the same way as regular nested functions are. So basically, they are just syntax sugar, but I think the brevity really worth the extra effort in the implementation.