Les paradigmes de programmation.

Introduction.

Pour rappel, le seul langage compris par la machine est l'assembleur et cela entraîne des problèmes pour le programmeur :

L'assembleur demande d'être proche de la machine, il doit connaître les instructions possibles par le processeur.
Faire un programme est long et compliqué.
Les programmes sont peu lisibles, peu maintenables et plus ils sont longs plus la chose empire.
Il n'y a pas d'assembleur unique, chaque architecture a son assembleur donc les programmes sont très peu portables.

Les programmeurs ont alors pensé à créer des langages dit de haut niveau, l'idée est de s'éloigner des contraintes du matériel pour écrire un programme de façon "universelle". Il y a des gradations dans ce "haut niveau", par exemple le langage C qui a ses débuts était considéré de haut niveau est maintenant considéré comme étant de bas niveau (en effet on doit gérer la mémoire de façon manuelle). Au final il faut traduire le programme en assembleur, cela se fait soit par compilation (tout d'un coup) soit de manière interprétée (à la volée).

Il existe énormément de langages différents, ils sont souvent spécialisés à certaines taches (Scratch pour la pédagogie, C pour la performance pure, C++ pour les jeux...). Les langages différent par la syntaxe mais aussi le paradigme c'est à dire la façon de penser la programmation. le tableu suivant présente des exemples de paradigme.

Paradigme	Idée	Exemples
Impératif	Utiliser des variables, en Python l'instruction a = a + 2 est typiquement de style impératif. on envisage le programme comme une succession d'état mémoire	Pratiquement tous les "vieux" langages C, C++, Java, Python.
Structuré	Eviter des sauts dans le programmes (comme le jaz de Cardiac, mais sur les vieux langages il existe des commandes goto ou lbl), on peut utiliser pour cela des instructions for ou While ou faire de la récurrence. Quand on utilise trop le goto on fait de la programmation spaghetti.	Pratiquement tous les langages courants actuels C, C++, Java, Python, dans les années 80 le langage Basic était très utilisé par les amateurs et utilisait le goto .
Procédural	Séparer le programme en petit morceaux (fonctions), la lecture est simple (si vous donnez des bons noms aux fonctions), le code est court, la maintenance pratique et on peut regrouper des fonctions dans des modules ou bibliothéque) pour réutiliser le travail plus tard (programmation modulaire)	Pratiquement tous les langages courants actuels.
Objet	Evolution de la programmation procédurale, pour simplifier on associe aux objets les fonctions qui sont associées. Voir plus loin.	Pratiquement tous les langages modernes.
Fonctionnel	A ne pas confondre avec le fait de créer des fonctions dans un programme, en programmation fonctionnelle on cherche à éviter les "effet de bord" et pour ça on évite les variables (a = a+1 n'a pas de sens en programmation fonctionnelle ou alors c'est un test)	Beaucoup des "nouveaux" langages. Ocaml, Haskell, F#, Rust

Certains paradigmes se marient bien (la programmation impérative et procédurale par exemple) d'autres sont contraires (impérative et fonctionnelles par exemple).

Enfin certains langages sont volontairement adaptés à certains paradigmes, Ocaml est fait pour la programmation fonctionnelle par exemple, y faire de l'impératif est compliqué.

Python autorise de nombreux paradigmes et on peut très bien faire une partie d'un programme en programmation fonctionnelle et une autre en impérative par exemple (mais bon mélanger les styles peut nullifier les avantages des paradigmes).

Tous les paradigmes permettent à la fin de faire les mêmes choses (n’oubliez pas que tous les programmes sont convertis en Assembleur, donc dans un langage bas niveau, impératif et non structuré) cependant ils peuvent simplifier le travail, permettre une meilleure maintenance, permettre une réutilisation aisée, simplifier le travail en groupe, éviter certaines erreurs...

Exemple

Voici différentes façons de programmer la suite de Fibonacci. La première en assembleur cardiac est un exemple de programmation spaghetti, le programme permet de sauter d'une ligne à l'autre. La deuxième est version Python en impératif et enfin la dernière une version Python fonctionnelle.



.at 10    ; On commence les instructions à 10
; Les variables
.word 1
.word 1
.word 0
.word 1
.word 2
INP 15

;On teste si n vaut 0 ou 1
LDA 15
SUB 13
JAZ 31 ; On passe à l'instruction de la case 31
; boucle principale
LDA 10
ADD 11
STA 12
LDA 11
STA 10
LDA 12
STA 11
LDA 14
ADD 13
STA 14
SUB 15
JAZ 16

OUT 11
HRS 00

Un langage comme Ocaml a été développé pour faire de la programmation fonctionnelle :

Vous pouvez utiliser le site suivant pour tester le code.

Programmation fonctionnelle.

La programmation fonctionnelle est la programmation à la "mode", un des ses atouts est d'éliminer les effets de bords (modifications du contenu d'une variable) qui amènent souvent des erreurs difficiles à corriger.

Programmer en fonctionnelle est assez différents de la programmation impérative classique, il faut "réapprendre" à programmer.

