Partage (programmation informatique) — Wikipédia

Pour les articles homonymes, voir Partage.

Ne doit pas être confondu avec Partage de fichiers.

En programmation, le partage de structures ou simplement le partage (en anglais sharing) est un mécanisme qui évite de copier des objets dupliqués. En effet, la programmation conduit souvent à la duplication de sous-structures, mais cette duplication peut avoir un effet déplorable sur la croissance de l'espace mémoire si des précautions ne sont pas prises pour utiliser la mémoire avec parcimonie.

Le partage ou partage de structure est une technique d'économie de la mémoire et du temps de calcul dans les programmes informatiques. Il comporte plusieurs variantes :

• le partage horizontal partage les sous-structures pour former un graphe orienté acyclique ;
• le partage vertical représente par des graphes avec cycles les termes infinis, comme ceux engendrés dans des appels récursifs ;
• le partage maximal (hash consing) partage toutes les structures identiques créées au cours de l'algorithme.

Fonctionnement[modifier | modifier le code]

L'outil de base du partage est le pointeur ou la référence^[1]. Supposons que les structures soient implantées par des cellules et des liens d'une cellule vers une autre. Quant au cours de la construction d'une structure on note qu'une sous-structure est identique à une sous-structure déjà construite, on ne construit pas la nouvelle sous-structure mais on fait pointer le lien vers la sous-structure déjà construite, évitant ainsi de perdre de la place.

Termes et graphes orientés acycliques[modifier | modifier le code]

Le partage se fait essentiellement dans les termes, la structure qui est alors construite est un graphe orienté acyclique, abrégé en anglais en DAG.

Une façon pour le programmeur de gérer le partage en programmation fonctionnelle est la construction syntaxique let qui crée une référence. Ainsi quand on écrit

let x = foo in bar,

cela signifie que l'objet (ou la structure) foo est partagée dans l'objet bar et que sa valeur ne sera calculée qu'une fois. Cependant, en programmation fonctionnelle, cette référence ne sera pas réaffectée.

Par exemple le terme f(a,g(b,b)) est représenté sans partage par le graphe de la figure à droite en bas et le même terme avec partage est représenté par la figure à droite en haut. Pour garantir le partage on pourrait l'écrire :

let x = b in g(a,f(x,x)).

Ces techniques de partage sont étudiées sous le nom de graphe de terme (en) et ont donné lieu à la conférence TERMGRAPH^[2] qui étudie la réécriture des graphes de termes et ses applications.

Gain en efficacité[modifier | modifier le code]

Outre le gain en place déjà évoqué, le partage permet un gain en temps de calcul. En effet, si on évalue des quantités associées à des sous-structures, il n'est pas nécessaire de faire deux fois le même calcul quand une sous-structure est partagée. Ces caractéristiques sont exploitées dans les diagrammes de décision binaire où le partage est important.

Partage vertical[modifier | modifier le code]

Une autre forme de partage consiste a représenter un terme infini, comme on en rencontre dans les appels récursifs, par un graphe avec cycle (voir les figures). On appelle ce type de partage, un partage vertical^[3]. Les termes des figures sont décrits par l'expression

let t = g(b,t) in f(a,t).

Partage maximal[modifier | modifier le code]

Dans le partage maximal, on exécute le partage de toutes les structures qui sont identiques. Pour retrouver et représenter les structures, on utilise des techniques de hachages.

Références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

• Erik Barendsen Term graph rewriting chapitre 13 de (en) Terese, Term Rewriting Systems, Cambridge Tracts in Theoretical Computer Science, 2003 (ISBN 0521391156)

Voir aussi[modifier | modifier le code]

• Système de réécriture
• Programmation fonctionnelle

• Portail de la programmation informatique
• Portail de l'informatique théorique