43 - Paradigmes de programmation

⏪

⏬

⏩

1 - Paradigme

2 - Impératif

3 - Objet

4 - Fonctionnel

5 - FAQ

Nous allons voir qu'il existe différentes façons de concevoir un langage de programmation. Vous pourrez distinguer trois manières de programmer :

La programmation impérative
La programmation objet
La programmation fonctionnelle

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ...

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

MODE COURS (cacher les questions)

1 - Paradigme

⇩ ⇧ ⤊

Paradigme

Le mot paradigme représente la façon dont on se représente le fonctionnement du monde. Pour avoir une telle vision du monde, le paradigme s'appuie sur des fondements définis par un modèle, qu'il soit scientifique, philosophique ou même religieux.

Bien entendu, les découvertes scientifiques ont fait évoluer ou disparaître certains paradigmes purement philosophiques ou religieux. On notera par exemple l'ancien paradigme aristotélicien qui plaçait la Terre au centre de l'Univers (un géocentrisme stable et un ordre immuable des éléments) qui a disparu suite aux idées de Galilée et des travaux de Copernic notamment. Le paradigme qui l'a remplacé est basé sur une approche modélisatrice copernicienne de l'Univers, proposant d'adopter l'héliocentrisme et les mouvements satellitaires.

Paradigme de programmation

L'informatique n'explique pas comment fonctionne le monde, mais elle peut être utilisée pour modéliser le monde. Du moins, au moins, un petit problème à la fois !

Un paradigme de programmation explique donc les grands principes qu'on veut voir appliquer dans le programme. Il s'agit bien également d'une sorte de philosophie, mais une philosophie de conception.

Un paradigme de programmation est la façon de formuler et traiter les problèmes.

La plupart des langages permettent d'utiliser plusieurs paradigmes de programmation, tout en en mettant souvent un en avant.

2 - Paradigme impératif

⇩ ⇧ ⤊

Paradigme impératif

Idée générale

Ce paradigme est le premier que vous ayez rencontré en NSI : la résolution du problème est basée sur l'exécution progressive d'une suite d'instructions qui vont modifier l'état des variables du programme.

Grands principes

Les principes importants du paradigme impératif sont :

