superior orden operaciones matematicas funciones c functional-programming higher-order-functions

operaciones - Funciones de orden superior en C



funciones de orden superior scheme (8)

El gran problema con la implementación de funciones de orden superior en C es que para hacer algo no trivial necesita cierres, que son punteros de función aumentados con estructuras de datos que contienen variables locales a las que tienen acceso. Dado que la idea detrás de los cierres es capturar variables locales y pasarlas junto con el puntero a la función, es difícil hacerlo sin el soporte del compilador. E incluso con el soporte del compilador es difícil hacerlo sin la recolección de basura porque las variables pueden existir fuera de su alcance, lo que dificulta saber cuándo liberarlas.

¿Hay una manera "adecuada" de implementar funciones de orden superior en C.

En mi mayoría, tengo curiosidad acerca de cosas como la portabilidad y la corrección de la sintaxis, y si hay más de una forma, cuáles son los méritos y las fallas.

Edición: la razón por la que quiero saber cómo crear funciones de orden superior es que he escrito un sistema para convertir las listas de PyObject (que se obtienen al llamar scripts de Python) en una lista de estructuras C que contienen los mismos datos pero organizadas de una manera que no Depende de las bibliotecas python.h. Por lo tanto, mi plan es tener una función que itere a través de una lista pythonic y llame a una función en cada elemento de la lista y coloque el resultado en una lista que luego devuelva.

Así que este es básicamente mi plan:

