DEUG MIAS M2


Sémantique





  1. Introduction
    1. Sémantique statique
    2. Sémantique dynamique
  2. Environnement et mémoire
    1. Mémoire
    2. Environnements
    3. Déclarations et instructions
  3. Portée des déclarations
    1. Portée statique et portée dynamique
  4. Sémantique de l'affectation
    1. Emplacement d'une variable
    2. Valeur d'une expression
      1. Effets de bord
  5. Sémantique des autres instructions
    1. Séquence
    2. Conditionnelle
    3. Boucles
  6. Procédures et fonctions
    1. Passage par valeur
    2. Passage par variable
      1. Usage du passage par variable
    3. Appels récursifs
  7. Les pointeurs
  8. Contrôle de types



Introduction

La sémantique d'un langage de programmation est la description du sens des constructions du langage. Comme dans une langue naturelle, les phrases syntaxiquement correctes d'un langage de programmation n'ont pas toutes un sens. Le compilateur, qui a la charge de traduire un programme source (par exemple en Pascal) vers un programme équivalent en langage machine, doit donc s'assurer que le programme a bien un sens (on dit qu'il est correct sémantiquement), avant d'effectuer la traduction à proprement parler.

Dans cette partie du cours, nous nous intéressons aux mécanismes qui permettent de décrire la sémantique d'un langage de programmation impératif. Ces mécanismes sont appliqués au langage Pascal dont une partie de la sémantique sera décrite. Les notions abordées sont notamment :

Sémantique statique


Dans le programme suivant, qui est correct syntaxiquement, on peut détecter aisément plusieurs erreurs sémantiques :

1	program demo;
2	var	x : integer;
3		t : array [1..10] of integer;
4	procedure p (z : real);
5		var	i : integer;
6		begin
7			z := i;
8		end; (* p *)
9	begin (* program demo *)
10		readln (i);
11		x := t;
12		p (x, i);
13	end.
 

Dans la procédure p, la variable i est utilisée (ligne 7) mais n'est pas initialisée. A la ligne 10, on utilise la variable i alors qu'elle n'est pas déclarée dans le bloc de déclarations correspondant. A la ligne 11, on affecte une variable t qui est un tableau à une variable x entière. Enfin à la ligne 12, la procédure p est appelée avec deux paramètres (x et i) alors qu'elle n'a été déclarée qu'avec un paramètre.

On voit que ces erreurs font référence à la notion de cohérence entre la déclaration d'un objet et ses utilisations. Dans un langage impératif, on impose en général de déclarer les objets (variables, types, procédures, etc.) avant de les utiliser, afin de pouvoir vérifier que l'utilisation est conforme à la déclaration.

Une erreur comme celle de la ligne 10 a trait à ce que l'on appelle la portée des identificateurs : lorsque l'on déclare un identificateur, cette déclaration n'est utilisable que dans une certaine partie du programme. Ici, la variable i, bien que déclarée dans p, n'est pas utilisable dans le programme principal.

Une erreur comme celle de la ligne 11 a trait au contrôle des types : on vérifie que chaque utilisation d'une variable correspond bien au type qu'on a déclaré pour cette variable.

Enfin, une erreur comme celle de la ligne 12 a trait à la sémantique de l'appel de procédures et de fonctions.

Dans la suite de ce cours, ces trois types de contrôles sémantiques seront étudiés en détail. L'ensemble de ces contrôles correspondent à la vérification de la sémantique statique du programme, c'est-à-dire de la partie de la sémantique qui peut être vérifiée sans exécuter le programme. La sémantique statique est contrôlée par le compilateur, qui interdit l'exécution du programme si elle n'est pas correcte.

Sémantique dynamique


Cependant, il n'est pas possible en général d'assurer que tout ce que fait le programme a un sens. En d'autres termes, toute la sémantique d'un langage ne peut être décrite pas sa sémantique statique (ou alors le langage est trop simple et sans intérêt). Considérons le programme suivant :

program p;
var	t : array [1..10] of integer;
	i : integer;
function f (n : integer) : integer;
	begin
		if n > 2
		then f := f (n-1) + f (n-2)
		else f := n
	end; (* f *)
 
begin (* program p *)
	i := 1;
	while f(i) < 1000 do
	begin
		writeln (t[i]);
		i := i + 1;
	end
end.
 

L'expression t[i] n'a de sens que si i est dans l'intervalle [1..10]. Ici, i vaut 1 au début, et est incrémenté jusqu'à ce que f(i) soit supérieur ou égal à 1000. Malheureusement il est impossible de savoir si la valeur de f(i) sera inférieure à 1000 lorsque i est inférieur à 10, même en regardant le corps de la fonction f, à moins de calculer effectivement les valeurs de f(i), c'est-à-dire d'exécuter le programme.

On appelle cette partie de la sémantique la sémantique dynamique car elle ne peut être contrôlée que lors de l'exécution du programme. L'un des avantages des langages impératifs est de diminuer la sémantique dynamique par rapport à la sémantique statique. Cela a pour effet qu'un plus grand nombre d'erreurs sémantiques sont découvertes avant d'exécuter le programme, à la compilation, et que les erreur d'exécution, qui sont difficiles à découvrir et à réparer, sont plus rares.

Environnement et mémoire

Une façon de décrire ce que fait un programme est de décrire ses effets observables lors de l'exécution. A l'exécution, un programme exécute des instructions (actions élémentaires ou composées) qui modifient :

Nous nous intéressons particulièrement aux effets d'un programme sur la mémoire. On considère que la mémoire est constituée d'emplacements, qui peuvent contenir des valeurs. Ainsi, un emplacement de 4 octets pourra contenir un entier, tandis qu'un emplacement de 200 octets pourra contenir un tableau de 200 caractères. Un emplacement correspond à une adresse dans la mémoire et une taille. On appelle E l'ensemble des emplacements et V l'ensemble des valeurs.

Mémoire


A un instant donné, l'état de la mémoire peut être vu comme une fonction qui donne la valeur contenue chacun de ses emplacements :

mem : E -> V

L'ensemble de tous les états possibles de la mémoire est l'ensemble de toutes les fonctions mem, noté MEM. A un instant donné, l'état de la mémoire est donc un élément de MEM.

Lorsque l'on change une valeur en mémoire, l'état de la mémoire change et correspond donc à un autre élément de MEM. Ainsi, si la valeur de l'emplacement e devient v, mem devient mem + {e -> v}. Cette notation signifie que, dorénavant, mem(e) = v. Au départ, on peut considérer que la mémoire est vide (mem(e) est indéfini quel que soit e), on bien qu'elle est initialisée avec des valeurs par défaut (par exemple mem(e) = 0 quel que soit e).

Cette modification de la mémoire peut être décrite par une fonction :

changevaleur : MEM x E x V -> MEM (mem, e, v) -> mem + {e->v}

Environnements


Dans un programme écrit dans un langage impératif, les emplacements sont dénotés par des identificateurs de variables. On appelle ID l'ensemble de tous les identificateurs possibles. A tout instant, on peut décrire l'emplacement dénoté par chaque identificateur du programme par une fonction appelée environnement :

env : ID -> E

Ainsi, pour connaître la valeur de la variable i dans un programme, il faut connaître l'emplacement e de i, et la valeur v de e :

e = env (i), v = mem (e), soit v = mem (env (i))

Au départ, env(i) est indéfini quel que soit i, c'est-à-dire qu'aucun identificateur n'est défini. Lorsque l'on définit un identificateur, il faut lui associer un emplacement, c'est-à-dire qu'il faut changer la fonction env. Comme pour le changement de valeur en mémoire, ce changement peut être décrit par une fonction :

declare : ENV x ID x E -> ENV (env, id, e) -> env + {id -> e}

Pour faire une analogie, une variable peut être vue comme le nom que l'on donne à une boîte, par exemple "mon bloc-tiroir" ou "l'armoire de l'entrée", et la valeur est le contenu de la boîte. Pour des personnes différentes, ou selon l'endroit où je me trouve, le nom "mon bloc-tiroir" ou "l'armoire de l'entrée" dénote un objet différent : cela correspond à des environnements différents.

Déclarations et instructions


Dans un langage impératif, l'environnement est modifié seulement par les déclarations, et la mémoire est modifiée seulement par les instructions.

Considérons le programme suivant :

program démo;
var x : integer;
begin
	x := 5;
end.
 

On trouve une déclaration (var x) et une instruction (x := 5). Au départ, l'environnement et la mémoire sont vides. Notons-les respectivement env0 et mem0.

L'effet de la déclaration est d'associer un emplacement libre (par exemple 1) à la variable x. L'environnement devient donc

env = env0 + {x -> 1}

L'effet de l'instruction est d'affecter une valeur (5) à l'emplacement env(x). La mémoire devient donc

mem = mem0 + {env(x) -> 5}

Il apparaît donc que l'instruction x := 5 n'aurait pas de sens si la déclaration de x était omise, car env (x) ne serait pas défini. Ainsi, en Pascal, comme dans tous les langages impératifs, toute variable doit être déclarée avant d'être utilisée. Cela est également vrai des autres entités du langage : constantes, types, procédures.

Considérons maintenant le programme suivant :

program démo;
var x, y : integer;
begin
	x := y;
end.
 

Avant l'affectation, l'environnement est

env = env0 + {x -> 1} + {y -> 2}

(on suppose que les emplacements des entiers ont une taille de 1). Pour réaliser l'affectation, il faut connaitre l'emplacement de x, et la valeur de y, soit respectivement env(x) et val(env(y)). L'effet de l'affectation est de modifier la mémoire de la façon suivante :

mem = mem0 + {env(x) -> mem(env(y)) }

Comme x et y ont été déclarés, env(x) et env(y) sont définis. Par contre, mem0 est indéfinie pour tout emplacement et donc mem(env(y)) est indéfini : la valeur de y n'a pas été initialisée, et l'affectation est donc sémantiquement incorrecte.

Considérons donc le programme suivant :

1 program démo;
2 var x, y : integer;
3 begin
4 	y := 5
5 	x := y;
6 end.
 

Avant d'exécuter la ligne 5, l'état de la mémoire est

mem = mem0 + {env(y) -> 5 }

La ligne 5 produit la modification de mem en

mem + {env(x) -> mem(env(y)) }

Cette fois-ci, mem(env(y)) est bien défini et vaut 5.

On voit donc que les notions d'environnement et de mémoire permettent déjà de réaliser deux contrôles sémantiques :

Note : Dans un langage fonctionnel, il n'y a pas besoin de la notion de mémoire pour définir la sémantique du langage. En effet, un environnement fait correspondre directement un identificateur à une valeur.

Portée des déclarations

Nous avons vu qu'une déclaration modifiait l'environnement en définissant un emplacement pour la variable déclarée. Dans la plupart des langages impératifs, les variables ont une portée, qui détermine la portion du programme où la variable est accessible (on dit : visible). Ainsi, dans un programme Pascal, les déclarations globales sont visibles dans tout le programme (d'où leur nom). Par contre, les déclarations de variables locales à une procédure ou fonction ont pour portée la seule procédure ou fonction où elles sont déclarées, ainsi que les procédures et fonctions imbriquées :

program demo
var x : integer;
procedure p;
	var y : integer;
	begin
		... x ... y ...
	end;
begin
	... x ...
end.
 

On peut représenter, dans la plupart des cas, les portées comme des boîtes imbriquées : les variables déclarées dans une boîte sont visibles dans cette boîte et dans les boîtes imbriquées. (On peut également représenter les portées comme un arbre : les variables déclarées à un noeud de l'arbre sont visibles dans ce noeud et dans tous les noeuds de son sous-arbre.) Lorsque l'on atteint la fin d'une portée, l'environnement est restauré à son état juste avant le début de la portée.

En 1, les déclarations visibles sont celles de Prog, P et P2. En 2, celles de Prog et de Q. En 3, celles de Prog.

Une variable d'un bloc englobant peut être cachée par la déclaration d'une variable de même nom dans le bloc courant :

program demo
var i : integer;
procedure p;
	var i : integer;
	begin
		... i ...
	end;
begin
	... i ...
end.
 

Cela correspond au fait que lorsque l'on déclare i dans p, ou modifie l'environnement pour y ajouter {i->env'(i)}, écrasant l'ancienne valeur env(i). Cependant, lorsque l'on est en dehors de la portée de p, c'est la première définition de i qui est visible (celle du programme principal). On voit donc que, selon le point du programme où l'on se trouve, un même identificateur peut désigner un emplacement différent.

Pour calculer l'environnement en un point du programme, on peut considérer qu'à chaque portée P correspond un environnement EP. L'environnement courant est la "somme" des environnements associés à chaque portée contenant la position courante. La "somme" de deux environnements est définie comme suit :

E0 = E1 + E2 : ID ->E pour tout x tel que E2(x) = y, E0(x) = y pour tout x tel que E1(x) = y et E2(x) n'est pas défini, E0(x) = y

Cette définition n'est pas tout à fait exacte car un identificateur n'est visible qu'à partir de son point de déclaration. En particulier, si l'on déclare la procédure P puis la procédure Q, P est visible depuis le corps de Q mais pas l'inverse.

En Pascal, une portée correspond au programme principal, et à chaque procédure ou fonction. Le nom de la procédure ou fonction fait cependant partie de l'environnement englobant - sinon, il serait impossible de l'appeler !

Portée statique et portée dynamique


Ce que nous avons décrit jusqu'à présent s'appelle la portée statique. Cela signifie que l'emplacement associé à une variable qui apparait dans le programme dépend de la déclaration de cette variable.

Sémantique de l'affectation

L'affectation est une instruction de la forme

var := expr

"var" est une variable simple ou composée (par exemple l.t[i].x), et "expr" est une expression. La sémantique d'une affectation simple est facile à décrire :

x := 5

change la mémoire de telle sorte que l'emplacement de x contienne 5. Lorsque la variable n'est pas une variable simple, il faut être capable de définir l'emplacement e représenté par la variable. Lorsque l'expression n'est pas une simple constante, il faut être capable de définir la valeur v représentée par cette expression. Un fois connus l'emplacement e et la valeur v, la sémantique de l'affectation peut être simplement définie par :

mem = mem0 + {e -> v}

c'est-à-dire que la mémoire mem0 est modifiée de telle sorte que la valeur de l'emplacement e est v.

Emplacement d'une variable


Soit un environnement env et une mémoire mem. Pour déterminer l'emplacement d'une variable var, il faut traiter chaque cas :

Nous savons donc calculer l'emplacement de toute variable complexe, en combinant les règles ci-dessus. Nous noterons cet emplacement Empl[[var]]. (Cette notation permet de distinguer la fonction env, définie sur l'ensemble des identificateurs, de l'évaluation de l'emplacement d'une variable, qui n'est pas à proprement parler une fonction). Les règles ci-dessus peuvent alors s'écrire :

(Val[[ expr ]] est décrit ci-dessous)

Valeur d'une expression


Nous considérons à nouveau un environnement env et une mémoire mem. Pour déterminer la valeur d'une expression, il faut, comme pour les variables, considérer les différents cas :

De façon similaire à l'accès aux variables, on note la procédure d'évaluation d'une expression Val[[ expr ]]. Les règles ci-dessus s'écrivent alors :

On note que Val fait référence à Empl, et Empl fait référence à Val. Ces deux procédures d'évaluation se font mutuellement référence. Cependant, jusqu'ici, ni Empl ni Val ne changent l'environnement ni la mémoire. (Seule l'affectation change la mémoire.) Cela signifie en particulier que l'ordre des évaluations n'a pas d'influence sur le résultat. Par exemple, évaluer Val[[e1]] puis Val[[e2]] produit le même résultat que si l'on évalue d'abord Val[[e2]] puis Val[[e1]].

Effets de bord

La propriété ci-dessus n'est malheureusement pas toujours vraie. Considérons le programme suivant :

program bord;
var	glob : integer;
	x : integer;
function f (x : integer) : integer;
	begin
		glob := glob + 1;
		f := x;
	end;
begin
	glob := 0;
	x := f(1) + glob;
end.
 

Selon que f(1) est évalué avant ou après glob, la valeur de x n'est pas la même ! On dit que l'appel de f produit un effet de bord sur la variable glob : l'évaluation de Val[[f(1)]] modifie la mémoire de telle sorte que Val[[glob]] ne donne pas le même résultat selon que Val[[f(1)]] est évalué avant ou après. Un problème similaire se poserait avec l'affectation :

t[glob] := f(1);
 

Les langages fonctionnels ne connaissent pas de problèmes d'effets de bord. Dans les langages impératifs, ils sont inévitables : c'est au programmeur d'y prendre garde, et de les eviter au maximum.

Sémantique des autres instructions

Munis de la notion de procédure d'évaluation (comme Var[[ ]] et Empl[[ ]]), nous pouvons donner la sémantique des autres instructions d'un langage impératif. Comme les instructions ne modifient que la mémoire et pas l'environnement, il suffit de donner, pour chaque instruction, sont effet sur la mémoire, grâce à la procédure Mem[[ ]] ("effet sur la mémoire").

Séquence

Mem[[ I1; I2 ]] = Mem [[ I2 ]] o Mem [[ I1 ]]

Cela signifie que l'instruction I2 s'exécute dans le contexte de la mémoire que lui transmet l'instruction I1.

Conditionnelle

Mem[[ if E then I1 else I2 ]] = si Val[[ E ]] alors Mem[[ I1 ]] sinon Mem [[ I2 ]]

Selon la valeur de E, c'est l'instruction I1 ou l'instruction I2 qui est exécutée. Si E modifie la mémoire, il faut composer Mem[[I1]] et Mem[[I2]] avec Mem[[E]].

Boucles

Mem[[ while E do I ]]

On peut voir cette boucle comme la séquence

if E then I; if E then I; if E then I; ...

Cette répétition se poursuit jusqu'à ce que la mémoire ne soit plus modifiée. La sémantique ne peut être exprimée de façon simple comme on l'a fait jusqu'à présent : il faut utiliser un opérateur spécial dit "plus petit point fixe". On retrouve cet opérateur lorsque l'on essaie de définir la sémantique de fonctions ou procédures récursives. (On peut d'ailleurs exprimer une boucle while sous forme d'une récursion).

Procédures et fonctions

Pour utiliser des procédures et fonctions, il faut les déclarer et les appeler. Lors de la déclaration, on définit le nom de la procédure ou fonction, ses paramètres formels, le type de sa valeur de retour (pour une fonction), ses déclarations locales, et son corps. Lors de l'appel, on donne la valeur des paramètres réels.

Lors de l'appel d'une procédure ou fonction, les étapes suivantes sont exécutées :

  1. Ajout à l'environnement des paramètres et variables locales, correspondant à l'entrée dans la portée définie par la procédure ou fonction ;
  2. Initialisation des valeurs des paramètres ("passage des paramètres"), c'est-à-dire modification de la mémoire ;
  3. Exécution du corps de la procédure ou fonction, dans l'environnement et la mémoire ainsi modifiés ;
  4. Pour les fonctions, retour de la valeur de la fonction ;
  5. Retour à l'environnement qui était en place avant l'appel : les paramètres et variables locales sont retirées, et les variables éventuellement masquées "réapparaissent".

Il faut noter que seul l'environnement est restauré. Les effets de la procédure ou fonction sur la mémoire persistent, ce qui est la cause des effets de bord que nous avons vu plus haut. Ces effets de bord ne peuvent être visibles que sur les variables qui sont dans le domaine de portée de l'appelant de la fonction : puisque les paramètres et variables locales ne sont plus accessibles après l'appel, leur valeur en mémoire n'a aucune importance.

Il existe deux modes principaux de passage de paramètres : par valeur et par variable. Le passage par valeur correspond aux paramètres de données, tandis que le passage par variable correspond aux paramètres de résultats ou de données-résultats.

Passage par valeur


Soit le programme suivant :

program pval;
var	x : integer;
procedure p (a : integer);
	begin
		Ecrire ("a = ", a);
		a := 0;
	end;
begin
	p (10);
	x := 10;
	p(x);
	Ecrire ("x = ", x);
end.
 

Avant l'appel p(10), l'environnement contient la variable x, et la mémoire ne contient rien. Au moment de l'appel, le paramètre formel a est ajouté à l'environnement, un emplacement libre lui est affecté et sa valeur est initialisée au paramètre réel 10. La procédure écrit la valeur de a (10), puis affecte 0 à a. Après le retour de l'appel de p, a est retiré de l'environnement (donc sa valeur 10 en mémoire devient inaccessible).

Lors du second appel p(x), la mémoire contient 10 pour l'emplacement de x, mais le reste de la séquence d'appel est exactement identique. En particulier, au retour de l'appel p(x), x vaut toujours 10.

On voit donc que lors du passage par valeur, il y a recopie de la valeur des paramètres réels dans les emplacements des paramètres réels. Toute modification d'un paramètre formel est sans effet sur les paramètres réels et de façon générale sur l'environnement que sera restauré au retour de l'appel. Les seuls effets de bord sont possibles en affectant des valeurs à des variables globales, c'est-à-dire à des emplacements accessibles après le retour de l'appel.

Notons enfin que si l'on avait appelé le paramètre formel de p x au lieu de a, le fonctionnement serait rigoureusement le même ! Le x, paramètre formel de p, masquerait le x, variable globale, et donc l'affectation de x dans p serait sans effet sur le x global.

Passage par variable


Considérons maintenant le programme suivant :

program pval;
var	x : integer;
procedure p (var a : integer);
	begin
		Ecrire ("a = ", a);
		a := 0;
	end;
begin
	p (10);	(* erreur ! *)
	x := 10;
	p (x);
	Ecrire ("x = ", x);
end.
 

Il s'agit du même programme, mais a est déclaré comme passé par variable.

Lors de l'appel, le paramètre formel a est ajouté à l'environnement, comme dans le passage par valeur. Mais, au contraire du passage par valeur où un nouvel emplacement libre est affecté au paramètre formel, l'emplacement du paramètre formel est le même que celui du paramètre réel. On a donc deux variables (ici x et a) qui partagent le même emplacement. Toute modification de a affecte alors x puisqu'il s'agit, en fait, de la même zone mémoire.

Pour que ce mode de passage soit possible, il faut que le paramètre réel dénote une emplacement, et non pas une valeur. L'appel p(10) est alors illégal, puisque 10 ne peut être évalué comme un emplacement. Il en serait de même d'un appel de la forme p(x+y) ou p(f(x)). Par contre p(x), p(t[i]), p(c.x) sont des appels licites car le paramètre réel est une variable dont on peut évaluer l'emplacement par Empl[[ ]].

Au retour de l'appel, le paramètre a est retiré de l'environnement, mais, contrairement à un paramètre passé par valeur, son emplacement reste accessible par l'intermédiaire du paramètre réel x. Dans l'exemple ci-dessus, après l'appel p(x), x vaut 0. C'est une seconde forme d'effet de bord, puisque la mémoire de l'appelant a été modifiée d'une façon visible.

Usage du passage par variable

Les passages de paramètres par variable sont utilisés en Pascal pour permettre de retourner des types complexes. En effet, le type de retour d'une fonction Pascal ne peut être qu'un type simple (entier, réel, énuméré). La seule façon pour une fonction de retourner, par exemple, un tableau, est de prendre le tableau comme paramètre par variable, et de le modifier :

program demo;
type	tab = array [1..10] of integer;
var	tablo : tab;
procedure zero (var t : tab);
	var	i : integer;
	begin
		for i := 1 to 10 do t[i] := 0;
	fin;
begin
	zero (tablo);	(* au lieu de : tablo := zero *)
end.
 

Le passage par variable est aussi indispensable lorsque l'on souhaite effectivement produire une effet de bord :

program echange;
var	x, y : integer;
procedure swap (var x : integer; var y : integer)
	var	tmp : integer;
	begin
		tmp := x;
		x := y;
		y := tmp;
	end;
begin
	Lire (x); Lire (y);
	swap (x, y);
	Ecrire ("x = ", x, "; y = ", y);
end.
 

Si x et y n'étaient pas passés par variable, la procédure ne produirait aucun effet perceptible !

Appels récursifs


Lorsqu'une procédure ou fonction s'appelle récursivement, le principe reste le même. Il en résulte que chaque appel enrichit l'environnement, et donc chaque paramètre formel x de la procédure ou fonction récursive masque celui de l'appel englobant :

program factorielle;
var	a : integer;
function fact (x : integer) : integer;
	begin
		if x <= 1
		then fact := 1
		else fact := x * fact (x - 1);
	end;
begin
	Lire (a);
	Ecrire (fact (a));
end.
 

Lorsque l'on calcule fact (3), on a successivement (les identificateurs entre parenthèses sont ceux qui sont masqués) :

env :   x      @1                   mem :    @1     3      
env :   (x) x  @1 @2                mem :    @1 @2  3 2    
env :   (x)    @1                   mem :    @1     3 2 1  
        (x) x  @2 @3                         @2 @3         
 
 

On voit que chaque appel de fact contient "son" x, les autres étant inaccessibles mais néanmoins présents. On comprend également que la place mémoire nécessaire est proportionnelle au nombre d'appels récursifs. Une récursion infinie va donc se solder par un débordement de la mémoire.

Les pointeurs

(à rédiger)

Contrôle de types

(à rédiger - pas fait en cours)


Autres chapitres :

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


Michel Beaudouin-Lafon, mbl@lri.fr