LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Links » LIP6 events

GdT programmation / séminaire IRILLRSS

Le sens du partage


02/14/2013
Speaker(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.
More details here
Emmanuel.Chailloux (at) nulllip6.fr
 Mentions légales
Site map |