C'è un modo per fare currying in C?

Question

Dire che ho un puntatore a una funzione _stack_push(stack* stk, void* el). Voglio essere in grado di chiamare curry(_stack_push, my_stack) e recuperare una funzione che richiede solo void* el. Non riuscivo a pensare a un modo per farlo, dato che C non consente la definizione della funzione di runtime, ma so che ci sono persone molto più intelligenti di me qui :). Qualche idea?

Answer 1

Ho trovato un articolo di Laurent Dami che discute currying in C/C++/Objective-C:

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

Di interesse per come viene implementato in C:

La nostra attuale l'implementazione utilizza costrutti C esistenti per aggiungere il meccanismo di curring. Questo è stato molto più facile da fare rispetto alla modifica del compilatore, ed è sufficiente a dimostrare l'interesse del curry. Questo approccio presenta tuttavia due inconvenienti. Innanzitutto, le funzioni al curry non possono essere controllate dal tipo e pertanto richiedono un uso attento per evitare errori. In secondo luogo, la funzione curry non può conoscere la dimensione dei suoi argomenti e li conta come se fossero tutti della dimensione di un intero.

Il documento non contiene un'implementazione di curry(), ma si può immaginare come viene implementato utilizzando function pointers e variadic functions.

Answer 2

Ecco la mia prima ipotesi dalla parte superiore della mia testa (potrebbe non essere la soluzione migliore).

La funzione curry potrebbe allocare parte della memoria dall'heap e inserire i valori dei parametri nella memoria allocata nell'heap. Il trucco è quindi che la funzione restituita sappia che dovrebbe leggere i suoi parametri da quella memoria allocata nell'heap. Se esiste una sola istanza della funzione restituita, un puntatore a questi parametri può essere memorizzato in un singleton/globale. Altrimenti se c'è più di una istanza della funzione restituita, allora penso che curry deve creare ogni istanza della funzione restituita nella memoria allocata nell'heap (scrivendo opcodi come "ottenere quel puntatore ai parametri", "push i parametri "e" invocano quell'altra funzione "nella memoria allocata nell'heap). In tal caso è necessario fare attenzione se la memoria allocata è eseguibile e forse (non so) avere paura dei programmi antivirus.

Answer 3

GCC fornisce un'estensione per la definizione di funzioni annidate. Anche se questo non è lo standard ISO C, questo può essere di qualche interesse, dal momento che consente di rispondere alla domanda abbastanza convenientemente. In breve, la funzione nidificata può accedere alle variabili locali della funzione padre e i puntatori a loro possono essere restituiti anche dalla funzione genitore.

Ecco una breve autoesplicativo esempio:

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

Esiste tuttavia una limitazione a questa costruzione. Se si mantiene un puntatore alla funzione risultante, come in

one_var_func u = partial (add_int, a); 

la funzione di chiamata u(0) può provocare un comportamento imprevisto, come la variabile a che u legge è stato distrutto poco dopo partial terminato.

Vedere this section of GCC's documentation.

Answer 4

Ecco un approccio per fare curry in C.Mentre questa applicazione di esempio utilizza l'output di iostream C++ per comodità, è tutta la codifica in stile C.

La chiave di questo approccio è di avere un struct che contiene un array di unsigned char e questo array viene utilizzato per creare un elenco di argomenti per una funzione. La funzione da chiamare viene specificata come uno degli argomenti che vengono inseriti nell'array. L'array risultante viene quindi assegnato a una funzione proxy che esegue effettivamente la chiusura di funzioni e argomenti.

In questo esempio fornisco un paio di funzioni di supporto specifiche del tipo per inserire argomenti nella chiusura e una funzione generica pushMem() per inviare un struct o altra area di memoria.

Questo approccio richiede l'allocazione di un'area di memoria che viene quindi utilizzata per i dati di chiusura. Sarebbe meglio usare lo stack per questa area di memoria in modo che la gestione della memoria non diventi un problema. C'è anche il problema di quanto sia grande per rendere l'area di memoria di archiviazione di chiusura in modo che ci sia spazio sufficiente per gli argomenti necessari ma non così grande che lo spazio inutilizzato in memoria o sullo stack è occupato dallo spazio inutilizzato.

Ho sperimentato l'uso di una struttura di chiusura leggermente definita che contiene un campo aggiuntivo per la dimensione attualmente utilizzata della matrice utilizzata per memorizzare i dati di chiusura. Questa diversa struttura di chiusura viene quindi utilizzata con una funzione helper modificata che elimina la necessità per l'utente delle funzioni di supporto di mantenere il proprio puntatore unsigned char * quando aggiungono argomenti alla struttura di chiusura.

Note e avvertimenti

Il seguente programma di esempio è stato compilato e testato con Visual Studio 2013. L'output di questo esempio viene fornito di seguito. Non sono sicuro dell'uso di GCC o CLANG con questo esempio, né sono sicuro di problemi che potrebbero essere visti con un compilatore a 64 bit poiché ho l'impressione che il mio test fosse con un'applicazione a 32 bit. Inoltre, questo approccio sembrerebbe funzionare solo con funzioni che utilizzano la dichiarazione C standard in cui la funzione di chiamata gestisce il popping degli argomenti dallo stack dopo che il chiamato restituisce (__cdecl e non __stdcall nell'API di Windows).

Poiché stiamo creando l'elenco degli argomenti in fase di esecuzione e quindi chiamiamo una funzione proxy, questo approccio non consente al compilatore di eseguire un controllo sugli argomenti. Ciò potrebbe portare a misteriosi guasti dovuti a tipi di parametri non corrispondenti che il compilatore non è in grado di segnalare.

Esempio di applicazione

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

uscita di prova

uscita da questo programma di esempio. Il numero tra parentesi è il numero della linea principale dove viene effettuata la chiamata alla funzione.

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)