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.

Lambda en Scheme (lambda.scm)
    1 (define (add a b) (+ a b))
    2 
    3 (define add
    4   (lambda (a b) (+ a b)))
Lambda en Python (lambda.py)
    1 def add(a,b):
    2     return a + b
    3 
    4 add = lambda a, b: a + b
Lambda en Javascript (lambda.js)
    1 function add(a,b) { return a + b;}
    2 
    3 var add = function(a,b) { return a + b; };
Lambda en O’Caml (lambda.ml)
    1 let add(a,b) = a + b;;
    2 
    3 let add = function (a,b) -> a + b;;
Lambda en Haskell (lambda.hs)
    1 add x y = x + y
    2 
    3 add2 = \x y -> x + y
Lambda en Golo (lambda.golo)
    1 function add = |a,b| { return a + b }
    2 
    3 let add2 = |a,b| -> a + b
Dans certain langages fonctionnels, cette distinction n’a pas vraiment de sens. Par exemple, en O’Caml ou en Scheme, la première définition n’est que du sucre syntaxique pour la seconde (de même qu’en Javascript).

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

gestion d’événements en Javascript (lambdaevt.js)
    1 mybutton.addEventListener("click", function(evt){alert("hello");});
gestion d’événements en Golo (lambdaevt.golo)
    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.

Closure en Scheme (closure.scm)
    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
Closure en Python (closure.py)
    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
Closure en Javascript (closure.js)
    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
Closure en O’Caml (closure.ml)
    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) ;;
Closure en Haskell (closure.hs)
    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
Closure en Golo (closure.golo)
    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.

Simulation de closure objet en Python (simulclosure.py)
    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:

Closure sans avoir recours à une lambda (closuredef.py)
    1 def adder(a):
    2     def annon(b):
    3         return a+b
    4     return annon
    5 
    6 addtwo = adder(2)
Une remarque concernant le ramasse miettes: définir une fermeture sur une variable crée une référence vers celle-ci, dans la fonction anonyme résultat de la fermeture. Tant que cette fonction existe, la variable ne sera pas récupérée, même en dehors de sa portée de création (c’est d’ailleurs ce qui permet aux fermetures de fonctionner.)

Exemple d’utilisation

Un exemple classique est en programmation événementielle pour créer une famille de handlers facilement.

Exemple d’utilisation de closure pour des handlers (Javascript) (closureex.js)
    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"));
Exemple d’utilisation de closure pour des handlers (Golo) (closureex.golo)
    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.

Application partielle en Scheme (partial.scm)
    1 (define (add a b) (+ a b))
    2 
    3 (let ((add-two (lambda (b) (add 2 b))))
    4      (display (add-two 40))) ; -> 42
Application partielle en Python (partial.py)
    1 def add(a, b):
    2     return a + b
    3 
    4 addtwo = lambda b: add(2, b)
    5 print(addtwo(40)) # -> 42
Application partielle en Javascript (partial.js)
    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 
Application partielle en O’Caml (partial.ml)
    1 let add a b = a+b;;
    2 
    3 let addtwo = function b -> (add 2 b);;
    4 print_int (addtwo 40);; (* -> 42 *)
Application partielle en Haskell (partial.hs)
    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).

Application partielle en Golo (partial.golo)
    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 }
Application partielle générique en Scheme (partialgen.scm)
    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
Application partielle générique en Python (partialgen.py)
    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
Application partielle générique en Javascript (partialgen.js)
    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
Application partielle générique en O’Caml (partialgen.ml)
    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 *)
Application partielle générique en Haskell (partialgen.hs)
    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.

Application partielle automatique en O’Caml: auto-curryfication (curry.ml)
    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 *)
Application partielle automatique en Haskell: auto-curryfication (curry.hs)
    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.

Curryfication simple en Python (curry.py)
    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
Curryfication simple en Javascript (curry.js)
    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
Curryfication simple en Golo (curry.golo)
    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 }
Curryfication simple en Scheme (curry.scm)
    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.

Curryfication explicite en O’Caml (curry2.ml)
    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 *)
Curryfication explicite en Haskell (curry2.hs)
    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
Curryfication explicite en Scheme (curry2.scm)
    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
Curryfication explicite en Python (curry2.py)
    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
Curryfication explicite en Javascript (curry2.js)
    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
Curryfication explicite en Golo (curry2.golo)
    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 à 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…

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