Is there a way to do currying in C?

Question

Say I have a pointer to a function _stack_push(stack* stk, void* el). I want to be able to call curry(_stack_push, my_stack) and get back a function that just takes void* el. I couldn't think of a way to do it, since C doesn't allow runtime function definition, but I know there are far cleverer people than me here :). Any ideas?

Krefetz

Answer 1

I found a paper by Laurent Dami that discusses currying in C/C++/Objective-C:

More Functional Reusability in C/C++/Objective-c with Curried Functions

Of interest to how it is implemented in C:

Our current implementation uses existing C constructs to add the currying mechanism. This was much easier to do than modifying the compiler, and is sufficient to prove the interest of currying. This approach has two drawbacks, however. First, curried functions cannot be type-checked, and therefore require careful use in order to avoid errors. Second, the curry function cannot know the size of its arguments, and counts them as if they were all of the size of an integer.

The paper does not contain an implementation of curry(), but you can imagine how it is implemented using function pointers and variadic functions.

Blocky

+1 great find, and I like "Although we did not run extensive tests, we can estimate a curried function call to be approximately 60 times slower than a normal function call." – Margheritamargi

(I like it because sometimes you need something very badly, and a solution that runs only 60 times slower is infinitely better than no solution at all.) – Margheritamargi

Thanks, I found the link on the Wikipedia page "Currying": en.wikipedia.org/wiki/Curried_function – Blocky

Variadic functions were actually the first thing that popped into my mind when I read the question and before scrolling down. Nice to see that my hunch was a decent one. – Islamism

Sadly that paper is not downloadable in 2021. – Bilocular

@BasileStarynkevitch: I found an alternative link here: docplayer.net/… – Encomiastic

In 2024 the document seems to be this one – Sippet

Answer 2

GCC provides an extension for the definition of nested functions. Although this is not ISO standard C, this may be of some interest, since it enables to answer the question quite conveniently. In short, nested function can access the parent function local variables and pointers to them can be returned by the parent function as well.

Here is a short, self-explanatory example:

#include <stdio.h>

typedef int (*two_var_func) (int, int);
typedef int (*one_var_func) (int);

int add_int (int a, int b) {
    return a+b;
}

one_var_func partial (two_var_func f, int a) {
    int g (int b) {
        return f (a, b);
    }
    return g;
}

int main (void) {
    int a = 1;
    int b = 2;
    printf ("%d\n", add_int (a, b));
    printf ("%d\n", partial (add_int, a) (b));
}

There is however a limitation to this construction. If you keep a pointer to the resulting function, as in

one_var_func u = partial (add_int, a);

the function call u(0) may result in an unexpected behaviour, as the variable a which u reads was destroyed just after partial terminated.

See this section of GCC's documentation.

Churchwarden

From the manual (under the link that you have provided): "If you try to call the nested function through its address after the containing function has exited, all hell will break loose." – Expiatory

If you're already restricting yourself to GCC, you could use statement expressions to postpone hell till the calling function exits (i.e: will work for everything but asynchronous callbacks): gist.github.com/a3f/2729c1248d0f2ee39b4a – Headcloth

"There is however a limitation": that limitation makes this solution unusable, as the whole purpose of currying is to call the resulting function after it has been returned. – Ruffled

Answer 3

