5. Fonctions de première classe▲
En Scala, une fonction est une « valeur de première classe ». Comme n'importe quelle autre valeur, elle peut être passée en paramètre ou renvoyée comme résultat. Les fonctions qui prennent en paramètres d'autres fonctions ou qui les renvoient comme résultat sont appelées fonction d'ordre supérieur. Ce chapitre présente ces fonctions d'ordre supérieur et montre qu'elles constituent un mécanisme souple et puissant pour la composition des programmes.
À titre d'exemple, considérons ces trois tâches apparentées :
- écrire une fonction additionnant tous les entiers compris entre deux bornes a et b :
def sumInts(a: Int, b: Int): Int =
if (a > b) 0 else a + sumInts(a + 1, b)- écrire une fonction additionnant les carrés de tous les entiers compris entre deux bornes a et b :
def square(x: Int): Int = x * x
def sumSquares(a: Int, b: Int): Int =
if (a > b) 0 else square(a) + sumSquares(a + 1, b)- écrire une fonction additionnant les puissances de 2 de tous les entiers compris entre deux bornes a et b :
2.
3.
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)
def sumPowersOfTwo(a: Int, b: Int): Int =
if (a > b) 0 else powerOfTwo(a) + sumPowersOfTwo(a + 1, b)
Ces fonctions étant toutes des instances de
kitxmlcodelatexdvp\sum\limits_{n=a}^{b} f(n)finkitxmlcodelatexdvp(« Somme de f(n) pour n variant de a à b »), nous pouvons mettre ce motif commun en facteur en définissant une fonction sum :
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f, a + 1, b)Le type Int => Int est celui des fonctions qui prennent un paramètre de type Int et qui renvoient un résultat de type Int. sum est donc une fonction qui prend en paramètre une autre fonction - autrement dit, c'est une fonction d'ordre supérieur.
Grâce à elle, nous pouvons reformuler nos trois fonctions précédentes de la façon suivante :
2.
3.
def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumSquares(a: Int, b: Int): Int = sum(square, a, b)
def sumPowersOfTwo(a: Int, b: Int): Int = sum(powerOfTwo, a, b)
avec :
2.
3.
def id(x: Int): Int = x
def square(x: Int): Int = x * x
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)
5-1. Fonctions anonymes▲
Le fait de passer des fonctions en paramètre pousse à créer de nombreuses petites fonctions. Dans l'exemple précédent, nous avons défini id, square et powerOfTwo comme des fonctions séparées afin de pouvoir les passer en paramètre à sum.
Au lieu d'utiliser des définitions de fonctions nommées pour ces paramètres, nous pouvons les formuler plus simplement à l'aide de fonctions anonymes. Une fonction anonyme est une expression dont l'évaluation produit une fonction - cette fonction est définie sans qu'on lui donne un nom. À titre d'exemple, voici une fonction anonyme qui calcule le carré d'un entier :
(x: Int) => x * xLa partie située avant la flèche => est la liste des paramètres de la fonction, la partie située après est son corps. Voici une fonction anonyme qui multiplie ses arguments :
(x: Int, y: Int) => x * yGrâce aux fonctions anonymes, nous pouvons reformuler les deux premières fonctions de sommation sans utiliser de fonctions auxiliaires nommées :
def sumInts(a: Int, b: Int): Int = sum((x: Int) => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum((x: Int) => x * x, a, b)Le plus souvent, le compilateur Scala peut déduire les types des paramètres à partir du contexte de la fonction anonyme, auquel cas ceux-ci peuvent être omis. Pour sumInts et sumSquares, par exemple, le type de sum nous indique que le premier paramètre doit être une fonction de type Int => Int. Le type Int du paramètre de la fonction anonyme est donc redondant et peut être omis. En outre, lorsqu'il n'y a qu'un seul paramètre et que l'on ne précise pas le type, nous pouvons également supprimer les parenthèses qui l'entourent :
def sumInts(a: Int, b: Int): Int = sum(x => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum(x => x * x, a, b)Généralement, le terme Scala (x1: T1, …, xn: Tn) => E définit une fonction qui fait correspondre à ses paramètres x1, …, xn le résultat de l'expression E (où E peut utiliser x1, …, xn). Les fonctions anonymes ne sont pas des éléments de langage essentiels de Scala, car elles peuvent toujours s'exprimer en termes de fonctions nommées. La fonction anonyme
(x1: T1, ..., xn: Tn) => Eest équivalente au bloc
{ def f (x1: T1, ..., xn: Tn) = E ; f _ }où f est un nouveau nom qui n'est utilisé nulle part ailleurs dans le programme. On dit aussi que les fonctions anonymes sont du « sucre syntaxique ».
5-2. Curryfication▲
Notre dernière formulation des fonctions de sommation est déjà très compacte, mais nous pouvons faire mieux. Vous remarquerez que a et b apparaissent comme paramètres et arguments de chaque fonction, mais qu'ils ne semblent pas faire grand-chose d'intéressant. Peut-on donc s'en débarrasser ?
Réécrivons sum pour qu'elle ne prenne pas les bornes a et b en paramètre :
2.
3.
4.
5.
def sum(f: Int => Int): (Int, Int) => Int = {
def sumF(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sumF(a + 1, b)
sumF
}
Ici, sum est une fonction qui renvoie une autre fonction, celle qui effectue la somme : sumF. C'est cette dernière qui fait tout le travail : elle prend les bornes a et b en paramètre, elle applique la fonction f qui a été passée à sum à tous les entiers compris entre ces bornes et additionne les résultats.
Grâce à cette nouvelle formulation de sum, nous pouvons maintenant écrire :
2.
3.
def sumInts = sum(x => x)
def sumSquares = sum(x => x * x)
def sumPowersOfTwo = sum(powerOfTwo)
Ou, avec des définitions de valeurs :
2.
3.
val sumInts = sum(x => x)
val sumSquares = sum(x => x * x)
val sumPowersOfTwo = sum(powerOfTwo)
On peut maintenant appliquer sumInts, sumSquares et sumPowersOfTwo comme n'importe quelle autre fonction :
scala> sumSquares(1, 10) + sumPowersOfTwo(10, 20)
res0: Int = 2096513Comment appliquer des fonctions qui renvoient des fonctions ? Dans l'expression sum(x => x * x)(1, 10), par exemple, la fonction sum peut s'appliquer à la fonction carré (x => x * x) et la fonction résultante est ensuite appliquée à la seconde liste de paramètres (1, 10). Cette notation est possible, car l'application des fonctions est associative à gauche : si arg1 et arg2 forment une liste d'arguments, alors f(arg11)(arg22) est équivalent à (f(arg1))(arg2).
Dans notre exemple, sum(x => x * x)(1, 10) est donc équivalent à (sum(x => x * x))(1, 10).
Les fonctions qui renvoient des fonctions sont si utiles que Scala dispose d'une syntaxe spéciale pour les exprimer. La définition suivante de sum, par exemple, est équivalente à la précédente, mais est plus courte :
def sum(f: Int => Int)(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f)(a + 1, b)De façon générale, une définition de fonction curryfiée :
f (params_1) ... (params_n) = Edans laquelle n > 1 se traduit en :
def f (params_1) ... (params_n-1) = { def g (params_n) = E ; g }où g est un nouvel identificateur. Avec une fonction anonyme, cette traduction est encore raccourcie :
def f (params_1) ... (params_n −1) = ( params_n ) => ESi l'on applique n fois cette transformation, on trouve donc que :
def f (params_1) ... (params_n) = Eéquivalaut à :
def f = (params_1) => ... => (params_n) => Eou, avec une définition de valeur :
val f = (params_1) => ... => (params_n) => ECe style de définition et d'application des fonctions s'appelle curryfication, en hommage aux travaux du mathématicien et logicien Haskell B. Curry dans les années 1930 - bien que ce concept remonte plus loin aux articles de Moses Schönfinkel et Gottlob Frege.
Le type d'une fonction renvoyant une fonction s'exprime de façon analogue à sa liste de paramètres. Le type de la dernière formulation de sum, par exemple, est (Int => Int) => (Int, Int) => Int. Cette écriture est possible, car les types des fonctions sont associatifs à droite : T1 => T2 => T3 est donc équivalent à T1 => (T2 => T3).
Exercice 5-2-1 : La fonction sum utilise une récursion linéaire. Écrivez une version récursive terminale en remplaçant les ?? dans le code ci-dessous :
2.
3.
4.
5.
6.
7.
def sum(f: Int => Int)(a: Int, b: Int): Int = {
def iter(a: Int, result: Int): Int = {
if (??) ??
else iter(??, ??)
}
iter(??, ??)
}
Exercice 5-2-2 : Écrivez une fonction product qui calcule le produit des valeurs d'une fonction pour les points appartenant à un certain intervalle.
Exercice 5-2-3 : Écrivez factorielle en termes de product.
Exercice 5-2-4 : Pouvez-vous écrire une fonction encore plus générale, qui généralise à la fois sum et product ?
5-3. Exemple : Trouver les points fixes des fonctions▲
Un nombre x est appelé point fixe d'une fonction f si f(x) = x.
Pour certaines fonctions f, nous pouvons trouver le point fixe en commençant par une valeur supposée et en appliquant f jusqu'à ce que cette valeur ne change plus (ou que la modification soit inférieure à un seuil de tolérance donné). Ceci est possible si la suite
x, f(x), f(f(x)), f(f(f(x))), ...converge vers le point fixe de f. Ce principe est capturé par la fonction suivante :
2.
3.
4.
5.
6.
7.
8.
9.
10.
val tolerance = 0.0001
def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
Nous pouvons maintenant appliquer ce principe pour reformuler la fonction racine carrée que nous avions étudiée précédemment. Commençons par spécifier sqrt :
sqrt(x) = y tel que y * y = x
= y tel que y = x /yPar conséquent, sqrt(x) est un point fixe de la fonction y => x / y. Ceci suggère qu'elle peut être calculée à l'aide de fixedPoint :
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)Cependant, nous constatons alors que ce calcul ne converge pas. Ajoutons à la fonction fixedPoint une instruction d'impression affichant la supposition courante :
2.
3.
4.
5.
6.
7.
8.
9.
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
println(next)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
L'appel sqrt(2) produit alors :
2.0
1.0
2.0
1.0
2.0
...Un moyen de contrôler ces oscillations consiste à empêcher la supposition de trop changer. Ceci peut se faire en calculant la moyenne des valeurs successives de la suite initiale :
2.
3.
4.
5.
6.
7.
8.
9.
scala> def sqrt(x: Double) = fixedPoint(y => (y + x/y) / 2)(1.0)
sqrt: (Double)Double
scala> sqrt(2.0)
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.4142135623746899
En fait, la traduction de la fonction fixedPoint produirait exactement notre définition précédente du point fixe de la section 4.4Exemple : racines carrées par la méthode de Newton.
Les exemples précédents ont montré que la puissance expressive d'un langage s'améliore considérablement lorsque l'on peut passer des fonctions en paramètre. L'exemple suivant montre que les fonctions qui renvoient des fonctions peuvent également être très utiles.
Reprenons à nouveau nos itérations pour trouver le point fixe. Nous sommes partis de l'observation que √(x) est un point fixe de la fonction y => x / y. Puis, nous avons fait en sorte que l'itération converge en faisant la moyenne des valeurs successives. Cette technique d'amortissement par la moyenne (average damping) est si générale que nous pouvons l'envelopper dans une autre fonction :
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2Grâce à averageDamp, nous pouvons reformuler la fonction racine carrée :
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)Cette définition exprime aussi clairement que possible les éléments de l'algorithme.
Exercice 5-3-1 : Écrivez une fonction calculant les racines cubiques en vous servant de fixedPoint et de averageDamp.
5-4. Résumé▲
Nous avions montré dans le chapitre précédent que les fonctions sont des abstractions essentielles, car elles permettent d'introduire des méthodes générales de calcul sous la forme d'éléments explicites et nommés dans le langage. Dans le présent chapitre, nous avons montré que ces abstractions pouvaient être combinées en fonctions d'ordre supérieur afin de créer d'autres abstractions. En tant que programmeurs, nous devons rechercher les opportunités d'abstraction et de réutilisation. Le niveau d'abstraction le plus haut n'est pas toujours le meilleur, mais il est important de connaître les techniques d'abstraction pour pouvoir les utiliser à bon escient.
5-5. Éléments du langage déjà vus▲
Les chapitres 4 et 5 ont présenté les éléments du langage qui permettent de créer des expressions et des types formés de données primitives et de fonctions. Nous indiquerons ci-dessous la syntaxe sans contexte de ces éléments selon le formalisme Backus-Naur étendu, où | représente une alternative, [ … ] un élément facultatif (0 ou 1 occurrence) et { … } une répétition (0 ou plusieurs occurrences).
5-5-1. Caractères▲
Les programmes Scala sont des suites de caractères Unicode. Nous distinguons les jeux de caractères suivants :
- les espaces, comme ' ', la tabulation ou les caractères de fin de ligne ;
- les lettres de 'a' à 'z' et de 'A' à 'Z' ;
- les chiffres de '0' à '9' ;
- les délimiteurs . , ; ( ) { } [ ] \ " ' ;
- les opérateurs comme '#' '+' ':'. Essentiellement, il s'agit des caractères affichables qui n'appartiennent à aucun des ensembles précédents.
5-5-2. Lexèmes▲
ident = lettre {lettre | chiffre}
| opérateur { opérateur }
| ident '_' ident
littéral = "comme en Java"Les littéraux sont les mêmes qu'en Java. Il définissent des nombres, des caractères, des chaînes ou des valeurs booléennes. Des exemples de littéraux sont 0, 1.0e10, 'x' , "il a dit 'bonjour !'" ou true.
Les identificateurs ont deux formes. Ils peuvent commencer par une lettre suivie (éventuellement) d'une suite de lettres ou de symboles, ou commencer par un caractère opérateur, suivi (éventuellement) d'une suite de caractères opérateurs. Les deux formes peuvent contenir des caractères blanc souligné '_'. En outre, un blanc souligné peut être suivi par une forme ou l'autre d'identificateur. Les identificateurs suivants sont donc corrects :
x Room10a + -- foldl_: +_vectorCette règle signifie que les identificateurs formés d'opérateurs doivent être séparés par des espaces. L'entrée x+-y sera donc analysée comme une séquence de trois lexèmes x, +- et y. Si nous voulons exprimer la somme de x avec l'opposé de y, nous devons ajouter un caractère espace pour écrire, par exemple, x+ -y.
Le caractère $ est réservé pour les identificateurs produits par le compilateur ; ne l'utilisez pas dans les sources de vos programmes.
Les mots suivants sont réservés et ne peuvent donc pas servir d'identificateurs :
abstract case catch class def
do else extends false final
finally for if implicit import
match new null object override
package private protected requires return
sealed super this throw trait
try true type val var
while with yield
_ : = => <- <: <% >: # @5-5-3. Types▲
Type = TypeSimple | TypeFonction
TypeFonction = TypeSimple '=>' Type | '(' [Types] ')' '=>' Type
TypeSimple = Byte | Short | Char | Int | Long | Float | Double |
Boolean | Unit | String
Types = Type {',' Type}Les types peuvent être :
- des types numériques : Byte, Short, Char, Int, Long, Float et Double (ce sont les mêmes qu'en Java) ;
- le type Boolean avec les valeurs true et false ;
- le type Unit avec la seule valeur () ;
- le type String ;
- des types fonctions, comme (Int, Int) => Int ou String => Int => String.
5-5-4. Expressions▲
Expr = ExprInfixe | ExprFonction | if '(' Expr ')' Expr else Expr
ExprInfixe = ExpPréfixe | ExprInfixe Opérateur ExprInfixe
Opérateur = ident
ExprPréfixe = ['+' | '-' | '!' | '~'] ExprSimple
ExprSimple = ident | littéral | ExprSimple '.' ident | Bloc
ExprFonction = (Liaisons | Id) '=>' Expr
Liaisons = '(' Laison {',' Liaison} ')'
Liaison = ident [':' Type]
Bloc = '{' {Def ';' } Expr '}'Les expressions peuvent être :
- des identificateurs comme x, isGoodEnough, * ou +- ;
- des littéraux comme 0, 1.0 ou "abc" ;
- des sélections de champs ou de méthodes comme System.out.println ;
- des appels de fonctions comme sqrt(x) ;
- des applications d'opérateurs comme -x ou y + x ;
- des conditionnelles comme if (x < 0) -x else x ;
- des blocs comme { val x = abs(y) ; x * 2 } ;
- des fonctions anonymes comme x => x + 1 ou (x: Int, y: Int) => x + y.
5-5-5. Définitions▲
Def = DefFonction | DefValeur
DefFonction = 'def' ident {'(' [Paramètres] ')'} [':' Type] '=' Expr
DefValeur = 'val' ident [':' Type] '=' Expr
Paramètres = Paramètre {',' Paramètre}
Paramètre = ident ':' ['=>'] TypeLes définitions peuvent être :
- des définitions de fonctions comme def square(x: Int): Int = x * x ;
- des définitions de valeurs comme val y = square(2).