Discussion :

[Ubiquité]

Est-ce que l'existance des pointeurs de fonction en C en fait un language fonctionnel ?
Si non, je serai curieux de savoir pourquoi.

[gasche]

Il n'y pas de définition stricte et formelle de ce qu'est un "langage fonctionnel". Il y a des outils utiles pour faire de la programmation fonctionnelle, mais souvent c'est aussi une convention "sociale", les langages dans lequel le style fonctionnel est encouragé.

Un critère objectif est le fait d'avoir ce qu'on appelle des "fonctions d'ordre supérieur". Un langage a les fonctions d'ordre supérieur quand les fonctions sont des valeurs à part entière du langage, c'est-à-dire qu'elles peuvent être reçues en arguments, renvoyées comme valeur de retour, et construites à tout moment de l'évaluation.

Les pointeurs de fonctions en C, à ma connaissance, ne remplissent pas tout à fait ce cahier des charges : on peut passer et renvoyer des adresses de fonctions existantes, mais ces fonctions sont créées "statiquement" dans le programme et ne peuvent pas être générées dynamiquement pendant l'exécution. Peut-être que les extensions pour les fonctions imbriquées et les fermetures/closures répondent à ce besoin, je ne sais pas.

On peut se passer de la nécessité de créer des fonctions dynamiquement en appliquant des transformations globales aux programmes qui "rendent statiques" toutes les fonctions (closure conversion, défonctionalisation...). C'est ce que font souvent les compilateurs de langages fonctionnels. Si tu as un programme utilisant des fonctions d'ordre-supérieur en tête, tu peux donc en écrire une forme transformée en C. Mais ce n'est pas satisfaisant car cette transformation globale rend le code moins maintenable et modulaire (une transformation qui était seulement locale dans le langage fonctionnel imaginaire peut te demander des modifications à de nombreux endroits dans un code C traduit).

[Ubiquité]

Mais d'aprés wikipédia, une fonction d'ordre supérieur c'est plus simple que ça :
Il suffit qu'une fonction soit capable de prendre comme paramétre une autre fonction ou bien d'en retourner une. Et ça grace au pointeur de fonction le C en est capable.
Mais effectivement on peut pas générer dynamiquement une fonction en C.*




*J'ai pour le moment pratiquement rien écrit dans un language fonctionnel, et j'arrive pas du tout à concevoir comment on peut générer dynamiquement une fonction ^^
Vivement que j'en connaisse un peu plus.

[gasche]

Tu as raison, j'ai fait une légère confusion de langage : prendre et retourner c'est "ordre supérieur" et "manipuler comme toute autre valeur" (donc ça comprend aussi la création) c'est "fonctions de première classe" (plus généralement "X de première classe" quand X est une valeur comme les autres; on peut par exemple considérer les références OCaml comme des "lvalues de première classe").


Au sujet de la création dynamique de fonctions : quand on fait de la programmation fonctionnelle on passe son temps à construire des fonctions. Par exemple, comment traduirais-tu en C le programme OCaml suivant ? L'important n'est pas ici ce qu'il fait (il calcule 1 + 2 + 3, facile), mais comment il le fait, en utilisant des fonctions.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
let compose f g = fun x -> f (g x)
let ajoute = fun a -> fun b -> a + b

let test =
  let f = compose (ajoute 1) (ajoute 2) in
  f 3

[Ubiquité]

Tu as raison, j'ai fait une légère confusion de langage : prendre et retourner c'est "ordre supérieur" et "manipuler comme toute autre valeur" (donc ça comprend aussi la création) c'est "fonctions de première classe" (plus généralement "X de première classe" quand X est une valeur comme les autres; on peut par exemple considérer les références OCaml comme des "lvalues de première classe").


Au sujet de la création dynamique de fonctions : quand on fait de la programmation fonctionnelle on passe son temps à construire des fonctions. Par exemple, comment traduirais-tu en C le programme OCaml suivant ? L'important n'est pas ici ce qu'il fait (il calcule 1 + 2 + 3, facile), mais comment il le fait, en utilisant des fonctions.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
let compose f g = fun x -> f (g x)
let ajoute = fun a -> fun b -> a + b

let test =
  let f = compose (ajoute 1) (ajoute 2) in
  f 3

J'essaye de comprendre exactement comment il le fait pour essayer de refaire la même chose en C mais je vois pas

[Mat.M]

Mais effectivement on peut pas générer dynamiquement une fonction en C.*

et j'arrive pas du tout à concevoir comment on peut générer dynamiquement une fonction ^^

qu'appelle tu "gérer dynamiquement une fonction en C" ?
Cela n'est pas possible le langage C est un langage compilé qui donne au final du code machine

[gasche]