la séquentialité (séquence d'instructions à suivre)
l'affectation et les variations d'états (on peut affecter des valeurs aux variables et faire varier cet état)
les opérations de branchements (dont parfois le goto, voir plus bas) qui permettent de réaliser :

Optionnel : les instructions conditionnelles (if-elif-else ou if-else if-else ou même juste if)
Optionnel : les boucles bornées et non bornées (for, while, do ... while)
Optionnel : la déclaration et l'appel de fonction

Exemple n°1 Impératif

# Initialisation des variables définissant l'état au début
 
vie_a = 400
force_a = 60
resistance_a = 63
nom_a = "Alice"
 
vie_b = 300
force_b = 70
resistance_b = 54
nom_b = "Bob"
 
# Evolution séquentielle des états des variables
 
while vie_a > 0 and vie_b > 0:
    vie_a = vie_a - force_b + resistance_a
    vie_b = vie_b - force_a + resistance_b
 
# Résolution du problème une fois l'état final atteint
 
if vie_a > 0:
    gagnant = 1
elif vie_b > 0:
    gagnant = 2
else:
    gagnant = 0
 
# Affichage du résultat (ou inscription dans un fichier ou autre)
 
if gagnant == 0:
    print("Aucun gagnant : les deux combattants sont ko")
elif gagnant == 1:
    print(f"{nom_a} a gagné et il lui reste {vie_a} PV")
else:
    print(f"{nom_b} a gagné et il lui reste {vie_b} PV")

Le fameux GOTO

On remarquera que le langage machine, et donc l'assembleur qui est une traduction des mots-machines en chaînes de caractères, sont basés sur ce paradigme dans la quasi totalité des cas. Ils comportent d'ailleurs des opérations de branchements dont le JUMP/GOTO direct : le goto qui permet de continuer l'exécution du programme en sautant à une ligne particulière.

Le JUMP est toujours présent en langage-machine mais certains langages empêchent l'utilisation directe du JUMP via un goto. Par contre, lorsqu'on tape une instruction conditionnelle ou une boucle, cela utilise en sous-main des JUMPs. Revoir l'activité M999 au besoin.

Voici un exemple de programme utilisant un Python imaginaire intégrant ce principe de goto :

Exemple n°2

# Initialisation des variables définissant l'état au début
 
vie_a = 400
force_a = 60
resistance_a = 63
nom_a = "Alice"
 
vie_b = 300
force_b = 70
resistance_b = 54
nom_b = "Bob"
 
# Evolution séquentielle des états des variables
 
if vie_a <= 0 or vie_b <= 0:
    goto 23
vie_a = vie_a - force_b + resistance_a
vie_b = vie_b - force_a + resistance_b
goto 15
 
# Résolution du problème une fois l'état final atteint
 
if vie_a > 0:
    gagnant = 1
elif vie_b > 0:
    gagnant = 2
else:
    gagnant = 0
 
# Affichage du résultat (ou inscription dans un fichier ou autre)
 
if gagnant == 0:
    print("Aucun gagnant : les deux combattants sont ko")
elif gagnant == 1:
    print(f"{nom_a} a gagné et il lui reste {vie_a} PV")
else:
    print(f"{nom_b} a gagné et il lui reste {vie_b} PV")

On voit que le test de la ligne 15 permet de savoir si on exécute celui de la ligne 16. Et que fait-on en ligne 16 ? On impose de partir en ligne 22... Sinon, on continue le déroulement normal et on rencontrera à un moment le goto imposant de repartir en ligne 15 !

Il s'agit donc bien qu'une boucle TANT QUE réalisée avec un branchement goto.

Pourquoi faire disparaître goto ?

Si on insérait une nouvelle ligne, il fallait changer toutes les valeurs associées à un goto !
La lecture du programme n'est vraiment pas facilité
il est difficile de prouver la correction d'un programme comportant des sauts.

Historiquement, les premières versions de FORTRAN ou le langage BASIC en contiennent.

Le langage C et C++ permettent de faire des gotos mais en version améliorée : on ne désigne pas la ligne par un numéro de ligne mais par un label, une étiquette.

Un "équivalent" en pseudo-code Python donnerait ceci :

# Initialisation des variables définissant l'état au début
 
vie_a = 400
force_a = 60
resistance_a = 63
nom_a = "Alice"
 
vie_b = 300
force_b = 70
resistance_b = 54
nom_b = "Bob"
 
# Evolution séquentielle des états des variables
 
DEPART: if vie_a <= 0 or vie_b <= 0:
    goto SORTIE
vie_a = vie_a - force_b + resistance_a
vie_b = vie_b - force_a + resistance_b
goto DEPART
 
# Résolution du problème une fois l'état final atteint
 
SORTIE: if vie_a > 0:
    gagnant = 1
elif vie_b > 0:
    gagnant = 2
else:
    gagnant = 0
 
# Affichage du résultat (ou inscription dans un fichier ou autre)
 
if gagnant == 0:
    print("Aucun gagnant : les deux combattants sont ko")
elif gagnant == 1:
    print(f"{nom_a} a gagné et il lui reste {vie_a} PV")
else:
    print(f"{nom_b} a gagné et il lui reste {vie_b} PV")

Evolutions

Il existe de nombreuses évolutions depuis le paradigme impératif de base. Vous n'avez pas à connaître leurs noms ou la classification exacte, je ne les propose ici qu'au titre de l'histoire de l'informatique :

Sans goto : il s'agit du paradigme itératif avec comme restriction de ne pas utiliser de goto de façon à rendre la lecture du code simple et plus structurée : on a donc besoin des boucles et des instructions conditionnelles.
Avec des routines : on encapsule les tâches dans des routines-procédures-fonctions ne dépassant 50-60 lignes par exemple.
Avec des modules : on encapsule encore plus les tâches en le plaçant cette fois dans des fichiers séparés.

Ces évolutions ne sont pas propres à ce paradigme et on retrouvera des choses similaires dans les deux autres paradigmes que nous allons rencontrer aujourd'hui.

01° Etudier le code suivant puis répondre aux questions :

ta est-elle une variable globale ou locale ?
tb est-elle une variable globale ou locale ?
tc est-elle une variable globale ou locale ?
En Python, quelle va être la différence entre les lignes 4 et 5 ?
quel va être le contenu du tableau ta après l'appel de la fonction ?

def mystere():
    """Agit (ou pas ?) sur le tableau-paramètre p reçu"""
 
    tb = [v for v in ta]
    tc = ta
    tb[0] = 100
    tc[1] = 200
 
 
ta = [10, 20, 30]
mystere()

Correction ?

...CORRECTION...

ta est-elle une variable globale ou locale ? Globale, son espace des noms est le programme principal (le "main")
tb est-elle une variable globale ou locale ? Locale, elle n'appartient qu'à l'espace des noms de la fonction
tc est-elle une variable globale ou locale ? Locale, elle n'appartient qu'à l'espace des noms de la fonction
En Python, quel va être la différence entre les lignes 4 et 5 ?

Ligne 4 : on crée une copie du tableau - on obtient deux espaces-mémoires qui vont contenir la même chose.
Ligne 5 : on crée juste un alias - on obtient deux variables qui pointent vers la même zone mémoire.

quel va être le contenu du tableau ta après l'appel de la fonction ? Puisque tc réference la même zone mémoire que ta, lorsque modifie la case numéro 1 en ligne 7, on modifie directement le tableau auquel ta fait référence. Du coup, la variable ta fait référence à [10, 200, 30] après le passage de cette ligne.

02° Comment se nomme l'effet qui permet de modifier le tableau ta ?

Expliquer le phénomène en utilisant les mots variables, alias et zone mémoire.

Correction ?

...CORRECTION...

Il s'agit de l'effet de bord.

Ce phénomène apparaît lorsque deux variables sont simplement des alias vers la même zone-mémoire : si on modifie la zone mémoire, on "modifie" nécessairement les deux variables puisque les deux références les mêmes cases.

On peut donc modifier une même zone mémoire en utilisant plus alias référençant la même zone. Ca peut être pratique. Ou pas.

03° Que devrait afficher ce programme ?

Attention : en Python, l'évaluation du range de la boucle ne se fait qu'au départ.

a = ["A", "B", "C"]
b = a
c = b
 
for i in range(len(a)):
    c.append(a[i])
    print(a)

Correction ?

...CORRECTION...

Les variables a, b et c sont trois alias vers une même zone mémoire.

Agir sur c revient donc à agir sur a.

Rajouter des éléments à c revient donc à rajouter des éléments à a... : elles désignent le même tableau.

C'est comme si on avait écrit ceci :

a = ["A", "B", "C"]

for i in range(3):
    a.append(a[i])
    print(a)


['A', 'B', 'C', 'A']
['A', 'B', 'C', 'A', 'B']
['A', 'B', 'C', 'A', 'B', 'C']

Nous avons vu qu'on pouvait remplacer un for par un while et inversement. Regardons :

04° Que devrait afficher ce programme ?

Attention : ici, il n'y a pas de range mais une simple fonction native len qui sera donc évaluée à chaque tour de boucle...

a = ["A", "B", "C"]
b = a
c = a
 
i = 0
while i < len(a) and i < 60:
    c.append(a[i])
    print(a)
    i = i + 1

Correction ?

...CORRECTION...

Les variables a, b et c sont trois alias vers une même zone mémoire.

Agir sur c revient donc à agir sur a.

On va donc rajouter l'élément 0 de a à a qui va donc en avoir 4.

On rajoute l'élément 1 de a à la fin de a : il en a maintenant 5...

Cette fois, la boucle serait une boucle infinie si nous n'avions pas pris nos précautions en imposant un nombre maximum de 60 éléments.


['A', 'B', 'C', 'A']
['A', 'B', 'C', 'A', 'B']
['A', 'B', 'C', 'A', 'B', 'C']

Effets de bord

Les effets de bord sont donc les modifications d'une même zone mémoire référencée par plusieurs variables, qu'on nommera des alias.

Avantage : comme on ne transfère que l'adresse ou la référence, il n'est pas plus compliqué de "transférer" un tableau de 1 millions d'éléments à une fonction qu'un tableau de 10 éléments.

Désavantage : on peut finir par modifier quelque chose qu'on ne voulait pas vraiment modifier !

Conséquence : il faut indiquer dans la documentation de vos fonctions lorsqu'il y a modification d'un paramètre par effet de bord.

C'est pour cela que nous avions vu en 1er deux façons de créer des fonctions gérant les tableaux :

Pour modifier un tableau par effet de bord depuis une fonction

Une seule façon de faire : l'accès via l'index.

def modifier(tableau):
    for index in range( len(tableau) ):
        tableau[index] = tableau[index] ** 2
 
notes = [15, 18, 8, 10, 12, 15, 20, 5, 12, 17, 12, 10, 18, 4]
modifier(notes)

Pour renvoyer un nouveau tableau basé sur un tableau-paramètre depuis une fonction

Deux façons : toujours l'index ou alors on modifie directement le tableau par compréhension.

Créer une copie du tableau initial
Modifier la copie en utilisant les index
Renvoyer la copie (et la stocker dans une variable !)

def copier_et_modifier_la_copie(tableau):
    copie = [valeur for valeur in tableau]
    for index in range( len(copie) ):
        copie[index] = copie[index] * 2
    return copie
 
notes = [15, 18, 8, 10, 12, 15, 20, 5, 12, 17, 12, 10, 18, 4]
nouvelles_notes = copier_et_modifier_la_copie(notes)

def copier_et_modifier_la_copie(tableau):
    return [valeur * 2 for valeur in tableau]
 
notes = [15, 18, 8, 10, 12, 15, 20, 5, 12, 17, 12, 10, 18, 4]
nouvelles_notes = copier_et_modifier_la_copie(notes)

Dernier exemple qui vous permettra de voir qu(il existe parfois des effets de bord non désirés.

05° Mettre le programme en mémoire puis utiliser les instructions consoles fournies. Que va afficher la dernière commande ?

entrees = ['tarte au saumon', 'crudités']
plats = ['steak frites', 'ratatouille']
menus = [entrees, plats]
 
entrees2 = entrees
plats2 = ['Pates aux épinards', 'Gratin de brocolis']
menus2 = [entrees2, plats2]


>>> menus
[['tarte au saumon', 'crudités'], ['steak frites', 'ratatouille']]
 
>>> menus2
[['tarte au saumon', 'crudités'], ['Pates aux épinards', 'Gratin de brocolis']]
 
>>> menus2[0].append('Oeufs mayo')
>>> menus2
[['tarte au saumon', 'crudités', 'Oeufs mayo'], ['Pates aux épinards', 'Gratin de brocolis']]
 
>>> menus
???

Correction ?

...CORRECTION...

On a modifié le contenu de menus en modifiant le contenu de menu2 !


>>> menus
[['tarte au saumon', 'crudités', 'Oeufs mayo'], ['steak frites', 'ratatouille']]

On a ici le cas d'un tableau de tableaux. Nos menus ne contiennent en réalité par les tableaux mais juste les références-mémoire vers les vrais tableaux.

Conclusion : il faut faire très attention aux copies lorsqu'on utilise un langage qui utilise un paradigme impératif : beaucoup d'objets sont des objets muables et en faire des "copies" avec une simple affectation ne permet que de recopier la référence-mémoire !

Copie d'objets muables avec Python

1 - Copie superficielle

On crée bien deux références mémoires différentes mais par contre, les contenus sont les mêmes. Du coup, si le contenu est un objet muable, on modifie aussi le contenu de l'autre variable !


>>> a = [10, [20], 30]
>>> b = [e for e in a]
>>> b[0] = 100
>>> b[1][0] = 200
>>> b
[100, [200], 30]
 
>>> a
[10, [200], 30]

Il existe aussi une méthode qui permet de faire pareil, mais bon, autant utiliser l'affectation dans ce cas.


>>> a = [10, [20], 30]
>>> b = a.copy()
>>> b[0] = 100
>>> b[1][0] = 200
>>> b
[100, [200], 30]
 
>>> a
[10, [200], 30]

2 - Copie profonde

Cette fois, on copie par récurrence tous les contenus en tant que nouveau contenu.

Cette fois, on peut utiliser une méthode Python assez pratique qui se nomme deepcopy. Ou on le code directement, à la main.


>>> import copy
>>> a = [10, [20], 30]
>>> b = copy.deepcopy(a)
>>> b
[10, [20], 30]
 
>>> b[0] = 100
>>> b[1][0] = 200
>>> b
[100, [200], 30]
 
>>> a
[10, [20], 30]

En conclusion : la programmation itérative est simple à prendre en main, mais il faut faire attention aux effets de bords indésirables.

3 - Programmation Orientée Objet (POO)

⇩ ⇧ ⤊

L'une des évolutions pour contrer (un peu) ces effets de bords problématiques est la programmation orientée objet ou POO.

J'ai noté un peu car la POO est basée sur les effets de bord. Le but n'est pas de les éviter mais juste de bien les gérer.

Paradigme objet

Idée générale

On ne crée pas un programme principal et des fonctions effectuant les tâches qu'on doit effectuer : on gère juste les interactions entre des objets qui possèdent :

leurs variables : les attributs
leurs fonctions : les méthodes

Les grands principes : encapsulation et notion de public/privée

Pour garantir le bon fonctionnement de l'objet alors qu'il fourmille d'effets de bords, on travaille sur l'encapsulation des objets et en considérant les données comme privées :

seul l'objet peut modifier directement ses attributs qui sont donc privés.
de l'extérieur, on doit utiliser des méthodes d'interface publiques pour modifier les attributs
ces méthodes d'interface vérifient les données à modifier avant d'appliquer les modifications : l'effet de bord existe toujours mais on surveille de près les changements venant de l'extérieur à travers ces méthodes.

Exemple Objet

class Personnage:
    """Classe définissant le personnage"""
 
    def __init__(self, nom:str, pv:int, fo:int, re:int):
        """Méthode initialisateur ou constructeur"""
        self.nom = nom
        self.vie = pv
        self.force = fo
        self.resistance = re
 
    def subir_degats(self, dgt:int):
        """(privée) Modifie les pv du personnage"""
        if type(dgt) == int and dgt > 0:
            self.vie = self.vie - dgt
        if self.vie < 0:
            self.vie = 0
 
    def combattre(self, adversaire):
        """(privée) Self subit l'assaut de l'adversaire"""
        degats = adversaire.obtenir_force() - self.resistance
        self.subir_degats(degats)
 
    def obtenir_nom(self) -> str:
        """Renvoie le nom du personnage"""
        return self.nom
 
    def obtenir_vie(self) -> int:
        """Renvoie le nombre de vie restante"""
        return self.vie
 
    def obtenir_force(self) -> int:
        """Renvoie la force du personnage"""
        return self.force
 
    def obtenir_resistance(self) -> int:
        """Renvoie la résistance du personnage"""
        return self.resistance
 
    def lancer_combat_avec(self, adversaire) -> str:
        """Lance un combat entre 2 personnages et renvoie le gagnant"""
        while self.obtenir_vie() > 0 and adversaire.obtenir_vie() > 0:
            self.combattre(adversaire)
            adversaire.combattre(self)
        if self.obtenir_vie() > 0:
            return self.nom
        elif adversaire.obtenir_vie() > 0:
            return adversaire.nom
        else:
            return "Aucun gagnant"
 
if __name__ == '__main__':
    a = Personnage("Alice", 400, 60, 63)
    b = Personnage("Bob", 300, 70, 54)


>>> a.lancer_combat_avec(b)
'Alice'

Vous remarquerez que l'un des problèmes de la POO pour les petits programmes est son côté verbeux : même en Python et sans vraiment respecter toutes les règles du paradigme, on a un code très long par rapport au même programme en impératif.

Langages adaptés

Une grande majorité des langages modernes permettent de faire de la POO mais avec une souplesse variable.

Certains imposent l'objet en mode privé-public dès les premières lignes (Java pour exemple, où même le "programme principal" est un objet)

D'autres permettent de faire de l'objet en mode privé-public si on veut (C++ par exemple)

D'autres permettent de travailler avec des objets mais sans permettre le mode privé-public. Python est l'un d'entre eux.

Enfin, certains langages ne permettent pas de faire de la programmation objet. Le C par exemple.

06° Associer le bon vocabulaire aux noms suivants :

Personnage
a
__init__
obtenir_vie
self
force

Correction ?

...CORRECTION...

Personnage -> Classe
a -> objet ou instance
__init__ -> méthode constructeur ou méthode initialisateur
obtenir_vie -> méthode
self -> objet en cours d'utilisation
force -> attribut

07° Expliquer ce que recoivent les deux paramètres self et adversaire de la méthode lacer_combat_avec lorsqu'on lance ceci :


>>> a.lancer_combat_avec(b)
'Alice'

08° Expliquer ensuite rapidement le comportement de cette méthode.

Que faut-il savoir sur la programmation objet pour le BAC alors ?

Très peu de choses en réalité.

Vous devez :

Etre capable de reconnaitre une Classe : le code qui permet de créer les objets
Etre capable de reconnaître un objet : un objet est une instance d'une Classe, une création concrête basée sur la Classe
Etre capable de reconnaitre un attribut : il s'agit d'une variable stockée dans un objet (variable d'instance) ou dans la classe directement (variable de classe)
Etre capable de reconnaitre une méthode : il s'agit d'une fonction stockée dans un objet. Contrairement à une fonction classique, elle a besoin d'au moins un premier paramètre qu'on nomme souvent self : l'instance de l'objet sur lequel elle doit travailler.
Accéder à une méthode : savoir faire appel à une méthode : reference.methode(...), le paramètre self recevant automatiquement reference.
Accéder à un attribut : lire ou modifier un attribut : reference.attribut ou reference.attribut = ...
Savoir définir seul une Classe et donc :

Connaitre la syntaxe de déclaration de la Classe (majuscule pour la première lettre du nom)
Savoir déclarer la méthode constructeur
Savoir déclarer des méthodes

Comprendre les principes généraux et l'intérêt de l'encapsulation mais sans maitrise réelle de ces principes : aucune question sur privée, publique, accesseur, mutateur par exemple. En Python, vous pouvez créer des programmes qui modifient ou lisent les attributs d'un objet sans devoir passer par des méthodes publiques.

4 - Programmation fonctionnelle

⇩ ⇧ ⤊

Nous avons donc vu :

Le paradigme impératif qui permet des sauts dans l'exécution et des effets de bord non surveillés, ce qui rend les preuves de correction parfois délicates à démontrer.
Le paradigme objet qui se base sur les effets de bord, c'est même le coeur de son fonctionnement. Mais il place beaucoup de restrictions lors de la modification des objets. Le système peut être stable mais les démonstrations mathématiques formelles de cette stabilité ne sont pas faciles à réaliser non plus...

Moralité : on voudrait un paradigme qui permette "facilement" de prouver la correction de notre programme. Ce sont visiblement les effets de bord qui posent problème.

Paradigme fonctionnel

Idée générale

Le paradigme fonctionnel est basé intégralement la non-variation de l'état du programme pour fournir sa réponse. Toute "modification d'une valeur" doit passer par un return qui sera géré en conséquence. Conséquence : tout appel à une fonction en fournissant les mêmes arguments, donnera TOUJOURS le même résultat.

Grands principes

Les principes importants du paradigme fonctionnel sont :

Un refus d'utiliser les effets de bord car cela rend la preuve de correction difficile.
l'absence de variables variables : au pire, on utilisera des constantes (en Python, cela revient donc à ne jamais changer le contenu associé à une variable après sa déclaration.
Les fonctions sont toutes des fonctions pures :

Elles ne créent aucun effet de bord
Elles répondent en ne travaillant qu'à partir des paramètres recus et ne vont à aucun moment aller lire une variable globale : toute l'information pour répondre est contenue dans la fonction
Elles se rapprochent donc énormément des fonctions mathématiques, non ?

Les structures de données sont non mutables : si on veut modifier un tableau, il faut créer un nouveau tableau !
du récursif (programmation récursive) plutôt que des boucles (programmation itérative)

Exemple Fonctionnel

# Déclaration des fonctions
 
def nv_pv(df:tuple, at:tuple) -> int:
    """Calcule le pv du défenseur df après attaque de l'attaquant at"""
    return df[0] - max(0, at[1] - df[2])
 
def maj(df:tuple, at:tuple) -> tuple:
    """Renvoie les nouvelle caractéristiques mise à jour du defenseur df après attaque de at"""
    return (nv_pv(df, at), df[1], df[2], df[3])
 
def est_hors_jeu(p):
    """Prédicat qui renvoie True si le personnage p à 0 pv ou moins"""
    return p[0] <= 0
 
def lancer_combat(a:tuple,b:tuple) -> str:
    """Lance le combat entre a et b et renvoie le nom du gagnant ou "Aucun gagnant""""
    if est_hors_jeu(a) or est_hors_jeu(b):  # Condition d'arret et cas de base
        if not est_hors_jeu(a):  # a a gagné car il lui reste des pv
            return a[3]
        elif not est_hors_jeu(b): # b a gagné car il lui reste des pv
            return b[3]
        return "Aucun gagnant"
    else:  # Cas recursif
        return lancer_combat(maj(a,b), maj(b,a))
 
# ETAT DU SYSTEME
# Chaque personne est un tuple (vie-0, force-1, resistance-2, nom-3) 
a = (400, 60, 63, "Alice")
b = (300, 70, 54, "Bob")

Programmation fonctionnelle et récursivité

Il est existe des méthodes de preuve de correction liée à la récursivité (proche des démonstration de récurrence en mathématique).

De plus, la récursivité permet assez naturellement de se passer des boucles et des variables variables.

On retrouve ainsi beaucoup de récurrence dans les programmes basés sur ce paradigme.

Création par compréhension en Python

De la même façon, puisqu'on tente de limiter fortement les variables en fonctionnel, renvoyer un tuple, une liste ou un dictionnaire via une déclaration en compréhension est assez courante/

Mais il y a un FOR dans cette déclaration ! Oui. Sachez qu'il existe des fonctions natives permettant de rapprocher un peu plus Python d'un langage fonctionnel (map, filter et reduce mais elles ne sont pas au programme). Alors, on gardera juste notre déclaration en compréhension.

09° Voici une fonction plus2. S'agit-il d'une version impérative ou fonctionnelle ?

def plus2(t:list) -> None:
    """Modifie t par effet de bord en rajoutant 2 à chaque valeur
 
    :: param t(list) :: le tableau qu'on veut modifier
    :: return(None)  :: fonction-procédure
 
    :: exemple ::
    >>> test = [1, 2, 3]
    >>> plus2_iter(test)
    >>> test
    [3, 4, 5]
 
    """
    for i in range(len(t)):
        t[i] = t[i] + 2

Correction ?

...CORRECTION...

Il s'agit clairement d'une version itérative : on modifie le tableau par effet de bord.

10° Voici une fonction plus2. S'agit-il d'une version impérative ou fonctionnelle ?

def plus2_fonc(t:list) -> list:
    """Renvoie une copie du tableau où toutes les valeurs sont augmentées de 2
 
    :: param t(list) :: le tableau qu'on veut modifier
    :: return(list)  :: la nouvelle version du tableau
 
    :: exemple ::
    >>> plus2_fonc([1, 2, 3])
    [3, 4, 5]
 
    """
    return [v+2 for v in t]

Correction ?

...CORRECTION...

Il s'agit d'une version fonctionnelle : on crée une copie et on renvoie le résultat.

Autre exemple : comment rajouter un élément dans un tableau en Python ? Pour une fois, nous allons regarder d'un peu plus près comme fonctionne Python.

11° Comparer les 3 versions fournies permettant de rajouter un élément dans un tableau Python. Laquelle pourrait correspondre à une version plus ou moins fonctionnelle ? Quelle est encore le gros défaut d'un point de vue fonctionnel ?


>>> a = [4, 8]
>>> id(a)
140030316223048
 
>>> a.append(12)
>>> a
[4, 8, 12]
 
>>> id(a)
140030316223048


>>> a = [4, 8]
>>> id(a)
140030316223304
 
>>> a = a + [12]
>>> a
[4, 8, 12]
 
>>> id(a)
140030316783822


>>> a = [4, 8]
>>> id(a)
140030316223368
 
>>> a += [12]
>>> a
[4, 8, 12]
 
>>> id(a)
140030316223368

Correction ?

...CORRECTION...

La seule version "correcte" pour faire du fonctionnel est la version a = a + [12] : c'est la seule qui modifie bien la référence de la variable : on crée donc un nouveau tableau qui écrase l'ancien.

Mais attention, même cette version ne convient pas : on affecte a à une autre référence, mais on a une affectation néanmoins.

12° Créer la fonction ajouter_elt(t, elt) qui renvoie un nouveau tableau semblable à celui reçu mais en lui rajoutant un nouvel élément.


>>> ajouter_elt([1,2,3], 12)
[1, 2, 3, 12]

Correction ?

...CORRECTION...

1
2

def ajouter_elt(t:list, elt) -> list:
    return t + [elt]

Attention, tout cela est artificiel : les tableaux de Python de type list sont mutables. Donc, on doit faire attention. Avec un langage purement fonctionnel, les structures de données seraient non mutables.

Les tuples de Python permettent beaucoup plus facilement de gérer ce type de demandes.

13° La fonction somme ci-dessous peut-elle être considérée comme fonctionnelle ?

def somme(t:list) -> int:
    if len(t) == 0:
        return 0
    else:
        return t[0] + somme([t[i] for i in range(len(t)) if i > 0])


>>> somme([1,2,3,4])
10

Correction ?

...CORRECTION...

Elle respecte bien le paradigme fonctionnelle :

Pas d'effet de bord
La fonction ne travaille qu'avec ses paramètres
La fonction renvoie constamment le même résultat pour le même appel

Langage fonctionnel

Un langage fonctionnel est un langage de programmation dont la syntaxe et les caractéristiques encouragent la programmation fonctionnelle.

Le premier fût LISP en 1958, ce n'est donc pas neuf...

LISP n'est pas fortement typé.

Les langages fonctionnels récents, comme Haskell (1990), OCaml (1996) ou Scala (2004) sont fortement typés.

Le Logo de OCaml :

Nous avons vu que le principe du codage-décodage de RSA est de calculer une mise à la puissance du message :

mc = (m^e) % n

n se nomme le module de chiffrement car il sert à faire un modulo et
e est l'exposant de chiffrement car on l'utilise en tant que mise à la puissance du message.

md = (mc^d) % n

n se nomme le module de chiffrement car il sert à faire un modulo et
d est l'exposant de déchiffrement car on l'utilise en tant que mise à la puissance du message.

14° Demander à Python de calculer cela (message 15 et exposant 437) :


>>> 15**437

Question : est-ce rapide ?

Correction ?

...CORRECTION...

Oui, c'est assez rapide. Le résultat apparaît tout de suite à l'échelle humaine.


>>> 15**437
8951178286285835053504334637121363496635561744942322831981649499685880630495193742162622726037172054932552041017789554974108750974231796350083483386737588631707451372572071839923611884846146982217961948970974188343920670569488604409502932712044073128843584147870956814158980915052673498934345180446817441904416161488553516020455611352563428830901482795268646403744376800464835118010898211170598580175760537342795125970200615956585889696932345818328232800457021236281194924953863445438173584989272058010101318359375

15° Faire la même chose avec un exposant plus conséquent :


>>> 15**135478415797

Question : est-ce rapide ?

Correction ?

...CORRECTION...

Oui, c'est assez rapide. Le résultat apparaît tout de suite à l'échelle humaine.

Cette fois, ça ne répond pas. En tous cas, pas assez rapidement pour être utilisable !

Comment faire alors ?

Comme d'habitude en informatique, nous allons "tricher" en refléchissant un peu à ce qu'on désire faire.

La méthode que nous allons utiliser se nomme l'exponentiation rapide : nous allons chercher à calculer des mises au carré successives.

En voici le principe :

Calcul normal de 15¹⁴⁰ = 15*15*15*15*...15 : on a donc 139 étapes et multiplications à faire.

Calcul de 15¹⁴⁰ en utilisant une forme d'exponentiation rapide&nbps;: cette fois, nous nous rendons compte de cela :

15¹⁴⁰ = (15²)⁷⁰
Or x⁷⁰ = (x²)³⁵

Notre calcul devient ( (15²)² )³⁵ ou encore ( 15⁴ )³⁵

Or x³⁵ = x * x³⁴ = x * (x²)¹⁷

Notre calcul devient 15⁴ * ( (15⁴)² )¹⁷ ou plus simplement 15⁴ * ( 15⁸ )¹⁷

Or x¹⁷ = x * x¹⁶ = x * (x²)⁸

Notre calcul devient 15⁴ * 15⁸ * ((15⁸)²)⁸ ou plus simplement 15⁴ * 15⁸ * ( 15¹⁶ )⁸

Or x⁸ = (x²)⁴

Notre calcul devient 15⁴ * 15⁸ * ( 15³² )⁴

Or x⁴ = (x²)²

Notre calcul devient 15⁴ * 15⁸ * ( 15⁶⁴ )²

Or x² = (x²)¹

Notre calcul devient 15⁴ * 15⁸ * 15¹²⁸

16° Que vaut le log2 de 140 ?

Correction ?

...CORRECTION...


>>> import math
>>> math.log2(2)
1.0
 
>>> math.log2(4)
2.0
 
>>> math.log2(8)
3.0
 
>>> math.log2(16)
4.0
 
>>> math.log2(32)
5.0
 
>>> math.log2(64)
6.0
 
>>> math.log2(128)
7.0
 
>>> math.log2(256)
8.0
 
>>> math.log2(140)
7.129283016944966

On voit donc qu'en utilisant cette méthode, le coût sera logarithmique et plus linéaire.

17° Créer la fonction exp_rapide qui se base sur ce principe :

Pour cela, répondre à ces questions :

Quelle est la condition d'arrêt et le cas de base ?
Quelles sont les cas récursifs ?
Ecrire votre fonction

def exp_rapide(x:int, n:int) -> int:
    """Permet de calcul rapidement x**n par exponentiation rapide"""
 
    pass

Correction ?

...CORRECTION...

def exp_rapide(x:int, n:int) -> int:
    """Permet de calcul rapidement x**n par exponentiation rapide"""
 
    if n == 1:
        return x
    else:
        if n % 2 == 0:
            return exp_rapide(x**2, n//2)
        else:
            return x * exp_rapide(x**2, n//2)

Bon en réalité, on ne gagnerait pas tant de temps que cela avec Python : l'interpréteur fait déjà beaucoup de choses en arrière plan, notamment des choses comme cela !


>>> exp_rapide(15, 1000000)
18157484464073660739361385102568524158220149848872846937473094084338562416435600258825258927114364712839829341411768452311029550801259916524900246903746519194985897747020245006432814081271944944964627390236954666710145306582011601145129555022325186721853618791672595463912004171293055341938033147384489585694289498265413669724284420949477001977110845859897875368169668416114495714422296461947959977507209937715186439064438131425513901959206795441747019104649609148833199725630876047378156331387001037180808890080716116968436588642510451555643891607257450337087994552240950881199410338261320946885933869043945205267399309758938761768181132819380600243748636479585529858305543412745779370119852657135462147041964832108657853166254330303043380167232806631380820413502768186120887225393677543981648418040350193501156397505591300574834511331696240298331934319251085780560315662176327891203483732254379720710255224027465322890549801666002622259344523039609988586765296270991956661834468803909345745301430799047608302495500558343690693948328129220745764023200277377029952984985103119029840354180928246004868169711967202323511189585031193872604307556558217276333010894347418411896888231717267155445117761313373888921441963525468019987159926340524956786999153787062512693330350238088080020442921724125824990990229224986026621047252275975796495163519032619559938479056192047610795930177066733589611777217692795304485460826580506209644043580875770071488864263212193779100187334028275117826502402970704098423975010571720339143334334270354077192313602371289581218972338447556778213779871466131774583840184268158567427234759570773775512030368686898417212085011291950005236709762568732864429440242131873004926936175433405160491559414830920819506814015893331146200559984442535407970399724436186166298591741472973275358939371486155134349524930098668859475146752929925648450413541296078799713864836196993020452251256159451417237475537449678684230351079512728513948361730340263032012709380021463768853127904493201678946617415613301611947372331896819052751740059501945940243625142353038213297749537740357487832738022463710092570280527410934835331778633526504663658705851066010319534055566679004116652879900944792596178459725873371807341324460560617987425055343539911604750993584473599394401011866262759146777035239516462227960402858604975320764720716676249811016985030867932433212554349936308019154541751222688947510305661407115432428235937815751291184204742297561486400158217472677240328365012721375728341686040559157538021540694187602994952262915557008339051743531205093439095111383845107351416146624706704565702129010242736992031289090583494405881279968513327209404209445987996974868042822235518898477744954677284576728292201624680063243938566756365600869200226212446810248920998271362456852685691823629445510974521633149110954799528137420559306705001813213955078404225387223212742905011804210381146220600256257393432975638679749993723630703950576284858811308993516708791876685261339909967085932227660533552604498120253003055885339296846300778290146591152091041378211836422383650982211646689501084827708389342762046175720484056416769374081620261966749283279708494178503043203104030562495651951358994738602535270672388088087398056139573831460647692907597611719301762430315102604589125089599793406968711468579649964826977919197812689289163504785509444164647159732111762259176103709454433719399810579529191171460710232139689129082378016486801216024009455716567545624298977603153401377551381829741350420623905000223591416771426672830688582952705846295598528323075282403746742106494739391369925221320689574228543107814735088460118421109826985617399470312025828395270460607883685119278299565811950651391464348942828263150833319960179601120300686665284559784335414028205070789322705694223097616478301105679322618672621630720227522272586614206564806188640246031923348639502513883270807116452522264958246287043361083359434418923496966597679618052453979679423732729101363979491102170464898886147424733615995686043665077650657369320996388895767554028097233660522073188833606664857071349735416942282698584836586589148778434382287382258907449201404300079969441924920864351236294398025739411174915089549274809898794335761605402416204765780801371501641420824609952871660997728499855310317646623258126920301425908419399674463396476249351551505562622452673517867163217684020310411542241380411389994030667787977709262571546455573082380931380000584751817797867893195935143427768434197910864089183748850952211209977174639851824207981266862794238539283093863122873271758184675611527085359108742415139230086274251893626645177424348456529223952489891900807105037337878836587844496972978139020991947036551652298475414528419520284081274067614321933876120132648056122818174942501535094828438505717889474274136465452632529835963767298261988466315228990270463805309322257644754176835748685462665251000480667177404982131526704202024134245117530660892641896815217648770012165375085175994728429281605869622756138898611443068554669984664696867161986…

Oui, mais RSA ne demande pas de faire ce calcul : on veut le modulo.

Et là, c'est intéressant : nous allons faire toutes les étapes mais en réalisant le modulo n à chaque étape. Du coup, les nombres à traiter seront bien plus courts.

Ici, on devra donc avoir un paramètre supplémentaire : le module de chiffrement.

18° Créer la fonction exp_rapide propre à RSA : on attend trois paramètres :

def exp_rapide_rsa(m:int, e:int, n:int) -> int:
    """Permet de calcul rapidement m**e %n par exponentiation rapide"""
 
    pass

Correction ?

...CORRECTION...

def exp_rapide_rsa(m:int, e:int, n:int) -> int:
    """Permet de calcul rapidement m**e %n par exponentiation rapide"""
 
    if e == 1:
        return m
    else:
        print(e)
        if e % 2 == 0:
 
            return (exp_rapide_rsa(m**2 % n, e//2, n)) % n
        else:
            return (m * exp_rapide_rsa(m**2 % n, e//2, n)) % n

19° Calculer la transformation de m = 190000 en utilisant les valeurs suivantes

n = 594127815299
e = 135478415797

Correction ?

...CORRECTION...


>>> exp_rapide_rsa(190000,135478415797,594127815299)

135478415797
67739207898
33869603949
16934801974
8467400987
4233700493
2116850246
1058425123
529212561
264606280
132303140
66151570
33075785
16537892
8268946
4134473
2067236
1033618
516809
258404
129202
64601
32300
16150
8075
4037
2018
1009
504
252
126
63
31
15
7
3

262963059740

20° Créer une fonction qui respecte le paradigme fonctionnel et qui permet d'obtenir un tableau dont le contenu est doublé par rapport à un tableau fourni en entrée.

21° Créer une fonction qui modifie le tableau en multipliant les valeurs par deux. Est-encore compatible avec le paradigme fonctionnel ? Justifiez.

22° Expliquer en quoi la fonction maximum respecte bien le paradigme fonctionnelle. Expliquer son fonctionnement.

def maximum(t):
    """Renvoi le maximum du tableau t"""

    if len(t) > 0:
        return trouver_maximum(t, t[0])
 
def trouver_maximum(t, maxi):
    if len(t) == 0:
        return maxi
    else:
        t2 = [t[i] for i in range(len(t)) if i>0]
        if t[0] > maxi:
            return trouver_maximum(t2, t[0])
        else:
            return trouver_maximum(t2, maxi)

23° On considère le programme suivant :

import math
 
def maximum(t):
    """Renvoi le maximum du tableau t"""
 
    if len(t) > 0:
        return trouver_maximum(t, t[0])
 
def trouver_maximum(t, maxi):
    if len(t) == 0:
        return maxi
    else:
        t2 = [t[i] for i in range(len(t)) if i>0]
        if t[0] > maxi:
            return trouver_maximum(t2, t[0])
        else:
            return trouver_maximum(t2, maxi)
 
def maximum_fonction(f, intervalle):
    """Renvoie le maximum d'une fonction sur un ensemble de valeurs entières"""
 
    return maximum([f(x) for x in intervalle])
 
def carre(x):
    return x*x
 
def racine(x):
    return math.sqrt(x)

Quels vont être les types de paramètres de la fonction maximum_fonction lors de cet appel ? Qu'est-ce qui devrait (au moins un peu) vous surprendre ?


>>> maximum_fonction(carre, [x for x in range(1000)])

`19`	`def maximum_fonction(f, intervalle):`

Fonctions-paramètres

On peut donc transmettre la référence d'une fonction (sans ses paramètres donc, juste la référence mémoire du code de la fonction) à une autre fonction.

Les fonctions ne sont finalement que des données comme les autres. Souvenez-vous qu'elles sont de toutes manières stockées dans la même mémoire que les données. Rien d'étrange en réalité.

Il s'agit également de l'un des fondamentaux de la programmation fonctionnelle : le passage de fonctions-paramètres et pas simplement l'appel de fonctions !

Dernière remarque (et hors programme en terme de connaissances pour le DS ou le BAC) : il est parfois pénible de transmettre une fonction à une autre fonction alors qu'on ne veut finalement que l'utiliser une seule fois. Surtout en mode console par exemple.

Il existe heureusement un type de fonction qu'on peut créer à la volée : les fonction lambda

Si cela vous intéresse, direction la FAQ ci-dessous, sinon, c'est fini !

5 - FAQ

⇩ ⇧ ⤊

J'ai entendu parler des lambda-fonctions. C'est quoi ?

Contrairement aux fonctions normales, elles ne portent pas de nom et on ne les déclare pas avec def mais avec ... lambda.

Si on veut créer une fonction identité x → x à la volée : lambda x: x

Si on veut créer une fonction carrée x → x² à la volée : lambda x: x**2

Si on veut créer une fonction racine carrée x → x² à la volée : lambda x: math.sqrt(x)

Du coup, on peut faire des appels à notre fonction maximum_fonction de cette façon :


>>> maximum_fonction(lambda x: x, [x for x in range(1000)])
999
 
>>> maximum_fonction(lambda x: x*x, [x for x in range(1000)])
998001
 
>>> maximum_fonction(lambda x: x**2 - 300*x, [x for x in range(1000)])
698301

Programmation itérative et impérative, c'est pareil ?

Lorsque le paradigme impératif a évolué en mettant de côté le goto, remplacé par des for et des while, on a parlé de programmation itérative.

Pendant longtemps, la plupart des langages basés sur le paradigme impératif ont surtout été utilisés en programmation itérative.

On continue donc à les associer mais les langages modernes impératifs permettant également d'autres types de programmation.

Et ça marche aussi avec matplotlib par exemple ?

import matplotlib.pyplot as plt
import math
 
def trace(f, x_min, x_max):
    absc = [x/10 for x in range(x_min*10, x_max*10+1)]
    ordo = [f(x) for x in absc]
    plt.plot(absc, ordo)
    plt.grid()
    plt.show()

Et on peut alors faire ceci pour tracer des courbes à la volée :


>>> trace(lambda x: x**2, -10, 10)


>>> trace(lambda x: math/log2(x), 1, 100)


>>> trace(lambda x: exp(x), 1, 10)

Programmation récursive et fonctionnelle, c'est pareil ?

Lorsque le paradigme fonctionnelle a émergé en mettant de côté les effets de bord ET le for-while, il a bien fallu trouver un moyen de remplacer les itérations via les boucles.

Pour cela, la programmation récursive est une solution très adaptée.

Mais attention, on peut aussi faire de la programmation récursive avec d'autres paradigmes.

Activité publiée le 07 03 2021
Dernière modification : 08 03 2021
Auteur : ows. h.

⏪

⏫

⏩