Quels outils existe-t-il pour la programmation fonctionnelle en C?

J'ai beaucoup réfléchi ces derniers temps à la façon de faire de la programmation fonctionnelle en C ( pas en C ++). De toute évidence, C est un langage procédural et ne prend pas vraiment en charge la programmation fonctionnelle de manière native.

Existe-t-il des extensions de compilateur / langage qui ajoutent des constructions de programmation fonctionnelles au langage? GCC fournit des fonctions imbriquées en tant qu'extension de langage; les fonctions imbriquées peuvent accéder aux variables depuis le cadre de la pile parent, mais c'est encore loin des fermetures matures.

Par exemple, une chose qui, je pense, pourrait être vraiment utile en C est que partout où un pointeur de fonction est attendu, vous pourriez être capable de passer une expression lambda, créant une fermeture qui se désintègre en un pointeur de fonction. C ++ 0x va inclure des expressions lambda (ce que je trouve génial); cependant, je recherche des outils applicables au C.

[Edit] Pour clarifier, je n'essaye pas de résoudre un problème particulier en C qui serait plus adapté à la programmation fonctionnelle; Je suis simplement curieux de savoir quels sont les outils disponibles si je voulais le faire.

FFCALL vous permet de créer des fermetures en C - callback = alloc_callback(&function, data)renvoie un pointeur de fonction tel que cela callback(arg1, ...)équivaut à appeler function(data, arg1, ...). Cependant, vous devrez gérer manuellement le garbage collection.

De même, des blocs ont été ajoutés au fork d'Apple de GCC; ce ne sont pas des pointeurs de fonction, mais ils vous permettent de contourner les lambdas tout en évitant le besoin de construire et de libérer du stockage pour les variables capturées à la main (effectivement, une copie et un comptage de références se produisent, cachés derrière des bibliothèques de sucre syntaxique et d'exécution).

Vous pouvez utiliser les fonctions imbriquées de GCC pour simuler des expressions lambda, en fait, j'ai une macro pour le faire pour moi:

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

Utilisez comme ceci:

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

La programmation fonctionnelle n'est pas une question de lambdas, c'est une question de fonctions pures. Ainsi, les éléments suivants favorisent largement le style fonctionnel:

1. N'utilisez que des arguments de fonction, n'utilisez pas l'état global.

2. Minimisez les effets secondaires, c'est-à-dire printf ou tout autre E / S. Renvoie les données décrivant les E / S qui peuvent être exécutées au lieu de provoquer les effets secondaires directement dans toutes les fonctions.

Ceci peut être réalisé en simple c, pas besoin de magie.

Le livre de Hartel & Muller, Functional C , peut de nos jours (2012-01-02) être trouvé à: http://eprints.eemcs.utwente.nl/1077/ (il y a un lien vers la version PDF).

La condition préalable au style de programmation fonctionnelle est une fonction de première classe. Il pourrait être simulé dans le portable C si vous tolérez ensuite:

• gestion manuelle des liaisons de portée lexicale, aka fermetures.
• gestion manuelle de la durée de vie des variables de fonction.
• syntaxe alternative de la fonction application / appel.

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

le temps d'exécution d'un tel code peut être aussi petit que celui ci-dessous

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 substance, nous imitons une fonction de première classe avec des fermetures représentées par une paire de fonctions / arguments plus un tas de macroses. Le code complet peut être trouvé ici .

La principale chose qui me vient à l'esprit est l'utilisation de générateurs de code. Seriez-vous prêt à programmer dans un langage différent fournissant la programmation fonctionnelle, puis à générer le code C à partir de cela?

Si ce n'est pas une option attrayante, vous pourriez abuser du RPC pour faire une partie du chemin. Le système de macros devrait vous permettre d'émuler certaines idées de programmation fonctionnelle. J'ai entendu dire que gcc est implémenté de cette façon mais je n'ai jamais vérifié.