The good news: There is a way to write a program that will do this in standard ANSI C, without using any compiler-specific features. (In particular, it does not require gcc's nested function support.)

The bad news: It requires creating little bits of executable code to serve as trampoline functions at runtime. This means that the implementation will be dependent on:

• The processor instruction set
• The ABI (in particular, the function calling convention)
• The operating system's ability to mark data as executable

The best news: If you just need to do this in real, production code… you should use the closure API of libffi. It's permissively-licensed and contains careful, flexible implementations for many platforms and ABIs.

---

If you're still here, you want to nerd out and understand how to implement this “from scratch.”

The program below demonstrates how to curry a 2-parameter function into a 1-parameter function in C, given…

• x86-64 processor architecture
• System V ABI
• Linux operating system

It is based on the “Trampoline Illustration” from Infectious Executable Stacks, but with the trampoline structure stored on the heap (via malloc) rather on than the stack. This is much safer because it means we don't have to disable the compiler's stack execution protection (no gcc -Wl,-z,execstack).

It uses the Linux mprotect system call to make the heap object executable.

The essence of the program is that it takes a pointer to a two-parameter function (uint32_t (*fp2)(uint32_t a, uint32_t b)) and converts it to a pointer to a one-parameter function (uint32_t (*fp1)(uint32_t a)) which invokes fp1 with a pre-set value for the parameter b. It does this by creating little 3-instruction trampoline functions:

movl $imm32, %esi  /* $imm32 filled in with the value of 'b' */
movq %imm64, %rax  /* $imm64 filled in with the value of 'fp2' */
jmpq *%rax

With the values of b and fp2 stitched into it appropriately, a pointer to the block of memory containing these 3 instructions can be used as the one-parameter function pointer fp1 precisely as described above. That's because it obeys the x86-64 System V calling convention, in which one-parameter functions receive their first parameter in the %edi/%rdi register, and two-parameter functions receive the second parameter in the %esi/%rsi register. In this case, the one-parameter trampoline function receives its uint32_t parameter in %edi, then fills in the value of the second uint32_t parameter in %esi, then jumps directly to the “real” two-parameter function which expects its two parameter in exactly those registers.

Here's the complete working code, which I've also put up on GitHub at dlenski/c-curry:

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

#include <unistd.h>
#include <sys/mman.h>
#include <stdint.h>

#define PAGE_START(P) ((uintptr_t)(P) & ~(pagesize-1))
#define PAGE_END(P)   (((uintptr_t)(P) + pagesize - 1) & ~(pagesize-1))

/* x86-64 ABI passes parameters in rdi, rsi, rdx, rcx, r8, r9
 * (https://wiki.osdev.org/System_V_ABI), and return value
 * goes in %rax.
 *
 * Binary format of useful opcodes:
 *
 *       0xbf, [le32] = movl $imm32, %edi (1st param)
 *       0xbe, [le32] = movl $imm32, %esi (2nd param)
 *       0xba, [le32] = movl $imm32, %edx (3rd param)
 *       0xb9, [le32] = movl $imm32, %ecx (4rd param)
 *       0xb8, [le32] = movl $imm32, %eax
 * 0x48, 0x__, [le64] = movq $imm64, %r__
 *       0xff, 0xe0   = jmpq *%rax
 */

typedef uint32_t (*one_param_func_ptr)(uint32_t);
one_param_func_ptr curry_two_param_func(
    void *two_param_func, 
    uint32_t second_param)
{
    /* This is a template for calling a "curried" version of 
     * uint32_t (*two_param_func)(uint32_t a, uint32_t b),
     * using the Linux x86-64 ABI. The curried version can be
     * treated as uint32_t (*one_param_func)(uint32_t a).
     */
    uintptr_t fp = (uintptr_t)two_param_func;
    uint8_t template[] = {
        0xbe, 0, 0, 0, 0,                                   /* movl $imm32, %esi */
        0x48, 0xb8, fp >>  0, fp >>  8, fp >> 16, fp >> 24, /* movq fp, %rax */
                    fp >> 32, fp >> 40, fp >> 48, fp >> 56,
        0xff, 0xe0                                          /* jmpq *%rax */
    };
    
    /* Now we create a copy of this template on the HEAP, and
     * fill in the second param. */
    uint8_t *buf = malloc(sizeof(template));
    if (!buf)
        return NULL;
    
    memcpy(buf, template, sizeof(template));
    buf[1] = second_param >> 0;
    buf[2] = second_param >> 8;
    buf[3] = second_param >> 16;
    buf[4] = second_param >> 24;
    
    /* We do NOT want to make the stack executable,
     * but we NEED the heap-allocated buf to be executable.
     * Compiling with 'gcc -Wl,-z,execstack' would do BOTH.
     *
     * This appears to be the right way to only make a heap object executable:
     *   https://mcmap.net/q/373761/-why-is-execstack-required-to-execute-code-on-the-heap
     */
    uintptr_t pagesize = sysconf(_SC_PAGE_SIZE);
    mprotect((void *)PAGE_START(buf),
             PAGE_END(buf + sizeof(template)) - PAGE_START(buf),
             PROT_READ|PROT_WRITE|PROT_EXEC);
    
    return (one_param_func_ptr)buf;
}

/********************************************/

int print_both_params(int a, int b)
{
    printf("Called with a=%d, b=%d\n", a, b);
    return a+b;
}

int main(int argc, char **argv)
{
    one_param_func_ptr print_both_params_b4 =
        curry_two_param_func(print_both_params, 4);
    one_param_func_ptr print_both_params_b256 = 
        curry_two_param_func(print_both_params, 256);
    
    print_both_params_b4(3);    // "Called with a=3, b=4"
    print_both_params_b256(6);  // "Called with a=6, b=256"

    return 0;
}

Engels

very nice, out of curiosity, what was your motivation when you built this function? – Proletarian

I was trying to figure out if there was a way to pass arbitrary user data into a callback function where the API provided no support for this (a substantial design flaw). I got into quite a rabbit hole, and ended up writing this. Turns out that libffi has an API for this, which works across many platforms and APIs. Still, this was fun to figure out and explore… – Engels

Answer 4

Here's my first guess off the top of my head (may not be the best solution).

The curry function could allocate some memory off the heap, and put the parameter values into that heap-allocated memory. The trick is then for the returned function to know that it's supposed to read its parameters from that heap-allocated memory. If there's only one instance of the returned function, then a pointer to those parameters can be stored in a singleton/global. Otherwise if there's more than one instance of the returned function, then I think that curry needs to create each instance of the returned function in the heap-allocated memory (by writing opcodes like "get that pointer to the parameters", "push the parameters", and "invoke that other function" into the heap-allocated memory). In that case you need to beware whether allocated memory is executable, and maybe (I don't know) even be afraid of anti-virus programs.

