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

Question

Скажем, у меня есть указатель на функцию _stack_push (stack * stk, void * el) . Я хочу иметь возможность вызывать curry (_stack_push, my_stack) и возвращать функцию, которая просто принимает void * el . Я не мог придумать, как это сделать, поскольку C не позволяет определять функции времени выполнения, но я знаю, что здесь есть намного умнее людей, чем я :). Есть идеи?

Answer 1

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

Больше функционального повторного использования в C / C ++ / Objective-c с каррированными функциями

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

  

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

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

Answer 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 , была уничтожена сразу после < код> частичный прекращен.

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

Answer 3

Вот мое первое предположение на макушке (возможно, это не лучшее решение).

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

Answer 4

Вот подход к выполнению карри в Си. В этом примере приложения для удобства используется вывод iostream C ++, все это - кодирование в стиле 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)