<!-- Slide number: 1 -->
Programmation Fonctionnelle
Chapitre I :
Introduction
BEJI Faryel
1
<!-- Slide number: 2 -->
ML, Lisp, and Haskell are the only programming languages that I've seen where one spends more time thinking than typing. Philip Greenspun
2
<!-- Slide number: 3 -->
Plan
I- Avant Propos
II- Programmation Impérative /Déclarative
III-Historique de la PF
IV- Paradigmes de Programmation
V- Intelligence Artificielle et PF
VI- Langages de PF
3
<!-- Slide number: 4 -->
I- Avant Propos
Souvent présentés comme le summum de la technologie, les ordinateurs sont en fait des machines assez simples (dans leur principe), fabriquées à partir de quelques types de circuits élémentaires :
registres, mémoires, additionneurs, décodeurs etc...
4
<!-- Slide number: 5 -->
Ces machines fonctionnent de la manière suivante :
- elles exécutent séquentiellement des programmes qui sont des suites d'instructions élémentaires
- les données que peuvent manipuler ces instructions appartiennent à quelques types bien connus :
(nombres entiers ou réels, caractères, adresses, et c'est à peu près tout...)
5
<!-- Slide number: 6 -->
Ceci convenait toutefois très bien aux premières applications des calculateurs :
- il s'agissait en effet d'effectuer des suites de calculs longues et répétitives
- pour établir des tables numériques , calculs numériques, etc …
6
<!-- Slide number: 7 -->
Les programmes de l'époque ne pouvaient guère être compliqués
- en raison de la très faible capacité des mémoires disponibles
7
<!-- Slide number: 8 -->
Cette capacité augmentant naturellement au fil des années, on s'est avisé qu'il pouvait être intéressant :
d'écrire des programmes en utilisant des noms mnémotechniques pour chacune des instructions de la machine : naissance du langage d'assemblage
(Ainsi les programmes sont plus facile à écrire et surtout à relire)
d'utiliser des langages de programmation indépendants de la machine utilisée : langages évolués
(chaque instruction en langage évolué se traduisant en une petite séquence d'instructions dans le langage de la machine)
8
<!-- Slide number: 9 -->
On remarque que cette évolution préserve deux traits fondamentaux de l'informatique des origines :
l'aspect séquentiel des programmes
la notion d'affectation
→
ce qu'on appelle «programmation impérative» puisqu'il s'agit de faire exécuter une suite d'ordres par une machine bête mais disciplinée
9
<!-- Slide number: 10 -->
Ne pouvant dire à la machine «c'est votre problème débrouillez-vous»
- le programmeur doit décrire la suite exhaustive des actions à exécuter
Vous connaissez tous l'aspect fastidieux de ce genre d'activité
- qui demande par ailleurs une formation particulière (songez à vos premiers démêlés avec l'algorithmique)
10
<!-- Slide number: 11 -->
La « crise » du logiciel
Comment :
gérer la taille et la complexité des programmes modernes?
réduire le temps et le coût du développement logiciel ?
accroître notre confiance qu’un programme fonctionne correctement ?
11
<!-- Slide number: 12 -->
Approche pour résoudre la crise
Créer des langages de programmation qui :
permettent que les programmes soient écrits clairement
à un haut niveau d’abstraction
supportent des composantes logicielles réutilisables
encouragent le recours à la vérification formelle
permettent un prototypage rapide
offrent des outils puissants pour résoudre les problèmes
Les langages de programmation fonctionnels (PF) :
boite à outils particulièrement élégante permettant de
réaliser tous ces objectifs
12
<!-- Slide number: 13 -->
II- Programmation Impérative/Déclarative
La plupart des langages de programmation (il en existe plusieurs milliers) relèvent de la susdite Programmation Impérative
Il existe cependant une autre catégorie : les langages déclaratifs (LD) ?
13
<!-- Slide number: 14 -->
Dans un langage déclaratif l'activité de programmation consiste essentiellement :
- à décrire le rapport qui existe entre les données et les résultats que l'on veut obtenir
- plutôt que la séquence de traitements qui mène des unes aux autres
(évidemment ceci représente un idéal...)
Publicité
14
<!-- Slide number: 15 -->
Deux approches sont fréquemment utilisées dans les LD :
Programmation Fonctionnelle :
Le but d'un traitement informatique est de calculer des résultats à partir de données
Pourquoi ne pas assimiler un programme à une fonction qui à des données associe un résultat ?
un traitement complexe s'obtiendra en combinant plusieurs fonctions intermédiaires (correspondant à des sous-traitements)
Exemples : Ml, Ocamel, Haskell, Sheme, Hope, Lisp, ...
Programmation Logique :
On décrit par une formule logique la relation qui existe entre les données et les résultats
Exemples : Prolog, Qlog, …
15
<!-- Slide number: 16 -->
III- Historique de la PF
16
<!-- Slide number: 17 -->
1930s
Alonzo Church développe le lambda-calcul, une théorie des fonctions, simple mais puissante
17
<!-- Slide number: 18 -->
1930s
Haskell B. Curry développe la logique combinatoire, qui deviendra le moteur des langages fonctionnels
18
<!-- Slide number: 19 -->
1950s
John McCarthy développe Lisp, le premier langage fonctionnel, sous l’influence du lambda-calcul, mais en conservant l’affectation des variables
19
<!-- Slide number: 20 -->
1960s
Peter Landin développe ISWIM 1, le premier langage de programmation fonctionnel pur, fortement basé sur le lambda-calcul, sans affectation de variables
1. De : « If you See What I Mean »
20
<!-- Slide number: 21 -->
1970s
John Backus développe FP, un langage de programmation fonctionnel qui pose l’accent sur les fonctions d’ordre supérieur et sur l’intégration avec le raisonnement sur les programmes
21
<!-- Slide number: 22 -->
1970s
Robin Milner et autres développent ML, le premier langage fonctionnel moderne, qui introduit l’inférence de type et les types polymorphes
22
<!-- Slide number: 23 -->
1970s - 1980s
David Turner développe un nombre de langages fonctionnels paresseux (lazy), qui culminent dans le système Miranda
23
<!-- Slide number: 24 -->
1987
Un comité international de chercheurs débute le développement de Haskell, un langage fonctionnel paresseux standard
24
<!-- Slide number: 25 -->
2003
Le comité publie le rapport Haskell 98, qui définit une version stable du langage
25
<!-- Slide number: 26 -->
Les héros français
1985
Gérard Huet et son équipe à l’INRIA développent CAM, une version du langage ML destiné à s’intégrer avec le système Coq
Autres intervenant dans le chemin CAM->CAML->OCAML : Xavier Leroy, Didier Rémy, Jérôme Vouillon
26
<!-- Slide number: 27 -->
IV- Paradigmes de Programmation
A- Programmation Impérative
En programmation impérative le programme est une suite d’instructions qui modifient l’état de la mémoire centrale
On peut représenter un programme par une machine d'états qui représente les états successifs de la mémoire
27
<!-- Slide number: 28 -->
L'implémentation de la quasi totalité des processeurs qui équipent les ordinateurs est de nature impérative
Les processeurs sont faits pour exécuter des instructions élémentaires exécutables par le processeur et modifiant l’état de la mémoire
28
<!-- Slide number: 29 -->
Ce type de programmation nécessite pour le programmeur de connaître à tout instant l'état de la mémoire
La plupart des langages de haut niveau suivent le paradigme impératif même s’ils utilisent des variables et des opérations plus complexes que les instructions élémentaires
• Fortran, C, Pascal, Java …
29
<!-- Slide number: 30 -->
Les langages de haut niveau intègrent également de nombreuses techniques destinées à réduire le nombre de variables à gérer :
Variables dont la portée se limite à la procédure dans laquelle elles ont été définies et qui sont automatiquement libérées à la sortie de la procédure
Encapsulation des données, à l'origine de la programmation structurée, et la programmation orienté objet
30
<!-- Slide number: 31 -->
B- Programmation Fonctionnelle
Publicité
Le paradigme fonctionnel n'utilise pas de machine d'états pour décrire un programme, mais un emboîtement de fonctions
Le programmeur ne se préoccupe pas de l’état de la mémoire
31
<!-- Slide number: 32 -->
Il est en théorie impossible d’assigner une valeur à une variable
Un programme est donc une application, au sens mathématique, qui ne donne qu'un seul résultat pour chaque ensemble de valeurs en entrée
→ Exécution d’un programme = Evaluation d’une fonction
32
<!-- Slide number: 33 -->
Cependant, pour des raisons d'efficacité, la plupart des langages fonctionnels autorisent l’utilisation de variables
→ Langages fonctionnels impurs
A noter également que beaucoup de langages impératifs permettent plus ou moins d’écrire dans un style fonctionnel
33
<!-- Slide number: 34 -->
Les langages fonctionnels emploient des types et des structures de données de haut niveau comme les listes extensibles
Il est ainsi généralement possible de réaliser facilement des opérations comme la concaténation de listes
Les langages fonctionnels font un large usage de la récursivité
34
<!-- Slide number: 35 -->
La programmation fonctionnelle offre des avantages sans équivalent en impératif
Malgré cela, elle reste peu utilisée en dehors du milieu universitaire et des lobbyistes
déficit en outils et en bibliothèques de qualité commerciale
manque de programmeurs formés
35
<!-- Slide number: 36 -->
Quelques langages fonctionnels :
Lisp (le premier)
Scheme, Caml, Haskell
XSLT (dédié au traitement XML)
Rebol (celui que je préfère)
…
36
<!-- Slide number: 37 -->
C- Programmation Logique
Fondée sur la logique mathématique
Programmation déclarative
On déclare des informations avérées:– le programme appelé aussi la base de connaissances
On déclare une requête (appelée aussi un but) – Le moteur Prolog tente de répondre à la requête en se servant des informations contenues dans la base de connaissance
37
<!-- Slide number: 38 -->
Utilisée en Intelligence Artificielle
La programmation logique se confond avec le langage Prolog !
38
<!-- Slide number: 39 -->
Exemple: Factorielle (impératif)
Programme C
int fac(int n) { int i; int res = 1; if(n==0) return 1; else for(i= 1; i <= n; i++) res *= i; return res; };int reponse = fac(3); printf("factorielle 3 vaut %d", reponse);
39
<!-- Slide number: 40 -->
Exemple: Factorielle (fonctionnel)
Programme LISP
(defun factorial (n) (if (<= n 1) 1 (* n (factorial (- n 1)))))(factorial 3)
Notez,
Aucune variable utilisée
L’appel récursif à la fonction factorial
L’emboitement des fonctions – la fonction <= emboitée dans la fonction if– la fonction emboitée dans la fonction if– la fonction factorial emboitée dans la fonction – la fonction - emboitée dans la fonction factorial
40
<!-- Slide number: 41 -->
Exemple: Factorielle (logique)
Base de connaissances Prolog
factoriel(0,1)
factoriel(X,Y) :-- X1 is X–1 et factoriel(X1,Z) et Y is Z*X
Requêtes Prolog
?- factoriel(3,6)true
?- factoriel(3,Y)Y = 6
41
<!-- Slide number: 42 -->
Donc
Deux différents paradigmes :
Principalement :
Programmation impérative
Procédurale (C, Fortran, …)
Objet (Java, C++, C#, …)
Programmation déclarative
Fonctionnelle (Haskell, … )
Logique (Prolog, …)
Et bien d'autres...
42
<!-- Slide number: 43 -->
Programmation impérative
Procédurale
Fonctions
Structures
… et c'est tout
Objet
Classes
Méthodes
Fonctions libres
→ On modifie des variables, tout le temps !
→ On spécifie chaque instruction !
Publicité
43
<!-- Slide number: 44 -->
Programmation déclarative
Fonctionnelle
Fonctions, fonctions, fonctions
Facilités pour les faire interagir
Pas d'instructions, que des expressions
Logique
Prédicats, prédicats, prédicats
Moteur d'inférence logique
44
<!-- Slide number: 45 -->
Qu’est ce qu’un langage fonctionnel ?
Plusieurs avis, pas de définition précise, mais (en gros) :
La programmation fonctionnelle est un
style de programmation
où l’étape élémentaire du calcul est
l’application d’une fonction à ses arguments
Un langage est fonctionnel s’il supporte et encourage ce style fonctionnel
45
<!-- Slide number: 46 -->
Exemple
Sommation des entiers de 1 à 5 en Java :
total = 0;
for (i = 1; i <= 5; ++i)
total = total+i;
Le calcul repose sur :
l’affectation des variables
les boucles
46
<!-- Slide number: 47 -->
Exemple
La fonction somme en Haskell :
somme :: [Int] -> Int
somme [] = 0
somme (x:xs) = x + somme xs
Sommation des entiers de 1 à 5 en Haskell :
1 + 2 + somme (3:4:5:[]) =
1 + 2 + 3 + somme (4:5:[]) =
1 + 2 + 3 + 4 + somme (5:[]) =
1 + 2 + 3 + 4 + 5 + somme [] =
1 + 2 + 3 + 4 + 5 + 0 =
15
47
<!-- Slide number: 48 -->
La méthode de calcul repose sur :
l’application d’une fonction à ses arguments
la récursion
l’évaluation d’une expression vers une valeur
48
<!-- Slide number: 49 -->
Essence de la PF
On peut définir, mélanger, composer […] des fonctions
wc_linenb filename = length . lines . readFile filename add_n_to_list n list = map (\x → x+n) list
Selon les langages, on peut définir des types de données algébriques
data Direction = Up | Down | Left | Right data Number = Positive Int | Zero | Negative Int
49
<!-- Slide number: 50 -->
On peut se servir de ces types efficacement :
pattern matching
is_positive (Positive n) = True
is_positive (Zero) = True
is_positive (Negative n) = False
On a les clôtures (transparence référentielle) :
x = 4
f y = x+y – c'est une fonction
x = 5
f 1 – on appelle la fonction
cela retourne … 5, et pas 6
50
<!-- Slide number: 51 -->
Essence de la PF
Finie la gestion de la mémoire
On applique des fonctions plutôt que de modifier des variables
51
<!-- Slide number: 52 -->
V- Intelligence Artificielle et PF
Dès la fin des années 50
→ un certain nombre d'équipes ont mené des recherches importantes dans le domaine baptisé communément Intelligence Artificielle (IA)
-(en particulier des programmes de démonstration automatique ; des programmes de jeu, etc... )
Qu'est-ce que l'IA ?
- C'est de faire faire par une machine des choses qui nous paraissent relever de l'Intelligence humaine
52
<!-- Slide number: 53 -->
Une des particularités de la programmation en IA est la nécessité de manipuler facilement des symboles et des listes de symboles
plutôt que des nombres ou des chaînes de caractères :
→ ce qu'on appelle la Programmation Symbolique
53
<!-- Slide number: 54 -->
Les langages de l'époque n'offrant pas ce genre de facilités
Publicité
→ un chercheur du MIT, John MacCarthy s'est lancé vers 56-58 dans la définition d'un langage ad hoc baptisé LISP
(LISt Processing language)
54
<!-- Slide number: 55 -->
Depuis LISP 1.5 (la première version largement diffusée)
plusieurs centaines d'implémentations de «dialectes Lisp» ont été développées
en effet l'écriture d'un interpréteur LISP n'est pas un travail énorme (quelques milliers d'instructions)
- comparativement au développement d'un compilateur pour un langage classique (plusieurs dizaines de milliers d'instructions)
→ d'où l'éclosion (années 60-70) de centaines de versions différentes
(presque autant que d'utilisateurs, disent les mauvaises langues !)
55
<!-- Slide number: 56 -->
Ce phénomène est également du au milieu Lispien
les chercheurs en IA étaient de fait d'excellents programmeurs car :
- peu liés par des contraintes extérieures de délais
- dont le travail consistait d'une part à trouver des idées
- d'autre part à les tester en écrivant des programmes prototypes qui seront entièrement réécrits si l'idée s'avère fructueuse
- et finiront au panier dans le cas contraire
(le plus fréquent)
56
<!-- Slide number: 57 -->
VI- Langages de PF
57
<!-- Slide number: 58 -->
la famille Lisp
L'engouement pour l'IA a favorisé la tendance à la standardisation du langage LISP
Il est évidemment plus économique de disposer du même langage sur toutes les machines sur lesquelles on désire porter un logiciel commercial
Parmi les LISP citons :
MACLISP développé au MIT pour la réalisation du système MACSYMA (calcul formel)
58
<!-- Slide number: 59 -->
FRANZ LISP qui, bien qu'écrit en C par des étudiants (Berkeley), fonctionne malgré tout sur la plupart des systèmes UNIX
LE_LISP développé à l'INRIA par Jérôme CHAILLOUX
59
<!-- Slide number: 60 -->
COMMON LISP, qui est (comme son nom l'indique) une proposition de standard d'origine américaine
Et enfin SCHEME, version modernisée et plus «propre» de ce langage
Il est à noter que certains logiciels (par exemple l'éditeur de textes Emacs, ou logiciel de CAO AutoCad) contiennent un petit interpréteur Lisp
- qui permet à l'utilisateur d'écrire des programmes qui étendent les possibilités de base du logiciel
Lisp → vieux, puissant mais laborieux,
communauté assez restreinte
60
<!-- Slide number: 61 -->
D’autres Langages
Langages de PF populaires :
Objective Caml : pas tellement vieux, rapide, autorise l'impératif, communauté correcte, nombre respectable d'outils & bibliothèques
Haskell : pas très vieux, purement fonctionnel, communauté hyperactive, énormément d'outils & bibliothèques !
Erlang, Clojure, Scheme, F#, …
→ généralement opensource, comités pour l'évolution, projets communautaires, ...
61
<!-- Slide number: 62 -->
#
XSLT (dédié au traitement XML)
Rebol
ISWIM
FP
ML
CAM (Camel, OCamel, …)
Hope
…
62
<!-- Slide number: 63 -->
Et dans la pratique …?
Souvent interpréteur intéractif (Ocaml, Haskell notamment)
Souvent compilateur vers bytecode, donc avec une VM – souvent munie d'un garbage collector
Quelques compilateurs vers du code natif pour les performances
Souvent une Foreign Function Interface pour appeler des fonctions C depuis le langage directement
63
<!-- Slide number: 64 -->
Et dans la pratique … ?
Soit statiquement typé (OCaml, Haskell), soit dynamiquement typé (Lisp, Scheme)
On fait ressortir autant de choses que possible dans les types (Maybe, …)
Les types sont généralement inférés automatiquement
Une fois que le code est testé, chances infimes que “cela plante en route”
La récursion remplace les boucles classiques
(for, while & co), et l'on a des primitives de récursions (“schémas” de récursion qui permettent presque de tout faire)
64
<!-- Slide number: 65 -->
Avantages
Le compilateur en PF facilite beaucoup le travail
Une fois la compilation passée, peu de risques de disfonctionnement
Un programme fonctionnel est presque un ensemble de phrases, on exprime ce qu'on veut et pas chaque étape → plus proche des langues humaines
Limiter voire interdire les effets de bord limite les surprises à l'exécution : 2 appels avec les mêmes arguments renvoient la même chose
→ et bien d'autres avec le temps...
65
<!-- Slide number: 66 -->
Inconvénients
Très (très très très) différent des langages impératifs, qui sont les plus utilisés & connus
Des fois, les effets de bord, ça aide …
Manque de bibliothèques / outils pour “rivaliser” avec des grosses technos (Java, .NET, etc)
Trop peu de boîtes qui utilisent les langages fonctionnels (même si dedans il y a Intel, MS, IBM, des boîtes de finances, l'aéronautique, aérospatial, ...)
66