Czy istnieje sposób na robienie curry w C?

Question

Powiedz, że mam wskaźnik do funkcji _stack_push(stack* stk, void* el). Chcę móc zadzwonić pod numer curry(_stack_push, my_stack) i odzyskać funkcję, która zajmuje tylko void* el. Nie mogłem wymyślić sposobu, aby to zrobić, ponieważ C nie pozwala na definiowanie funkcji środowiska wykonawczego, ale wiem, że tu jest o wiele sprytniej niż ja :). Jakieś pomysły?

Answer 1

znalazłem papier Laurent Dami, który omawia currying w C/C++/Objective-C:

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

Co ciekawe, jak to jest realizowane w C:

Aktualnym implementacja wykorzystuje istniejące konstrukty C w celu dodania mechanizmu curry. Było to znacznie łatwiejsze niż modyfikowanie kompilatora i wystarczające do udowodnienia zainteresowania curry. Takie podejście ma jednak dwie wady. Po pierwsze, funkcje curry nie mogą być sprawdzane typu, a zatem wymagają starannego użycia, aby uniknąć błędów. Po drugie, funkcja curry nie może znać wielkości swoich argumentów i zlicza je tak, jakby były wielkości liczb całkowitych.

Papier nie zawiera implementację curry(), ale można sobie wyobrazić, jak to jest realizowane za pomocą function pointers i variadic functions.

Answer 2

Oto moje pierwsze przypuszczenie ze szczytu mojej głowy (może nie być najlepszym rozwiązaniem).

Funkcja curry może przydzielić trochę pamięci poza stertę i wprowadzić wartości parametrów do tej pamięci przydzielonej sterty. Sztuczka polega na tym, że zwrócona funkcja wie, że powinna odczytać jej parametry z pamięci przydzielonej sterty. Jeśli istnieje tylko jedna instancja zwróconej funkcji, wskaźnik do tych parametrów może być zapisany w singleton/global. W przeciwnym razie, jeśli istnieje więcej niż jedna instancja zwróconej funkcji, myślę, że curry musi utworzyć każdą instancję zwróconej funkcji w pamięci przydzielonej sterty (przez napisanie opcodu takich jak "pobierz ten wskaźnik do parametrów", "push" parametry "i" wywołaj tę inną funkcję "w pamięci przydzielonej sterty). W takim przypadku należy wystrzegać się, czy przydzielona pamięć jest wykonywalna, i być może (nie wiem) nawet bać się programów antywirusowych.

Answer 3

GCC stanowi rozszerzenie definicji funkcji zagnieżdżonych. Chociaż nie jest to norma ISO C, może to być interesujące, ponieważ pozwala dość wygodnie odpowiedzieć na pytanie. W skrócie funkcja zagnieżdżona może uzyskać dostęp do zmiennych lokalnych funkcji nadrzędnej, a wskaźniki do nich mogą być również zwracane przez funkcję macierzystą.

Oto krótka, oczywisty przykład:

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

Istnieje jednak ograniczenie do tej konstrukcji. Jeśli trzymać wskaźnik do wynikowego funkcji, jak w

one_var_func u = partial (add_int, a); 

wywołanie funkcji u(0) może spowodować nieoczekiwane zachowanie, jako zmiennej a który u czyta została zniszczona tuż po partial zakończona.

Zobacz this section of GCC's documentation.

Answer 4

Oto podejście do robienia curry w C.Podczas gdy ta przykładowa aplikacja korzysta z wyjścia Costostream dla wygody, jest to kodowanie w stylu C.

Kluczem do tego podejścia jest posiadanie struct, który zawiera tablicę z unsigned char, a tablica ta służy do budowania listy argumentów dla funkcji. Wywoływana funkcja jest określona jako jeden z argumentów, które są przekazywane do tablicy. Wynikowa tablica jest następnie przekazywana do funkcji proxy, która faktycznie wykonuje zamknięcie funkcji i argumentów.

W tym przykładzie udostępniam kilka specyficznych dla danego typu funkcji pomocniczych, które popychają argumenty do zamknięcia, a także ogólną funkcję pushMem(), która przepycha numer struct lub inny obszar pamięci.

To podejście wymaga przydziału obszaru pamięci, który jest następnie używany do danych zamknięcia. Najlepiej byłoby użyć stosu dla tego obszaru pamięci, aby zarządzanie pamięcią nie stanowiło problemu. Występuje również problem, jak duży by utworzyć obszar pamięci zamykania zamknięcia, tak aby było wystarczająco dużo miejsca na niezbędne argumenty, ale nie tak duży, że nadmiar miejsca w pamięci lub na stosie jest zajęty przez nieużywane miejsce.

Eksperymentowałem z użyciem nieco inaczej zdefiniowanej struktury zamknięcia, która zawiera dodatkowe pole dla aktualnie używanego rozmiaru tablicy używanej do przechowywania danych zamknięcia. Ta odmienna struktura zamykająca jest następnie używana ze zmodyfikowanymi funkcjami pomocniczymi, która eliminuje potrzebę, aby użytkownik funkcji pomocnika utrzymywał swój własny wskaźnik unsigned char * podczas dodawania argumentów do struktury zamknięcia.

Uwagi i zastrzeżenia

Poniższy przykład program został opracowany i przetestowany z Visual Studio 2013. Wyjście z tej próbce znajduje się poniżej. Nie jestem pewien co do użycia GCC lub CLANG z tym przykładem i nie jestem pewien co do kwestii, które mogą być widoczne w 64-bitowym kompilatorze, ponieważ jestem pod wrażeniem, że moje testy były z aplikacją 32-bitową. Również takie podejście wydaje się działać tylko w przypadku funkcji, które używają standardowej deklaracji C, w której funkcja wywołująca obsługuje popping argumentów ze stosu po zwrocie przez wywoływacza (__cdecl, a nie __stdcall w Windows API).

Ponieważ budujemy listę argumentów w czasie wykonywania, a następnie wywołujemy funkcję proxy, to podejście nie pozwala kompilatorowi na sprawdzenie argumentów. Może to prowadzić do tajemniczych awarii spowodowanych niedopasowanymi typami parametrów, których kompilator nie może zgłosić.

Przykład zastosowania

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

Wyjście testowe

wyjście z tego programu próbki. Liczba w nawiasie to numer linii w głównym polu, w którym wykonywane jest wywołanie funkcji.

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)