typedef gpointer (converter_func_type)(PyObject *) gpointer converter_function(PyObject *obj) { // do som stuff and return a struct cast into a gpointer (which is a void *) } GList *pylist_to_clist(PyObject *obj, converter_func_type f) { GList *some_glist; for each item in obj { some_glist = g_list_append(some_glist, f(item)); } return some_glist; } void some_function_that_executes_a_python_script(void) { PyObject *result = python stuff that returns a list; GList *clist = pylist_to_clist(result, converter_function); }

Y para aclarar la pregunta: quiero saber cómo hacer esto de manera más segura y correcta C. Realmente me gustaría mantener el estilo de función de orden superior, pero si eso está mal visto, aprecio enormemente las formas de hacerlo de otra manera.

En la c recta, esto solo se hace a través de indicadores de función, que son a la vez dolor y no están diseñados para este tipo de cosas (que es en parte la razón por la que son un dolor). Sin embargo, los bloques (o cierres, según no Apple) son fantásticos para esto. Se compilan en gcc-4.x o algo así, e icc en algo, pero independientemente de eso es lo que estás buscando. Desafortunadamente, parece que no puedo encontrar buenos tutoriales en línea, pero es suficiente para decir que funciona algo como esto:

void iterate(char *str, int count, (^block)(str *)){ for(int i = 0; i < count; i++){ block(list[i]); } } main() { char str[20]; iterate(str, 20, ^(char c){ printf("%c ", c); }); int accum = 0; iterate(someList, 20, ^(char c){ accum += c; iterate(str, 20, ^(char c){ printf("%c ", c); }); }); }

obviamente, este código no tiene sentido, pero imprime cada carácter de una cadena (str) con un espacio entre ellos, luego suma todos los caracteres juntos en la acumulación, y cada vez que lo hace imprime la lista de caracteres nuevamente.

Espero que esto ayude. Por cierto, los bloques son muy visibles en las aplicaciones de Mac OS X Snow Leopard, y creo que están en el próximo estándar de C ++ 0x, por lo que no son tan inusuales.

Esta es una respuesta a la pregunta: cómo componer funciones en C, que se redirige aquí.

Puede crear una estructura de datos para implementar un tipo de datos de lista. Esa estructura puede contener punteros de función.

#include<stdlib.h> #include<malloc.h> typedef (*fun)(); typedef struct funList { fun car; struct funList *cdr;} *funList; const funList nil = NULL; int null(funList fs){ return nil==fs; } fun car(funList fs) { if(!null(fs)) return fs->car; else { fprintf(stderr,"error:can''t car(nil) line:%d/n",__LINE__); exit(1); } } funList cdr(funList ls) { if(!null(ls)) return ls->cdr; else { fprintf(stderr,"error:can''t cdr(nil) line:%d/n",__LINE__); exit(1); } } funList cons(fun f, funList fs) { funList ls; ls=(funList) malloc(sizeof(struct funList)); if(NULL==ls) { fprintf(stderr,"error:can''t alloc mem for cons(...) line:%d/n",__LINE__); exit(1); } ls->car=f; ls->cdr=fs; return ls; }

Podemos escribir una función comp que aplica una lista de funciones:

type_2 comp(funList fs, type_1 x) { return (null(fs)) ? x : car(fs)(comp(cdr(fs),x)); }

Un ejemplo de cómo funciona. Utilizamos (fgh) como una notación corta para cons (f, cons (g, cons (h, nil)), que se aplica a un argumento dado x:

comp((f g h),x)

=

f(comp((g h),x))

=

f(g(comp((h),x)))

=

f(g(h(comp(nil,x))))

=

f(g(h(x)))

Si ha usado el tipo de lista polimórfica en un lenguaje escrito como SML o Haskell, el tipo de comp debería ser:

comp :: ([a -> a],a) -> a

porque en ese contexto todos los miembros en una lista tienen el mismo tipo. C puede ser más flexible en este sentido. Tal vez algo como

typedef void (*fun)();

o

typedef (*fun)();

Deberías ver lo que dice el manual de C sobre esto. Y asegúrese de que todas las funciones contiguas tengan tipos compatibles.

Las funciones a componer deben ser puras, es decir, sin efectos secundarios ni variables libres.

Prácticamente cualquier aplicación de función de orden superior interesante requiere cierres, lo que en C conlleva la rutina laboriosa y propensa a errores de definir y completar manualmente los argumentos de función de estructura.

Si desea crear funciones de orden superior, no use C. Hay soluciones de C para su problema. Puede que no sean elegantes, o pueden ser más elegantes de lo que te das cuenta.

[Editar] Sugerí que la única forma de lograr esto era usar un lenguaje de scripting. Otros me han llamado. Entonces, estoy reemplazando esa sugerencia con esto: [/ Editar]

¿Qué estás intentando lograr? Si desea imitar los cierres, use un lenguaje que los admita (puede vincularlos con Ruby, lua, javascript, etc. a través de las bibliotecas). Si desea utilizar devoluciones de llamada, los punteros de función están bien. Los punteros de función combinan las áreas más peligrosas de C (los punteros y el sistema de tipo débil), así que tenga cuidado. Las declaraciones de puntero de función tampoco son divertidas de leer.

Puede encontrar algunas bibliotecas de C que utilizan punteros de función porque tienen que hacerlo. Si estás escribiendo una biblioteca, quizás también necesites usarlos. Si solo los estás usando dentro de tu propio código, probablemente no estés pensando en C. Estás pensando en lisp o esquema o ruby ​​o ... y tratas de escribirlo en C. Aprende la forma en C.

Si está interesado en hacer esto en C simple, debe recordar incluir la opción para pasar un puntero de contexto desde la persona que llama al functor (la función de orden superior) a la función pasada. Esto le permite simular lo suficiente De un cierre que puede hacer que las cosas funcionen fácilmente. A lo que apunta ese puntero ... bueno, depende de usted, pero debe ser un void* en la API del functor (o uno de los muchos alias para él, como gpointer en el mundo GLib o ClientData en la API de Tcl C) ).

[EDITAR]: Para usar / adaptar su ejemplo:

typedef gpointer (converter_func_type)(gpointer,PyObject *) gpointer converter_function(gpointer context_ptr,PyObject *obj) { int *number_of_calls_ptr = context_ptr; *number_of_calls_ptr++; // do som stuff and return a struct cast into a gpointer (which is a void *) } GList *pylist_to_clist(PyObject *obj, converter_func_type f, gpointer context_ptr) { GList *some_glist; for each item in obj { some_glist = g_list_append(some_glist, f(context_ptr,item)); } return some_glist; } void some_function_that_executes_a_python_script(void) { int number_of_calls = 0; PyObject *result = python stuff that returns a list; GList *clist = pylist_to_clist(result, converter_function, &number_of_calls); // Now number_of_calls has how often converter_function was called... }

Este es un ejemplo trivial de cómo hacerlo, pero debería mostrarle el camino.

Técnicamente, las funciones de orden superior son solo funciones que toman o devuelven funciones. Así que cosas como qsort ya son de orden superior.

Si te refieres a algo más parecido a las funciones lambda que se encuentran en los lenguajes funcionales (que es donde las funciones de orden superior realmente se vuelven útiles), son bastante más difíciles y no se pueden hacer de forma natural en el estándar actual C. Simplemente no son parte de el idioma. La extensión de bloques de Apple es el mejor candidato. Solo funciona en GCC (y en el compilador C de LLVM), pero son realmente útiles. Esperemos que algo así se prenda. Aquí hay algunos recursos relevantes: