Y at-il un moyen de faire currying en C?

StackOverflow https://stackoverflow.com/questions/1023261

Question

Disons que j'ai un pointeur sur une fonction _stack_push (pile * stk, void * el) . Je veux pouvoir appeler curry (_stack_push, my_stack) et récupérer une fonction qui prend juste void * el . Je ne pouvais pas penser à un moyen de le faire, car C n'autorise pas la définition de la fonction d'exécution, mais je sais qu'il y a des gens beaucoup plus intelligents que moi ici :). Des idées?

Était-ce utile?

La solution

J'ai trouvé un article de Laurent Dami qui parle de currying en C / C ++ / Objective-C:

Plus de réutilisation fonctionnelle en C / C ++ / Objective-c avec fonctions curryisées

Intérêt pour son implémentation dans C:

  

Notre implémentation actuelle utilise les constructions C existantes pour ajouter le mécanisme de currying. C'était beaucoup plus facile à faire que de modifier le compilateur et suffisait pour prouver l'intérêt du curry. Cette approche présente toutefois deux inconvénients. Premièrement, les fonctions au curried ne peuvent pas être vérifiées, et nécessitent donc une utilisation soigneuse afin d'éviter les erreurs. Deuxièmement, la fonction curry ne peut pas connaître la taille de ses arguments et les compte comme s’ils étaient tous de la taille d’un entier.

Le document ne contient pas d'implémentation de curry () , mais vous pouvez imaginer son implémentation à l'aide de pointeurs de fonction et fonctions variées .

Autres conseils

GCC fournit une extension pour la définition des fonctions imbriquées. Bien qu’il ne s’agisse pas de la norme ISO C, cela peut présenter un certain intérêt, car cela permet de répondre à la question très facilement. En bref, la fonction imbriquée peut accéder à la variable parent de la fonction parent et les pointeurs qui les dirigent peuvent également être renvoyés par la fonction parent.

Voici un exemple court et explicite: 

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

Il existe toutefois une limite à cette construction. Si vous conservez un pointeur sur la fonction résultante, comme dans 

one_var_func u = partial (add_int, a);

l'appel de fonction u (0) peut entraîner un comportement inattendu, car la variable a que u lit a été détruite juste après < code> partiel terminé.

Voir cette section de la documentation de GCC .

Voici ma première hypothèse (il se peut que ce ne soit pas la meilleure solution).

La fonction curry pourrait allouer de la mémoire hors du tas et placer les valeurs de paramètre dans la mémoire allouée au tas. L'astuce consiste alors pour la fonction renvoyée à savoir qu'elle est supposée lire ses paramètres à partir de la mémoire allouée. S'il n'y a qu'une seule instance de la fonction retournée, un pointeur sur ces paramètres peut être stocké dans un singleton / global. Sinon, s'il y a plus d'une instance de la fonction renvoyée, alors je pense que Curry doit créer chaque instance de la fonction renvoyée dans la mémoire allouée au tas (en écrivant des codes opération tels que "renvoie ce pointeur à les paramètres "," poussent les paramètres "et" invoquent cette autre fonction "dans la mémoire allouée au segment de mémoire). Dans ce cas, vous devez vous méfier si la mémoire allouée est exécutable et peut-être (je ne sais pas) même avoir peur des programmes anti-virus.

Voici une approche pour effectuer un curry en C. Bien que cet exemple d'application utilise la sortie iostream C ++ pour des raisons pratiques, il s'agit uniquement d'un codage de style C.

La clé de cette approche est d’avoir une struct contenant un tableau de chars non signés et ce tableau est utilisé pour construire une liste d’arguments pour une fonction. La fonction à appeler est spécifiée comme l'un des arguments poussés dans le tableau. Le tableau résultant est ensuite attribué à une fonction proxy qui exécute la fermeture de la fonction et des arguments.

Dans cet exemple, je fournis quelques fonctions d'assistance spécifiques au type pour insérer des arguments dans la fermeture, ainsi qu'une fonction générique pushMem () permettant de transmettre une struct ou une autre région de la mémoire.

Cette approche nécessite l’attribution d’une zone mémoire qui est ensuite utilisée pour les données de fermeture. Il serait préférable d’utiliser la pile pour cette zone mémoire afin que la gestion de la mémoire ne devienne pas un problème. Il faut également déterminer la taille de la zone de mémoire de fermeture afin de laisser suffisamment d’espace pour les arguments nécessaires, mais pas assez pour que l’espace supplémentaire dans la mémoire ou sur la pile soit utilisé par de l’espace inutilisé.

J'ai expérimenté l'utilisation d'une structure de fermeture légèrement définie différemment, qui contient un champ supplémentaire pour la taille actuellement utilisée du tableau utilisé pour stocker les données de fermeture. Cette structure de fermeture différente est ensuite utilisée avec une fonction d'assistance modifiée, ce qui évite à l'utilisateur de la tâche de conserver son propre pointeur unsigned char * lors de l'ajout d'arguments à la structure de fermeture.

Notes et mises en garde

L'exemple de programme suivant a été compilé et testé avec Visual Studio 2013. Le résultat de cet exemple est fourni ci-dessous. Je ne suis pas sûr de l’utilisation de GCC ou de CLANG avec cet exemple, ni des problèmes que l’on pourrait rencontrer avec un compilateur 64 bits, car j’ai l’impression que mes tests ont été effectués avec une application 32 bits. De plus, cette approche ne semblerait fonctionner qu'avec les fonctions qui utilisent la déclaration standard C dans laquelle la fonction appelante gère le vidage des arguments de la pile après le retour de l'appelé ( __ cdecl et non __ stdcall dans l'API Windows).

Etant donné que nous construisons la liste des arguments au moment de l'exécution, puis que nous appelons une fonction proxy, cette approche ne permet pas au compilateur de vérifier les arguments. Cela pourrait entraîner de mystérieux échecs en raison de types de paramètres incompatibles que le compilateur ne peut pas signaler.

Exemple d'application 

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

Résultat du test

Sortie de cet exemple de programme. Le numéro entre parenthèses est le numéro de la ligne principale où la fonction est appelée. 

 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)
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top