Hinshaw

Answer 5

since C doesn't allow runtime function definition

This is in principle true in standard C. Read n1570 for details.

However, in practice it can be false. Consider

• on POSIX systems (e.g. Linux) generating some C code at runtime in some temporary file /tmp/generated1234.c file which defines some void genfoo1234(void) function, compiling that file (e.g. using a recent GCC compiler as gcc -O -fPIC -Wall -shared /tmp/generated1234.c -o /tmp/generated1234.so) then using dlopen(3) on /tmp/generated1234.so then dlsym(3) on genfoo1234 on the handle returned by dlopen to get a function pointer). By personal experience, such an approach is today (in 2021, on Linux laptops) fast enough even for interactive usage (if each temporary generated C file has a few hundred lines of C code).

• on x86, x86-64, ARM processors using some machine code generating library like GNU lightning, libgccjit (or in C++, asmjit)

In practice, you would generate code for a closure (grouping a function pointer with closed values) and use it as a callback.

A related point is garbage collection, so read the garbage collection handbook.

Consider also embedding some existing interpreter in your application, like Lua, GNU guile, Python, etc....

Study, at least for inspiration, the source code of these interpreters.

Quenniec's book Lisp in small pieces and the Dragon book are worthwhile reading. Both explain practical issues and implementation details

See also the __builtin_call_with_static_chain in recent GCC compilers (in 2021).

Bilocular

This is a great answer, full of cool information and ideas. Thank you! – Denationalize

Answer 6

Here is an approach to doing currying in C. While this sample application is using the C++ iostream output for convenience it is all C style coding.

The key to this approach is to have a struct which contains an array of unsigned char and this array is used to build up an argument list for a function. The function to be called is specified as one of the arguments that are pushed into the array. The resulting array is then given to a proxy function which actually executes the closure of function and arguments.

In this example I provide a couple of type specific helper functions to push arguments into the closure as well as a generic pushMem() function to push a struct or other memory region.

This approach does require allocation of a memory area that is then used for the closure data. It would be best to use the stack for this memory area so that memory management does not become a problem. There is also the issue as to how large to make the closure storage memory area so that there is sufficient room for the necessary arguments but not so large that excess space in memory or on the stack is taken up by unused space.

I have experimented with the use of a slightly differently defined closure struct which contains an additional field for the currently used size of the array used to store the closure data. This different closure struct is then used with a modified helper functions which removes the need for the user of the helper functions to maintain their own unsigned char * pointer when adding arguments to the closure struct.

Notes and caveats

The following example program was compiled and tested with Visual Studio 2013. The output from this sample is provided below. I am not sure about the use of GCC or CLANG with this example nor am I sure as to issues that may be seen with a 64 bit compiler as I am under the impression that my testing was with a 32 bit application. Also this would approach would only seem to work with functions that use the standard C declaration in which the calling function handles popping the arguments from the stack after the callee returns (__cdecl and not __stdcall in Windows API).

Since we are building the argument list at run time and then calling a proxy function, this approach does not allow the compiler to perform a check on arguments. This could lead to mysterious failures due to mismatched parameter types which the compiler is unable to flag.

Example application

// currytest.cpp : Defines the entry point for the console application.
//
// while this is C++ usng the standard C++ I/O it is written in
// a C style so as to demonstrate use of currying with C.
//
// this example shows implementing a closure with C function pointers
// along with arguments of various kinds. the closure is then used
// to provide a saved state which is used with other functions.

#include "stdafx.h"
#include <iostream>

// notation is used in the following defines
//   - tname is used to represent type name for a type
//   - cname is used to represent the closure type name that was defined
//   - fname is used to represent the function name

#define CLOSURE_MEM(tname,size) \
    typedef struct { \
        union { \
            void *p; \
            unsigned char args[size + sizeof(void *)]; \
        }; \
    } tname;

#define CLOSURE_ARGS(x,cname) *(cname *)(((x).args) + sizeof(void *))
#define CLOSURE_FTYPE(tname,m) ((tname((*)(...)))(m).p)

