Les langages de programmation et les schémas d'exécutions entretiennent des rapports assez complexes et cela rend les généralisations un peu risquées. Nous appelons schémas d'exécution une implémentation d'une sémantique opérationnelle d'un langage. Au nombre des questions qui sont réglées à ce niveau on trouve la gestion de mémoire, «Qu'est-ce qui consomme de la mémoire et pour combien de temps ?», et le détail de certaines opérations macroscopiques comme l´unification* en programmation logique, ou le passage de paramètre en programmation procédurale. Il est souvent commode de considérer qu'un schéma d'exécution est implémenté par un machine spécialisée, abstraite ou concrète. Nous allons montrer que les langages de programmation et les machines sont plus fortement liés que ne le laisse supposer l'orthodoxie dénotationnelle.
En principe, un langage de programmation et sa sémantique abstraite (par exemple, dénotationnelle) pourrait admettre plusieurs sémantiques opérationnelles, et encore plus de schémas d'exécution. En pratique, il n'en est rien dès qu'on considère toutes les capacités d'une implémentation particulière d'un langage de programmation que son utilisateur doit connaître pour produire des programmes utilisables. De plus, même quand l'idéal d'indépendance est atteint (par exemple pour le noyau pur d'un langage de programmation), c'est souvent le schéma d'exécution qui dit quelles sont les constructions de programme qui sont judicieuses et celles qui ne le sont pas. Nous pensons que si deux schémas d'exécution d'un même langage diffèrent tellement que la manière de programmer en est changée, il s'agit de deux implémentations de deux langages différents. On peut continuer à leur donner le même nom lorsqu'il s'agit de langages expérimentaux qui ne sont pas complètement stabilisés et pour lesquels on ne connaît pas encore de bon schéma d'exécution, mais il faut que ces détails soient figés dans un système de plus large diffusion. Cette distinction est très clairement faite pour la dichotomie nom/valeur du passage de paramètre des langages de programmation fonctionnelle, mais nous pensons qu'elle devrait être faite pour d'autres aspects, plus obscurs, comme la gestion de mémoire.
La manière de réaliser la récupération de la mémoire est un trait d'une machine
qui est fortement conditionné par le langage.
Le plus souvent,
un schéma d'exécution contient naturellement la faculté de récupérer de la
mémoire (par exemple, dépilement au retour de procédure),
mais tout aussi souvent ce n'est pas suffisant et il faut ajouter une
opération explicite de normalisation de la mémoire occupée.
On appelle cette opération le «glanage de cellules»
.
La sémantique de certains langages (par exemple, le langage C) est telle qu'ils ne peuvent admettre qu'un glaneur de cellules conservatif (c'est-à-dire qui n'est pas certain de récupérer toute la mémoire qui n'est plus utilisée, mais qui ne doit pas tenter de récupérer de la mémoire utilisée). Dans le cas de C, les sources d'accès aux structures de données sont les pointeurs vers le tas, mais ceux-ci peuvent être transformés ou même dissimulés, de telle manière que le glaneur de cellules doit prendre en compte toute combinaison de bits qui référence le tas lorsqu'elle est considérée comme un pointeur. C'est une vue pessimiste de l'état de la mémoire qui peut conduire à des fuites de mémoire (memory leaks). Enfin, les possibilités de dissimulation sont telles que le glaneur de cellules ne peut même pas être complètement conservatif. Certaines dissimulations doivent donc être interdites, d'où on conclut que le langage C avec glaneur de cellules, même conservatif, n'est pas le même que le langage C sans.
On vient de voir un exemple où l'introduction d'un glaneur de cellules perturbe la sémantique d'un langage de programmation. Inversement, la sémantique peut être suffisamment abstraite pour résister à ce changement. C'est le cas des langages de programmation logique ou fonctionnelle. Mais, même dans ce cas, la manière d'utiliser le langage de programmation change.
Par exemple, il y a en Prolog trois causes de récupération de mémoire : le retour-arrière, car il cause généralement un dépilement, le retour de prédicat, qui cause aussi un dépilement, mais est limité par le retour-arrière, et un glaneur de cellules, quand il y en a un. Le dépilement pour retour de prédicat est limité par le retour-arrière car ce dernier peut vouloir revenir à la situation d'avant le retour de prédicat. Si on dépilait pour de vrai, il faudrait stocker le tronçon dépilé pour permettre de le réinstaller au retour-arrière. On préfère en général faire semblant de dépiler. La pile d'appel des prédicats n'est donc pas tout à fait une pile, mais plutôt une pile cactus.
Les premiers systèmes Prolog n'implémentaient que les deux premières causes (et souvent la première seulement). Ils favorisaient ainsi des idiomes de programmation qui utilisaient le retour-arrière. Les systèmes plus récents implémentent les trois causes et on a même vu suggérer de ne plus implémenter que la troisième [Bevemyr et Lindgren 94]. Sans changer la sémantique, cela favorise d'autres idiomes fondés sur la récursivité plutôt que sur le retour-arrière [Warren 82].
On trouve un autre exemple du rôle du schéma d'exécution avec l'indexation des clauses en Prolog. Rappelons qu'un programme Prolog est une collection de formules appelées «clauses» parmi lesquelles on recherche celles qui permettent de répondre à une question. Cette collection est partitionnée en «prédicats» qui sont des ensembles de clauses qui définissent la même relation. Cela correspond à l'idée de procédure. Dans les premiers systèmes Prolog, la recherche du prédicat se faisait par accès direct, mais la recherche d'une clause dans un prédicat se faisait par accès séquentiel. Warren [Warren 77] a amélioré cette situation en proposant qu'un compilateur calcule un accès plus direct sur la base des arguments des prédicats dans les têtes de clauses ; c'est l'indexation des clauses. Au début, l'indexation des clauses ne se faisait que sur le premier argument (le plus à gauche), induisant un style de programmation qui en tenait compte [O'Keefe 90]. Ensuite, cette contrainte a été relachée jusqu'à la situation actuelle où tous les arguments peuvent contribuer au calcul de l'indexation, rendant ainsi obsolètes les anciens idiomes de programmation.
Dans le cas du glaneur de cellules, un changement de schéma d'exécution affecte la sémantique d'un langage de programmation, C, qui n'abstrait pas beaucoup le modèle de mémoire. Il ne change pas la sémantique d'un langage de programmation beaucoup plus abstrait, Prolog, mais il change un comportement observable qui n'est pas décrit par la sémantique : la complexité en mémoire du calcul. Dans le cas de l'indexation des clauses, le changement de schéma d'exécution ne change pas la sémantique, mais change un autre comportement observable qui n'est pas décrit dans la sémantique : la complexité en temps du calcul. Dans un langage temps-réel, le temps serait pris en compte par la sémantique sous une forme ou une autre (secondes, tops d'horloge, séquences, histoires) ce qui contraindrait plus le schéma d'exécution. De la même manière, on peut imaginer un langage «mémoire-réelle» (par exemple, pour programmer des systèmes embarqués) où la consommation de mémoire décrite sous une forme plus ou moins abstraite est prise en compte par la sémantique.
De tout cela on conclut que le schéma d'exécution et l'emploi, voire la sémantique, d'un langage de programmation sont plus intiment liés que par des relations de correction et de complétude d'implémentation. Une sémantique assez abstraite peut favoriser l'application de schémas d'exécution importants soit pour l'efficacité, soit pour la robustesse des applications. Au contraire, une sémantique qui n'est pas assez abstraite peut empêcher l'application de ces schémas d'exécution. Enfin, une sémantique abstraite n'est pas nécessairement complètement découplée du temps ou de la mémoire. Elle peut en rendre compte sous une forme abstraite. Par exemple, il existe des langages de programmation temps-réel fondés sur une abstraction du temps qualifiée de synchrone [Halbswachs 93]. Même sans abstraction du temps, un formalisme peut être suffisamment restreint pour que la complexité de tous ses calculs soit prévisible. Un exemple en est les bases de données (déductives) pour lesquelles on connaît ainsi des bornes supérieures des durées et des quantités de mémoire nécessaires pour répondre à une requête selon le langage de la requête ou des règles de la base de données déductive [Gottlob 94].