Langages fonctionnels
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 variance
Apl
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]