// define a call function that calls specified function, fname,
// that returns a value of type tname using the specified closure
// type of cname.
#define CLOSURE_FUNC(fname, tname, cname) \
    tname fname (cname m) \
    { \
        return ((tname((*)(...)))m.p)(CLOSURE_ARGS(m,cname)); \
    }

// helper functions that are used to build the closure.
unsigned char * pushPtr(unsigned char *pDest, void *ptr) {
    *(void * *)pDest = ptr;
    return pDest + sizeof(void *);
}

unsigned char * pushInt(unsigned char *pDest, int i) {
    *(int *)pDest = i;
    return pDest + sizeof(int);
}

unsigned char * pushFloat(unsigned char *pDest, float f) {
    *(float *)pDest = f;
    return pDest + sizeof(float);
}

unsigned char * pushMem(unsigned char *pDest, void *p, size_t nBytes) {
    memcpy(pDest, p, nBytes);
    return pDest + nBytes;
}


// test functions that show they are called and have arguments.
int func1(int i, int j) {
    std::cout << " func1 " << i << " " << j;
    return i + 2;
}

int func2(int i) {
    std::cout << " func2 " << i;
    return i + 3;
}

float func3(float f) {
    std::cout << " func3 " << f;
    return f + 2.0;
}

float func4(float f) {
    std::cout << " func4 " << f;
    return f + 3.0;
}

typedef struct {
    int i;
    char *xc;
} XStruct;

int func21(XStruct m) {
    std::cout << " fun21 " << m.i << " " << m.xc << ";";
    return m.i + 10;
}

int func22(XStruct *m) {
    std::cout << " fun22 " << m->i << " " << m->xc << ";";
    return m->i + 10;
}

void func33(int i, int j) {
    std::cout << " func33 " << i << " " << j;
}

// define my closure memory type along with the function(s) using it.

CLOSURE_MEM(XClosure2, 256)           // closure memory
CLOSURE_FUNC(doit, int, XClosure2)    // closure execution for return int
CLOSURE_FUNC(doitf, float, XClosure2) // closure execution for return float
CLOSURE_FUNC(doitv, void, XClosure2)  // closure execution for void

// a function that accepts a closure, adds additional arguments and
// then calls the function that is saved as part of the closure.
int doitargs(XClosure2 *m, unsigned char *x, int a1, int a2) {
    x = pushInt(x, a1);
    x = pushInt(x, a2);
    return CLOSURE_FTYPE(int, *m)(CLOSURE_ARGS(*m, XClosure2));
}

int _tmain(int argc, _TCHAR* argv[])
{
    int k = func2(func1(3, 23));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    XClosure2 myClosure;
    unsigned char *x;

    x = myClosure.args;
    x = pushPtr(x, func1);
    x = pushInt(x, 4);
    x = pushInt(x, 20);
    k = func2(doit(myClosure));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    x = myClosure.args;
    x = pushPtr(x, func1);
    x = pushInt(x, 4);
    pushInt(x, 24);               // call with second arg 24
    k = func2(doit(myClosure));   // first call with closure
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;
    pushInt(x, 14);              // call with second arg now 14 not 24
    k = func2(doit(myClosure));  // second call with closure, different value
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    k = func2(doitargs(&myClosure, x, 16, 0));  // second call with closure, different value
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    // further explorations of other argument types

    XStruct xs;

    xs.i = 8;
    xs.xc = "take 1";
    x = myClosure.args;
    x = pushPtr(x, func21);
    x = pushMem(x, &xs, sizeof(xs));
    k = func2(doit(myClosure));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    xs.i = 11;
    xs.xc = "take 2";
    x = myClosure.args;
    x = pushPtr(x, func22);
    x = pushPtr(x, &xs);
    k = func2(doit(myClosure));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    x = myClosure.args;
    x = pushPtr(x, func3);
    x = pushFloat(x, 4.0);

    float dof = func4(doitf(myClosure));
    std::cout << " main (" << __LINE__ << ") " << dof << std::endl;

    x = myClosure.args;
    x = pushPtr(x, func33);
    x = pushInt(x, 6);
    x = pushInt(x, 26);
    doitv(myClosure);
    std::cout << " main (" << __LINE__ << ") " << std::endl;

    return 0;
}

Test output

Output from this sample program. The number in parenthesis is the line number in the main where the function call is made.

 func1 3 23 func2 5 main (118) 8
 func1 4 20 func2 6 main (128) 9
 func1 4 24 func2 6 main (135) 9
 func1 4 14 func2 6 main (138) 9
 func1 4 16 func2 6 main (141) 9
 fun21 8 take 1; func2 18 main (153) 21
 fun22 11 take 2; func2 21 main (161) 24
 func3 4 func4 6 main (168) 9
 func33 6 26 main (175)

Aldose