Function style en F#

A quelle image pourrait-on associer le développement ? On pourrait volontiers le comparer au jeu Lego. A cette différence près qu’en programmation objet (POO), on construit les briques pour assembler des ensembles plus gros et ainsi de suite. Mais cette image est particulièrement statique. C’est l’une des différences fondamentales avec la programmation fonctionnelle qui est beaucoup plus vivante et dynamique. Nombreux sont ceux qui partagent ce point de vue, et pour vous en convaincre, visionnez donc cette vidéo : IF YOU’RE NOTLIVE CODING, YOU’RE DEAD CODING.

Dans les langages fonctionnels, les fonctions tiennent une place particulière. Elles sont en effet le principal outil servant au design des programmes et l’une des sources de leur dynamicité. Dans les langages purement fonctionnels (comme le Haskel), leur représentation et leur fonctionnement sont très différents des méthodes de la programmation objet (POO). D’une part, les fonctions ne sont pas liées à un objet et d’autre part, elles bénéficient de fonctionnalités très différentes des méthodes. Elles offrent également une expressivité bien distincte mais non moins puissante que les méthodes de la POO.

Pour les langages multi-paradigmes (POO et fonctionnel) comme le Scala ou le F#, seule la représentation change réellement. En effet, la compilation et les langages intermédiaires nous ramènent aux méthodes des objets en utilisant des fonctionnalités propres à ces langages et à leur compilateur. Ce post “Functions vs methods in Scala” de stackoverflow explique comment cela fonctionne en Scala. La représentation des fonctions devient alors une forme de sucre syntaxique qui nous permet de garder l’expressivité propre aux langages fonctionnels. Par ailleurs, la plupart des fonctionnalités liées à la programmation fonctionnelle y sont implémentées pour permettre de profiter pleinement de ce style de programmation.

Génériques par défaut

L’inférence de type va encore une fois offrir une aide précieuse, car elle va permettre de rendre une fonction la plus générique possible. Voyons un exemple pour bien saisir.

En F#, on peut définir le type optionnel de la façon suivante :

type Option = 
    | Some of 'a
    | None

Il permet de représenter quelque chose qui peut potentiellement prendre une valeur. Dans le cas contraire, on obtiendra la valeur None. Si l’on veut pouvoir appliquer une fonction à une telle valeur, on va utiliser le pattern matching pour savoir s’il existe ou non une valeur. Dans le premier cas, on appliquera notre fonction et on renverra une option contenant le résultat. Sinon, on renverra le None correspondant au type Option ou ‘b est le type de sortie de la fonction. Cela donne :

let map fn = 
    function 
    | Some value -> fn value |> Some
    | None -> None

Dans ce cas, le compilateur va immédiatement inférer que fn est dû type ‘a -> ‘b, que l’option en entrée est du type Option et en sortie du type Option.

Cette solution s’avère plutôt efficace et pratique même si elle possède ses limites. Voici ce qui se passe si l’on veut écrire une fonction qui additionne deux nombres. On écrit cette fonction en F# comme ceci :

let add a b = a + b

Cette fonction additionne deux éléments a et b, et le type inféré est le suivant :

int -> int -> int.

En Scala, nous l’écrivons de la façon suivante :

def add (x:Int, y:Int) = x + y

Il a fallu écrire de façon explicite les types. Dans ce cas, le type de la fonction s’écrit plutôt :

(Int, Int) => Int.

Ici, l’inférence de type prévoit que nous utilisions la fonction add avec deux int en entrée. De prime abord, cela ne semble pas très générique et la promesse d’un maximum de généricité n’est pas tenue. Il faut se souvenir que les langages fonctionnels sont le plus souvent typés statiquement. Ici le problème vient du fait que l’opérateur (+) correspond (sans plus d’indication) à une opération sur des entiers. Si nous voulons utiliser notre fonction avec des doubles, il faudrait préciser le type de l’entrée et écrire :

let add (a : double) b = a + b

Il suffit finalement de préciser le type d’un seul des éléments en entrée pour que l’inférence de type modifie le type de la fonction :

double -> double -> double.

En Scala comme en F#, l’utilisation du polymorphisme ad hoc n’est pas immédiate, ce qui rend la définition de notre fonction finalement assez peu générique. En F#, si l’on veut atteindre ce but, il faut utiliser le mot clé inline. Notre fonction devient alors :

let inline add a b = a + b

Le type inféré devient alors :

^T -> ^U -> ^V.

Le mot clé inline est en fait un raccourci pour un mécanisme beaucoup plus complexe et puissant que nous n’allons pas exposer ici. Nous allons simplement expliquer les conséquences directes de cette utilisation. D’abord, ^T signifie qu’on s’attend à un type T. Le signe ^ signifie que ce type sera déterminé au runtime. Pour un type déterminé au compile time, on écrit 'T. Une autre conséquence, moins évidente, est que l’on s’attend à ce que l’opérateur (+) soit défini de façon statique pour le type ^Tavec le type ^U en deuxième argument, avec en sortie un type ^V. Désormais, on peut utiliser notre fonction add avec deux int, deux double mais pas un int et un double (à cause de la contrainte sur l’opérateur statique).

