“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 73 — #83
i
i
i
i
i
i
i
i
2.5 La gestion de mémoire
73
( [({LowerBound A C}, {Y → y
, LowerBound → lb, A → a, C → c})],
{ lb = (proc {$ X Z} if X>=Y then Z=X else Z=Y end end,
{Y → y}), y
= 10, y = 5, a = 3, c} )
L’environnement à l’appel a un peu changé : Y référence une nouvelle variable y
, qui
est liée à 10. Quand on fait l’appel, le nouvel environnement est calculé exactement
comme avant, en commençant avec l’environnement contextuel et en ajoutant les
arguments formels. La variable y
est ignorée ! Nous obtenons exactement la même
situation qu’avant sur la pile sémantique :
( [(if X>=Y then Z=X else Z=Y end, {Y → y, X → a, Z → c})],
{ lb = (proc {$ X Z} if X>=Y then Z=X else Z=Y end end,
{Y → y}), y
= 10, y = 5, a = 3, c} )
La mémoire contient toujours le lien y
= 10. Mais comme y
n’est pas référencée par
la pile sémantique, ce lien n’a aucun effet sur l’exécution.
2.5 LA GESTION DE MÉMOIRE
La machine abstraite que nous avons définie dans la section précédente est un outil
puissant pour analyser les propriétés des calculs. Nous allons faire une première
exploration pour regarder le comportement en mémoire, pour voir comment les tailles
de la pile sémantique et la mémoire évoluent quand le calcul progresse. Nous verrons
le principe de l’optimisation terminale et nous l’expliquerons au moyen de la machine
abstraite. Cela nous mènera aux concepts de cycle de vie mémoire et de ramassage de
miettes (« garbage collection »).
2.5.1 L’optimisation terminale
Regardons une procédure récursive avec un seul appel récursif qui est le dernier appel
dans le corps de la procédure. Nous appelons une telle procédure récursive-terminale.
Nous montrons que la machine abstraite exécute une procédure récursive-terminale
avec une taille de pile constante. Cette propriété s’appelle l’optimisation du dernier
appel ou l’optimisation terminale (« last call optimization »). Le terme de récursion
terminale est parfois employé, mais il est moins précis parce que l’optimisation fonctionne pour tout dernier appel, pas seulement pour les appels récursifs (voir exercices,
section 2.8). Voici la procédure que nous investiguons :
proc {Loop10 I}
if I==10 then skip
else {Browse I} {Loop10 I+1} end
end
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
2.5 La gestion de mémoire
73
( [({LowerBound A C}, {Y → y
, LowerBound → lb, A → a, C → c})],
{ lb = (proc {$ X Z} if X>=Y then Z=X else Z=Y end end,
{Y → y}), y
= 10, y = 5, a = 3, c} )
L’environnement à l’appel a un peu changé : Y référence une nouvelle variable y
, qui
est liée à 10. Quand on fait l’appel, le nouvel environnement est calculé exactement
comme avant, en commençant avec l’environnement contextuel et en ajoutant les
arguments formels. La variable y
est ignorée ! Nous obtenons exactement la même
situation qu’avant sur la pile sémantique :
( [(if X>=Y then Z=X else Z=Y end, {Y → y, X → a, Z → c})],
{ lb = (proc {$ X Z} if X>=Y then Z=X else Z=Y end end,
{Y → y}), y
= 10, y = 5, a = 3, c} )
La mémoire contient toujours le lien y
= 10. Mais comme y
n’est pas référencée par
la pile sémantique, ce lien n’a aucun effet sur l’exécution.
2.5 LA GESTION DE MÉMOIRE
La machine abstraite que nous avons définie dans la section précédente est un outil
puissant pour analyser les propriétés des calculs. Nous allons faire une première
exploration pour regarder le comportement en mémoire, pour voir comment les tailles
de la pile sémantique et la mémoire évoluent quand le calcul progresse. Nous verrons
le principe de l’optimisation terminale et nous l’expliquerons au moyen de la machine
abstraite. Cela nous mènera aux concepts de cycle de vie mémoire et de ramassage de
miettes (« garbage collection »).
2.5.1 L’optimisation terminale
Regardons une procédure récursive avec un seul appel récursif qui est le dernier appel
dans le corps de la procédure. Nous appelons une telle procédure récursive-terminale.
Nous montrons que la machine abstraite exécute une procédure récursive-terminale
avec une taille de pile constante. Cette propriété s’appelle l’optimisation du dernier
appel ou l’optimisation terminale (« last call optimization »). Le terme de récursion
terminale est parfois employé, mais il est moins précis parce que l’optimisation fonctionne pour tout dernier appel, pas seulement pour les appels récursifs (voir exercices,
section 2.8). Voici la procédure que nous investiguons :
proc {Loop10 I}
if I==10 then skip
else {Browse I} {Loop10 I+1} end
end
© Dunod – La photocopie non autorisée est un délit