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