DEUG MIAS M2

Introduction - Langage de réalisation

Objectifs du cours
Les objectifs de ce cours sont :
•	Présentation du style impératif de programmation ;
•	Apprentissage d'un langage impératif : Pascal (essentiellement en TD) ;
•	Retour sur les notions de type et de variable ;
•	Notion d'abstraction - structures de données et algorithmes associés ;
•	Mécanismes d'entrées/sorties ;
•	Syntaxe et sémantique.
Fonctionnel vs Impératif
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.
•	donnees décrites par leurs types ;
•	traitements décrits par des fonctions.
Les types sont définis à partir de :
•	types de base ;
•	constructeurs de types (produit, union, liste ...).
Les fonctions sont définies par :
•	un profil (c'est tout ce dont on a besoin pour se servir de la fonction)
•	une structure (une expression)
Les noms que l'on utilise représentent :
•	des fonctions ;
•	des arguments (on dit aussi paramètres formels) ;
•	des expressions (par le mécanisme d'abstraction).
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 données sont décrite par des types;
•	les traitements sont décrits par des fonctions et des actions (procédures).
Les types sont définis à partir de :
•	types de base ;
•	constructeurs de types (différents de ceux de l'approche fonctionnelle).
Les fonctions et actions sont définies par :
•	un profil
•	une structure (une séquence d'actions élémentaires ou composées, appelées aussi instructions.
Les noms représentent :
•	des fonctions et des actions ;
•	des arguments ;
•	des variables.
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".
Exemple
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 - √d / 2a)
			écrire (-b + √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 -√d / 2a,
						-b + √d / 2a)

Discriminant (a, b, c) : b2 - 4ac
Langage de réalisation
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 :
•	déclaration d'actions ;
•	déclaration des types des objets (arguments, variables) ;
•	actions élémentaires : affectation, lire, écrire ;
•	actions composées : répéter, retourner.
On va donc décrire plus précisement ce langage de réalisation :
Actions élémentaires
Affectation
Le symbole d'affectation "<-" se lit "reçoit"
a <- 2
val <- 2x + 1
Lecture
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)
Ecriture
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)
Actions composées
Séquence
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)
Découpage par cas
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
Itération
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
Actions nommées et fonctions
Actions nommées
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 :
•	des données : leur valeur est transmise à l'action lors de l'appel ;
•	des résultats : leur valeur est calculée par l'action et retransmise à l'appelant à la fin de l'invocation ;
•	des données-résultats : leur valeur est transmise à l'action lors de l'appel, éventuellement modifiée dans l'action, et retransmise à l'appelant à la fin de l'invocation.
Illustration :
•	je donne une lettre à quelqu'un, qui va la poster pour moi : passage de données ;
•	je demande à une personne de me ramener mon courrier : passage de résultat ;
•	je fais signer une lettre par une personne : passage de donnée-résultat.
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)
Fonctions
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.