Langages fonctionnels

Fonctions

Dans un langage fonctionnel "pur", le terme fonction est à prendre au sens mathématique du terme.
f(x) = y.
En informatique, cela se traduit par une fonction qui prend x en paramètre et renvoie y :
// isVoyelle('a') = true
// isVoyelle('r') = false
boolean isVoyelle(char c){ ... }
Une fonction transforme un type de donnée en un autre : char -- isVoyelle() --> boolean Dans les langages impératifs, à l'intérieur de la fonction isVoyelle(), on pourrait aller lire ou écrire dans un fichier, afficher une chaîne à l'écran, modifier une variable globale, tout en renvoyant toujours le même résultat. Une fonction peut avoir des effets de bord, son exécution a toujours lieu dans le cadre global de l'environnement d'exécution du programme.

C'est bien pratique mais ça ne donne pas la garantie qu'une fonction fera toujours exactement la même chose chaque fois qu'on l'appelle, ce qui peut avoir comme effet :

Fonction pure

Une fonction est dite pure si elle n'a pas d'effet de bord ; pour une valeur donnée d'un argument, la valeur du retour sera toujours la même.

En pratique, quand on programme, les fonctions ne sont pas pures, elles peuvent : Par exemple, la fonction test() suivante n'est pas pure.
class ExempleFonctionImpure {
    
    private static int i = 0;
    
    public static String test(int j){
        i += j;
        return i;
    }
    
}
En effet, test(1) va renvoyer 1 au premier appel, puis 2 au second appel etc.

Transparence référentielle

Propriété d'un langage (ou d'un programme) qui fait que toute variable, ainsi que tout appel à une fonction, peut être remplacée par sa valeur sans changer le comportement du programme.
(tiré de www.fil.univ-lille1.fr)

Pour satisfaire cette propriété,

Monades

En pratique, on a besoin des effets de bords - sans eux, on ne pourrait même pas connaître le résultat de l'exécution d'un programme !
Comment faire tout en respectant l'intégrité référentielle ?
C'est expliqué ici : You Could Have Invented Monads! (And Maybe You Already Have.)

Dans un langage fonctionnel pur, les effets de bords sont "emprisonnées" dans des monades.

Prenons deux fonctions pures, f et g, qui transforment un float en float.
    f : float -> float
    g : float -> float
Pour débugger, on voudrait que chaque fonction, en plus de renvoyer un float, renvoie aussi un message.
Si on ne peut pas afficher à l'écran ou remplir un log global, on peut toujours construire deux fonctions qui renvoient un message (string) en plus d'un float :
    f' : float -> (float, string)
    g' : float -> (float, string)
    f'(x) = (f(x), "f a été appelée")
On voudrait en plus continuer à pouvoir composer nos fonctions.
Avec f et g, pas de problème:
    x --f--> y = f(x) --g--> z = g(y) = g(f(x)) = g o f (x)
    |        |               |
  float    float           float
Avec f' et g', on peut le faire aussi, en définissant par exemple:
g'(f'(x)) = ( g(f(x)), "message de f" + "message de g" )
    (x, "")
      |
      f'
      |
      y = (f(x), "message de f")
      |
      g'
      |
      z = (g(y), "message de g")
        = (g( (f(x), "message de f") ), "message de g")
        = ( g(f(x)), "message de f" + "message de g" )
On réussit à composer f' et g', mais ça n'est pas pratique car chaque fois qu'on utilise f' ou g', on doit se préoccuper de la concaténation des messages.

Divers

Mémoïsation

Si une fonction est pure, pour un argument donné elle renvoie toujours la même valeur.
On peut donc fabriquer un cache : enregistrer dans un tableau toutes les valeurs possibles que peut prendre le argument, avec la valeur de retour de la fonction. on dit qu'on peut la mémoïser.
Que l'on renvoie la valeur calculée ou la valeur stockée dans le cache, on aura le même résultat.
On dit que la fonction est mémoïsable.

En pratique, on ne peut pas le faire pour des types infinis (dont le cardinal de l'ensemble des valeurs du type est infini).

Curryfication

La notion de fonction pure est plus large que la notion mathématique de fonction ; en effet, une fonction pure peut avoir plusieurs arguments en entrée (et dans certains langages renvoyer plusieurs valeurs).
Mais on peut transformer une fonction prenant plusieurs arguments en une fonction prenant le premier argument et renvoyant une fonction prenant les arguments suivants. Ce procédé s'appelle la curryfication (le nom vient de Haskel Curry).

Exemple en PHP :
<?php
function uncurried_add($x, $y){
    return $x + $y;
}

// Avant PHP 7.4
function curried_add($x){
    return function($y) use($x) { return $x + $y; };
}

// Depuis PHP 7.4 ("arrow functions")
function curried_add2($x){
    return fn($y) => $x + $y;
}

echo "uncurried_add(3, 5) = " . uncurried_add(3, 5) . "\n";
echo "curried_add(3)(5) = " . curried_add(3)(5) . "\n";
echo "curried_add2(3)(5) = " . curried_add2(3)(5) . "\n";
(code source)

Voir aussi un exemple en java.

Vocabulaire :
Une fonction d'ordre supérieur est une fonction qui prend en paramètre une fonction ou qui renvoie une fonction.

Functions as first class citizens

Les fonctions font partie des types connus des langages fonctionnels ; elles peuvent être
- nommées
- évaluées
- passées comme argument
- renvoyées comme résultat
- utilisées partout où une expression peut l'être. On se retrouve donc avec deux manières de programmer équivalentes mais différentes.

Exemple : factorielle

En java :
public class Factorial{
    public static int compute(int n){
        int res = 1;
        for (int c = 1; c <= n; c++)
            res = res * c;
        return res;
    }
}
En ~ lambda-calcul :
λ n.if n=0 then 1 else n*(fact (n-1))
En Ocaml :
let rec fact =
    function n -> if n=0 then 1 else n*(fact (n-1))
En Haskell :
factorial n = if n < 2
              then 1
              else n * factorial (n - 1)
ou
factorial 0 = 1
factorial n = n * factorial (n - 1)
En Lisp :
(defun factorial (n)
  (if (= n 1)              
      1                           
      (* n (factorial (- n 1))))) 

On peut remplacer la fonction par son résultat, on est surs qu'on ne va pas avoir fait Dans un langage purement fonctionnel, une fonction ne fait qu'une seule chose : elle prend un (ou plusieurs) argument(s) en entrée et renvoie une valeur en sortie.
Le corps de la fonction est comme un gros return, on se concentre sur ce qu'on renvoie, pas ce qu'on fait entre temps.
La syntaxe facilite cette orientation.
Par exemple en java, if then else est une instruction composée, qui fait des choses. En Ocaml, c'est une expression, qui calcule la valeur d'un type.