Discussion :

[SpiceGuid]

On va assister à une intégration plus ou moins poussée de la notion de fonction anonyme et de fermeture lexicale dans les langages/plateformes les plus utilisées.

Par contre pour les notions d'immutabilité, d'inférence de type, de types algébriques et de filtrage, ça va rester assez confidentiel.

Il y a deux opportunités pour le paradigme fonctionnel:

1. la course à la fréquence n'a pas stoppé mais elle a tellement ralenti que pour l'instant seul le niveau de parallélisme offre des perpectives de gains importants
2. le niveau des normes concernant les systèmes critiques ne cesse de monter

Le gros problème pour la première opportunité c'est l'étroitesse de la fenêtre de tir, le monde des semi-conducteurs est très réactif et le parallélisme est une mode qui n'a pas encore trouvé sa killer-app. Et si elle la trouvait je doute que ce soit du côté de la programmation fonctionnelle.

Sachant que la mode dans le fonctionnel est à la certification, ça deviendra peut être un paradigme important dans les domaines sensibles à la sureté. Et dans le secteur des services ça pourrait devenir un gage de sérieux pour les candidatures à l'embauche. Mais là encore ça peut tenir à des intangibles comme le succès d'image de F#. Récemment, avec Vista, on a bien vu les conséquences d'image d'une campagne promotionnelle trop aggressive et des exigences trop éloignées de la réalité des utilisateurs.

[gorgonite]

pour infos, C++0x semble quand même avoir adopté l'inférence de type

[InOCamlWeTrust]

vou zavez rien comprieuh ! le futur, c'est Java é lé zapplicassion internèteuh !mon prof y me la di !

[LLB]

pour infos, C++0x semble quand même avoir adopté l'inférence de type

Si c'est de l'inférence de type comme dans C#, je n'appelle pas ça de la vraie inférence :

Code :

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

var x = "test";

Le type de "test" était déjà connu par le compilateur, il suffit de le réutiliser pour x. Tous les cas les plus intéressants de l'inférence ne sont pas traités.

[gorgonite]

Si c'est de l'inférence de type comme dans C#, je n'appelle pas ça de la vraie inférence :

Code :

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

var x = "test";

Le type de "test" était déjà connu par le compilateur, il suffit de le réutiliser pour x. Tous les cas les plus intéressants de l'inférence ne sont pas traités.

je crois que c'est quand même plus complexe que cela...

enfin, c'est quand même un bon début pour un langage "classique", attendons la suite

[HanLee]

Si c'est de l'inférence de type comme dans C#, je n'appelle pas ça de la vraie inférence :

Code :

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

var x = "test";

Le type de "test" était déjà connu par le compilateur, il suffit de le réutiliser pour x. Tous les cas les plus intéressants de l'inférence ne sont pas traités.

Donne un exemple plus complexe ?
Et c'est quoi les limites de l'inférence de type C# ?
Il me semble que l'inférence de type du C++ sera plutôt pas mal évoluée.

[LLB]

L'inférence de type se limite à la déclaration de variables locales, il me semble. C'est donc de la forme :

Code :

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

var id = expression

Le compilateur a toujours connu le type de l'expression. Il s'en servait pour vérifier le typage. Donc, réutiliser ce type pour la déclaration de la valeur est simpliste.

Inférer le type des arguments d'une fonction est déjà plus compliqué et plus intéressant.

En F# :

Code :

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

let f x y = x + x * y

La fonction f a 2 arguments, qui suivent un certain nombre de contraintes. Le type définitif de f sera fixé à la première utilisation (dans ce cas, le type de f dépend du contexte). Ou sinon, f peut être vraiment générique avec le mot-clé "inline". Son type est alors :

Code :

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

1
2
3
4
val inline f :
   ^a ->  ^c ->  ^d
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b ->  ^d) and
         ( ^a or  ^c) : (static member ( * ) :  ^a *  ^c ->  ^b)

En gros, il faut que les opérateurs d'addition et de multiplication soient définis sur les arguments. Le type de retour de la fonction dépend du type des arguments, ainsi que des méthodes disponibles. C'est donc quelque chose d'autrement plus complexe.

Pareil pour OCaml :

Code :

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

1
2
3
# let f x y = x#foo + y#foo * x#bar;;

val f : < bar : int; foo : int; .. > -> < foo : int; .. > -> int = <fun>

La fonction f prend deux objets en argument, l'un ayant les attributs foo et bar, l'autre juste bar. La fonction renvoie un type entier.



