Dans le premier article sur les fonctions nous avons parlé de quelques unes des possibilités qu’offrent les fonctions mais il serait difficile de faire la différence avec un langage procédural non fonctionnel tel que le C sans aller un cran plus loin. Comme je l’ai déjà dit les fonctions sont vraiment centrales. Elles sont elles aussi une vraie source d’originalité. Nous allons donc aborder des pratiques plus avancées et plus originales de la programmation fonctionnelle.
La curryfication
Les travaux du logicien Haskell Curry ont contribué à poser les bases de la programmation fonctionnelle moderne. Son prénom a d’ailleurs été donné au langage éponyme et son nom de famille désigne un procédé important de la programmation fonctionnelle, la curryfication. Cette fonctionnalité permet l’application partielle des fonctions. Il s’agit en effet de créer une fonction à partir d’une fonction à laquelle on applique une partie des arguments nécessaire à son fonctionnement. C’est une des stratégies de développement les plus puissantes de la programmation fonctionnelle.
La curryfication en F#
Le F# est un langage issu du OCaml, lui même issu du Caml. En fait, on peut remonter cette généalogie assez longtemps. Dans ce langage, la syntaxe de la curryfication est assez classique. Nous avons l’habitude depuis le début de cette série de présenter les exemples en F# en parallèle de ceux en Scala. Ici nous allons d’abord voir des exemples en F#. Nous reparlerons du Scala ensuite. Considérons la fonction suivante (en F# donc) :
let add a b = a + b
Elle prend donc deux arguments a et b en entrée. Les arguments sont lus de gauche à droite. Le type de la fonction add est donc int -> int -> int.
On va transformer add en une fonction qui ajoute 2 à un entier. Dans ce cas, on connaît dès le début du traitement la valeur d’un des paramètres. On va alors créer une nouvelle fonction à partir de la fonction add en fixant la valeur de la variable a (puisque les paramètre se lisent de gauche à droite).
let add2 = add 2
Comme nous l’avons dit plus haut, la signature de add est int -> int -> int. C’est une fonction qui prend un entier et qui retourne une fonction dont la signature est int -> int. Lorsque nous avons créé la fonction add2, en appliquant la valeur 2 à la fonction add, nous avons donc récupéré une fonction dont la signature est int -> int, et qui ajoute 2 à l’entier en entrée.
Si on revient au langage C ou à la programmation objet, on traiterait plutôt add comme une fonction qui prend deux entiers en entrée et retourne un entier. La signature de cette fonction serait définie par (int x int) -> int. Il est possible d’écrire une fonction en F# avec une telle signature :
let add (a, b) = a + b
Pour simuler les fonctions habituelles, il faut utiliser un tuple. Ce qui est amusant c’est qu’en plus de reproduire la signature, la représentation (avec les parenthèse) reste également reproduite. Pourtant elle contient une petite subtilité : il s’agit d’une fonction qui prend un tuple de deux int en entrée et qui donne un int. Les arguments a et b sont ici résolus grâce au pattern matching pour déconstruire le tuple.
En plus court, les fonctions F# sont présentées dans une version directement curryfiée. Pour moi, il s’agit de la forme naturelle des fonctions en F#. Il ne faut pas s’interdire la seconde version. Vous trouverez ici un post de stackoverflow qui parle de comment faire le choix entre les deux formes.
Continuons notre exploration de la curryfication et réécrivons la fonction add de la façon suivante :
let add' a = (fun b -> a + b)
Cette fonction a exactement le même type que la précédente définition. On ne fait que pousser un peu le jeu sur la signature de la fonction add que l’on a écrite au début. Elle s’utilise exactement de la même façon. Bien entendu il est préférable d’utiliser la première forme pour des raisons de compréhension de code, mais la seconde forme a le mérite de mettre en perspective la curryfication.
En utilisant la fonction apply, il est possible de réécrire encore une fois le mécanisme de la curryfication. Il s’agit de garder une trace de la valeur que l’on souhaite appliquer partiellement et de renvoyer une fonction avec un seul argument qui finira l’application. On peut l’écrire de la façon suivante :
let add2' = (fun c -> apply 2 (fun i -> add i c))
Le Scala
Le Scala se démarque des autres langages fonctionnels dans la syntaxe et dans la pratique. Si on réécrit la fonction add en Scala, on obtient ceci :
def addT (x:Int, y:Int) = x + y
Comme nous l’avons vu dans le premier article parlant des fonctions, cette forme est proche de ce que l’on utilise en POO. C’est également celle qui est d’usage en Scala. Ici la signature est (Int, Int) => Int.
La forme curryfiée s’écrit :
def addC (x:Int) (y:Int) = x + y
et cette fois nous utiliserons cette fonction avec la syntaxe suivante :
addC (2) (3)
La signature est Int => Int => Int. On peut d’ailleurs passer d’une forme à l’autre de la façon suivante :
def addC (x:Int) (y:Int) = addT(x, y)
L’application partielle est possible en utilisant les deux formes. Si on se base sur addT, on peut écrire :
def add2 (x:Int) = add (_,2)
ou
def add2 (x:Int) = add (2,_)
En se basant, sur la forme curryfiée, on peut écrire :
def addC2 : Int => Int = addC (2)
Un autre point intéressant avec le Scala c’est que l’on peut transformer une lambda basée sur un tuple en une lambda basée sur la forme curryfiée. Par exemple :
def sumT: (Int, Int) => Int = _ + _ def sumC : Int => Int => Int = sum.curried
On peut également convertir la même lambda vers une forme basée sur les tuples.
def sumT : ((Int, Int)) => Int = sum.tupled
La signature est ((Int, Int)) => Int avec le double parenthésage pour indiquer que l’on attend un tuple en entrée.
La syntaxe est plus riche en Scala. C’est une conséquence d’un parti pris très fort qui constitue l’une des caractéristiques principales du langage. Même si le C# est au F# ce que le Java est au Scala, les designers de ce langage ont fait le choix d’une syntaxe plus intermédiaire avec le Java (ce qui facilite la transition de l’un vers l’autre). Le Scala reste tout de même extrêmement puissant et propose des fonctionnalités particulièrement avancées (celui ci par exemple est impossible à faire en F# en tant que tel).
Retour sur les fonctions d’ordre supérieur : la mémoïsation des objets
Une bonne pratique dans les langages multi paradigme fonctionnel first (comme le F# ou le Scala) est d’encapsuler les valeurs mutables ou les instances de classe dans des fonctions afin d’en masquer l’utilisation. Cela permet de garder une interface fonctionnelle bien que l’on utilise toutes les ressources à disposition. On va donc créer une fonction d’ordre supérieur qui va produire une fonctionnalité précise. Pour fonctionner, cette fonction gardera la trace d’un objet créer dans la fonction d’ordre supérieur. Il s’agit simplement d’un mécanisme de mise en cache d’une valeur.
Par exemple, si on souhaite créer une fonction capable de générer le n-ième nombre de Fibonacci, on écrira certainement dans un premier temps la fonction suivante en F# :
let rec fibonacci n = match n with | 0 -> 0 | 1 | 2 -> 1 | ni -> (fibonacci(ni - 1)) + (fibonacci(ni - 2))
et en Scala :
def fibonacci (n:Int) : Int = {
n match{
case 0 => 0
case i if i < 3 => 1
case i => fibonacci(i-1) + fibonacci(i-2)
}
}
L’inconvénient de cette fonction est que la fonction utilisé en interne est récursive. Cette fonction fait deux appels récursifs dans la même expression. Elle n’est pas “tail recursive”. Une même valeur de la suite de Fibonacci peut donc être calculée deux fois. On aura alors intérêt à créer une fonction utilisant un mécanisme lui permettant de garder la trace du résultat des précédent calcul pour les réutiliser afin de réduire à la fois les calculs et les appels récursifs.
La version permettant le calcul d’un nombre de Fibonacci qui est donné ici n’est pas “tail recursive”. Cela ne veut pas dire qu’une telle version n’existe pas. Cependant, l’écrire changerait radicalement la signature de la méthode. Si on ne l’utilise pas ici, c’est simplement pour que la fonction génératrice garde la même signature dans les prochains exemples.
Nous allons donc appliquer ce dont nous parlions en introduction de cette partie et créer une fonction d’ordre supérieur qui va générer une fonction capable de calculer le n-ième nombre de Fibonacci en utilisant un mécanisme de mise en cache. La génération de la fonction va nous permettre d’encapsuler l’objet de mémoïsation au sein de la fonction et de l’utiliser de façon totalement transparente pour l’utilisateur. On peut l’écrire de cette façon en F# :
let fibonacciGeneratorBuilder() = let cache = new System.Collections.Generic.Dictionary<int, int>() let rec fib n = if cache.ContainsKey(n) then cache.[n] else match n with | 0 -> 0 | 1 | 2 -> 1 | ni -> let res = (fib(ni - 1)) + (fib(ni - 2)) cache.Add((n, res)) res (fun ni -> fib ni)
Et en Scala :
def fibonacciGeneratorBuilder () : Int => Int =
{
val cache = scala.collection.mutable.HashMap.empty[Int,Int]
def fib (n:Int) : Int =
if (cache.contains(n)){
cache(n)
}
else n match {
case 0 => 0
case i if i < 3 => 1
case i =>
val temp = fib(i-1) + fib(i-2)
cache.put(n,temp)
temp
}
(x: Int) => fib(x)
}
Pour générer les 30 premiers nombres de Fibonacci sur mon ordinateur, mon ordinateur (MacBook 13 pouce early 2015 pour la configuration) mets 19 millièmes de seconde avec la première version F# et 1 millième avec la deuxième version F#. C’est un gain non négligeable, surtout si la fonction est appelée souvent.
La façon dont on a capturé la variable cache dans la fonction fibonacciGeneratorBuilder s’appelle une fermeture (un “closure” en anglais). Pour réaliser cette fermeture, nous nous sommes appuyé sur le scope de la fonction fibonacciGeneratorBuilder. En effet, la variable cache et la déclaration de la fonction fib font partie du même scope, ce qui nous autorise à utiliser la première dans la seconde.
En C#, il faut savoir se méfier des “closure” car leur valeur est évaluée au moment de l’exécution. Si bien que le code suivant (écrit en C#) :
for (var it = 0; it < 20; it++)
{
arr[it] = (() => Console.WriteLine("Iterator : {0}", it));
}
foreach(var fn in arr)
{
fn();
}
affichera vingt fois la phrase “Iterator : 20”. En effet, au moment de l’exécution it vaut 20 d’où le résultat. Considérons maintenant le code équivalent en F# :
let arr = Array.zeroCreate<unit -> unit>(20) for i in 0..19 do arr.[i] <- (fun () -> do printfn "Accumulator value: %i " i) Array.iter (fun fn -> fn()) arr
et le code équivalent en Scala :
val arr = new Array[Unit=>Unit](20)
for (i <- 0 to 19){
arr(i) = (Unit => println("Accumulator value: " + i.toString))
}
arr.foreach(_.apply(()))
Il affiche pour sa part :
Accumulator value: 0 Accumulator value: 1 … Accumulator value: 18 Accumulator value: 19
Ce qui est le résultat souhaité en général. Les “closure” capturent donc bien la valeur de la variable au moment où la fermeture est réalisée et non pas au moment où elle est évaluée comme dans l’exemple en C#. Il est possible de corriger le code C# en utilisant une variable locale pour stocker la valeur de l’itérateur dans le corps de la boucle for.
La version fonctionnelle de l’injection de dépendance
Inconvénient de l’exemple précédent : la fonction fibonacciGeneratorBuilder ne nous laisse pas le choix du mécanisme de mise en cache des valeurs. Il est possible de corriger cela en conservant les propriété déjà acquises (l’encapsulation de la partie mutable). Pour y parvenir, nous allons ajouter des variables à notre fonction. La fonction suivante en F# en est le premier prototype :
let fibonacciFunctionBuilder (push : int -> int -> unit) (get : int -> int) (exist : int -> bool) = let rec fib n = if exist n then get n else match n with | 0 -> 0 | 1 | 2 -> 1 | ni -> let res = (fib(ni - 1)) + (fib(ni - 2)) do push n res res (fun ni -> fib ni)
Comme on peut le voir, nous avons simplement trois fonctions en entrée. J’ai ajouté les signatures de chacune d’elles par commodité car si l’inférence de type est parfaitement capable de déduire le type, le site web sur lequel on va publier n’en est pas capable ! Avec un dictionnaire pour faire le cache, on peut écrire le code suivant (en F#) :
let generateCacheFunctionWithDictionary() = let cache = new System.Collections.Generic.Dictionary<int, int>() ((fun key value -> cache.Add(key, value)), (fun key -> cache.[key]), (fun key -> cache.ContainsKey(key))) let fibonacciFunctionBuilder' = fun () -> generateCacheFunctionWithDictionary() |||> fibonacciFunctionBuilder
Et voici l’intégralité du code en Scala :
def fibonacciFunctionBuilder (push:(Int, Int)=>Unit, get_Int=>Int, exist_Int=>Boolean) : Int => Int ={
def fib (n:Int) : Int =
if (exist(n)){
get(n)
}
else n match {
case 0 => 0
case i if i < 3 => 1
case i =>
val temp = fib(i-1) + fib(i-2)
push(n,temp)
temp
}
(x: Int) => fib(x)
}
def generateCacheFunctionWithHashMap () : ((Int, Int)=>Unit, Int=>Int, Int=>Boolean) ={
val cache = scala.collection.mutable.HashMap.empty[Int,Int]
val push : (Int, Int)=>Unit = cache.put(_, _)
val get : Int => Int = cache(_)
val exist : Int => Boolean = cache.contains(_)
(push, get, exist)
}
def fibonacciGenerator () : Int => Int ={
val temp :((Int, Int)=>Unit, Int=>Int, Int=>Boolean) => (Int=>Int) = fibonacciFunctionBuilder(_, _, _)
temp.tupled(generateCacheFunctionWithHashMap ())
}
On peut se dire que nous avons alourdi la signature de la fonction fibonacciFunctionBuilder et qu’il est envisageable de faire plus simple. Bien entendu, un développeur en POO aura envie d’utiliser une interface pour le faire, et c’est tout à fait possible. Commençons par définir l’interface en F# :
type ICache = abstract Push : int -> int -> unit abstract Get : int -> int abstract Exist : int -> bool
Il reste ensuite à refactorer le code précédent. Voici une façon de procéder :
let fibonacciFunctionBuilder(cache : ICache) =
let rec fib n =
if cache.Exist n then cache.Get n
else
match n with
| 0 -> 0
| 1 | 2 -> 1
| ni ->
let res = (fib(ni - 1)) + (fib(ni - 2))
do cache.Push n res
res
(fun ni -> fib ni)
let adaptDictionaryToICache() =
let cache = new System.Collections.Generic.Dictionary<int, int>()
{new ICache with
member this.Push key value = cache.Add(key, value)
member this.Get key = cache.[key]
member this.Exist key = cache.ContainsKey(key)
}
let fibonacciFunctionbuilder'' =
fun () -> adaptDictionaryToICache() |> fibonacciFunctionbuilder
La fonction adaptDictionaryToICache permet de créer un adapteur implémentant ICache. La syntaxe utilisée est celle des “object expression”. Elle permet d’instancier un objet implémentant l’interface sans avoir à définir une classe ou un type autre que l’interface.
Voici maintenant le refactoring complet du code Scala :
trait ICache
{
def Push(key:Int, value:Int) : Unit
def Get(key:Int) : Int
def Exist(key:Int) : Boolean
}
def fibonacciFunctionBuilder (cache:ICache) : Int => Int ={
def fib (n:Int) : Int =
if (cache.Exist(n)){
cache.Get(n)
}
else n match {
case 0 => 0
case i if i < 3 => 1
case i =>
val temp = fib(i-1) + fib(i-2)
cache.Push(n,temp)
temp
}
(x: Int) => fib(x)
}
class CacheHashMapBased extends ICache{
private val _cache = scala.collection.mutable.HashMap.empty[Int,Int]
override def Push(key:Int, value:Int) = _cache.put(key, value)
override def Get(key:Int) = _cache(key)
override def Exist(key:Int) = _cache.contains(key)
}
def generateCacheFunctionWithHashMap () : ICache = new CacheHashMapBased()
Dans cet exemple, on utilise un trait. On peut voir ce type comme l’interface que l’on définit en F#. Cela fonctionne exactement de la même façon.
Dans l’exemple précédent, on utilise la curryfication pour faire de l’injection de dépendance.
Cette particularité s’y prête plutôt bien. La vraie question est de savoir si l’injection de dépendance est une bonne chose en programmation fonctionnelle. En effet, l’injection de dépendance consiste en premier lieu à injecter un objet externe dans un contexte d’exécution. Et si l’on injecte l’objet en question, c’est souvent parce qu’il a un lien avec un autre contexte d’exécution. C’est déjà le cas dans notre exemple avec la fonction fibonacciFunctionBuilder. Quand la fonction générée crée une nouvelle valeur, elle la pousse dans le contexte du cache. En soit c’est un effet de bord et par conséquent on perd l’aspect fonction pure. On perd aussi la capacité à raisonner simplement à propos des fonctions que l’on a écrites.
C’est pourquoi beaucoup de développeurs en langage fonctionnel souhaitent garder l’approche la plus fonctionnelle possible et donc manipuler un maximum de fonctions pures.Il faut cependant bien noter qu’injecter un objet qui aura très souvent un comportement impur va transformer une fonction pure en fonction impure. Heureusement, d’autres outils permettent heureusement d’interagir avec les contextes extérieurs : les monades par exemple. Globalement, et dans tous les cas, l’idée est de cloisonner les comportements impurs et de faire vivre les parties fonctionnelles entre les recours aux comportements impurs (accès fichier ou base de données par exemple, et plus généralement tout ce qui a un effet de bord). Ces deux articles de Mark Seeman (ici et là) l’expliquent très bien et donnent les alternatives fonctionnelles.
Pas encore de commentaires