¿Qué herramientas hay para la programación funcional en C?

Últimamente he estado pensando mucho sobre cómo hacer programación funcional en C ( no en C ++). Obviamente, C es un lenguaje de procedimiento y realmente no admite la programación funcional de forma nativa.

¿Hay alguna extensión de compilador / lenguaje que agregue algunas construcciones de programación funcional al lenguaje? GCC proporciona funciones anidadas como una extensión de lenguaje; Las funciones anidadas pueden acceder a las variables desde el marco de la pila principal, pero esto todavía está muy lejos de los cierres maduros.

Por ejemplo, una cosa que creo que podría ser realmente útil en C es que en cualquier lugar donde se espera un puntero de función, podría pasar una expresión lambda, creando un cierre que se desintegra en un puntero de función. C ++ 0x va a incluir expresiones lambda (que creo que es increíble); Sin embargo, estoy buscando herramientas aplicables a la C.

[Editar] Para aclarar, no estoy tratando de resolver un problema particular en C que sería más adecuado para la programación funcional; Simplemente tengo curiosidad acerca de qué herramientas hay si quisiera hacerlo.

FFCALL le permite crear cierres en C: callback = alloc_callback(&function, data)devuelve un puntero de función que callback(arg1, ...)es equivalente a llamar function(data, arg1, ...). Sin embargo, tendrá que manejar la recolección de basura manualmente.

Relacionado, se han agregado bloques al tenedor de GCC de Apple; no son punteros de función, pero le permiten pasar lambdas mientras evitan la necesidad de construir y liberar almacenamiento para las variables capturadas a mano (de hecho, ocurre una copia y un recuento de referencias, oculto detrás de algunas bibliotecas sintácticas de azúcar y tiempo de ejecución).

Puede usar las funciones anidadas de GCC para simular expresiones lambda, de hecho, tengo una macro para hacerlo por mí:

#define lambda(return_type, function_body) \
  ({ \
    return_type anon_func_name_ function_body \
    anon_func_name_; \
  })

Usar así:

int (*max)(int, int) = lambda (int, (int x, int y) { return x > y ? x : y; });

La programación funcional no se trata de lambdas, se trata de funciones puras. Entonces, lo siguiente promueve ampliamente el estilo funcional:

1. Solo use argumentos de función, no use estado global.

2. Minimice los efectos secundarios, es decir, printf o cualquier IO. Devuelve datos que describen IO que se pueden ejecutar en lugar de causar los efectos secundarios directamente en todas las funciones.

Esto se puede lograr en plano C, sin necesidad de magia.

El libro de Hartel y Muller, Functional C , se puede encontrar hoy en día (2012-01-02) en: http://eprints.eemcs.utwente.nl/1077/ (hay un enlace a la versión PDF).

El requisito previo para el estilo de programación funcional es una función de primera clase. Podría simularse en C portátil si tolera lo siguiente:

• gestión manual de enlaces de ámbito léxico, también conocidos como cierres.
• Gestión manual de las variables de función de por vida.
• sintaxis alternativa de aplicación de función / llamada.

/* 
 * with constraints desribed above we could have
 * good approximation of FP style in plain C
 */

int increment_int(int x) {
  return x + 1;
}

WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS(increment, increment_int);