Ce mécanisme de généralisation est particulièrement puissant même s’il faut parfois lui donner un petit coup de pouce. La limitation que nous venons de montrer est en fait un mécanisme permettant de garantir le typage statique. En utilisant le mot clé  inline, on reporte certaines vérifications au runtime avec les conséquences que cela peut engendrer.

Pour rendre ce code générique (la fonction add), il faut garantir l’existence de l’opération (+) convenablement définie. En Scala, le problème est réglé de façon légèrement différente. On ne va pas faire appel à l’opération (+) en tant que telle. On va appeler une abstraction de cette opération qui sera valable pour tous les types définissant cette opération. Dans certains cas, le F# fait également appel à cette stratégie. Voilà donc comment on écrit une fonction générique en Scala :

def add[A] (x:A, y:A) (implicit numeric: Numeric[A]) = numeric.plus(x,y)

Encore une fois, nous n’allons pas entrer dans les détails du mot clé (implicit). Je peux cependant renvoyer le lecteur intéressé vers deux articles écrits par Clément Carreau traitant ce sujet. Vous trouverez le premier en parcourant cet article “Les “implicits” en Scala, ou comment sous-traiter au compilateur”, et le second ici : La résolution des implicits Scala, une liberté qui a un coût.

Les Lambda

Ces fonctions tirent leur nom du lambda calculus qui sert de base théorique au langage fonctionnel. Il s’agit de fonctions que l’on définit à la volée. Ce type de fonctions est désormais monnaie courante même dans des langages objets qui ne sont pas orientés fonctionnel. Cette possibilité offre une souplesse non négligeable dans l’écriture des programmes.

En F#, le mot clé fun permet de générer une lambda. Si l’on souhaite créer une fonction qui ajoute 2 à un entier, on écrira :

let add2 x = (fun x -> add 2 x)

En Scala, aucun mot clé particulier n’est nécessaire, on écrira simplement :

val add2 = (x:Int) => add (2, x)

Les techniques qui découlent de l’utilisation des lambda sont multiples. Nous allons exposer ici un certain nombre d’entre elles. Même si nous sommes déjà familiers avec ce type de fonctions, leur utilisation dans la programmation fonctionnelle peut paraître assez différente.

Les fonctions : des citoyens de premier rang

Dans la littérature, on parlera plutôt de “First-class function”. Il s’agit de donner aux fonctions la possibilité d’agir comme un argument en entrée ou en sortie d’autres fonctions. Ces dernières sont alors appelées fonctions d’ordre supérieur. Aujourd’hui, par le biais des lambda, beaucoup de langages (parmi eux, certains de type objet) offrent cette possibilité.

Voici un exemple de fonction d’ordre supérieur :

let applyFunction a fn = fn a

Il s’agit d’une fonction assez simple qui prend deux paramètres en entrée. Le premier est un élément qui sera appliqué au deuxième argument qui est une fonction prenant un argument en entrée. Le but de la fonction applyFunction est donc simplement d’appliquer un argument à une fonction et de sortir le résultat. Le type de cette fonction est :

'a -> ('a->'b) -> 'b.

En d’autres termes, cette fonction attend deux objets du type 'a et 'a->'b en entrée et produira un objet du type 'b. L’objet du type 'a->'b étant simplement une autre fonction qui prend un ‘a en entrée et qui produit un 'b.

Je parle ici du type d’une fonction là où d’autres parleraient plutôt de la signature de la fonction. Pour parler de la signature de la fonction applyFunction , j’écrirai plutôt :

(('a, ('a->'b)), ('b)).

Ce qui revient à écrire un tuple contenant le tuple des types d’entrées et le tuple des éléments de sortie.

En Scala, on peut également définir cette fonction :

def applyFunction[A, B] (a:A, fn_A=>B) = fn (a)

Dans le cas du Scala, la signature s’écrit :

applyFunction: applyFunction[A,B](val a: A)(val fn: A => B) => B

Finalement, l’écriture s’apparente surtout à une histoire de convention. Mais alors, pourquoi parler du type d’une fonction ? Simplement, car ce sont des “citoyens de premier rang”, ce qui revient à dire que les  fonctions sont des objets que l’on manipule au même titre qu’un int, un tuple, une liste ou tout autre objet définissable par l’utilisateur. Pour chacune d’entre elle, il existe donc un type les définissant. C’est assez évident d’ailleurs avec les lambda, en Scala on a utilisé le mot clé val pour définir la variable qui va représenter notre lambda. Le type d’une fonction est le type de cette variable (moins la partie indiquant que c’est une lambda).

Le Let binding du point de vue des fonctions

Revenons à notre fonction applyFunction, à quoi peut elle être utile ? Considérons le morceau de code suivant :

let a = 3
let b = 4
let c = a + b

On fait 3 “binding“ pour obtenir le résultat de l’addition de 3 et 4. On pourrait simplement utiliser la fonction add que nous avons défini précédemment. Ou alors on peut utiliser la fonction applyFunction de la façon suivante :

let c = applyFunction 3 (fun a -> applyFunction 4 (fun b -> a + b))

ou encore en Scala :

