Есть ли способ сделать currying в C?

Ответ 1

Я нашел статью Лорана Дами, в которой обсуждается каррирование в C/С++/ Objective-C:

Более функциональное повторное использование в C/С++/ Objective-c с помощью Curried Functions

Интерес к тому, как он реализован в C:

В нашей текущей реализации используются существующие конструкторы C, чтобы добавить механизм currying. Это было намного легче сделать, чем модифицировать компилятор, и этого достаточно, чтобы доказать интерес к карри. Однако этот подход имеет два недостатка. Во-первых, функции, зависящие от карри, не могут быть проверены на соответствие типам и поэтому требуют тщательного использования, чтобы избежать ошибок. Во-вторых, функция curry не может знать размер своих аргументов и считает их так, как если бы они были размером целого числа.

В документе не содержится реализация curry(), но вы можете себе представить, как она реализована с помощью указателей функций и вариативные функции.

Ответ 2

GCC предоставляет расширение для определения вложенных функций. Хотя это не стандарт ISO C, это может представлять определенный интерес, поскольку он позволяет легко ответить на вопрос. Короче говоря, вложенная функция может обращаться к родительской функции. Локальные переменные и указатели на них могут быть возвращены родительской функцией.

Вот короткий, самоочевидный пример:

#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));
}

Однако для этой конструкции существует ограничение. Если вы сохраните указатель на результирующую функцию, как в

one_var_func u = partial (add_int, a);

вызов функции u(0) может привести к неожиданному поведению, поскольку переменная a, которая читает u, была уничтожена сразу после завершения partial.

Смотрите этот раздел документации GCC.

Ответ 3

Здесь мое первое предположение от верхней части моей головы (может быть, не лучшее решение).

Функция curry может выделить некоторую память из кучи и поместить значения параметров в эту память, выделенную кучей. Трюк заключается в том, что возвращаемая функция знает, что она должна читать свои параметры из этой памяти, выделенной кучей. Если есть только один экземпляр возвращаемой функции, то указатель на эти параметры может быть сохранен в singleton/global. В противном случае, если имеется более одного экземпляра возвращаемой функции, я думаю, что карри должен создать каждый экземпляр возвращаемой функции в памяти, выделенной кучей (путем написания опкодов типа "получить этот указатель на параметры", "нажимать параметры" и "вызвать эту другую функцию" в память, выделенную кучей). В этом случае вам нужно остерегаться, является ли выделенная память исполняемой, и, может быть, (я не знаю) даже боюсь антивирусных программ.

Ответ 4

Вот подход к выполнению currying в C. Хотя это примерное приложение использует вывод iostream С++ для удобства, это все кодирование стиля C.

Ключом к этому подходу является наличие struct, который содержит массив unsigned char, и этот массив используется для создания списка аргументов для функции. Вызываемая функция задается как один из аргументов, которые вставляются в массив. Получившийся массив затем передается прокси-функции, которая фактически выполняет закрытие функции и аргументов.

В этом примере я предоставляю пару специальных вспомогательных функций типа для ввода аргументов в закрытие, а также универсальную функцию pushMem() для нажатия struct или другой области памяти.

Этот подход требует выделения области памяти, которая затем используется для данных закрытия. Было бы лучше использовать стек для этой области памяти, чтобы управление памятью не стало проблемой. Также возникает вопрос о том, насколько большой размер области памяти для хранения закрывается, так что имеется достаточное количество необходимых аргументов, но не такое большое, что лишнее пространство в памяти или в стеке занято неиспользуемым пространством.

Я экспериментировал с использованием немного иначе определенной структуры замыкания, которая содержит дополнительное поле для используемого в настоящее время размера массива, используемого для хранения данных закрытия. Затем эта разная структура замыкания используется с модифицированными вспомогательными функциями, что устраняет необходимость в том, чтобы пользователь вспомогательных функций сохранял свой собственный указатель unsigned char * при добавлении аргументов в структуру замыкания.

Примечания и оговорки

Следующая примерная программа была скомпилирована и протестирована с помощью Visual Studio 2013. Результаты этого примера приведены ниже. Я не уверен в использовании GCC или CLANG с этим примером, и я не уверен в проблемах, которые могут быть замечены с 64-битным компилятором, поскольку у меня возникает впечатление, что мое тестирование было с 32-разрядным приложением. Также это будет работать только с функциями, использующими стандартное объявление C, в котором вызывающая функция обрабатывает вызовы из стека после возвращения вызываемого абонента (__cdecl, а не __stdcall в Windows API).

Поскольку мы создаем список аргументов во время выполнения и затем вызываем прокси-функцию, этот подход не позволяет компилятору выполнить проверку аргументов. Это может привести к таинственным отказам из-за несогласованных типов параметров, которые компилятор не может определить.

Пример приложения

// 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;
}

Тестируемый выход

Вывод из этой примерной программы. Число в скобках - это номер строки в главном, где выполняется вызов функции.

 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)