map(increment, list(number(0), number(1)); // --> list(1, 2)


/* composition of first class function is also possible */

function_t* computation = compose(
  increment,
  increment,
  increment
);

*(int*) call(computation, number(1)) == 4;

el tiempo de ejecución de dicho código podría ser tan pequeño como el siguiente

struct list_t {
  void* head;
  struct list_t* tail;
};

struct function_t {
   void* (*thunk)(list_t*);
   struct list_t* arguments;
}

void* apply(struct function_t* fn, struct list_t* arguments) {
  return fn->thunk(concat(fn->arguments, arguments));
}

/* expansion of WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS */
void* increment_thunk(struct list_t* arguments) {
  int x_arg = *(int*) arguments->head;
  int value = increment_int(x_arg);
  int* number = malloc(sizeof *number);

  return number ? (*number = value, number) : NULL;
}

struct function_t* increment = &(struct function_t) {
  increment_thunk,
  NULL
};

/* call(increment, number(1)) expands to */
apply(increment, &(struct list_t) { number(1), NULL });

En esencia, imitamos la función de primera clase con cierres representados como un par de funciones / argumentos más macros. El código completo se puede encontrar aquí .

Lo principal que viene a la mente es el uso de generadores de código. ¿Estaría dispuesto a programar en un lenguaje diferente que proporcionara la programación funcional y luego generar el código C a partir de eso?

Si esa no es una opción atractiva, entonces podría abusar de CPP para obtener parte del camino. El sistema macro debería permitirle emular algunas ideas de programación funcional. He oído decir que gcc se implementa de esta manera, pero nunca lo he comprobado.

C, por supuesto, puede pasar funciones utilizando punteros de función, los principales problemas son la falta de cierres y el sistema de tipos tiende a interferir. Podría explorar sistemas macro más potentes que CPP como M4. Supongo que, en última instancia, lo que estoy sugiriendo es que el verdadero C no está a la altura de la tarea sin un gran esfuerzo, pero podría extender C para que esté a la altura de la tarea. Esa extensión se parecería más a C si usa CPP o podría ir al otro extremo del espectro y generar código C desde otro lenguaje.

Si desea implementar cierres, tendrá que ponerse firme con el lenguaje ensamblador y el intercambio / gestión de la pila. No lo recomiendo, solo digo que eso es lo que tendrás que hacer.

Sin embargo, no estoy seguro de cómo manejará las funciones anónimas en C. En una máquina von Neumann, podría hacer funciones anónimas en asm.

Mire el libro de Hartel y Muller, Funcional C

http://www.ub.utwente.nl/webdocs/ctit/1/00000084.pdf
http://www.cs.bris.ac.uk/~henkm/f2c/index.html

El lenguaje Felix compila a C ++. Tal vez eso podría ser una piedra angular, si no te importa C ++.

Un buen número de lenguajes de programación están escritos en C. Y algunos de ellos admiten funciones como ciudadanos de primera clase, los idiomas en esa área son ecl (embebible common lisp IIRC), Gnu Smalltalk (gst) (Smalltalk tiene bloques), luego hay bibliotecas para "cierres", por ejemplo, en glib2 http://library.gnome.org/devel/gobject/unstable/chapter-signal.html#closure que al menos se acercaba a la programación funcional. Entonces, tal vez usar algunas de esas implementaciones para hacer programación funcional puede ser una opción.

Bueno, o puedes ir a aprender Ocaml, Haskell, Mozart / Oz o similares ;-)

Saludos

La forma en que hice la programación funcional en C fue escribir un intérprete de lenguaje funcional en C. Lo llamé Fexl, que es la abreviatura de "Function EXpression Language".

El intérprete es muy pequeño, compilando hasta 68K en mi sistema con -O3 habilitado. Tampoco es un juguete: lo estoy usando para todo el nuevo código de producción que escribo para mi negocio (contabilidad basada en web para asociaciones de inversión).

Ahora escribo código C solo para (1) agregar una función incorporada que llama a una rutina del sistema (por ejemplo, fork, exec, setrlimit, etc.), u (2) optimizar una función que de otro modo podría escribirse en Fexl (por ejemplo, buscar para una subcadena).

El mecanismo del módulo se basa en el concepto de "contexto". Un contexto es una función (escrita en Fexl) que asigna un símbolo a su definición. Cuando lee un archivo Fexl, puede resolverlo con el contexto que desee. Esto le permite crear entornos personalizados o ejecutar código en un "sandbox" restringido.

http://fexl.com

¿Qué tiene C que desea que sea funcional, la sintaxis o la semántica? La semántica de la programación funcional ciertamente podría agregarse al compilador de C, pero para cuando haya terminado, esencialmente tendría el equivalente de uno de los lenguajes funcionales existentes, como Scheme, Haskell, etc.

Sería un mejor uso del tiempo aprender la sintaxis de esos idiomas que admiten directamente esa semántica.

No sé acerca de C. Sin embargo, hay algunas características funcionales en Objective-C, GCC en OSX también admite algunas características, sin embargo, recomendaría nuevamente comenzar a usar un lenguaje funcional, hay muchas mencionadas anteriormente. Personalmente comencé con Scheme, hay algunos libros excelentes como The Little Schemer que pueden ayudarte a hacerlo.