How is this familiar function implemented in C?

Question

Consider the following code segment written in S-expr notation:

(lambda (x) (lambda (y) (+ x y)))

or in Javascript:

function(x) { return function(y) { return x+y; }; }

How do I write this in C?

Answer 1

This is difficult to do in C, since it relies on closures. With C you have to pass an explicit context, so you might end up with something like this.

#include <stdio.h>

struct closure {
    int saved_x;
    int (*function)(struct closure, int);
};

int second_half_add(struct closure context, int y) {
    return context.saved_x + y;
}

struct closure curried_add(int x) {
    struct closure ret;
    ret.saved_x = x;
    ret.function = second_half_add;
    return ret;
}

int main() {
    struct closure context = curried_add(3);
    printf("%d\n", context.function(context, 4));
}

It's really ugly, and you lose almost all benefit of currying, but it is possible

Answer 2

C doesn't have first class functions, so the answer is: Nohow.

Answer 3

This depends on what you mean when you say “C.”

Supposing that you really want to get something back which you can call by simple function application, ISO C makes such a thing pretty hard to do—probably impossible if you really want to stay within the confounds of the standard and not use some low-level assembly tricks.

Clang, however, implements non-standard support for closures that actually makes such things possible. Using this feature, your example could be implemented in the following way:

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

int (^plus(int x))() {
  return Block_copy(^(int y) {
    return x + y;
  });
}

int main() {
  int (^plus2)(int) = plus(2);
  printf("2 + 3 = %d\n", plus2(3));
  Block_release(plus2);
  return EXIT_SUCCESS;
}

Answer 4

Well, you can do it. It's not pretty. It goes something like this:

typedef int (*intfuncint)(Env*, int);

// this is the "closure" block
typedef struct Env {
  int x;
  intfuncint f;
} env_t;

// this is the internal function
int sum(Env* me, int y){return me->x + y;}

// this is the external function
Env* foo(int x){
  Env* result = malloc(sizeof(*result));
  result->x = x;
  result->f = sum;
  return result;
}

Using it to get the sum of 3 and 5 would look something like this:

Env* p = foo(3); p->f(p, 5)

Answer 5

You can't write it in c, for several reasons, mostly that c just doesn't work like that.

If this is a homework question your teacher may say otherwise... something like:

struct functor {
  int x;
  functiontype* f;
}

int dofunctor(functor*, y) { ... }

But it generalises so poorly that it's not worth doing.

You can write it in some other c-like languages - such as perl.

You can do something like this in c++ - see the following answer:

C++ Functors - and their uses