La Prog Fonctionnelle, Partie III

[b0fh]

La Prog Fonctionnelle, Partie III

Evaluation Paresseuse

Python, ayant une sémantique stricte, évalue complètement ses arguments avant d'appeler le corps de la fonction.

Dans un langage paresseux, comme Haskell, le corps d'une fonction peut commencer a s'évaluer avant ses arguments. Dans le cas des listes, il est possible que seul le début d'une liste soit évalué. Dans ce cas, un pipeline de map/filter aura le même comportement que la boucle for, puisque les listes intermédiaires seront évaluées en parallèle, a la demande, pour être détruites aussitôt. Le compilo pourra éliminer les allocations mémoire intermédiaires inutiles.

Nous allons simuler la sémantique paresseuse à l'aide de fonctions: pour empêcher l'évaluation d'un argument, nous pouvons l'enrober dans une fonction sans argument.

A titre d'exemple, essayons d'écrire une fonction qui émule le comportement d'un operateur ternaire.

Code PYTHON :

def my_if(test, good, bad):
    if test:
        return good
    else:
        return bad

Cette fonction n'a pas la même sémantique qu'un opérateur ternaire. Voyez-vous pourquoi ?

Le code suivant:

Code PYTHON :

if 0 == 1:
    return sys.exit(0)
else:
    return None

N'est très clairement pas équivalent à

Code PYTHON :

my_if(0 == 1, sys.exit(0), None)

Parce que la fonction évalue ses arguments avant l'appel, alors que la structure if n'évalue que le corps de la branche pertinente, après avoir terminé le test.Pouvons-nous reproduire ce comportement en fonctionnel ?

Oui, on peut, en retardant l'évaluation au moyen de fonctions constantes:

Code PYTHON :

def my_if(test,good,bad):
    if test:
        good()
    else:
        bad()

my_if(0 == 1, lambda: sys.exit(0), lambda: None)

Ici, les lambdas définissent des fonctions sans argument. On peut les passer a d'autres fonctions, sans que leur corps ne soit évalué; on déclenche l'évaluation avec ().

Itérateurs

L'avantage du style fonctionnel, c'est qu'il se compose facilement. Par exemple, il est plus facile d'empiler des maps/filters que des boucles for:

Code PYTHON :

def even(x):
    return filter(lambda x: x % 2 == 0, x)

def affine(x):
    return map(lambda x: 3*x + 1, x)

out = affine(even(input))

Ici, il est très facile de séparér les deux opérations (filtrer les éléments pairs, et leur appliquer une transformation affine.) La version basée sur les boucles mélange les deux opérations, ce qui rend le code moins modulaire et moins clair:

Code PYTHON :

out = []
for x in input:
    if x % 2 == 0:
        out.append(3*x + 1)

Malheureusement, avec les implémentations de map et filter telles qu'elles ont été présentées dans la Partie I, la version fonctionnelle se traduit en:

Code PYTHON :

out1 = []
for x in input:
    if x % 2 == 0:
        out1.append(x)

out = []
for x in out1:
    out.append(3*x+1)

Ce qui est beaucoup moins efficace, puisqu'on alloue une liste intermédiaire pour la consommer et la détruire aussitôt.

Nous allons résoudre ce problème, en utilisant le truc de l'évaluation paresseuse pour représenter une liste dont les éléments sont évalués un à un.

Code PYTHON :

class StopIteration(Exception):
    pass

class Iterator(object):
    def __init__(self, normal_list):
        self.l = normal_list

    def next():
        try:
            return self.l.pop(1)
        except IndexError:
            raise EndOfList()

Cette classe, a partir d'une liste classique, construit une liste paresseuse qui renvoie ses éléments un par un, à chaque appel de la méthode next().

Nous pouvons maintenant définir notre fonction map sur les LazyLists, sous forme d'une classe:

Code PYTHON :

class Map(object):
    def __init__(self, f, src):
        self.f = f
        self.src = src

    def next():
        return self.f(src.next())

Nous pouvons aussi définir Filter:

Code PYTHON :

class Filter(object):
    def __init__(self, test, src):
        self.test = test
        self.src = src

    def next():
        while True:
            x = self.src.next()
        if self.text(x):
            return x

Notez l'utilisation astucieuse des exceptions, qui permet de propager naturellement les fins de liste le long de la chaine sans avoir a écrire explicitement du code pour le gérer.

Manque encore une méthode dans LazyList pour la convertir en liste normale:

Code PYTHON :

def toList(self):
    out = []
    try:
        while True:
            out.append(self.next())
    except StopIteration:
        return out

Je peux maintenant écrire

Code PYTHON :

out = Map(lambda x: 3*x + 1, Filter(lambda x: x % 2 == 0, input)).toList()

Et le code aura le même comportement désirable que la boucle for, qui consiste a traiter les éléments un par un le long de tout le pipeline.