Le langage OCaml, dans lequel j'ai donné cet exemple, est aussi compilé vers du code machine. Le compilateur ne fait pas du JIT pour les déclarations de fonction (compiler le code de la fonction pendant l'exécution), ce serait bien trop coûteux: il utilise des techniques de traduction pour éliminer les fonctions "dynamiques" (les fonctions, anonymes ou non, qui ne sont pas au toplevel).

Ubiquité : tu ne comprends pas le sens du code ((fun x -> foo) est une fonction anonyme qui renvoie (foo) quand on lui donne la valeur de (x)), ou tu ne comprends pas comment il est exécuté ?

Syntaxiquement le code a le comportement suivant :

let f = compose (ajoute 1) (ajoute 2) in f 3
=> let f = compose (fun b -> 1 + b) (fun c -> 2 + c) in f 3
=> let f = fun x -> (fun b -> 1 + b) ((fun c -> 2 + c) x) in f 3
=> (fun x -> (fun b -> 1 + b) ((fun c -> 2 + c) x)) 3
=> (fun b -> 1 + b) ((fun c -> 2 + c) 3)
=> (fun b -> 1 + b) (2 + 3)
=> (fun b -> 1 + b) 5
=> 1 + 5
=> 6

[Ubiquité]

Ubiquité : tu ne comprends pas le sens du code ((fun x -> foo) est une fonction anonyme qui renvoie (foo) quand on lui donne la valeur de (x)), ou tu ne comprends pas comment il est exécuté ?

Syntaxiquement le code a le comportement suivant :

let f = compose (ajoute 1) (ajoute 2) in f 3
=> let f = compose (fun b -> 1 + b) (fun c -> 2 + c) in f 3
=> let f = fun x -> (fun b -> 1 + b) ((fun c -> 2 + c) x) in f 3
=> (fun x -> (fun b -> 1 + b) ((fun c -> 2 + c) x)) 3
=> (fun b -> 1 + b) ((fun c -> 2 + c) 3)
=> (fun b -> 1 + b) (2 + 3)
=> (fun b -> 1 + b) 5
=> 1 + 5
=> 6

Je comprend pas le sens du code.
in f 3 ca veut dire quoi ?

[gasche]

"let x = a in b" c'est la forme des déclarations locale en Caml, ça veut dire "déclare la variable x comme ayant la valeur de a, et évalue b (qui peut utiliser x)".
Tu connais un autre langage fonctionnel (ou un autre langage qui a au moins des fonctions de première classe) dans lequel je pourrais fournir l'exemple ?


En Javascript:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function compose(f, g) {
    return function(x) {
        return f(g(x));
    }
}

function addition(a) {
    return function(b) {
        return a + b;
    }
}

var f = compose(addition(1), addition(2));
var test = f(3);

[Ubiquité]

Je galere pour faire ca en C mais en C++ avec les foncteurs ca doit être bien plus faisable.

Déjà la fonction addition pen C++ peut être un foncteur comme celui là :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Addition {
private:
  double a;
public:
  Addition (double _a)
    :a(_a)
  {
  }

  double operator()(double _b)
  {
    return _b + a;
  }
}

[TropMDR]

C et C++ dans leur version actuelle ne sont pas du tout des "langages fonctionnels" parce qu'ils ne permettent pas de capture de variable lors de la définition des fonctions (c'est ça qui permet de "créer dynamiquement" des fonctions, appelées aussi "fermetures").