val c = applyFunction (2, (a:Int) => applyFunction (3, (b:Int) => a + b))

C’est une façon d’expliquer comment le mécanisme de binding fonctionne. On peut d’ailleurs retrouver différentes formes de cette fonction sous le nom bind.

La récursion

La récursion est souvent un sujet délicat dans de nombreux langages. Et même s’il est plus naturel d’écrire certains algorithmes sous leur forme récursive, il est d’usage de les dérécursiver avant de les passer en production. La raison ? Les “stackoverflow exception”. Pour différentes raisons expliquées dans l’article de Clément Carreau “La récursion terminale à la rescousse !”, la récursion est un outil sur lequel on peut compter en programmation fonctionnelle. En effet, sans la récursion, il est parfois difficile d’exploiter au maximum l’expressivité de ces langages. De plus, certains types s’expriment très naturellement de façon récursive.

Reprenons la stack que nous avions utilisée pour présenter la création des types fonctionnels. En F#, nous l’avions écrite ainsi :

type stack = 
    | Node of 'a * stack
    | Nil

En Scala, nous ne l’avions alors pas définie. Voici comment nous pourrions l’écrire :

sealed trait Stack[A]

case class Node[A](elem:A, rest:Stack[A]) extends Stack[A]

case class Nil[A] () extends Stack[A]

Et pour la fonction cons que nous avions définie :

def cons[A] (elem:A, stack:Stack[A]) : Stack[A] = new Node[A](elem, stack)

Le type stack est récursif. Si nous disposons d’un objet de type stack et d’une fonction fn, comment construire un nouvel objet constitué du résultat de l’application de fn sur chacun des éléments de notre objet ? On va pour cela introduire une fonction (d’ordre supérieur) que l’on va appeler map. Voici la définition en F#  immédiatement suivie d’un exemple d’utilisation :

let map fn stack = 
    let rec internalMap ifn iStack acc = 
        match iStack with
        | Node(elem, rest) -> 
            let lambda st = acc  acc Nil
    internalMap fn stack (fun st -> st)

let stInt = 
    cons 5 Stack.Nil
    |> cons 4
    |> cons 3
    |> cons 2
    |> cons 1

let stDbl = map (fun (i : int) -> 1. / ((double) i)) stInt

La même chose en Scala donne :

def map[A,B] (fn:A=>B, stack:Stack[A]) : Stack[B] =
{
  @tailrec
  def internalMap (fn:A=>B, aStack:Stack[A], bStackAcc:Stack[B] => Stack[B]) : Stack[B] =
  {
    aStack match {
      case Node(elem, rest) =>
        val lambda:Stack[B] => Stack[B] = stack => bStackAcc(cons(fn(elem), stack))
        internalMap(fn, rest, lambda)
      case Nil () => bStackAcc(new Nil[B]())
    }
  }
  internalMap(fn, stack, st => st)
}

val st = cons(1,cons(2,cons(3,cons(4,cons(5,new Nil())))))

val nst = map((i:Int) => 1./(i.toDouble), st)

Les deux implémentations sont équivalentes. Et dans les deux cas, on utilise une lambda pour créer la nouvelle liste. Nous sommes obligés de procéder ainsi pour conserver l’ordre. En effet, en accumulant directement le nouvel objet Stack, nous inverserions l’ordre par rapport à la lecture, car nous sommes en train d’utiliser une pile. On peut d’ailleurs remarquer que l’accumulation de l’exécution de lambda fonctionne exactement comme une pile d’appel. C’est la création de cette “stack” implicite qui permet de conserver l’ordre. Bien entendu, on peut également générer la pile dans l’ordre inverse pour ensuite l’inverser.

De prime abord, on peut penser que la démarche est compliquée. Seulement, écrire une fonction qui fait le même travail en utilisant de la programmation impérative (un while par exemple) s’avère bien plus complexe. Cela est dû au fait que chaque passage dans la récursion crée un contexte local permettant de stocker les variables locales sans besoin d’écrire. L’optimisation de récursivité terminale permet quant à elle de faire le nettoyage de façon complètement silencieuse également. On peut dès lors se concentrer sur l’essentiel, à savoir la reconstruction de l’objet stack.

Les fonctions constituent une brique élémentaire des programmes fonctionnels et nous avons présenté ici quelques-unes de leurs capacités. Elles recèlent d’autres possibilités qui en font leur originalité. La curryfication, par exemple, permet beaucoup de choses assez difficiles à reproduire en POO sans aide. Le travail des compilateurs des fonctions ajoute à leur originalité. Leur évaluation des fonctions en F# par exemple est immédiate (“eager evaluation”). En Haskell en revanche, on utilise la “lazy evaluation”, ce qui nous oblige à réfléchir encore autrement.

Il faut savoir être attentif à ces fonctionnements afin de pouvoir les exploiter au maximum. Une telle richesse permet de pouvoir créer une articulation claire et précise des programmes. C’est l’un des points essentiels de la programmation fonctionnelle et les concepts permettant de mieux contrôler le flux sont particulièrement poussés. Dans ce registre, nous parlerons plus tard des monades qui constituent un des outils les plus puissants des langages fonctionnels.