Partage (programmation informatique)

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.

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.

Un terme infini

Le même terme avec une boucle

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.

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

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.

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

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