Lazi

Question

Peut-on arriver à ne faire aucune duplication de calcul en supposant qu'il n'y a aucune duplication dans les définitions ?

Étude

Exemple 1

Soit f=$F x → g h $F y → i j y x, si on calcul f a.

On peut partager le calcul de "i j". Lors de l'application du premier argument (x), il y a copie du corps de la fonction. Comme "i j" est sans variable, le calcul est partagé.

Exemple 2

Soit f=$F x → g h x $F y → i y j Avec le système où on sait seulement si l'expression dans laquelle on a remplacé une variable contient une variable, on n'a pas l'information qu'il n'y a pas x dans $F y → i y j, qui n'est donc pas considéré comme partageable.

Si le critère pour créer un Sharer était de ne pas contenir la variable x, alors dans la formule $F x → g h x $F y → i y j x, on aurait un Sharer pour i y j ce qui fait que y n'aurait pas été remplacé par la suite.

Besoins

Un Sharer est une Formula contenant une autre Formula et servant à indiquer que la sous-formule n'a pas de variable libre. Le Sharer sert aussi à partager le calcul, une fois le calcul de la formule incluse effectué, il positionne un flag à "computed" pour indiquer que la formule interne n'est plus à calculer. Si on veut juste se servir des Sharer pour indiquer qu'il n'y a pas de variable libre, il suffit de positionner dès le début le flag "computed" à true.

La duplication se produit lors du remplacement des corps des fonctions, on n'utilisera donc les Sharer que dans les corps des fonctions.

Un Sharer contenant une variable est inutile car le contenue aura un remplacement (qui n'est pas partagé) avant d'être calculé.

Il est utile de savoir si une sous-formule est sans variable car alors la fonction de remplacement de variable (qui prend un temps conséquent) est triviale. Pour certaines formules on le sait déjà: par exemples les constantes globales ou encore les représentations de formules. Savoir si une sous-formule est sans variable libre permet à la fois de partager le calcul (en utilisant un Sharer) et aussi d'indiquer qu'il n'y a pas de remplacement de variable à effectuer. Il nous suffit donc d'englober les formules maximales sans variable libre par un Sharer. Le flag "computed" du Sharer permet de me pas tenter de calculer les formules sans variable non calculables seules.

Actuellement, les formules à mettre dans les Sharer sont les Apply et les Functions, seules les Apply étant calculables seuls.

Nous avons donc besoin de détecter les formules sans variable de taille maximales.

Une formule sans variable libre de taille maximale ne peut être que la formule entière ou une enfant d'un Apply.

Essai 3

Voir aussi les /essais infructueux. (ancien wiki))

Ordre de remplacement des variables

Pour une sous-formule donnée, l'ordre de remplacement des variables libres est fixé: il dépend de l'ordre d'imbrication des fonctions.

Mais les fonctions sont aussi dans des arguments, pour qu'un arguments ne subissent pas les remplacements liés à l'endroit où il se trouve il faut qu'il soit dans un Sharer. C'est possible même pour un argument marqué "no-comp", il suffit pour ce cas que le flag du Sharer soit mis à "computed".

Nous avons donc un ordre fixé. Il est inutile de remplacer une variable ne se trouvant pas dans un sous-formule. En ayant un moyen d'indiquer que le remplacement est inutile, le remplacement ne s'effectue pas dans la sous-formule, ce qui change l'ordre de remplacement dans cette sous-formule puisqu'un remplacement est manquant.

Pour une sous-formule donnée, une fois l'ordre des remplacements déterminés (et nous avons vue qu'il dépend de l'imbrication des fonctions mais aussi de l'absence des variables dans les formules parents), il suffit d'avoir l'information de la présence de la variable libre pour chaque remplacement. On peut donc se contenter d'une liste de booléen.

Si cette liste est dans le même ordre que l'ordre des remplacements, alors nous pouvons remarquer qu'à partir du moment où les flags sont à "variable absente", la sous-formule est sans variable libre et peut donc être entourée d'un Sharer. Nous pouvons donc, dès la préparation de cette liste, supprimer les derniers éléments contigus indiquant "pas de variable". Ainsi on met en place le Sharer quand la liste est vide.

PreSharer

Un PreSharer contient une formule (comme un Sharer) et sert à indiquer qu'il contient des variables libres et quels sont les variables libres incluses relativement à l'ordre des remplacement qu'il subira. Comme nous avons vu le dernier flag indique que la variable est présente. Une fois tous les remplacements correspondant à des variables libres de la sous-formule effectués, on remplace le PreSharer par un Sharer.

Calcul des PreSharer

On ne peut pas calculer les PreSharer en une fois car il est à la fois nécessaire d'examiner le contenue de la formule, mais aussi d'avoir l'information des remplacements effectués, ce qui provient des PreSharer parents. On a donc à la fois besoin d'informations des parents pas encore disponibles et de l'information des formules.

Il faut donc faire le calcul en deux passes:

  1. À partir de la liste des variables des fonctions englobantes, on détermine la liste (booléens) des flags "variable présente dans la sous-formule".
  2. À partir de la liste de booléen des remplacements qui seront visible relativement à tous les remplacements, réduit la liste des flags en éliminant ceux ne correspondant pas (localement) à un remplacement.

Optimisation

La préparation des PreSharer nécessite de d'ajouter et supprimer des éléments dans une liste. Mais lors des calculs il n'y a plus besoin que de lire les éléments, de tester s'il y en a encore et de copier l'objet. La liste n'a pas besoin de changer, la copie peut donc se contenter de dupliquer uniquement l'itérateur (il faut un flag pour indiquer que c'est le possesseur). On peut donc utiliser une liste pour stocker les booléens puisque lors des calculs il n'y aura que des opérations sur l'itérateur.

On peut aussi faire une version plus réduite en mémoire et peut-être plus rapide qui utiliser un champs de bits dans un unsigned long long int.

Réponse

Oui, voir l'étude.