C peut bien sûr passer des fonctions à l'aide de pointeurs de fonction, les principaux problèmes sont le manque de fermetures et le système de types a tendance à se mettre en travers. Vous pouvez explorer des systèmes macro plus puissants que CPP tels que M4. Je suppose qu'en fin de compte, ce que je suggère, c'est que le vrai C n'est pas à la hauteur de la tâche sans grand effort, mais vous pouvez étendre C pour qu'il soit à la hauteur de la tâche. Cette extension ressemblerait le plus à C si vous utilisez CPP ou vous pourriez aller à l'autre extrémité du spectre et générer du code C à partir d'un autre langage.

Si vous souhaitez implémenter des fermetures, vous devrez vous familiariser avec le langage d'assemblage et l'échange / la gestion de la pile. Ne pas recommander contre cela, juste dire que c'est ce que vous devrez faire.

Vous ne savez pas comment vous allez gérer les fonctions anonymes en C. Sur une machine von Neumann, vous pouvez cependant faire des fonctions anonymes dans asm.

Regardez le livre de Hartel & Muller, Functional C

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

Le langage Felix compile en C ++. Cela pourrait peut-être être un pas en avant, si cela ne vous dérange pas C ++.

Eh bien, un certain nombre de langages de programmation sont écrits en C. Et certains d'entre eux prennent en charge des fonctions en tant que citoyens de première classe, les langages dans ce domaine sont ecl (embbedabble common lisp IIRC), Gnu Smalltalk (gst) (Smalltalk a des blocs), puis il y a des bibliothèques pour les "fermetures", par exemple dans glib2 http://library.gnome.org/devel/gobject/unstable/chapter-signal.html#closure qui a au moins obtenu une programmation presque fonctionnelle. Alors peut-être que l'utilisation de certaines de ces implémentations pour faire de la programmation fonctionnelle peut être une option.

Ou vous pouvez aller apprendre Ocaml, Haskell, Mozart / Oz ou autres ;-)

Cordialement

La façon dont j'ai fait de la programmation fonctionnelle en C était d'écrire un interpréteur de langage fonctionnel en C. Je l'ai nommé Fexl, qui est l'abréviation de «Function EXpression Language».

L'interpréteur est très petit, compilant jusqu'à 68K sur mon système avec -O3 activé. Ce n'est pas non plus un jouet - je l'utilise pour tout le nouveau code de production que j'écris pour mon entreprise (comptabilité en ligne pour les partenariats d'investissement).

Maintenant, j'écris du code C uniquement pour (1) ajouter une fonction intégrée qui appelle une routine système (par exemple, fork, exec, setrlimit, etc.), ou (2) optimiser une fonction qui pourrait autrement être écrite en Fexl (par exemple, search pour une sous-chaîne).

Le mécanisme du module est basé sur le concept de «contexte». Un contexte est une fonction (écrite en Fexl) qui associe un symbole à sa définition. Lorsque vous lisez un fichier Fexl, vous pouvez le résoudre avec n'importe quel contexte que vous souhaitez. Cela vous permet de créer des environnements personnalisés ou d'exécuter du code dans un «bac à sable» restreint.

http://fexl.com

Qu'est-ce que vous voulez rendre fonctionnel en C, la syntaxe ou la sémantique? La sémantique de la programmation fonctionnelle pourrait certainement être ajoutée au compilateur C, mais au moment où vous auriez terminé, vous auriez essentiellement l'équivalent de l'un des langages fonctionnels existants, tels que Scheme, Haskell, etc.

Ce serait une meilleure utilisation du temps pour simplement apprendre la syntaxe de ces langages qui prennent directement en charge cette sémantique.

Je ne sais pas à propos de C. Il existe cependant des fonctionnalités fonctionnelles dans Objective-C, GCC sur OSX prend également en charge certaines fonctionnalités, mais je recommanderais à nouveau de commencer à utiliser un langage fonctionnel, il y en a beaucoup mentionnés ci-dessus. Personnellement, j'ai commencé avec le schéma, il existe d'excellents livres tels que The Little Schemer qui peuvent vous aider à le faire.