Dans la librairie standard, Iterator s'appelle en fait iter. A noter que la boucle for accepte implicitement un itérateur, on peut donc écrire:

for x in Map(lambda x: ...., src): ....

Coroutines

Le concept d'itérateur devient particulièrement puissant si on le combine avec celui des coroutines. Les coroutines sont une primitive de programmation concurrente, encore plus primitive que les threads. Comme les threads, les coroutines s'exécutent chacune avec leur propre stack, mais pas en parallèle; le passage d'une coroutine a une autre se fait coopérativement, en des points-clef du code, plutôt que par préemption.

Les coroutines s'écrivent en python à l'aide du mot-clef yield. Une fonction qui contient un mot yield n'est plus une fonction, mais un objet itérateur. yield fonctionne un peu comme un return, mais sauvegarde l'état de la fonction, de sorte que l'exécution reprend à la suite du yield au prochain appel à next().

Voici un exemple simple (bien que peu utile) pour en visualiser le flot:

Code PYTHON :

def my_coroutine():
    a = yield(1)
    b = yield(a*2)
    yield(b*3)


def my_main():
    cor = my_coroutine()
    x = cor.next()
    y = cor.next(x+2)
    z = cor.next(y+3)

Voyons pas à pas ce qui se passe dans my_main:

• une nouvelle instance de la coroutine my_coroutine est créée dans cor
  
• au premier appel à next(), la coroutine commence à s'exécuter. le premier appel à yield, fait retourner next avec l'argument (1) comme valeur de retour. x contient donc 1.
  
• le main appelle `next(x+2), ce qui fait reprendre l'exécution de la coroutine ou elle s'était arrêtée; a reçoit la valeur de l'argument à next (x+2).
  
• la coroutine yield sur la valeur (a2), qui cause le retour de la fonction next dans le main, y contient donc a2.
  
• l'appel a next relance la coroutine, causant le retour du dernier yield avec la valeur y+3. b contient donc y+3
  
• la coroutine fait un yield final sur b*3, qui est récupéré dans le main par z.
  

Au final, on aura eu: x=1, a=x+2, y=a2, b=y+3, z=b3. L'exécution de la coroutine et de la fonction principale sont entrelacées.

De manière générale, les coroutines de ce style, bidirectionnelles, sont dangereuses. Les débugger peut être un vrai cauchemar.

Beaucoup moins dangereuses, sont les coroutines qui ne communiquent que dans une seule direction. Deux scénarios possibles:

• Yield est appelé sans argument, et on ignore la valeur de retour de next(). La coroutine se comporte comme un consommateur de données; on a un modèle basé sur le push.
  
• On ignore la valeur de retour de yield, et on ne passe pas d'argument à next(); la coroutine se comporte comme un producteur. On l'appelle alors générateur.
  

On peut donc facilement réécrire nos combinateurs précédents en termes de générateurs:

Code PYTHON :

def map(f, src):
    for x in src:
        yield f(x)

def filter(test, src):
    for x in src:
        if test(x):
            yield x

Générateurs

Les générateurs peuvent faire mieux que ça. Par exemple, vous savez peut-être que les fichiers ouverts en mode texte implémentent une interface d'itérateur qui permet de traiter les lignes une a une:

Code PYTHON :

for line in open('fichier'):
   ....

Et si nous voulions lire, non pas des lignes, mais des mots ?

Code PYTHON :

def words(lines):
    for line in lines:
        for word in line.split():
            yield word

On peut ensuite faire:

Code PYTHON :

for word in words(open('fichier'))
    ...

Et, contrairement à une fonction classique, cet usage de words() ne cause évidemment pas le chargement du fichier entier en mémoire; la boucle de découpage de words tournera entrelacée avec celle du programme principal.

Notez que dans les versions récentes, il existe une notation raccourcie équivalente:

Code PYTHON :

def words(lines):
    for line in lines:
        yield from line.split()

Voici un exemple de générateur qui ne termine pas, et qui génère une infinité de nombrs entiers.

Code PYTHON :

def enum():
    i = 0
    while True:
        yield i
        i += i

Voici un générateur qui garde les n premiers éléments d'un itérateur:

Code PYTHON :

def head(n, src):
    while n > 0:
        yield src.next()
        n -= 1

Et on peut les combiner pour obtenir une range:

    r = list(head(10, enum()))

Compréhensions de Générateurs

La notation des compréhensions de listes, présentée dans la partie I, génère une vraie liste et souffre des mêmes problèmes d'allocations inutiles.

Heureusement, la même syntaxe peut être utilisée pour fabriquer des générateurs, il suffit de remplacer les crochets par des parenthèses. Par exemple:

[code=python]out = (x*3 + 1 for x in src if x % 2 == 0)

Est équivalent à notre

Code PYTHON :

out = Map(lambda x: x*3, Filter(lambda x: x%2 == 0, src))

Et offre le comportement d'entrelacement que l'on souhaite.