Prenons un exemple de ce que permettrait la capture en C (en fait, de ce qu'elle permet, grace à l'extension "block" d'apple)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* Exemple tiré de Wikipedia*/
#include <stdio.h>
#include <Block.h>
typedef int (^IntBlock)();
 
IntBlock MakeCounter(int start, int increment) {
        __block int i = start;
 
        return Block_copy( ^ {
                int ret = i;
                i += increment;
                return ret;
        });
 
}
 
int main(void) {
        IntBlock mycounter = MakeCounter(5, 2);
        printf("First call: %d\n", mycounter());
        printf("Second call: %d\n", mycounter());
        printf("Third call: %d\n", mycounter());
 
        /* because it was copied, it must also be released */
        Block_release(mycounter);
 
        return 0;
}
/* Output:
        First call: 5
        Second call: 7
        Third call: 9
*/

L'idée est que dans la fonction MakeCounter, on "crée" une nouvelle fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
        return Block_copy( ^ {
                int ret = i;
                i += increment;
                return ret;
        });

Cette fonction utilise deux variables, i et increment, qui ne sont pas des variables globales, et qui ne sont pas définis directement dans la fonction. Ce sont des variables qui ont été "capturées" depuis la fonction MakeCounter.

En développant un peu cet exemple (et sans avoir testé), supposons que la fonction main deviennent

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(void) {
        IntBlock mycounter52 = MakeCounter(5, 2);
        IntBlock mycounter11 = MakeCounter(1, 1);
        printf("First call of 5 2: %d\n", mycounter52());
        printf("First call of 1 1: %d\n", mycounter11());
        printf("Second call of 1 1: %d\n", mycounter11());
        printf("Second call of 5 2: %d\n", mycounter52());
 
        /* because it was copied, it must also be released */
        Block_release(mycounter52);
        Block_release(mycounter11);
 
        return 0;
}

Ca produirait la sortie

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
First call of 5 2: 5
First call of 1 1: 1
Second call of 1 1: 2
Second call of 5 2: 7

On voit qu'il y a bien deux fonctions différentes qui ont été produites, et qu'elles ne partagent pas leurs variables capturées.

Et attention, ici tous les paramètres sont connus, mais il n'y a pas deux fonctions créées lors de la compilation. On pourrait très bien imaginer un tableau de fonctions

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int i;
IntBlock mycounters [10];
for(i = 0; i < 0; ++i){
  mycounters[i] = MakeCounter(1, i);
}
...

ou que ça dépendent de paramètres extérieurs, etc etc.

Tout ça est impossible à faire en C standard (on peut "tricher" en créant une structure contenant le pointeur de fonction et le tableau de ses variables capturées, puis avoir une macro d'application qui rajoute le tableau comme premier argument, ce que fait sans doute l'implémentation, mais ce n'est pas la même chose !). Ce sera possible en C++0x avec les "lambdas"

J'espère que ça aide avec une syntaxe moins "caml" (même si la syntaxe caml est quand même nettement plus adaptées :-D)

[Ubiquité]

Donc finalement avoir des fonctions d'ordre supérieur ne suffit pas ? Les fonctions d'un langage doivent être un objet de première classe pour que le langage implement le paradigme fonctionnel ?


Et t'es sur que les foncteurs du c++ ne permettent pas la capture ?

[gl]

Et t'es sur que les foncteurs du c++ ne permettent pas la capture ?

Non, les foncteurs ne capturent pas en C++.

On peut se rapprocher de ce comportement avec les foncteurs et leurs constructeurs mais il n'y a pas de capture.

[gasche]

Donc finalement avoir des fonctions d'ordre supérieur ne suffit pas ? Les fonctions d'un langage doivent être un objet de première classe pour que le langage implement le paradigme fonctionnel ?

Oui.

Si tu n'arrives pas à implémenter mon exemple dans un langage de programmation (en utilisant des fonctions), il peut difficilement se prétendre un langage fonctionnel.

[Ubiquité]

Oki,
Merci pour toutes les précisions.
Quand je reviendrai je serai surement entrain de lire Real World Haskell.

[LLB]

Pour info, les fonctions anonymes arrivent avec C++0x (et on choisit à chaque fois si la capture se fait par copie ou par référence).

[NokyDaOne]

Tous les langages savent manier les fonctions (sauf JAVA qui a décider de suivre la voie 100% objet) vu que l'assembleur sait le faire.

Ce qui fait réellement un langage fonctionnel, c'est l'application partielle. Dès que l'on a cette fonctionnalité on peut coder en fonctionnel, quand on ne l'a pas on ne peut pas coder en fonctionnel. Et dans ce domaine le C est un incapable. Ce n'est donc pas un langage fonctionnel.

[gasche]

NokyDaOne > pardon ? L'assembleur "gère les fonctions" ? Comment ? Mais il ne "gère" pas l'application partielle ? Qu'est-ce que c'est ?
Ça ne veut pas dire grand chose ce que tu dis...

[NokyDaOne]

NokyDaOne > pardon ? L'assembleur "gère les fonctions" ? Comment ? Mais il ne "gère" pas l'application partielle ? Qu'est-ce que c'est ?
Ça ne veut pas dire grand chose ce que tu dis...

Ce que je voulais dire c'est que l'assembleur gère les pointeurs de fonction (c'est la raison pour laquelle le C sait le faire). Mais l'assembleur ne permet pas de faire d'application partielle (c'est la raison pour laquelle le C ne sait pas le faire).
Si, ce que je dis veut dire quelque-chose , je m'exprime mal, c'est tout.

[gorgonite]

Ce que je voulais dire c'est que l'assembleur gère les pointeurs de fonction (c'est la raison pour laquelle le C sait le faire). Mais l'assembleur ne permet pas de faire d'application partielle (c'est la raison pour laquelle le C ne sait pas le faire).

euh c'est extrêmement réducteur... tu en arrives presque à dire que C = assembleur en terme de fonctionnalités
je sais bien que les aficionados français des langages fonctionnels sont plus proches de la famille ML, mais il ne faudrait tout de même pas dire que la famille Algol (et son représentant le plus représenté aujourd'hui : C) est limitée à l'assembleur...