La Prog Fonctionnelle, Partie II

[b0fh]

La Prog Fonctionnelle, Partie II

Closures

Jusqu'a présent, nous avons vu des fonctions d'ordre supérieur prenant en argument d'autres fonction. Une fonction peut aussi retourner en résultat une autre fonction !

Par exemple, imaginons que nous avons une lib qui exécute un algorithme de clustering de points. Le prototype serait le suivant:

Code PYTHON :

def cluster(points, distance_function):
    ...

points est une liste de points, et pour que l'algorithme soit personnalisable, on peut lui passer une fonction qui calcule la distance entre deux points. On pourrait utiliser la distance euclidienne:

Code PYTHON :

def distance_euclidienne(a, b):
    dx = b.x - a.x
    dy = b.y - a.y
    return math.sqrt(dx*dx + dy*dy) # pythagore

Ou, la "distance manhattan":

Code PYTHON :

def distance_manhattan(a, b):
    dx = b.x - a.x
    dy = b.y - a.y
    return (dx + dy)

Ou, pourquoi pas une distance cubique:

Code PYTHON :

def distance_cubique(a, b):
    dx = b.x - a.x
    dy = b.y - a.y
    return math.pow(math.pow(dx,3) + math.pow(dy,3), 1/3)

Ces fonctions sont identiques à l'exception de la puissance. Nous pouvons donc essayer d'écrire une fonction générique prenant un argument supplémentaire:

Code PYTHON :

def distance_générique(ordre, a, b):
    dx = b.x - a.x
    dy = b.y - a.y
    return math.pow(math.pow(dx,ordre) + math.pow(dy,ordre), 1/ordre)
   

(La distance manhattan est d'ordre 1, la distance euclidienne d'ordre 2. La généralisation s'appelle la distance de Minkowski)

Problème: notre algorithme exige une fonction à deux arguments, pas à trois. Il nous faudrait un moyen d'"enregistrer" et cacher le premier argument dans un objet fonction.

Heureusement, c'est possible est très facile, dans un langage supportant les Closures (Fermetures en bon français):

Code PYTHON :

def distance_minkowski(ordre):
    def distance(a,b):
        dx = b.x - a.x
        dy = b.y - a.y
        return math.pow(math.pow(dx,ordre) + math.pow(dy,ordre), 1/ordre)
    return distance

On peut ensuite écrire, ou appeler directement:

Code PYTHON :

distance_manhattan = distance_minkowski(1)
distance_euclidienne = distance_minkowski(2)
distance_chebychev   = distance_minkowski(10000)

Ceci est très difficile à réaliser en C, par exemple, parce que C permet de retourner un pointeur vers une fonction, mais pas une Closure. Mais une Closure, c'est quoi ?

C'est un bout de code (comme vu précédemment) associé a un contexte qui stocke les valeurs des variables "non-libres", çad celles qui ne sont pas des arguments.

Quand je définis la fonction distance() a l'intérieur de distance_minkowski, a et b sont des variables libres; elles seront passées quand la fonction sera appelée, aucun problème. ordre, par contre, n'est pas une variable libre. Bien que le code ne soit compilé qu'une seule fois, au moment ou l'instruction def distance(): est exécutée, la valeur des variables non-libres est "capturée" et stockée dans la closure. Dans cet exemple, distance_manhattan et distance_euclidienne sont des closures, qui pointent vers le même code (distance), mais avec une valeur différente pour ordre.

L'absence de closures en C classique est une des raisons principales qui en font un langage mal adapté au style fonctionnel.

Décorateurs

Puisque nous pouvons accepter des fonctions en argument, et retourner des fonctions, nous pouvons donc écrire des fonctions d'ordre supérieur qui transforment d'autres fonctions. On appelle ces fonctions spéciales des décorateurs.

Considérez cette implémentation naive de la fonction de Fibonacci:

Code PYTHON :

def fib(n):
    if n < 1:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

C'est l'archétype de la mauvaise implémentation: la fonction fib s'appellera récursivement en nombre de fois proportionnel à la valeur du résultat, une catastrophe.

Si on veut garder (pour des raisons esthétiques) une implémentation récursive plutôt qu'itérative, on peut énormément accélérer la performance en memoizant la fonction, c'est-à-dire en la dotant d'une mémoire, qui évite de recalculer plusieurs fois le résultat de la même valeur:

Code PYTHON :

fib_memory = dict()
def fib(n):
   if n in fib_memory:
       return fib_memory[n]
   if n < 1:
       return 0
   if n == 1:
       return 1
   res = fib(n-1) + fib(n-2)
   fib_memory[n] = res
   return res

C'est une technique suffisamment intéressante pour la réutiliser; nous allons donc écrire une fonction d'ordre supérieur qui ajoute la mémoization à une fonction quelconque.

Code PYTHON :

def memoize(f):
    memory = dict()
    def new_f(x):
        if x in memory:
            return memory[x]
        res = f(x)
        memory[x] = res
        return res
    return new_f

On peut ensuite écrire:

Code PYTHON :

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

fib = memoize(fib)

(Note pour les experts: ça marche parce que def n'inclut pas la fonction elle-même dans son scope local, l'appel récursif utilise donc le scope global; après le remplacement par la version mémoizée dans le scope global, l'appel récursif se fera dans le scope global sur la fonction mémoizée, et plus sur la fonction originale)

On peut imaginer le même truc pour, par exemple, ajouter du logging à une fonction, convertir automatiquement des types en entrées, appliquer un contrôle d'accès, etc etc.

Ce pattern est tellement pratique et courant qu'il existe un raccourci pour l'écrire plus joliment:

Code PYTHON :

@memoize
def fib(n):
    ...

Ce qui suit le @ peut être n'importe quelle fonction, qui sera appelée avec la fonction originale en argument, et le résultat remplacera la définition originale.

On peut empiler les décorateurs:

Code PYTHON :

@decorateur1
@decorateur2
@decorateur3
def f(bli,bla,blu):
    ...

Ce qui est équivalent à

Code PYTHON :

def f(bli,bla,blu):
    ...
f = decorateur1(decorateur2(decorateur3(f)))

On peut aussi utiliser des arguments:

Code PYTHON :

@deco(a,b,c)
def f(x):
    ....

Ce qui est un peu plus technique: deco(a,b,c) doit être un décorateur, donc deco est une fonction qui retourne un décorateur. Functionception !

Une utilisation courante est, par exemple, l'enregistrement de points d'entrée pour une application web ou un bot irc:

Code PYTHON :

@command('kick')
def kick():
    ...

def command(name):
    def decorator(f):
        global_commands[name] = f
        return f
    return decorator

On se retrouve avec un dict global_commands contenant une référence à toutes les fonctions enregistrées. Plus sûr que la reflexion !