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

    1 > (map (lambda (x) (* 2 x)) '(0 1 2 3 4))
    2 (0 2 4 6 8)

    1 >>> map(lambda x: 2*x, range(5))
    2 [0, 2, 4, 6, 8]

    1 # List.map (function x -> 2*x) [0;1;2;3;4];;
    2 - : int list = [0; 2; 4; 6; 8]

    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

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

• 2013-04-10: post initial
• 2013-04-11: ajout d’extraits de code Golo
• 2013-04-12:
  • 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.
• 2013-04-12: traduction anglaise
• 2013-12-05: ajout d’exemples en Haskell
• 2014-02-27: mise en ligne de la présentation de l’APIHour