Concepts fonctionnels
un petit bilan
Avec la redécouverte des langages fonctionnels, poussés notamment par le besoin de parallélisme sur les architectures multi-cœur et les problématiques de passage à l’échelle, différent concepts, inconnus du développeur non familiarisé avec l’approche fonctionnelle, deviennent populaires. On entend ainsi de plus en plus parler de lambda, closure, voire même de partial ou currying.
Le but ici n’est que de présenter ces différents concepts de manière succincte, sans forcément en illustrer toute la puissance, mais pour permettre de s’y retrouver un peu dans ce jargon. Que les puristes me pardonnent donc les raccourcis et simplifications.
Lambda ¶
Les lambda, dont le nom est hérité du λ-calcul, sont un des fondements (au moins théorique) des langages fonctionnels. Si l’on fait abstraction du sucre syntaxique, ce n’est ni plus ni moins qu’une fonction anonyme.
Dans le contexte des langages fonctionnel, les fonctions sont des valeurs comme les autres, et peuvent donc être affectées à des variables (ou plutôt des symboles), passées en paramètre ou être retournées par d’autres fonctions (on parle de fonctions d’ordre supérieur). C’est ce que l’on appelle des valeurs de première classe (sans lien avec l’objet, mais plutôt avec les trains).
L’avantage d’une lambda
par rapport à une fonction « normale » est qu’elle est crée à la demande, avec
une portée locale, et peut être récupérée par le garbage collector
lorsqu’elles ne sont plus nécessaires. Ceci est particulièrement utile avec les
paradigmes de programmation fonctionnelle, qui font une grande utilisation des
fonctions d’ordre supérieur (composition, travail sur les listes tels que
map
, filter
et reduce
), ainsi qu’en
programmation événementielle, où l’on affecte directement une fonction au
handler de l’événement. Dans la plupart des cas, ces fonctions sont à « usage
unique », et il est donc plus simple de les définir par lambda.
Dans certains langages, une fonction lambda doit être
fonctionnellement pure,
c’est-à-dire retourner une valeur qui ne dépend que de ses paramètres d’entrée
et ne pas avoir d’effet de bord. L’application de la fonction peut donc
toujours être remplacé par le résultat sans changer la sémantique du programme
(c’est ce que l’on appelle la transparence référentielle).
Dans ces cas là, le mot-clé
return
est omis, et l’application de la fonction est en fait
considérée comme une expression, ce qui apporte un sucre syntaxique: la
fonction est écrite comme une fonction mathématique (ceci n’est d’ailleurs pas
limité au lambda dans les langages purement fonctionnels).
Les extraits de code suivants comparent la définition d’une fonction normale avec la définition par lambda.
1 (define (add a b) (+ a b)) 2 3 (define add 4 (lambda (a b) (+ a b)))
1 def add(a,b): 2 return a + b 3 4 add = lambda a, b: a + b
1 function add(a,b) { return a + b;} 2 3 var add = function(a,b) { return a + b; };
1 let add(a,b) = a + b;; 2 3 let add = function (a,b) -> a + b;;
1 add x y = x + y 2 3 add2 = \x y -> x + y
1 function add = |a,b| { return a + b } 2 3 let add2 = |a,b| -> a + b
Exemples d’utilisation
Map
map
en Scheme (lambdamap.scm)1 > (map (lambda (x) (* 2 x)) '(0 1 2 3 4)) 2 (0 2 4 6 8)
map
en Python (lambdamap.py)1 >>> map(lambda x: 2*x, range(5)) 2 [0, 2, 4, 6, 8]
map
en O’Caml (lambdamap.ml)1 # List.map (function x -> 2*x) [0;1;2;3;4];; 2 - : int list = [0; 2; 4; 6; 8]
map
en Haskell (lambdamap.hs)1 > map (\x -> 2*x) [0,1,2,3,4] 2 [0,2,4,6,8]
Événements
1 mybutton.addEventListener("click", function(evt){alert("hello");});
1 local function listener = |handler| -> asInterfaceInstance(ActionListener.class, handler) 2 button: addActionListener(listener(|event| -> println("Clicked!")))
Une autre utilisation des lambda, c’est justement les closures.
Closure ¶
Formellement, une closure, ou clôture, ou fermeture, est le fait de « capturer » des références à des variables, ou des valeurs, extérieures directement dans la définition d’une fonction.
Cela prend en général la forme d’une fonction d’ordre supérieur, qui retourne une fonction dont la définition va dépendre des valeurs données, le plus souvent grâce à une lambda.
1 (define (adder a) 2 (lambda (b) (+ a b))) 3 4 (define add-two (adder 2)) 5 (display (add-two 40)) ; -> 42 6 7 (let ((my-add (adder 21))) 8 (display (my-add 21))) ; -> 42 9 10 (display ((adder 18) 24)) ; -> 42
1 def adder(a): 2 return lambda b: a+b 3 4 addtwo = adder(2) 5 print(addtwo(40)) # -> 42 6 7 myadd = adder(21) 8 print(myadd(21)) # -> 42 9 10 print(adder(18)(24)) # -> 42
1 function adder(a) { 2 return function(b) { 3 return a+b; 4 }; 5 } 6 7 var addtwo = adder(2); 8 console.log(addtwo(40)); // -> 42 9 10 var myadd = adder(21); 11 console.log(myadd(21)); // -> 42 12 13 console.log(adder(18)(24)); // -> 42
1 let adder a = function b -> a+b ;; 2 3 let addtwo = adder 2 ;; 4 print_int (addtwo 40) ;; (* -> 42 *) 5 6 let myadd = adder 21 ;; 7 print_int (myadd 21) ;; (* -> 42 *) 8 9 print_int (adder 18 24) ;;
1 2 adder a = \b -> a + b 3 4 addtwo = adder 2 5 6 myadd = adder 21 7 8 main = do 9 print (addtwo 40); -- -> 42 10 print (myadd 21); -- -> 42
1 module Closure 2 3 function adder = |a| { 4 return |b| -> a + b 5 } 6 function main = |args| { 7 let addtwo = adder(2) 8 println(addtwo(40)) # -> 42 9 10 let myadd = adder(21) 11 println(myadd(21)) # -> 42 12 }
Dans les exemples précédents, la variable a
est close
dans la définition de la fonction anonyme retournée. Un appel à
adder
retourne donc une fonction, crée pour l’occasion, qui sera
utilisable comme toute fonction.
La fonction adder
permet donc de créer une famille de fonctions, paramétrées par
a
.
On peut remarquer qu’il n’est pas nécessaire de récupérer la fonction retournée
dans une variable, on peut l’utiliser directement comme
adder(21)(21)
.
De ce point de vue, les fermetures sont en quelque sorte le dual de l’objet, dans lequel on capture du comportement (les méthodes) au sein de la structure de donnée. Ici, on capture des données (les valeurs closes) au sein du traitement. Dans les deux cas, ces constructions permettent de définir une famille d’éléments de traitement paramétrés par leur état. Plutôt que de créer une nouvelle instance d’une classe, la closure vas donc créer une nouvelle fonction à chaque appel (fabrique de fonction).
C’est d’ailleurs l’approche souvent utilisée pour simuler des closures dans les langages n’en disposant pas : on crée une classe callable (souvent en inner class) dont les attributs représentent les valeurs closes, comme illustré ci-dessous en Python, qui est équivalent à la closure précédente.
1 class adder: 2 def __init__(self, a): 3 self._a = a 4 5 def __call__(self, b): 6 return self._a + b 7 8 addtwo = adder(2) 9 print(addtwo(40)) # -> 42
À noter que même si on utilise classiquement les fonctions anonymes pour créer des fermetures, cela n’est pas nécessaire si l’on dispose de fonction internes. Encore une fois, en python, cela donne:
1 def adder(a): 2 def annon(b): 3 return a+b 4 return annon 5 6 addtwo = adder(2)
Exemple d’utilisation
Un exemple classique est en programmation événementielle pour créer une famille de handlers facilement.
1 function displayMessage(message) { 2 // ... 3 } 4 5 function handleWithMessage(message) { 6 return function(evt) { displayMessage(message); } 7 } 8 9 button1.addEventListener("click", handleWithMessage("hello")); 10 button2.addEventListener("click", handleWithMessage("salut"));
1 function displayMessage = |message| { 2 # ... 3 } 4 5 function handleWithMessage = |message| { 6 return asInterfaceInstance( 7 ActionListener.class, 8 (|evt| -> displayMessage(message)) 9 ) 10 } 11 12 button1: addActionListener(handleWithMessage("hello")) 13 button2: addActionListener(handleWithMessage("salut"))
Ici, on dispose d’une fonction prenant un message en paramètre et
l’affichant. On ne peut l’utiliser telle qu’elle comme handler, puisque
ces fonctions prennent un unique argument, l’événement. On crée donc la
fermeture handleWithMessage
, qui prend le message à afficher en
paramètre, et nous retourne une fonction utilisable (qui prend un événement et
affiche le message). Le message est clôt dans la définition de cette fonction
(au sens strict, c’est la fonction retournée qui est une closure, pas
handleWithMessage
qui est plutôt une fabrique).
Application partielle ¶
L’utilisation des fermetures nous amène naturellement à l’application partielle de fonctions (ou partialisation).
Une application partielle consiste à fixer un ou plusieurs arguments d’une fonction polyadique. On obtient ainsi une nouvelle fonction, acceptant d’autant moins de paramètres. Cela revient donc à créer une fermeture d’une fonction existante sur un ou plusieurs de ses arguments.
1 (define (add a b) (+ a b)) 2 3 (let ((add-two (lambda (b) (add 2 b)))) 4 (display (add-two 40))) ; -> 42
1 def add(a, b): 2 return a + b 3 4 addtwo = lambda b: add(2, b) 5 print(addtwo(40)) # -> 42
1 function add(a, b) { return a + b; } 2 3 var addtwo = function(b) { return add(2,b); }; 4 console.log(addtwo(40)); // -> 42 5
1 let add a b = a+b;; 2 3 let addtwo = function b -> (add 2 b);; 4 print_int (addtwo 40);; (* -> 42 *)
1 2 add a b = a + b 3 4 addtwo = \b -> add 2 b 5 6 main = do 7 print (addtwo 40) ; -- -> 42
Dans les langages acceptant des paramètres indéfinis, il est facile de créer une fonction de partialisation générique. Dans les autres cas, il faut définir une fonction de partialisation par arité de fonction, ce qui peut vite être fastidieux (ici, pour des fonction binaires).
Dans les langages acceptant les paramètres nommés, il est possible de
partialiser n’importe quel paramètre, et pas uniquement le premier. Python
dispose d’ailleur d’une fonction de partialisation
(functools.partial
, recodée ici pour la démonstration),
ainsi que Golo (:bindWith
).
1 module Partial 2 3 function add = |a, b| -> a + b 4 5 function add3 = |a, b, c| -> a + b + c 6 7 function main = |args| { 8 let addtwo = |b| -> add(2, b) 9 println(addtwo(40)) # -> 42 10 11 let myadd = ^add: bindTo(21) 12 println(myadd(21)) # -> 42 13 14 let superadd = ^add3: bindTo(14): bindTo(14) 15 println(superadd(14)) # -> 42 16 }
1 (define (partialize f p) 2 (lambda args 3 (apply f (cons p args)))) 4 5 (define (add a b) (+ a b)) 6 (define (add3 a b c) (+ a b c)) 7 8 (let ((my-add (partialize add 21))) 9 (display (my-add 21)) (display "\n")) ; -> 42 10 11 (let ((super-add (partialize (partialize add3 14) 14))) 12 (display (super-add 14)) (display "\n")) ; -> 42
1 def partialize(f, p): 2 return lambda *args: f(p, *args) 3 4 def add(a, b): 5 return a + b 6 7 def add3(a, b, c): 8 return a + b + c 9 10 myadd = partialize(add, 21) 11 print(myadd(21)) # -> 42 12 13 superadd = partialize(partialize(add3, 14), 14) 14 print(superadd(14)) # -> 42
1 function partialize(f, p) { 2 return function() { 3 return f.apply(null, 4 [p].concat(Array.prototype.slice.call(arguments))); }; 5 } 6 7 function add(a, b) { return a + b; } 8 function add3(a, b, c) { return a + b + c; } 9 10 var myadd = partialize(add, 21); 11 console.log(myadd(21)); // -> 42 12 13 var superadd = partialize(partialize(add3, 14), 14); 14 console.log(superadd(14)); // -> 42
1 let partial2 f a = function b -> (f a b);; 2 3 let add a b = a + b;; 4 5 let myadd = partial2 add 21;; 6 print_int (myadd 21) ;; (* -> 42 *)
1 2 partial2 f a = \b -> (f a b) 3 4 add a b = a + b 5 6 myadd = partial2 add 21 7 8 main = do 9 print (myadd 21); -- -> 42
Les plus habitués aux langages fonctionnels auront remarqué que pour
partialiser facilement une fonction, on peut réduire la liste des arguments
avec la fontion de partialisation. Par exemple en python, on peut écrire
superadd = reduce(partialize, [14,14], add3)
.
Je reviendrais sur les réductions (reduce), ainsi que les map vue plus haut (map, reduce, ça vous rappelle un truc ?), dans un autre article.
Curryfication ¶
L’exemple Caml (et Haskell) est purement didactique, car ce langage permet directement de faire une application partielle sur n’importe quelle fonction. Le simple fait d’appeler une fonction avec moins de paramètres que nécessaire retourne une application partielle.
1 let add a b = a + b ;; 2 let add3 a b c = a + b + c ;; 3 4 let addtwo = add 2 ;; 5 let myadd = add 21 ;; 6 7 addtwo 40 ;; (* -> 42 *) 8 print_int (myadd 21) ;; (* -> 42 *) 9 10 let superadd = add3 14 14 ;; 11 print_int (superadd 14) ;; 12 13 let mysuperadd = (+) 20 ;; 14 print_int (mysuperadd 22) ;; (* -> 42 *)
1 add a b = a + b 2 add3 a b c = a + b + c 3 4 addtwo = add 2 5 myadd = add 21 6 7 superadd = add3 14 14 8 9 mysuperadd = (+) 20 10 11 main = do 12 print (addtwo 40); -- -> 42 13 print (myadd 21); -- -> 42 14 print (superadd 14); -- -> 42 15 print (mysuperadd 22); -- -> 42
L’addition en Caml étant une fonction comme les autres (mais infixée), on peut même écrire cela plus simplement, comme dans le dernier exemple.
Dans Caml, mais aussi les autres langages ML et leurs dérivés,
Haskell et bien d’autres, les fonctions sont dites
auto-curryfiées. Ainsi, une fonction de plusieurs paramètre est en
fait définie en interne comme une fonction d’un seul paramètre, retournant une
fonction d’un seul paramètre, retournant une fonction d’un seul paramètre, etc.
D’où la signature de l’addition: add : int → int → int
, qui peut
s’écrire add : int → (int → int)
(une fonction prenant un entier
et retournant une fonction prenant un entier et retournant un entier).
Curryfier une fonction polyadique (du mathématicien américain Haskell Curry, qui a aussi donné son nom au langage fonctionnel), c’est donc la transformer en un enchaînement de fonctions monadiques, ou plus simplement, la rendre automatiquement partialisable.
1 def add(a): 2 return lambda b: a + b 3 4 print(add(21)(21)) # -> 42 5 6 myadd = add(21) 7 print(myadd(21)) # -> 42
1 function add(a) { return function(b) { return a+b; } } 2 3 add(21)(21); // -> 42 4 5 var myadd = add(21); 6 myadd(21); //-> 42
1 module Curry 2 3 function add = |a| { 4 return |b| -> a + b 5 } 6 7 function main = |args| { 8 let myadd = add(21) 9 println(myadd(21)) 10 11 #println(add(21)(21)) 12 }
1 (define (add a) 2 (lambda (b) (+ a b))) 3 4 (display ((add 21) 21)) ; -> 42 5 6 (let ((my-add (add 21))) 7 (display (my-add 21))) ; -> 42
Cela revient donc à définir notre fonction comme une série de lambda imbriquées, chacune étant une fermeture sur le paramètre de la précédente.
1 let add3 = function a -> function b -> function c -> a+b+c ;; 2 add3 14 14 14 ;;(* -> 42 *) 3 4 let add1 = add3 14 14 ;; 5 add1 14 ;;(* -> 42 *) 6 7 let add2 = add3 14 ;; 8 add2 14 14 ;; (* -> 42 *)
1 add3 = \a -> \b -> \c -> a+b+c 2 3 add1 = add3 14 14 4 5 add2 = add3 14 6 7 main = do 8 print (add3 14 14 14); -- -> 42 9 print (add2 14 14); -- -> 42 10 print (add1 14); -- -> 42
1 (define add3 2 (lambda (a) 3 (lambda (b) 4 (lambda (c) (+ a b c))))) 5 6 (display (((add3 14) 14) 14) ) ; -> 42 7 8 (let ((add1 ((add3 14) 14))) 9 (display (add1 14))) ; -> 42 10 11 (let ((add2 (add3 14))) 12 (display ((add2 14) 14))) ; -> 42
1 add3 = lambda a: lambda b: lambda c: a+b+c 2 print(add3(14)(14)(14)) # -> 42 3 4 add1 = add3(14)(14) 5 print(add1(14)) # -> 42 6 7 add2 = add3(14) 8 print(add2(14)(14)) # -> 42
1 var add3 = function(a) { 2 return function(b) { 3 return function (c) { 4 return a+b+c; 5 } 6 } 7 } 8 add3(14)(14)(14); // -> 42 9 10 var add1 = add3(14)(14); 11 add1(14); // -> 42 12 13 var add2 = add3(14); 14 add2(14)(14) // -> 42
1 module Curry2 2 3 function add2 = |a| -> |b| -> a+b 4 5 function main = |args| { 6 7 let add1 = add2(21) 8 println(add1(21)) # -> 42 9 10 }
Ainsi, il n’est plus nécessaire de partialiser explicitement ces fonctions, puisque l’invocation avec un nombre insuffisant de paramètre donnera une fonction partielle.
Encore une fois, il est possible d’écrire une fonction d’auto-curryfication, c’est-à-dire une fonction prenant en paramètre une fonction et en retournant une version curryfiée (que je laisse en exercice au lecteur).
Pour conclure
J’espère que ces concepts sont désormais plus clairs. Si vous avez des questions ou des remarques, n’hésitez pas.
Je continuerais probablement à affiner cet article, notamment en ajoutant des exemples dans d’autres langages ; j’aime assez ce genre d’exercice, qui aide à voir les concepts au-delà de la syntaxe et des spécificités du langage.
J’ai fait une suite à cet article, présentant une simulation de ces concepts en Java.
Références
Si vous voulez creuser un peu les langages présentés ici…
- Teach Yourself Scheme in Fixnum Days
- The Scheme Programming Language
- The Golo Programming Language
- Python
- Javascript
- O’Caml
- Developing Applications With Objective Caml
- The OCaml system
- The Haskell Programming Language
- Real World Haskell
Mises à jour
- : post initial
- : ajout d’extraits de code Golo
- :
- ajout de la remarque diverses;
- ajout de quelques exemples Golo;
- modification de la partie sur les applications partielles;
- section de références;
- ajout de Scheme;
- ajout de check en début pour sélectionner les langages affichés.
- : traduction anglaise
- : ajout d’exemples en Haskell
- : mise en ligne de la présentation de l’APIHour