Ensuite, on peut donner d'autres exemples plus complexes avec les fonctions d'ordre supérieur. Par exemple, le type List.map est entièrement inféré par le compilateur. Ca m'étonnerait fortement que le compilateur C# puisse en faire autant.

[HanLee]

Ben je crois que C++0x sera capable d'en faire autant à peu près.

Papier de 2003 :
http://anubis.dkuug.dk/jtc1/sc22/wg2...2003/n1527.pdf

Papier de 2006 :
http://www.open-std.org/jtc1/sc22/wg...2006/n2115.pdf

Le 2003 comporte des introductions, le 2006 est plus direct dans la spécification de la norme, un peu moins lisible.

[gorgonite]

l'exemple "standard" est :

Code c++ :

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

1
2
3
4
5
6
7
8
9
10
 
int main () {
  auto a = 4;
  std::vector<int> v;
  v.push_back(a);
  v.push_back(2);
  for (auto i = v.begin() ; i != v.end() ; ++i) {
    // ...
  }
}

contrairement à ce que l'exemple de LLB aurait pu faire croire (attention, je n'ai dit que LLB a dit quelque chose de faux ), auto ne fait qu'utiliser une recherche du type (natif ou précédemment déclaré) tout comme l'aurait fait decltype(v.begin())


plus d'infos : http://www.open-std.org/jtc1/sc22/wg...2006/n2115.pdf



EDIT : arf, grillé... trop tard

[nonpoluant]

Le paradigme fonctionnel, basé sur le lambda calcul, a ceci de particulier qu'on ne modifi pas la memoire interne de la machine.
Comme dit précédement, c'est une bonne chose car cela permet de savoir à tous les coups ce qu'il y a dedans quand on la lit, et donc évite les erreures.
Mais ça interdit les tableaux comme structure de donnée.

Le tableau est la seule structure de donnée que je connaisse, où les éléments sont accessibles en temps constant. Et donc tous les algorithmes efficaces basé sur cette propriété des tableaux, tombent à l'eau en programmation fonctionnelle.

J'aurais aimé savoir comment faire donc, sans tableau, pour avoir une structure de donnée où les éléments sont accessibles en temps constant, et donc pouvoir s'en servir pour déveloper dessus les algo les plus efficaces possibles??

[InOCamlWeTrust]

On pourrait faire, bien que ce ne soit jamais implanté dans les langages réels, des tableaux non modifiables dont les éléments sont accessibles en temps constant.

Il serait, par exemple en OCaml, possible de créer un module utilisant les tableaux classiques, mais en en abstrayant le type, dont les éléments de la structure de données seraient tous accessibles en temps constant.

C'est très simple à faire, et l'utilisateur final n'a pas à connaître la structure de données réelle.

[nonpoluant]

Mais y a un problème.

Dans une liste, on simule la modification d'un élément, en enlevant l'élément et en le remplaçant par un autre, et en reconstruisant la liste. La complexité de ça c'est globalement linéaire, comme dans la modification d'une liste en langage impératif. Donc on ne perd pas vraiment en performence.

La modification d'un élément d'un tableau, en langage imperatif, est clairement constant. Je ne vois pas commencer simuler ça en fonctionnel, car pour le simuler il faudrait reconstruire le tableau, ce qui se fait en temps linéaire.

Est-ce que je me trompe quelque part?

[SpiceGuid]

Le tableau est la seule structure de donnée que je connaisse, où les éléments sont accessibles en temps constant. Et donc tous les algorithmes efficaces basés sur cette propriété des tableaux, tombent à l'eau en programmation fonctionnelle.

L'élément d'un tableau n'est accessible en temps constant que si tu le désignes par son indice, si tu cherches le minimum, le maximum, ou tout autre élément satisfaisant une quelconque propriété, alors cet élément n'est accessible qu'en temps linéaire.

Or, satisfaire à une certaine propriété c'est l'exigence la plus courante en algorithmie, être désigné par un indice entier c'est surtout le cas des opérations de bas niveau, en fait c'est principalement réservé à l'accès à une variable par son indice De Bruijn.

Pour les besoins courants tu as des équivalences entre algos impératifs et fonctionnels, la version fonctionnelle étant parfois asymptotiquement meilleure:

• le quicksort est à remplacer par le merge-sort
• la recherche par dichotomie et la table de hachage sont à remplacer par l'AVL (foncteur Map.Make en OCaml)

La modification d'un élément d'un tableau, en langage imperatif, est clairement constant. Je ne vois pas commencer simuler ça en fonctionnel, car pour le simuler il faudrait reconstruire le tableau, ce qui se fait en temps linéaire.

