Les objectifs de ce cours sont :
Dans l'approche fonctionnelle, on compose des fonctions qui prennent des arguments et retournent des valeurs.
Les programmes sont décrits à l'aide de données et de traitements.
Les types sont définis à partir de :
Les fonctions sont définies par :
Les noms que l'on utilise représentent :
On utilise le terme de variable, dans un sens mathématique : sous la portée de l'abstraction, toute instance d'une variable x représente la même valeur, qui a été liée à la variable dans la déclaration de l'abstraction.
Dans l'approche impérative, on décrit aussi les programmes à l'aide de données et de traitements.
Les types sont définis à partir de :
Les fonctions et actions sont définies par :
Les noms représentent :
Ces variables sont différentes des variables de la programmation fonctionnelle. Ce ne sont pas des variables au sens mathématique. Chaque variable a une valeur, mais qui peut changer au cours du temps, à l'intérieur de son domaine de portée. On attribue une valeur à une variable par l'affectation. On peut visualiser une variable comme une boîte, qui a une étiquette (son nom) et un contenu (sa valeur).
En mode impératif, on peut écrire :
x <- 2 y <- 2*x + 1 x <- y * y
Il n'y a pas d'équivalent en programmation fonctionnelle.
La programmation impérative est plus proche du fonctionnement réel de la machine (on peut voir une variable comme l'étiquette d'une partie de la mémoire), tandis que la programmation fonctionnelle est plus proche d'un modèle mathématique de calcul, donc plus "abstraite".
Nous allons illustrer ces concepts de base par un petit exemple, la résolution du trinôme du second degré.
action RésoudreTrinôme { lit 3 réels a, b, c, a != 0, et écrit les solutions réelles de l'équation ax2 + bx + c = 0 } lexique a, b, c, d : réel début lire_non_nul (a) lire (b) lire (c) d <- discriminant (a, b, c) selon le cas d d < 0 : écrire ("pas de solution") d = 0 : écrire ("une solution double") écrire (-b / 2a); d > 0 : écrire ("deux solutions") écrire (-b - sqrt(d) / 2a) écrire (-b + sqrt(d) / 2a); fin action lire_non_nul (résultat x : réel) { lit un entier non nul au clavier } début répéter lire (x) jusqu'à x != 0 fin fonction discriminant (a, b, c : réel) -> réel { calcule le discriminant d'un trinôme du second degré de coéfficients a, b, c } début retourner b2 - 4ac fin
A titre de comparaison, une version fonctionnelle de cet exemple pourrait être (sans les entrées-sorties) :
type solution { représente les solutions possibles d'un trinôme } pas_de_solution une_solution : réel -> solution deux_solutions : réel * réel -> solution RrésoudreTrinôme (a, b, c) : soit d = discriminant (a, b, c) dans : selon le cas d d < 0 : pas_de_solution d = 0 : une_solution (- b / 2a) d > 0 : deux_solutions (-b - sqrt(d) / 2a, -b + sqrt(d) / 2a) Discriminant (a, b, c) : b2 - 4ac
Pour permettre de prendre en compte les concepts de la programmation impérative, le langage de réalisation a été modifié par rapport à celui vu en M1 :
On va donc décrire plus précisement ce langage de réalisation :
Le symbole d'affectation "<-" se lit "reçoit"
a <- 2 val <- 2x + 1
Lire une donnée entrée au clavier. Selon le type de x, seuls sont acceptés des nombre entiers ou réels.
lire (x)
Ecrire un message, un entier ou un réel à l'écran.
écrire ("message") écrire (x) écrire (2x + 1)
On peut également mettre plusieurs arguments :
écrire ("x = ", x)
est équivalent à :
écrire ("x = ") écrire (x)
Les actions d'une séquence sont exécutées l'une après l'autre :
lire (x); lire (y); écrire (x+y)
ou
lire (x) lire (y) ecrire (x+y)
ou
lire (x); lire (y) ecrire (x+y)
Comme dans le langage de réalisation vu au M1 :
selon le cas x x < 0 : écrire ("négatif") x = 0 : écrire ("nul") x > 0 : écrire ("positif") selon le cas x x > 0 : écrire ("négatif") x = 0 : écrire ("nul") sinon : écrire ("positif") si pair (x) alors x <- x - 1 sinon x <- 3x + 2 si x < 0 alors x <- -x
Dans une itération, le corps est exécuté 0, 1 ou plusieurs fois en fonction du contrôle de la boucle. Si le corps est exécuté une infinité de fois, on dit que le programme "boucle". C'est une erreur de conception ou de programmation.
Dans un "tantque", le corps est exécuté tant que la condition est vraie :
tantque pair (x) x <- x / 2
Dans un "répéter", le corps est exécuté jusqu'à ce que la condition soit vraie :
répéter lire (x) jusqu'à x != 0
Pour qu'une itération de type "tantque" (resp. "répéter") ne boucle pas, il faut s'assurer que la condition peut devenir fausse (resp. vraie). Il faut donc au moins que le corps de la boucle modifie des variables qui sont utilisées dans la condition.
Cette itération boucle indéfiniement si x est positif.
tantque x > 0 écrire (x)
Dans un "pour", le corps est exécuté un nombre pré-déterminé de fois :
s <- 0 pour i parcourant [1..10] s <- s + i pour i parcourant [0..5] en sens inverse écrire (i, "...")
Les itérations "pour" ne peuvent pas boucler. Il est interdit de modifier la valeur de la variable de boucle dans le corps de la boucle. Les bornes de l'intervalle sont évaluées une seule fois, au début de la boucle. La boucle suivante est exécutée exactement 10 fois :
x <- 10 pour i parcourant [1..x] x <- 20
Le nommage est un mécanisme d'abstraction : il permet de créer une boîte noire (l'action nommée) qui peut être utilisée comme une action élémentaire.
action démo (x, y : entier) lexique { déclaration des variables utilisées } z : réel début { corps de l'action } z <- x + y écrire (z) fin
Les variables déclarées dans le lexique ne sont utilisables que dans le corps.
Appels de l'action :
démo (1, 2) démo (n + 1, p * 2)
Le nombre et le type des arguments utilisés dans un appel doivent correspondre à ceux utilisés dans la déclaration de l'action.
Dans une action nommée, les arguments peuvent être :
Illustration :
Les arguments de données sont les plus fréquents. Les arguments de résultat et de donnée-résultat doivent être explicitement déclarés dans la déclaration de l'action :
action div (a, b : entier; résultat q, r : entier) début q <- 0 tantque a > b a <- a - b q <- q + 1 r <- b fin action échange (donnée-résultat x, y : entier) lexique t : entier début t <- x x <- y y <- t fin
Lors de l'invocation, les arguments qui sont déclarés résultat ou donnée-résultat doivent être des variables :
div (15, 4, quotient, reste) échange (quotient, reste)
Les fonctions peuvent être définies comme les actions nommées :
fonction fact (n : entier) -> entier lexique res : entier début si n = 0 alors res <- 1 sinon res <- n * fib (n - 1) retourner res fin
L'action retourner n'est valide que dans une fonction. Elle permet d'indiquer la valeur retournée par la fonction. Il est recommandé que retourner n'apparaissent que comme dernière action du corps de la fonction.
Contrairement aux actions, les fonctions n'acceptent que des arguments de données.