¿Hay alguna forma de currying en C?

Question

Supongo que tengo un puntero a una función _stack_push(stack* stk, void* el). Quiero poder llamar al curry(_stack_push, my_stack) y recuperar una función que solo requiere void* el. No pude pensar en una forma de hacerlo, ya que C no permite la definición de la función de tiempo de ejecución, pero sé que hay personas mucho más inteligentes que yo aquí :). ¿Algunas ideas?

Answer 1

He encontrado un artículo de Laurent Dami que discute currying en C/C++/Objective-C:

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

De interés para la forma en que se implementa en C:

Nuestro actual la implementación usa constructos C existentes para agregar el mecanismo de curritura. Esto fue mucho más fácil de hacer que modificar el compilador, y es suficiente para demostrar el interés de currying. Sin embargo, este enfoque tiene dos inconvenientes. En primer lugar, las funciones al curry no se pueden verificar por tipo y, por lo tanto, requieren un uso cuidadoso para evitar errores. En segundo lugar, la función de curry no puede conocer el tamaño de sus argumentos y los cuenta como si tuvieran el tamaño de un entero.

El documento no contiene una implementación de curry(), pero se puede imaginar cómo se implementa utilizando function pointers y variadic functions.

Answer 2

Aquí está mi primera conjetura en la cabeza (puede que no sea la mejor solución).

La función curry podría asignar algo de memoria del montón y colocar los valores de los parámetros en esa memoria asignada en el montón. El truco es que la función devuelta sepa que se supone que debe leer sus parámetros de esa memoria asignada en el montón. Si solo hay una instancia de la función devuelta, se puede almacenar un puntero a esos parámetros en un singleton/global. De lo contrario, si hay más de una instancia de la función devuelta, entonces creo que Curry necesita crear cada instancia de la función devuelta en la memoria asignada en el montón (escribiendo códigos de operación como "obtener ese puntero a los parámetros", "empujar" los parámetros "e" invocan esa otra función "en la memoria asignada en el montón). En ese caso, debe tener cuidado con la posibilidad de que la memoria asignada sea ejecutable y, quizás (no sé), tenga miedo de los programas antivirus.

Answer 3

GCC proporciona una extensión para la definición de funciones anidadas. Aunque esto no es el estándar ISO C, esto puede ser de interés, ya que permite responder la pregunta de manera bastante conveniente. En resumen, la función anidada puede acceder a las variables locales de la función primaria y los punteros a ellas también pueden ser devueltos por la función principal.

He aquí una breve, explica por sí mismo ejemplo:

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

Sin embargo, existe una limitación a esta construcción. Si se mantiene un puntero a la función resultante, como en

one_var_func u = partial (add_int, a); 

la llamada de función u(0) puede resultar en un comportamiento inesperado, como la variable a el que lee u fue destruida justo después partial terminado.

Ver this section of GCC's documentation.

Answer 4

Aquí hay un enfoque para hacer currying en C.Si bien esta aplicación de muestra utiliza la salida iostream de C++ por conveniencia, es todo código de estilo C.

La clave de este enfoque es tener un struct que contiene una serie de unsigned char y esta matriz se utiliza para construir una lista de argumentos de una función. La función a llamar se especifica como uno de los argumentos que se insertan en la matriz. La matriz resultante se asigna a una función proxy que realmente ejecuta el cierre de la función y los argumentos.

En este ejemplo, proporciono un par de funciones auxiliares específicas del tipo para insertar argumentos en el cierre, así como una función genérica pushMem() para insertar un struct u otra región de memoria.

Este enfoque requiere la asignación de un área de memoria que luego se utiliza para los datos de cierre. Lo mejor sería usar la pila para esta área de memoria para que la administración de la memoria no se convierta en un problema. También existe la cuestión de qué tan grande debe ser el área de memoria de almacenamiento de cierre para que haya espacio suficiente para los argumentos necesarios, pero no tan grande como para ocupar el espacio excedente en la memoria o en la pila.

He experimentado con el uso de una estructura de cierre definida de forma ligeramente diferente que contiene un campo adicional para el tamaño utilizado actualmente de la matriz utilizada para almacenar los datos de cierre. Esta estructura de cierre diferente se utiliza luego con funciones de ayuda modificadas que elimina la necesidad de que el usuario de las funciones auxiliares mantenga su propio puntero unsigned char * al agregar argumentos a la estructura de cierre.

Notas y advertencias

El siguiente programa de ejemplo fue compilado y probado con Visual Studio 2013. Se proporciona la salida de esta muestra a continuación. No estoy seguro sobre el uso de GCC o CLANG con este ejemplo ni estoy seguro de los problemas que se pueden ver con un compilador de 64 bits, ya que tengo la impresión de que mi prueba fue con una aplicación de 32 bits. Además, este enfoque solo funcionaría con funciones que usan la declaración C estándar en la que la función de llamada maneja la extracción de argumentos de la pila después de que el destinatario devuelve (__cdecl y no __stdcall en la API de Windows).

Como estamos construyendo la lista de argumentos en tiempo de ejecución y luego llamando a una función proxy, este enfoque no le permite al compilador verificar los argumentos. Esto podría conducir a fallas misteriosas debido a tipos de parámetros no coincidentes que el compilador no puede marcar.

Ejemplo aplicación

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

salida de prueba

de salida de este programa de ejemplo. El número entre paréntesis es el número de línea en el principal donde se realiza la llamada a la función.

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)