Est-ce que je me trompe quelque part?

À l'aide d'un arbre binaire la copie modifiée du tableau se fait en un temps linéaire au nombre de bits du mot machine, c'est-à-dire en 32 ou 64 étapes maximum. C'est une constante.
Mais en pratique il est plus direct de ne pas utiliser du tout d'indices entiers.

[nonpoluant]

la table de hachage [est] à remplacer par l'AVL

Je supose que tu parles du chainage lors de la gestion des colisions?

indice De Bruijn.

Je n'sais pas du tout c'que c'est qu'ça. Désolé pour mon ignorance.

À l'aide d'un arbre binaire la copie modifiée du tableau se fait en un temps linéaire au nombre de bits du mot machine, c'est-à-dire en 32 ou 64 étapes maximum. C'est une constante.

Je n'connais pas non plus cette technique/propriété. Toujours à cause de mon ignorance. Comment cela est-il mis en oeuvre??


Il faut quand même avouer, que la façon de résoudre un problème est quand même plus subtil par une approche fonctionnelle, que par une approche impérative. J'utilise ici le mot "subtil"... non pas dans un sens negatif mais... plutôt dans le sens où c'est quand même pas donné aux amateurs quoi (noté que j'ai pas utilisé le mot "naturel", ou "facile", pour pas relancer le débat là dessus mdr).

[SpiceGuid]

• L'indice De Bruijn c'est le déplacement dans la fenêtre de pile (offset d'une variable dans la stack-frame)
• Un AVL est un arbre binaire (de recherche) équilibré
• Dans un arbre binaire le chemin qui mène de la racine à un certain noeud est de la forme (left|right)*, alors qu'un entier en base 2 est de la forme (0|1)*. L'astuce consiste à considérer l'indice dans un tableau d'abord comme un entier en base 2 puis comme un chemin dans un arbre binaire, bit à 0 aller à gauche, bit à 1 aller à droite. Pour modifier un élément il suffit alors de dupliquer le chemin depuis la racine jusqu'à la feuille et de n'y changer que la valeur de la clé concernée.

[nonpoluant]

Je sais ce qu'est un AVL, mais une table de hache est un tableau muni d'une fonction de hachage. L'un des principes pour gerer les colisions est l'utilisation de listes chainés, mais sur wikipedia il est dit que ces listes chainés peuvent être remplacé par des arbres équilibrés. Je me demandais si c'etait de ça que tu parlais.
Mais au vu de ce que tu dis, j'ai plutot tendance à penser que tu parles d'un AVL pour remplacer la totalité de la table de hachage, et de la recopier à chaque fois en un temps 32 ou 64 comme tu le ferais pour simuler un tableau. Et biensur, tu résoud les colisions par la technique de l'adressage ouvert.

En tout cas c'est très interessant.

[gorgonite]

pour infos, quand SpiceGuid parle d'équivalences quicksort/mergesort, il y a quand même un ENORME oubli... le fait que le tri soit fait sur place, ce qui est un plus si l'on traite beaucoup de données, ou que l'on se place en environnement "limité"

[SpiceGuid]

Effectivement, ça n'est pas du tout une équivalence, c'est seulement un substitut d'une façon impérative (avec utilisation d'un tableau) vers une autre façon plus fonctionnelle (sans utilisation d'un tableau).
Ça vaut aussi pour les hashtableet les AVL qui sont substituables en terme d'interface mais qui ont aussi leurs qualités respectives.

Tout ça pour dire qu'il ne faut pas forcément utiliser les même algos en fonctionnel qu'en impératif ( le quicksort sur les listes dans tools/basis.anubis).

[nonpoluant]

il y a quand même un ENORME oubli... le fait que le tri soit fait sur place

J'imagine, mais ce n'est pas le propos de ma question, d'autant plus que cette difference est en faveur du tri fusion. Ma question porte seulement sur la complexité.

EDIT en rapport avec le message du dessous :
pardon, tu as dis "sur place" dans ma tete j'ai pensée "stable"

[gorgonite]

J'imagine, mais ce n'est pas le propos de ma question, d'autant plus que cette difference est en faveur du tri fusion.

ben tu n'as soit jamais fait de "gros" programmes, soit rien compris à ce que j'ai dit plus haut

Ma question porte seulement sur la complexité.

ben tu as ta réponse... il est possible d'avoir des structures de même complexité dans les langages fonctionnels (même si ce sera surement une interface fonctionnel sur quelque chose d'impératif ), donc les mêmes complexités théoriques