DEUG MIAS M2


Introduction - Langage de réalisation





  1. Objectifs du cours
    1. Fonctionnel vs Impératif
  2. Exemple
  3. Langage de réalisation
    1. Actions élémentaires
      1. Affectation
      2. Lecture
      3. Ecriture
    2. Actions composées
      1. Séquence
      2. Découpage par cas
      3. Itération
    3. Actions nommées et fonctions
      1. Actions nommées
      2. Fonctions



Objectifs du cours

Les objectifs de ce cours sont :

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.

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".

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 - 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
 

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 :

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 :

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)
 

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.


Autres chapitres :

  1. Introduction - Langage de réalisation (ce chapitre)
  2. Structures de données
  3. Lexique et syntaxe
  4. Sémantique


Michel Beaudouin-Lafon, mbl@lri.fr