GdT programmation / séminaire IRILL

RSS

Le sens du partage

Thursday, February 14, 2013
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.


More details here …
Emmanuel.Chailloux (at) nulllip6.fr