Programmation fonctionnelle Dr.
Michael Luggen, SA 2023
Programmation logique
1
Statistics! (Ice Breaker)
Objectif: Trier par :
Apprendre à se connaître. 1. Trier par la distance à parcourir chaque jour
Une première réflexion sur l'impératif vs. le pour se rendre à l'université. (du plus long au
fonctionnel. plus court, en fonction de la durée).
2. Je pense que je préfère la programmation
logique ou fonctionnelle ?
3. Trier par nom de famille, de A à Z.
2
Programming Paradigms
Imperative Programming
• Procedural
• Object-Oriented
Declarative Programming
• Functional Programming
• Logical Programming
• Mathematical Programming
• Reactive Programming
https://w.wiki/5iv6
Programming Paradigms
Quels languages de programmation connaissez-vous ?
https://padlet.com/padmichael/FALP1
4
Introduction
Enseignant : Dr. Luggen Michael
Assistant : Mattias Dürrmeier
Il s'agit de la deuxième édition du cours après la reprise par Le Peutrec Stephane. Les
diapositives et les séries sont basées sur le travail de Le Peutrec Stephane.
13:15 – 14:15 Suivi du matériel et préparation des questions
14:15 – 16:15 Cours frontal
16:15 – 17:15 Session d'exercices
Cours et séries accessibles et dépôt de vos travaux sur Moodle
raccourci : https://xr.si/f/278008
clé: FALP
5
Introduction
• Cours en 2 parties
• 1ère partie :
Programmation fonctionnelle
Introduction à Haskell
• 2ème partie :
Programmation logique
Introduction à Prolog
6
Motivations
Quelles sont vos attentes vis-à-vis de ce cours ?
https://padlet.com/padmichael/FALP2
Comment s'est passé le triage au début du cours.?
7
Programmation fonctionnelle
λ
8
Introduction
• Paradigme de programmation basé sur le concept de fonction (fonction mathématique).
• Une fonction est une « boîte noire » ayant des arguments en entrée et qui retourne un
résultat en sortie en se basant uniquement sur ses arguments.
v1
… fonction Résultat
vn
• Programmer avec un langage fonctionnel : composition de fonctions.
fct1
fct4
fct2
fct6
fct3 fct5
9
Langage fonctionnel versus langage impératif
• Langage impératif :
• Concept de base : Instruction.
• On décrit des changements d’état de la mémoire : affectation, pointeur
• Programme : séquence d’instructions
• Langage fonctionnel :
• Concept de base : fonction
• On définit des fonctions et on les compose entre elles
• Programme : ensemble de définitions de fonctions
10
Historique
LISP acronyme de « LISt Processing »
1958 : Création de Lisp 1.5 par John Mac Carthy
Conçu à l’origine pour disposer d’un système de calcul formel s’inspirant du modèle
mathématique : Lambda Calcul.
Au lieu de manipuler des valeurs numériques, le lambda calcul permet de faire du
calcul avec des valeurs littérales.
⇒ Lisp est dédié au calcul symbolique
⇒ Turing Complete
11
Historique
Nombreux autres langages inspirés et dérivés du LISP
• Langages fonctionnels purs : n’intègrent pas de programmation impérative
• Langages fonctionnels impurs : intègrent les principes de la programmation impérative
Quelques exemples :
Scheme (1975) fonctionnel impur, typage dynamique
Common Lisp (1984) fonctionnel impur, objet, typage dynamique
ML (1973) fonctionnel, impératif, typage statique
HasKell (1987) fonctionnel pur, typage statique
Erlang (2003) fonctionnel, concurrent, distribué, typage dynamique
F# (2002) fonctionnel, impératif et objet typage statique
Scala (2003) fonctionnel, objet, typage statique
12
Caractéristiques
Caractéristiques les plus fréquentes des langages fonctionnels
• Pas d’affectation
• Tout est fonction (pas d’instruction)
• Transparence référentielle
• Langages interprétés (et aussi compilés)
• Calcul symbolique, expression symbolique : uniformisation des données et du code
• Structure de données récursive : liste intégrée au langage
• Exploite largement la récursivité (fonctions récursives)
• Récursivité terminale (certains langages intègrent des mécanismes pour gérer efficacement la récursivité
terminale, ex: Scheme, Haskell)
• Fonctions d’ordre supérieur
• Fonctions anonymes
• Gestion dynamique et automatique de la mémoire et ramasse miettes
13
Transparence référentielle
• Principe : le résultat d’une fonction est toujours le même à chaque appel ayant en arguments des
expressions de valeurs égales.
• Exemple : pour toute fonction f les appels suivants retournent les mêmes résultats,
f(v) = f(v-1+1) = f(2 + v – 5 + 3) = …
• Exemple d’une fonction en C ne respectant pas la transparence référentielle
int n = 2;
int inc(int k) {
n = n + k;
return n;
}
pas de transparence référentielle car inc(1) + inc(1) différent de 2 * inc(1)
• Propriété importante pour la maintenance et la parallélisation d’un programme.
14
Haskell
15
Introduction 1/2
• Fonctionnel pur
• Evaluation paresseuse (Lazy evaluation)
• Soit doubleElts(l) une fonction qui multiplie par deux chaque élément de la liste l
• L’évaluation paresseuse fait en sorte que l'appel
doubleElts(doubleElts(doubleElts(L)))
génère un seul parcours de la liste L et non trois.
• Typé statiquement
• Inférence de type
16
Introduction 2/2
Quelques types de base : Int, Integer, Float, Double, Bool, Char, String
Exemples : 3, 3.4, True, False, ‘a‘, ‘‘ toto ‘‘
Opérateurs arithmétiques ^ * / + -
Opérateurs booléens : not && ||
égalité/inégalité : == /=
Notes :
• Opérateurs sont des fonctions
• Integer n'est pas borné
• String sont des listes de Char (vu dans cours suivant)
• précédence habituelle des opérateurs arithmétiques
• précédence habituelle des opérateurs booléen
17
Introduction aux fonctions 1/5
Fonctions sont pour la plupart préfixes
Syntaxe des appels <nom fct> <param1> <param2> ... <paramn>
min 2 3
Fonctions des opérateurs usuels sont infixes
Syntaxe <param1> <nom fct> <param2>
2 + 3
18
Introduction aux fonctions 2/5
Fonctions préfixes prioritaires sur fonctions infixes
succ 9 * 10 retourne 100
succ (9 * 10) retourne 91
max 2 3 + 5 est égale à (max 2 3) + 5
et non à max 2 ( 3 + 5)
max 3 max 5 2 est incorrect,
solution : max 3 (max 5 2)
Fonctions préfixes à deux paramètres ont une forme infixe
Syntaxe infixe : <param1> `<nom fct>` <param2>
2 `max` 8
19
Introduction aux fonctions 3/5
Déclaration de fonctions
<nom fct> <nom param1> … <nom param n> = <expression>
Notes :
• lors d'un appel, le résultat de la fonction est le résultat de l'expression
• nom de fonction : commence par une minuscule
Exemples:
doubleMe x = x + x
bidon y = doubleMe y
20
Introduction aux fonctions 4/5
Entête de fonction :
• But : préciser les types des arguments et du résultat
• Entête est facultative car l'inférence de type détermine les types
:t doubleMe retourne doubleMe Num a => a -> a
a désigne un type variable
Num a est une contrainte de classe signifie que a doit être un nombre :
Int, Integer, Float, Double
21
Introduction aux fonctions 5/5
Syntaxe entête
(version simple : sans variables de type et sans contrainte de classe)
<nom fct> :: paramètres et résultat séparés par ->
doubleMe :: Int -> Int
doubleMe x = x + x
Cette fonction ne peut être utilisée qu'avec des entiers
en arguments
cercleCircumference :: Float -> Float
cercleCircumference r = 2 * pi * r
22
Conditionnelle
Syntaxe
if <expression booléenne>
then <expression1>
else <expression2>
• if est une expression, si <expression booléenne> est évaluée à vrai alors le
résultat de la condition est le résultat de <expression1> sinon le résultat est le
résultat de <expression2>.
• else est obligatoire
myMax :: Int -> Int -> Int
myMax x y = if x > y
then x
else y
23
Garde 1/3
Utilisée pour implémenter une fonction, évite les if imbriqués
syntaxe :
<nom fonction> <paramètres>
| <expression booléenne 1> = <expression 1>
...
| <expression booléenne n> = <expression n>
[ | otherwise = <résultat> ]
L’interprétation de la fonction est le résultat de l’expression associée à la première
expression booléenne satisfaite.
Notes : | doivent être alignées
attention à l’ordre des gardes
24
Garde 2/3
resultIMC :: Float -> String
resultIMC imc
| imc <= 18.5 = "votre poids est faible"
| imc <= 25.0 = "votre poids est normal"
| imc <= 30 = "vous êtes en surpoids"
| otherwise = "votre poids est trop élevé"
resultIMC :: Float -> Float -> String
resultIMC weight height
| weight / height ^2 <= 18.5 = "votre poids est faible"
| weight / height ^2 <= 25.0 = "votre poids est normal"
| weight / height ^2 <= 30 = "vous êtes en surpoids"
| otherwise = "votre poids est trop élevé"
25
Garde 3/3
myMax :: Int -> Int -> Int
myMax x y
| x > y = x
| otherwise = y
26
Where 1/ 2
permet de lier des valeurs ou des fonctions à des symboles et de les utiliser dans les
gardes ou dans le corps de la fonction
Syntaxe
<nom fonction> <paramètres>
| <garde 1> = <résultat 1>
...
where <v1> = <expression1>
<v2> = <expression 2>
...
27
Where 2/2
resultIMC :: Float -> Float -> String
resultIMC weight height
| imc <= 18.5 = "votre poids est faible"
| imc <= 25.0 = "votre poids est normal"
| imc <= 30 = "vous êtes en surpoids"
| otherwise = "votre poids est trop élevé"
where imc = weight / height ^2
28
