Best viewed in 24pt and full-screen
next up previous contents
Next: S´appuyer sur un modèle Up: Implémentation Previous: Implémentation

Étendre la tex2html_wrap_inline52108

La principale différence méthodologique entre le projet de Gopalan Nadathur et le nôtre a été le choix du point de départ. Gopalan Nadathur a choisi de partir de la machine abstraite de Warren [Warren 83a, Aït-Kaci 91] (tex2html_wrap_inline52108 pour Warren's Abstract Machine). La tex2html_wrap_inline52108 a dominé le monde de la compilation de Prolog, et a servi de point de départ à de nombreux projets de compilation d'extensions de Prolog. La tex2html_wrap_inline52108 est définie par des registres, des piles et des instructions. Elle résulte d'une analyse, de nombreuses fois raffinée, des besoins de l'exécution de Prolog. En particulier, une disposition particulière des zones mémoires, associée à des invariants subtils de l'exécution de Prolog, permet une implémentation très efficace de ses instructions. Par exemple, on convient que toutes les adresses mémoires (piles et registres) sont comparables entre elles, et qu'elles représentent l'âge de création de l'objet qui occupe une adresse donnée. On convient aussi que, lorsqu'il faut substituer une variable à une autre, il faut toujours substituer la plus ancienne à la plus récente. Tester l'âge ne coûte presque rien grâce à la première convention, et le bénéfice est que, en cas de retour-arrière, la variable substituée et la substitution disparaissent sans n'avoir rien à faire. Sans cette convention, il faudrait défaire la substitution explicitement.

Cette disposition des zones mémoires n'offre plus aucun intérêt si les invariants ne sont pas vérifiés. En fait, beaucoup d'extensions de la tex2html_wrap_inline52108 qui prennent en compte des extensions de Prolog les pénalisent volontairement pour conserver les invariants. La gestion de mémoire est particulièrement cruciale et pourtant elle est souvent sacrifiée dans ces extensions de la tex2html_wrap_inline52108. Par exemple, un grand nombre de dispositifs «modernes», qui nécessitent donc une extension de la tex2html_wrap_inline52108, peuvent être implémentés par la technique de la variable à attribut [Le Huitouze 90b]. Cette technique permet d'étendre la tex2html_wrap_inline52108 sans la bouleverser. Son inconvénient est que sa mise en tex2html_wrap52064uvre naïve conduit à violer presque systématiquement la seconde convention mentionnée plus haut : dans les applications qui utilisent la variable à attribut, on a le plus souvent besoin de substituer une variable nouvelle à une variable ancienne [Noyé 94a, Noyé 94b]. Un invariant de la tex2html_wrap_inline52108 s'effondre et le retour-arrière devient plus coûteux.

C'est acceptable si l'extension n'est utilisée que de manière marginale, mais c'est insupportable si c'est tout le paradigme qui change. En choisissant de partir de la tex2html_wrap_inline52108 pour compiler tex2html_wrap_inline56836Prolog, on choisit délibérément de sacrifier ce qui est au ctex2html_wrap52064ur de tex2html_wrap_inline56836Prolog. Par exemple, la tex2html_wrap_inline53988-réduction* est un des ces dispositifs qui peuvent utiliser la technique de la variable à attribut. En effet, l'unification de tex2html_wrap_inline56836Prolog demande de calculer des formes normales de tête*. On pourrait les oublier sitôt l'unification terminée, mais ce serait dommage car elles peuvent resservir et les conserver ne coûte pas beaucoup. Pour ce faire, il faut substituer une forme normale de tête au terme original -- un terme nouveau à un terme ancien -- ce qui est contraire au dogme de la tex2html_wrap_inline52108. Similairement, une implémentation efficace de l'implication dans les buts demande de pouvoir substituer un prédicat étendu (parce que augmenté de nouvelles clauses) à un prédicat plus ancien. Étendre la tex2html_wrap_inline52108 n'est donc pas une chose simple quand le paradigme implémenté est vraiment nouveau.

De plus, la tex2html_wrap_inline52108 ne fournit aucune réponse sur la manière d'implémenter les nouveaux traits de tex2html_wrap_inline56836Prolog. Elle fait des hypothèses très fortes sur la nature des objets de base : une variable, un registre et un champ de structure devraient être homogènes (alors qu'en tex2html_wrap_inline56836Prolog la notion de variable se diversifie en des objets -- variable existentielle, universelle, de type, tex2html_wrap_inline56836-variable -- qu'on a aucun intérêt à rendre homogènes -- certains portent un type d'autres non, etc), il n'y a de variables que dans les buts (alors qu'en tex2html_wrap_inline56836Prolog il peut aussi y en avoir dans les clauses impliquées), le traitement de la tête de clause est purement fonctionnel (alors qu'en tex2html_wrap_inline56836Prolog il peut créer des points de choix car l'unification n'est pas unitaire), etc.


next up previous contents
Next: S´appuyer sur un modèle Up: Implémentation Previous: Implémentation

Olivier Ridoux
Mon Apr 27 11:10:23 MET DST 1998