logo le blog invivoo blanc

Paradigme de programmation fonctionnel

27 février 2020 | C#, C++, Java, Python | 0 comments

Cet article sur le paradigme de programmation fonctionnel est le 3ème de notre série sur les paradigmes de programmation. N’hésitez pas à prendre connaissance des deux premiers articles :

Lambda-calcul, un système du paradigme de programmation fonctionnel

Créée par Alonzo Church en 1930, cette théorie mathématique définit les fondations des fonctions et des applications. C’est le premier formalisme qui permet de gérer les fonctions récursives. Le lambda-calcul, la machine de Turing et le modèle Herbrand-Gödel sont des éléments essentiels de la théorie de la calculabilité.

L’un des principes du lambda-calcul est que « tout est fonction ». Comme le changement d’état et la mutation des données ne peuvent pas être représentés par des évaluations de fonctions la programmation fonctionnelle ne les admet pas, au contraire elle met en avant l’application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d’état.

Lisp

En 1958, John Mac Carthy et son équipe implémente le premier interpréteur LISP (LISt Processing ou, pour les médisants, Lots of Idiot and Stupid Parenthesis) en se basant sur la théorie du lambda-calcul. Dédié à résoudre des problèmes qui ne pouvait pas être résolu par FORTRAN (notamment grâce à la récursivité), le Lisp est à l’origine de beaucoup de progrès en informatique théorique. La programmation orientée objet dérive des langages fonctionnels : Smalltalk le premier langage objet qui a été popularisé était écrit en Lisp…

Le Lisp est un langage dit préfixé : la fonctionnelle est toujours en première position ce qui facilite le parsing. Le noyau de base est composé de très peu d’instructions (defun, car, cdr, cond, cons et les opérateurs de base). C’est, donc, un langage relativement simple mais très expressif :

  • ( + 5 3)
    -> 8
  •  (/ 8 2)
    -> 4
  • (defun f(x) (* x x))
    -> définit une fonction f qui prend un argument x et qui retourne x*x

De nombreuses variantes de Lisp ont été développé au cours du temps. La plus répandue aujourd’hui est GNU Common Lisp. Lisp est aussi le langage de macros dans emacs (un éditeur de texte sous unix qui est très populaire), ou sous sa version AutoLisp le langage de macros dans AutoCAD. Pour en apprendre plus, je vous conseille de jeter à œil à : https://fr.wikipedia.org/wiki/Lisp.

Concepts sous-jacent du paradigme fonctionnel

La pureté

Les fonctions sont dites ‘pure’ lorsqu’elles ont des résultats qui ne dépendent strictement que de leurs arguments, sans autre effet externe. Voici un exemple de fonction pure :

def f( i ):
	return i + 4
>> f(1)
5
>> f(1)
5

Voici un exemple de fonction impure :

n = 4
def f( i ):
	global n
	n += i
	return n
>> f(1)
5
>> f(1)
6

Une fonction pure permet de cloisonner, de localiser le code mis en œuvre. Cela augmente sa stabilité, son déterminisme et facilite sa compositionnalité.

Fonction de première classe

Être de première classe, c’est donc avoir le même statut qu’une valeur telle qu’un entier ou un caractère, c’est-à-dire :

  • Pouvoir être nommé, affecté (et typé) :

x=sin

  • Pouvoir être défini et créé à la demande :

x= lambda x: x+1

  • Pouvoir être passé en argument à une fonction :

map(lambda x: x*x, [1, 3, 4 ] )

  • Pouvoir être le résultat d’une fonction :

(f( 3 ) ) ( 5 )

  • Pouvoir être stocké dans une structure de données quelconque :

array=[ log, exp, tan ]

Notion de fermeture

Mais, pour être pure et/ou de première classe, une fonction doit parfois être transformée en fermeture (closure), i.e. l’association du code de la fonction avec un environnement de définitions.

def f(i, j):
       def h(k):
             return i + j + k
       return h

La fonction f retourne une fonction h qui prend un argument mais dépend des 2 arguments passés à f.

Exemple de paradigme fonctionnel

Voici un exemple de fonction qui parcourt récursivement une arborescence de fichiers et, qui pour chaque fichier qui respecterait un ‘prédicat’ appliquerait une fonction.

from os import scandir

def scan_directory( path, action, predicate ):
    with scandir( path ) as it:
        if predicate:
            for entry in it:
                if entry.is_dir():
                    scan_directory( entry.path, action, predicate )
                elif predicate( entry ):
                    action( entry )
        else:
            for entry in it:
                if entry.is_dir():
                    scan_directory( entry.path, action, predicate )
                else:
                    action( entry )

scan_directory( "C:/Tools/Anaconda3",
                lambda entry: print( entry.path ),
                lambda entry: entry.name.lower().endswith( ".py" ) )

Sans programmation fonctionnelle, ce type d’implémentations serait impossible.

Conclusion

  • La programmation fonctionnelle est bonne pour le développement de programmes : pureté et première classe induisent une part de stabilité, déterminisme, testabilité, cloisonnement, fluidité d’utilisation, compositionalité, généralisation, extensibilité, etc.
  • La programmation fonctionnelle est bonne pour l’objet-modulaire : elle met un peu d’huile dans les rouages, et amoindrit parfois la complexité des architectures.
  • La programmation fonctionnelle est soluble : pureté et première classe des fonctions peuvent être considérées, incluses et facilitées dans n’importe quel langage.

La plupart des langages supportent le paradigme fonctionnel : Python, C++, Java, C#, etc…