La référence la plus vénérable utilisée en programmation à propos du mot "paradigme" est probablement celle d'un ouvrage d'épistémologie de T.S. Kuhn intitulé "The Structure of Scientific Revolutions". Univ. of Chicago Press, 1962.
Ce mot apparaît également dans des textes comme celui de R.W. Floyd, "The paradigms of programming", Commun. ACM 22, 1979, où il s'agissait d'exposer la situation à propos des techniques de résolution de problèmes par la programmation. Les "paradigmes" étaient alors d'ordre assez divers, par ex. la "programmation structurée", la "division-pour-régner", le "branch-and-bound", l'"orienté-règle", la "construction hiérarchisée de langages", le "genérer/flitrer/accumuler", la "machine à état", etc. (et donc nous n'étions pas loin d'une énumération avec raton-laveur).
Dans les années 80, l'usage a fixé l'expression "paradigme de programmation" afin d'établir surtout des distinctions générales parmi les langages de programmation (et non plus parmi les techniques de résolution de problèmes). On trouve par ex. une assez bonne description informelle du concept de "paradigme" dans le livre classique de J. Coplien, "Advanced C++, Programming Styles and Idioms", Addison-Wesley, 1992 : "The rules, conventions, and concepts of programming drive the structure of the systems we build: They give us a model of how to build systems. A model for problem decomposition and system composition is a *paradigm*, a pattern for dividing the world into manageable parts."
Les catégories impératif/fonctionnel/logique/distribué/etc. sont alors
devenues usuelles. Une des références historiques de ce fait est celle de
P. Wegner : "Introduction to programming language paradigms". ACM Computing
Surveys, 21, 1989. Ensuite, la plupart des livres sur les langages de
programmation se sont fait l'écho de ces catégories. Par exemple, un livre
où elles sont présentées de manière plutôt claire est celui de D. Appleby et
J. VandeKopple, "Programming Languages (Paradigms and Practice)", Mc Graw
Hill, 1997 (1991).
Parmi les langages qui offrent une multiplicité de constructions et de styles (cf. C++, Java, Ada, etc.), il faut également citer C# qui, non content d'être objet et générique, offre aussi des possibilités de programmation fonctionnelle (en particulier depuis sa version 3.0). Quelques textes au sujet de C# traitent désormais de l'intégration de techniques de programmation fonctionnelle en programmation objet : par ex. certains chapitres dans "C# Cookbook", de Jay Hilyard and Stephen Teilhet, chez O'Reilly, 2006, ou le livre "C# 3.0 Design Patterns" de J. Bishop, chez O'Reilly, 2008. On pourra également se rapporter à notre tentative de synthèse sur le sujet).
Afin de bien faire comprendre que les entrées/sorties sont également
problématiques pour la programmation fonctionnelle de base, il suffit de
reconsidérer l'expression f(1)-f(1) basée sur l'opération
f de la p. 2, et de l'adapter de la manière suivante (en supposant
que readint est une fonction qui lit un entier sur l'entrée
standard) :
x = readint() - readint();
On voit ici les mêmes problèmes apparaître que ceux de l'opération
f : la valeur x dépend de l'ordre d'évaluation des deux
readint, et elle n'est évidemment pas assurée d'être 0. L'opération
readint n'est certes pas une fonction au sens mathématique.
Une "définition par intention" d'une fonction est une description finie en termes abstraits OU basée sur une procédure de calcul. L'implémentation d'une fonction peut donc également constituer en elle-même une définition par intention.
À propos de l'ambiguÏté de syntaxe qui demande à ce que le programmeur OCaml
ajoute des espaces lors d'une désinfixation -- par ex. "( * )" au
lieu de "(*)" --, et qui n'est pas du plus bel effet, on notera que
le même genre de problème existe aussi en C -- par ex. "n/ *p" au
lieu de "n/*p", rendu également nécessaire par la syntaxe des
commentaires du C--, et aussi dans les expressions imbriquéees de templates
C++ -- par ex. "Stack
La version du pliage des arbres présentée en p. 255 n'est pas aussi générale
qu'elle aurait pu l'être. Rappelons-la :
let rec tree_fold g f e t = match t with
| TreeEmpty -> e
| TreeNode (x, t_list) ->
g x (List.fold_left f e
(List.map (tree_fold g f e) t_list));;
(* ('a -> 'b -> 'b) -> ('b -> 'b -> 'b) -> 'b -> 'a tree -> 'b *)
En particulier, cette fonction de pliage ne permet pas d'obtenir facilement une implémentation du map. En effet, l'argument e ci-dessus se doit d'être de type tree, et donc 'b est instancié par tree. Ainsi, l'argument f qui est de type ('b -> 'b -> 'b) ne peut produire qu'un arbre, alors que l'on s'attendrait à ce qu'il produise une liste de sous-arbres modifiés par le map.
Voici 3 façons de remédier à cette faiblesse :
let rec tree_fold f e t = match t with
| TreeEmpty -> e
| TreeNode (x, t_list) ->
f x (List.map (tree_fold f e) t_list);;
(* ('a -> 'b list -> 'b) -> 'b -> 'a tree -> 'b *)
Ce pliage est donc établi à partir d'une fonction f de type ('a
-> 'b list -> 'b). Le map est alors aisément obtenu :
let tree_map f t = tree_fold (fun x l -> TreeNode(f x, l)) TreeEmpty t;;
(* ('a -> 'b) -> 'a tree -> 'b tree *)
Néanmoins, l'implémentation de la plupart des traitements n'est pas très
facile, car la fonction de pliage doit inclure explicitement la gestion d'une
liste. Par exemple :
let tree_sum t = tree_fold (fun x l -> x + (List.fold_left (+) 0 l)) 0 t;;
let rec tree_fold g f e1 e2 t = match t with
| TreeEmpty -> e1
| TreeNode (x, t_list) ->
g x (List.fold_left f e2
(List.map (tree_fold g f e1 e2) t_list));;
(* ('a -> 'b -> 'c) -> ('b -> 'c -> 'b) -> 'c -> 'b -> 'a tree -> 'c *)
On remarque alors que l'on obtient ici un type avec trois variables distinctes
de type au lieu de deux. Désormais, le map peut s'écrire ainsi :
let tree_map f t =
tree_fold (fun x l -> TreeNode(f x, List.rev l))
(fun l x -> x :: l)
TreeEmpty [] t;;
(Remarque : le List.rev ci-dessus n'est pas strictement nécessaire en termes d'isomorphisme d'arbres -- par ex. TreeNode(x, [t1, t2]) est isomorphe à TreeNode(x, [t2, t1]). Néanmoins, il peut y avoir des cas où l'ordre des sous-arbres dans leur liste respective est importante. Notons à ce propos que l'utilisation de List.fold_right dans tree_fold permettrait de résoudre ce problème de manière plus directe.)
Et comme attendu, l'implémentation des traitements de base est alors facilitée :let tree_sum t = tree_fold ( + ) ( + ) 0 0 t;;
type 'a bintree =
| BinEmpty
| BinNode of 'a * 'a bintree * 'a bintree;;
let rec bin_fold f e t = match t with
| BinEmpty -> e
| BinNode(x, t1, t2) -> bin_fold f (f x (bin_fold f e t1)) t2;;
(* ('a -> 'b -> 'b) -> 'b -> 'a bintree -> 'b *)
Ce pliage -- fondé sur une fonction binaire -- dépend ici d'un parcours en
profondeur, et fonctionne sans problème lorsque f se trouve être
associative et commutative. Cette idée peut être étendue à n'importe quelle
structure. Et par exemple pour les arbres :
let fold f e t =
let rec down e t = match t with
| TreeEmpty -> e
| TreeNode(x, t_list) -> f x (right e t_list)
and right e t_list = match t_list with
| [] -> e
| x :: xs -> down (right e xs) x
in down e t;;
(* ('a -> 'b -> 'b) -> 'b -> 'a tree -> 'b *)
Les lecteurs interessés par ces questions de pliage pourront se référer aux travaux qui les ont généralisées, par ex. le chapitre "Origami Programming" de J. Gibbons. dans le livre "The Fun of Programming", Cornerstones in Computing. Palgrave, 2003, ou l'article "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" de E. Meijer, M. Fokkinga, R. Paterson, 1991, Springer-Verlag, LNCS 523.
Ce style de programmation peut être décrit dans un cadre plus général que celui de la programmation fonctionnelle.
En effet, la programmation dirigée par les données est également le fait "d'établir une distinction claire entre le code et les données sur lesquelles ce code agit, de manière à ce que l'on puisse changer la logique d'un programme non pas en modifiant le code mais les données" (E. Raymond dans son "The Art of Unix Programming", Addison, 2004 -- traduit chez Vuibert, 2006.)
Par conséquent, si les fonctions de première classe facilitent évidemment la concrétisation de cette technique, elles ne lui sont pas nécessaires. On pourra à ce titre considérer l'exemple en programmation objet de R.C. Martin dans "Agile Software Development", Prentice Hall, 2003, pp.107-108, qui exploite la programmation dirigée par les données afin d'améliorer les possibilités d'extension d'un ensemble de classes.
La programmation dirigée par les données peut également se rattacher à un problème plus général -- et souvent associé à la programmation objet --, à savoir, la sélection des méthodes. En effet, cette technique peut être aussi décrite ainsi: il s'agit de sélectionner des fonctions au vu de certaines données, et cette sélection peut être dépendante de mécanismes explicitement implémentés par le programmeur (cf. par ex. Richard P. Gabriel, Jon L. White, Daniel G. Bobrow dans "CLOS: integrating object-oriented and functional programming" September 1991, Communications of the ACM, Volume 34 Issue 9).
Rappelons cette notion telle qu'elle apparaît dans le texte :
Soit S l'ensemble des signatures qui spécifient un programme modulaire P, et soit M un composant de P qui satisfait une signature s dans S. Alors, tout composant qui satisfait également s peut être substitué à M sans entraîner d'autres modifications dans P.
En fait, cet énoncé est à comparer avec celui dit du Principe de substitution de Liskov (cf. "Data Abstraction and Hierarchy". B. Liskov. SIGPLAN Notices. 1988 -- voir aussi "Agile Software Development" de Martin. Addison. 2003, ou "Multi-Paradigm Design in C++" de Coplien. Addison. 1999.) :
Si pour chaque objet o1 de type S, il y a un objet o2 de type T tel que pour tous les programmes P definis en termes de T, le comportement de P se trouve inchangé lorsque o1 est substitué à o2, alors S est un sous-type de T.
D'autre part, on trouve des traces de ce néologisme difficile à prononcer au petit matin, -- i.e. "substitutivité" -- dans le livre de Szyperski et al., "Component Software, Beyond Object-Oriented Programming", Addison. 2002. cf. pp. 83-87 et p.566, ainsi que dans l'article "On Object System and Behavioral Inheritance", de D. Harel et O. Kupferman, IEEE Transactions on Software Engineering, vol. 28, 9, 2002.
Les définitions d'agrégation et d'association de types de données modulaires présentées dans le livre sont les équivalents des définitions classiques en programmation objet, mais cela en *OMT* (Object Modeling Technique). Ce cadre de description des concepts objet -- tombé en désuétude actuellement -- est celui utilisé dans le livre "Design Patterns" de Gamma et al.
Il est alors important de souligner que ces mêmes termes -- c'est-à-dire agrégation et association -- prennent des sens différents en UML (Unified Modeling Language), et non loin d'en être les inverses réciproques...
Un bon article qui explique le fonctionnement et les enjeux de la généricité en Java 5,6 pour le programmeur est celui de M. Odersky et Ph. Wadler, "Leftover Curry and reheated Pizza: How functional programming nourishes software reuse", Fifth International Conference on Software Reuse, IEEE, 1998. Cet article explique de manìère claire la tactique dite de l'"effacement" (erasure) qui distingue la généricité modulaire de Java de celle de C++ ou de celle de ML.
(Remarque : notons que malgré ses qualités, le titre de cet article n'est pas des moins trompeurs. Tout d'abord, rappelons que "Pizza" fut le nom de code d'un prototype qui permettait à Java d'être générique avant Java 5. D'autre part, cet article ne parle quasiment pas de programmation fonctionnelle. Le rapprochement entre généricité et programmation fonctionnelle n'est évoqué qu'au sujet des fonctions génériques, certes un outil important pour bénéficier d'une réutilisation flexible et statiquement typée des fonctions.)