Un langage fonctionnel repose sur l'idée que tout (ou presque est fonction). Cela n'est possible qu'avec des notations non classiques (au sens de Pascal, C etc.), des structures de données non conventionnelles et des mécanismes dédiés d'interprétation. Nous prendrons comme exemple Lisp, Apl et un langage récent, celui de Mathematica (mais on aurait aussi pu choisir Maple).Problèmes posés par le postulat "tout est fonction"
Dans un langage classique, on distingue des expressions, des fonctions, des sous-programmes. Tout ramener à des fonctions est possible mais demande des aménagements et en particulier aboutit à une écriture non "naturelle". Ainsi l'expression 3 + 2 peut être comprise comme l'application de la fonction Plus aux arguments 2 et 3. De même, l'affectation x <-- 1 peut être comprise comme l'application de la fonction Affecte aux arguments x et 1. On en déduit que l'instruction x <-- 1 + 2 * y doit être considérée comme la composition des trois fonctions Multiplie, Plus et Affecte. Pour faire ressortir les fonctions, il est commode de mettre la fonction en début (notation préfixée), d'où les traductions en notation fonctionnelle mathématique : 3 + 2 devient Plus(3,2) x <-- 1 devient Affecte(x,1) x <-- 1 + 2 * y devient Affecte(x,Plus(1,Multiplie(2,y))) L'un des problèmes principaux posés est ici la non-lisibilité de telles instructions de par la multiplication du nombre de parenthèses (du à la fonctionnalisation de toutes les expressions) et à la non-naturalité de l'ordre des expressions. Par exemple, la variance d'un échantillon qui peut se calculer comme la moyenne du carré moins le carré de la moyenne s'écrit, dans un langage classique : variance < -- moyenne(prodl(ech,ech))) - carre(moyenne(ech)) où : - prodl(x,y) renvoie la liste des produits terme à terme des listes x et y - carre(t) est simplement le carré du nombre t - moyenne(l) est la moyenne de la liste l En notation foncionnelle, cette affectation devient : Affecte(variance,Moins(moyenne(prodl(ech,ech)), carre(moyenne(ech))))Problèmes dus à l'interprétation
Pour tirer au mieux parti des fonctions, il faut utiliser des structures de données adaptées. Si on réduit toute instruction à un appel de fonction, on conçoit qu'on peut réduire toute structure de données à un modéle unique, celui de liste (terme traditionnel qui vient de Lisp, mais ambigu à notre goût). Qui plus est, on peut aussi réduire (ou intégrer, assimiler ) un appel de fonction à une liste car si on convient de noter les listes entre parenthèses et de séparer les éléments par des espaces, au lieu de la notation fonctionnelle Plus(x,y) on peut écrire, en utilisant une notation listielle (Plus x y). La notion de liste est plus fondamentale que celle de fonction puisque tout est liste alors que remplacer (x y z...) par Liste(x,y,z...) ne permet pas de de tout inclure comme fonction. C'est pourquoi Lisp ne s'appelle Foncp (LISt Processing rather than FONCtion Processing). Les listes sont alors les seules structures de données et doivent, pour répondre aux exigences des différentes fonctions être dynamiques (de longueur non fixe), hétérogènes (les éléments de la liste ne sont pas forcément de même nature), emboitables (un élément d'une liste peut contenir une autre liste) etc. Le moyen classique de gestion et d'utilisation des listes est alors la récursivité, qui amène le problème de la lisibilité (là-encore), de l'efficacité, de l'opti- misation et de la mise au point. Prenons un exemple simple, celui de la somme des n premiers entiers (problème trivial puisqu'il existe une formule, mais équivalent au problème de la somme d'une liste de n éléments, la définition des éléments en moins). Si un algorithme classique tel que : * Calcul de la somme des n premiers entiers somme <-- 0 pour i De1A n somme <-- somme + i { écrire i, somme } finpour i De1A n est simple à récursiver, le programme récursif final n'est pas unique. On peut en effet raisonnablement penser aux solutions : * Solution 1 récursive pour la somme des * n premiers entiers * Syntaxe d'appel : Somme(n) si n = 0 alors renvoyer 0 sinon renvoyer i + Somme(i-1) finsi n = 0 * Solution 2 récursive pour la somme des * n premiers entiers * Syntaxe d'appel : Somme(n) si n = 0 alors renvoyer 0 sinon renvoyer Somme(i-1) + i finsi n = 0 Ces deux solutions sont équivalents du point de vue du calcul, mais certainement pas du point de vue de la réalisation en machine. D'autre part, le commentaire de suivi dans l'algorithme itératif parait difficile à insérer. Comment suivre alors ce qui se passe ? Reprenons l'exemple du calcul de la variance. Une écriture fonctionnelle "pure et dure" ne passe pas par des variables globales. Les calculs de la moyenne de l'échantillon et de son carré sont alors calculés séparamént et récursivement par (moyenne ech) et (moyenne (prodl(ech ech))). Moyenne doit certainement être définie par : Divise(somme(listea),longueur(listea)) et longueur(listeb) par : si listevide(listeb) alors renvoyer 0 sinon renvoyer 1 + longueur(reste(listeb)) finsi listevide(listeb) où reste(lst) renvoie la liste lstprivé de son premier élément. Une telle programmation est nécessairement inefficace (même si elle est très modulaire) car elle conduit à effectuer 4 appels récursifs similaires : -. un pour longueur de ech .- un pour longueur de prodl(ech,ech) .- un pour la somme de ech .- un pour la somme de prodl(ech,ech) On se retrouve dans la situation où on écrirait sans les regrouper les 4 boucles : somme <-- 0 pour i De1A n somme <-- somme + i finpour i De1A n longech <-- 0 pour i De1A n longech <-- longech + 1 finpour i De1A n longprod <-- 0 pour i De1A n longprod <-- longprod + 1 finpour i De1A n somcar <-- 0 pour i De1A n somcar <-- somcar + i * i finpour i De1A n Une solution plus optimale serait de grouper les appels, par exemple en réalisant : Affecte(n,longueur(ech)) Affecte(variance, Moins(divise(somme(prodl(ech,ech)),n), carre(divise(somme(ech),n )))) mais on augmente encore la non-lisibilité. Et on utilise des variables globales (ce qui pour certains puristes semble être plus grave). Les mêmes problèmes ressurgissent quant à l'extraction des éléments. Si dans une structure indicée classique nommée Tab les élements Tab[1] et Tab[n] semblent jouer le même rôle et semblent être récupérables par le même mécanisme d'extraction, il en va différement pour les listes. Si Prem(lst) renvoie le premier élément de la liste lst et si Reste est définie comme précédem ment, la façon récursive d'obtenir le n-ième élément est : * Renvoie le nième élément de lst * Appel : ieme(lst,n) si n = 1 alors renvoyer prem(lst) sinon renvoyer ieme( reste(lst), n-1 ) finsi n = 1 On conçoit alors que le temps d'accès à un élement augmente sensiblement avec sa position dans la structure. Si on recherche le dernier élément de la structure, une solution comme Prem(Retourne(lst)) est aussi sympathique et monstrueuse que la solution qui consiste à trier tout un tableau et en prendre le premier élément pour en calculer le maximum. On trouvera ci-dessous quelques exemples et remarques spécifiques aux langages utilisés.Lisp
A titre d'illustration, voici quelques fonctions en LeLisp qui implémentent ce qui a été dit plus quelques autres significatives. Le calcul de la longueur d'une liste est clair sir on se rappelle que CDR renvoie la liste privée de son premier élément. Le total (rapide) de la somme des éléments d'une liste se fait grâce à Apply alors que la solution récursive (lente) a été nommée cumul. Pour tester le calcul de la somme des n premiers entiers, nous créé la fonction Iota (du nom du symbole Apl associé) telle que iota(n) renvoie la liste 1,2..n ; comme indiqué, la solution récursive "bloque" rapidement (dès n=395) alors que la solution itérative nommée iotaD permet de dépasser facilement n=1000 (mais en un temps non négligeable). (de longueur(listea) ; renvoie le nombre d'éléments de listea (cond ( (null listea) 0 ) ( t (+ 1 (longueur(cdr listea) ) ) ) ) ) ; fin de longueur (de somme (listeb) ; renvoie le total des éléments de listeb (apply '+ listeb) ) ; fin de somme (de cumul (listeb) ; renvoie le total des éléments de listeb ; calcul récursif (cond ((null listeb) 0 ) (t (+ (car listeb) (cumul (cdr listeb) ) ) ) ) ) ; fin de cumul (de iota ( nombre ) ; renvoie 1, 2 ... nombre en récursif (cond ((= 1 nombre) (list 1)) (t (append (iota (- nombre 1)) (list nombre)))) ) ; fin de iota ; nombre ne peut dépasser 395 (de iotaD ( nombre ) ; renvoie 1, 2 ... nombre en itératif (setq lst (list (setq i 1))) (while (< i nombre) (setq i (1+ i)) (setq lst (append lst (list i) )) ) ; fin de while lst ) ; fin de iotaD - on peut aller jusqu'à 1000 sans problème (de moyenne(listec) ; renvoie la moyenne des éléments de listec (/ (somme listec) (longueur listec) ) ; ou (/ (apply '+ listec) (length listec) ) ) ; fin de moyenne (de variance(listec) ; renvoie la variance des éléments de listec (- (moyenne (prodl listec listec)) (carre (moyenne listec)) ) ) ; fin de varianceApl
Les premiers interprètes Apl, aussi vieux que les premiers interprètes Lisp, ne disposaient que de tableaux hétérogènes à longueur variable. Les interprètes APL des années 80 ont des "tableaux généralisés" ou "tableaux de tableaux" qui ont de fortes similarités avec les listes de Lisp. Apl étant moins bien connu que Lisp, nous détaillerons plus les fonctions Apl que les fonctions Lisp. On peut très simplement réécrire les fonctions de base Lisp en Apl. La syntaxe Z {CARSPECIAUX 67 \f "Lucida Bright Math Sym bol"} arg1 FONCTION arg2 est en APL l'en-tête de la fonction. L'opérateur rho extrait la longueur de son argument. Alors : Z <-- IS_NIL L défini par : Z <-- 0 = {CARSPECIAUX 60 \f "Lucida Bright Math Italic"} L permet de tester si une liste est vide. L'opérateur {CARSPECIAUX 69 \f "Lucida Bright Math Symbol"} extrait des éléments. n {CARSPECIAUX 69 \f "Lucida Bright Math Symbol"} Lst extrait les n premiers éléments de Lst si n est positif, les n derniers si n est négatif. Cas particulier, 1 {CARSPECIAUX 69 \f "Lucida Bright Math Symbol"} Lst est donc le premier élément et -1 {CARSPECIAUX 69 \f "Lucida Bright Math Symbol"} Lst le dernier. De même l'opérateur {CARSPECIAUX 70 \f "Lucida Bright Math Symbol"} supprime des éléments. Dans ces conditions : Z {C ARSPECIAUX 67 \f "Lucida Bright Math Symbol"} CAR L est défini par : Z <-- 1 {CARSPECIAUX 69 \f "Lucida Bright Math Symbol"} L et Z <-- CDR L est défini par : Z <-- 1 {CARSPECIAUX 70 \f "Lucida Bright Math Symbol"} L. La concaténation par , met bout à bout en dépliant les structures alors que la concaténation par espace blanc conserve les structures. Ainsi (2 3) , 5 devient 2 3 5 alors que (2 3) 5 est exactement la liste ( (2 3) 5 ) de Lisp. Donc : Z <-- F APPEND L est défini par : Z <-- L F et Z <-- F PREPEND L est défini par : Z <-- F L Pour reprendre les fonctions récursives de Lisp, il faut savoir qu'en APL on quitte une fonction par goto 0. Le résultat explicite de la fonction peut alors être calculé en même temps comme résultat d'une affectation. D'où des expressions comme goto (IS_NIL L) / Z <-- 0 ou même, parfois (mais ce n'est pas le cas ici) comme : goto (IS_NIL L) / 0 x Z <-- (résultat) de façon à obtenir une écriture compacte. Les symboles APL ont été remplacés par leur nom en minuscule. Z <-- CUMUL L est défini par : (comment) le plus simple : (comment) Z <-- +/L qui correspond à Apply '+ (comment) SOLUTION RECURSIVE goto (IS_NIL L) / Z<--0 Z <-- (CAR L ) + CUMUL CDR L Z <-- LONGUEUR L est défiini par : (comment) le plus simple : Z <-- rho L (comment) SOLUTION RECURSIVE goto (IS_NIL L) / Z <-- 0 Z <-- 1 + LONGUEUR CDR L Z <-- MOYENNE L est défini par : Z <-- (CUMUL L)ö(LONGUEUR L) Z <-- VARIANCE L est défini par : Z <-- (MOYENNE LxL)-(MOYENNE L)*2 On remarquera ici que l'écriture pseudo-traditionnelle d'Apl gagne en lisibilité par rapport à Lisp. Elles est pourtant non naturelle aussi dans la mesure où 2 x 1 + 3 vaut 8 en APL et non pas 5 comme on serait tenté de le croire.Mathematica
Dédié aux mathématiques, le logiciel Mathematica dispose d'un langage "ultrafonctionnel" issu de Lisp, C et Apl, ce que ne fait pas ressortir ses notations à notre goût parfois maladroites. Ainsi l'appel classique f(x) d'une fonction f avec un argument x devient f[x], le renvoi à la valeur nø i du tableau tab notée d'habitude tab[i] devient tab[[i]] et la structure de base est la liste repérable à ses accolades { et } et dont les éléments sont séparés par des virgules (notation mathématique réservée en principe aux ensembles !). Mathematica est intéressant par ses réalisations : plus de 800 fonctions dédiées aux mathématiques et aux listes en général. Son langage est à la fois procédural, récursif et itératif et dynamique. Il s'exécute en mode direct et/ou en mode macro et/ou en mode programme. Nous reprenons ici l'exemple de la somme des n premiers entiers en nous inspirant fortement des "ten little n-sums" de S. Skinna ; toutefois, les n premiers entiers sont mis dans une liste et on calcule en fait la somme des éléments d'une liste. Il y a 10 façons de calculer la somme. La méthode 0 correspond à la formule n*(n+1)/2 ; l'espace en Mathematica est interprété comme la multiplication, (ce qui permet d'écrire 2 x + 1 comme en maths). La somme 1 correspond au calcul traditionnel de Lisp ave Apply ; La somme 2 est une boucle Pour implicite et la 3 une boucle Pour explicite, la boucle 4 une Tant Que. Pour la somme 5, on utilise une évaluation dynamique avec une "fonction pure" (voir plus bas). La somme 6 utilise la fonction interne Sum. Pour la somme 7, on génére la liste des cumuls progressifs des éléments de la liste et on ne conserve que le dernier terme. Pour la somme 8 on utilise les itérations de la fonction Plus ; pour la somme 9, on applique une fonction pure à chacun des éléments de la liste, obtenant ainsi une liste de cumuls dont on ne conserve que le dernier terme. Enfin, pour la somme 10, on utilise le coefficient du binôme C(n+1,2). TstSum[0] := n (n+1) / 2 TstSum[1] := Apply[ Plus, liste ] TstSum[2] := Module[ {sum=0} , Do[ sum += liste[[i]] , {i,n} ]; sum ] TstSum[3] := Module[ {sum=0,i} , For[ i=1, i<=n, i++, sum += liste[[i]] ]; sum ] TstSum[4] := Module[ {sum=0,i=1} , While[ i<=n, sum += liste[[i++]] ]; sum ] TstSum[5] := Module[ {sum=0} , Scan[ (sum+=#)&, liste ]; sum ] TstSum[6] := Sum[ liste[[i]],{i,n} ] TstSum[7] := Module[ {sum=0,i} , Last[ Table[sum+=liste[[i]],{i,n} ]]] TstSum[8] := Last[ FoldList[Plus,0,liste]] TstSum[9] := Module[ {sum=0} , Last[ Map[(sum+=liste[[#]])&,liste]]] TstSum[10] := Binomial[n+1,2] Pour tester ces sommes, on donne une valeur à n, on génère la liste des n premiers entiers grâce à la fonction Range qui est la fonction équivalente à Iota d'Apl. On calcule alors grâce à Table la liste des temps d'exécution en secondes. Ceux-ci correspondent au premier élément de la liste renvoyée par la fonction Timing. L'extraction au niveau de la liste se fait par l'utilisation conjointe de Map et de First. Enfin, pour générer les colonnes de résultat (numéro et cadrage non compris) on compose la représentation matricielle (MatrixForm) avec la fonction de représentation numérique (N) apliquées à une partie entière d'une fonction pure qui donne les centièmes de secondes et le rapport au premier élément de la liste, soit les instructions : n = 100000 ; liste = Range[n] ; som = Map[ First, Table[Timing[TstSum[i]],{i,0,10} ] /. Second -> ""] ; MatrixForm[ N[ Map[ Floor[List[100 #,#/First[som]]]& , som ]]] La liste nommée som contient vaut : {0.27,11.81,96.94,118.92,117.48,81.95,45.54,109.3,70.47,266.27,1.05} et l'affichage final est, hormis la présentation : nø Centième Rapport de durée de seconde 0 27 1 1 1181 43 2 9694 359 3 11892 440 4 11748 435 5 8195 303 6 4554 168 7 10930 404 8 7047 260 9 26627 986 10 105 3 Les fonctions pures, issues du lambda calcul, sont des fonctions anonymes. Ainsi, pour calculer 2^1, 2^2 ... 2^n, on peut définir la fonction PdD (puissance de deux) et l'appliquer à une liste, soit les instructions : PdD[x_] := 2^x ; Apply[ PdD, Range[n] ] ou définir la fonction pure # 2^# et l'intégrer comme argument 1 de Apply : Apply[ 2^#& , Range[n] ] Le symbole # désigne la variable courante et le symbole & indique la fin de définition de la fonction. En particulier, on utilise cette technique avec des fonctions sur liste, comme Map, Apply, Select. Par exemple, l'instruction Length[ Select[ Table[Random[Integer,100],{10}], #<50& ] ] indique combien, sur 10 nombres aléatoires entiers entre 1 et 100, sont inférieurs à 50. Une somme récursive comme : SumRec[0_] := 0 ; SumRec[n_] := n + SumRec[n-1] ; est encore plus longue à s'effectuer ; pour la valeur de n proposée (n = 100000) le nombre d'appels récursifs dépasse la puissance de la machine... Toutefois, Mathematica permet une construction dynamique grâce à l'écriture : SumRec[n_] := SumRec[n] = n + SumRec[n-1] ; L'expression SumRec[n_] := est la définition de la fonction SumRec dont n est l'argument (repéré par l'espace souligné) ; l'expression SumRec[n] = correspond à l'affectation pour la valeur n du résultat de la fonction. C'est un peu comme si SumRec construit un tableau SumRec avec les valeurs trouvées au fur et à mesure. Malheureusement, même avec cette construction, la barre des n = 100000 ne peut toujours pas être franchie. Ce genre de construction est particulièrement intéressant pour les suites du genre Fibonacci ou Ackerman. Le détail des fonctions de Mathematica peut être rendu plus explicite grâce à la session suivante où les In[] sont les entrées clavier et les Out[] les résultats produits par M athematica. Le ? est une demande de renseignements et << le chargement d'un fichier de commandes. Mathematica 2.0 for MS-DOS 386 Copyright 1988-91 Wolfram Research, Inc. In[1] := n = 3 Out[1] = 3 In[2] := v = Array[x,n] Out[2] = {x[1], x[2], x[3]} In[3] := Apply[f,v] Out[3] = f[x[1], x[2], x[3]] In[4] := Map[f,v] Out[4] = {f[x[1]], f[x[2]], f[x[3]]} In[5] := FoldList[f,x0,v] Out[5] = {x0, f[x0, x[1]], f[f[x0, x[1]], x[2]], f[f[f[x0, x[1]], x[2]], x[3]]} In[6] := << sumrec.m In[7] := ? SumRec Out[7] = Global`SumRec SumRec[0] := SumRec[0] = 0 SumRec[n_] := SumRec[n] = n + SumRec[n - 1] In[8] := SumRec[3] Out[8] = 6 In[9] := ? SumRec Out[9] = Global`SumRec SumRec[0] = 0 SumRec[1] = 1 SumRec[2] = 3 SumRec[3] = 6 SumRec[n_] := SumRec[n] = n + SumRec[n - 1]