Auteur : Thibaut Balabonski (Gallium - Inria)

Titre : Le sens du partage.

Abstract :

Le partage, ou la mémorisation de résultats intermédiaires, ajoute des
« raccourcis » à l'espace de réduction d'un programme fonctionnel. On
pourrait penser que ces raccourcis permettent d'arriver plus vite au
résultat. Ce n'est cependant qu'à moitié exact.  Nous montrerons en
effet que dans le cadre de la « réduction faible », qui donne une
bonne approximation des stratégies d'évaluation que l'on sait mettre
en œuvre simplement, les réductions optimales avec ou sans partage ont
même longueur.  En revanche, toujours en réduction faible, nous
verrons que sans partage ces stratégies optimales ne peuvent pas être
calculables, alors qu'avec partage il existe des stratégies optimales
très simples, à commencer par « l'appel par nécessité » de Wadsworth.
Le partage ne modifie donc pas la borne inférieure. Il la rend
accessible.

Attention. Cet exposé contient des utilisations inusuelles du
lambda-lifting et des transformations CPS.