C'è un modo per fare curry 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, dal momento 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 parla del curry in C / C ++ / Objective-C:

Riutilizzabilità più funzionale in C / C ++ / Objective-c con funzioni curry

Di interesse per come è implementato in C:

  

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

Il documento non contiene un'implementazione di curry () , ma puoi immaginare come viene implementato usando puntatori a funzione e funzioni variadiche .

Answer 2

GCC fornisce un'estensione per la definizione di funzioni nidificate. Sebbene questo non sia lo standard ISO C, questo può essere di qualche interesse, poiché consente di rispondere alla domanda abbastanza convenientemente. In breve, la funzione nidificata può accedere alle variabili locali della funzione padre e anche i puntatori possono essere restituiti dalla funzione padre.

Ecco un breve esempio autoesplicativo:

#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 mantieni un puntatore alla funzione risultante, come in

one_var_func u = partial (add_int, a);

la chiamata di funzione u (0) può provocare un comportamento imprevisto, poiché la variabile a che u è stata distrutta subito dopo < codice> parziale terminato.

Vedi questa sezione della documentazione di GCC .

Answer 3

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 in quella memoria allocata dall'heap. Il trucco è quindi che la funzione restituita sappia che dovrebbe leggere i suoi parametri da quella memoria allocata in heap. Se esiste solo un'istanza della funzione restituita, è possibile archiviare un puntatore a tali parametri in un singleton / globale. Altrimenti se c'è più di un'istanza della funzione restituita, allora penso che curry debba creare ogni istanza della funzione restituita nella memoria allocata in heap (scrivendo codici operativi come " ottieni quel puntatore a i parametri "," spingono i parametri "e" invocano quell'altra funzione "nella memoria allocata in heap). In tal caso è necessario fare attenzione se la memoria allocata è eseguibile e forse (non lo so) anche avere paura dei programmi antivirus.

Answer 4

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

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

In questo esempio fornisco un paio di funzioni di supporto specifiche per tipo per inserire argomenti nella chiusura e una funzione generica pushMem () per inviare una struct o altro regione 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 quest'area di memoria in modo che la gestione della memoria non diventi un problema. C'è anche il problema di quanto sia grande l'area di memoria di chiusura in modo che vi sia spazio sufficiente per gli argomenti necessari ma non così grande che lo spazio in eccesso nella memoria o nello stack sia occupato da spazio inutilizzato.

Ho sperimentato l'uso di una struttura di chiusura definita in modo leggermente diverso che contiene un campo aggiuntivo per la dimensione attualmente utilizzata dell'array utilizzato per archiviare 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 helper di mantenere il proprio puntatore unsigned char * quando si aggiungono argomenti alla struttura di chiusura.

Note e avvertenze

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 dei problemi che possono essere visti con un compilatore a 64 bit poiché ho l'impressione che il mio test fosse con un'applicazione a 32 bit. Anche questo approccio sembrerebbe funzionare solo con funzioni che usano la dichiarazione C standard in cui la funzione chiamante gestisce il pop-up degli argomenti dallo stack dopo che il richiamo restituisce ( __cdecl e non __stdcall nell'API di Windows).

Dato che stiamo costruendo l'elenco degli argomenti in fase di esecuzione e quindi chiamando 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 contrassegnare.

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

Test dell'output

Output da questo programma di esempio. Il numero tra parentesi è il numero della linea principale in cui viene effettuata la chiamata di 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)