GdT programmation / séminaire IRILLRSS

Le sens du partage

14/02/2013
Intervenant(s) : Thibaut Balabonski (Inria)
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.

Plus d'informations ici …
Emmanuel.Chailloux (at) nulllip6.fr
Mentions légales
Carte du site