En programmation fonctionnelle on utilise souvent la récursivité, mais on peut aussi utiliser la récursivité en programmation impérative, en programmation fonctionnelle il n'y a pas de 'variables', on peut placer des valeurs dans des conteneurs constants (a = 2) mais on n'a pas la possibilité de la modifier (a = a + 1 n'existe pas de la programmation fonctionnelle).

Comme déjà mentionné, on peut faire les mêmes choses dans tous les langages de programmations, le résultat peut être plus ou moins compliqué ou plus ou moins rapide à l’exécution, ou plus ou moins consommateur d'énergie ou de mémoire mais au final le résultat sera le même. Par exemple voici le tri par insertion et par sélection en programmation fonctionnelle (attention c'est personnel et peu optimisé).

Exemple

Sélection :

Insertion :

La programmation fonctionnelle fait aussi un gros usage des fonctions, que l'on peut utiliser comme variable dans une autre fonction et même comme retour d'une fonction, par exemple la fonction suivante prend une fonction en entrée et retourne la même fonction en affichant le temps d’exécution en plus.

Exemple

Les instructions map, filter et reduce sont très utilisées en programmation fonctionnelle, cela dit en python la construction par compréhension est très pratique.

Exercice

Que va donner exercice1(0), exercice1(1), exercice1(2) et exercice1(4) ?
Que va donner exercice2([4,2,3,6],0), exercice2([4,2,3,6],1), exercice2([4,2,3,6],2), exercice2([4,2,3,6],3) et exercice2([4,2,3,6],4) ?
Que va donner exercice3([1,2,2,4,3],5) et exercice3([1,2,3],3) ?
On souhaite programmer la multiplication de deux entiers positifs sans utiliser l'opérateur * mais en utilisant l'opérateur + (donc il faut multiplier en utilisant uniquement l'addition).
- On appelle multiplication(a,b) le produit de a et de b ( = a × b mais n'oubliez pas que l'on ne veut pas utiliser la multiplication). Établir une relation entre multiplication(a,b) et multiplication(a,b-1).
  Cliquez ici pour une aide.
  
  a × b = a × (b-1) + ...
- Pour quelle valeur de b connaissez vous la réponse de multiplication(a,b).
- Compléter :
  Mulplication(a,b)
  
  Si b == ...
  
  | retour ...
  
  Sinon
  
  | retour ... + ...
- Ecrire le programme en python.
- Le réecrire mais en tuilisant le while et pas la récursion.
On souhaite programmer une fonction pair(nb) qui retourne True si le nb est pair et False sinon.
- Que pouvez vous dire sur pair(nb) si pair(nb-1) = True ?
- Définir la valeur d'arret de nb.
- Compléter :
  pair(nb)
  
  Si nb == ...
  
  | retour ...
  
  Sinon
  
  | Si pair(...) == True
  
  | | retour ...
  
  | Sinon
  
  | | retour ...
- Ecrire le programme en python.
- Le réecrire en utilisant le while.
- Le réecrire sans utiliser de boucle ou de récursion.
- Donner les complexités des différentes versions.
On souhaite programmer puissance(a,b) qui donne a^b.
- Donner une relation de récurence sur b.
- Donner l'arret.
- Programmer puissance sur Python en récursif.
- Faire la même chose mais en utilisant while (ou for).
On souhaite savoir le nombre de chiffres d'un nombre (par exemple 5648 est écrit avec 4 chiffres). Soit nb_chiffres(n) la fonction.
- Quelle opération sur python permet de passer 5648 à 564 ?
- Comment définir la valeur d'arret ?
- Programmer nb_chiffres en récursif.
- La complexité sur n de la fonction précédente est O(ln). Uniquement si vous connaisez la fonction ln, Comment obtenir nb_chiffres en O(1).
On souhaite programmer maximum_liste(liste,n) qui donne le maximum de liste sur les n premiers éléments (0 < n <= len(liste) ).
- Que vaut maximum_liste(liste, 1) ?
- Comment connaître maximum_liste(liste, n) si on connaît maximum(liste,n-1) ?
  Cliquez ici pour une aide.
  
  a₀ a₁ ... a_n-2 a_n-1
  maximum_liste(liste,n-1) a_n-1
- Programmer maximum_liste(liste, n) en récursif (n'oubliez pas que l'indice d'un tableau commence à 0.)
- Programmer maximum_liste(liste, n) avec une boucle.
En Python :
- Faire une fonction somme(liste,n) qui calcul la somme des n premiers éléments d'une liste en version récursive.
- Faire la même chose en version non récursive.
Faire une fonction nb_apparitions(liste,nb,n) qui retourne le nombre de fois ou nb apparaît dans les n premiers éléments de liste.
- En version récursive.
- En version non récursive.
Compléter le programme suivant qui permet d'obtenir la fonction dérivée d'une fonction f donnée.

a₀	a₁	...	a_n-2	a_n-1
maximum_liste(liste,n-1)				a_n-1