Prolog
La première implémentation complète de Prolog est le système 
*.
C'est un interpréteur écrit en Lisp.
C'est un système plutôt lent, à la gestion de mémoire défectueuse.
Ce dernier point est important car le système Lisp est lui-même doté
d'une gestion de mémoire réputée efficace.
Ce qu'il faut en retenir est que la gestion de mémoire ne traverse pas
automatiquement les couches d'interprétation.
Il y a deux raisons à cela.
Premièrement,
une gestion de mémoire ne peut rien contre des structures de données
qui sont intrinsèquement gourmandes.
Deuxièmement,
Lisp et Prolog
(et Prolog, et la programmation logique en général)
n'ont pas les mêmes logiques d'utilité.
Cela signifie que les objets de la représentation de l'état d'une
exécution ne sont pas utiles pour les mêmes raisons en Lisp et en Prolog.
Se pourrait-il que la représentation d'un objet utile pour le langage objet
(ici, Prolog),
ne le soit pas pour le métalangage
(ici, Lisp) ?
Non,
car on peut faire l'hypothèse que l'interpréteur est correct
et que donc tous les objets qui lui sont utiles le sont aussi au sens de Lisp.
Donc,
la différence de logique d'utilité ne s'exerce que dans un sens :
des objets inutiles pour le langage objet sont jugés utiles,
parce qu'accessibles au sens du métalangage.
C'est la source de ce qu'on appelle des fuites de mémoire
(memory leaks).
Cette observation et son développement sont à l'origine
du projet 
vers 1984.
La production concrète de ce projet a été la définition de la mémoire
*
et sa réalisation en matériel et en logiciel.
Elle a été voulue générale plutôt que dédiée à un système Prolog particulier,
et c'est pourquoi nous avons pu l'utiliser sans modification pour Prolog.
Il faut cependant admettre que le message n'est pas passé dans toute sa généralité. Par exemple, il est devenu assez commun d'utiliser Java comme langage cible d'un compilateur. Certains programmeurs espèrent ainsi faire bénéficier le langage source de l'environnement d'exécution de Java : librairies, vérifications de sûreté et sécurité, et gestion de mémoire. Ils oublient que cela ne suffit pas pour récupérer toute la mémoire qui est libérable selon la logique d'utilité du langage source.
Figure: Comparaison de temps de calcul pour renverser une liste fonctionnelle, sun4, 50 Mo (longueur de la liste 
temps de calcul en secondes, échelle log-log)
Un nouveau système Prolog vient de sortir : Terzo*.
C'est encore un interpréteur,
mais il est écrit en Standard 
.
Là encore,
le système souffre d'une gestion de mémoire inadaptée.
Au total,
les performances de Terzo ne sont pas vraiment meilleures que celles de .
En particulier,
on observe le même comportement quadratique que celui de là où
un calcul de complexité linéaire est possible
(voir la figure 8).
Sans parler de gain en complexité,
il ne semble même pas que Terzo améliore la consommation de mémoire
d'un facteur significatif.
Par exemple,
Terzo utilise 36 méga-octets
de mémoire pour renverser une liste de 800 éléments,
alors que en utilisait moins de 32 pour une liste de plus de 500 éléments.
Nous ne connaissons aucune publication sur ce système,
mais ses auteurs font référence dans sa documentation aux techniques
projetées par Gopalan Nadathur [Nadathur et Wilson 90] :
notation de de Bruijn* et environnements.
Pour la comparaison des deux systèmes,
nous avons mesuré le temps pris pour renverser des listes fonctionnelles
de tailles croissantes jusqu'à atteindre la saturation de la mémoire
(voir à la figure 6
une comparaison similaire entre 
et ).
Sur la station de travail utilisée (sun4)
celle-ci survient lorsque près de 50 méga-octets de mémoire sont consommés.
Dans cette comparaison,
le système atteint la taille de liste où Terzo sature la mémoire
(c'est-à-dire consomme 50 méga-octets pour une liste 1600 éléments)
en ne consommant que 2 méga-octets.
Nous ne savons rien de la politique de gestion de mémoire de Terzo et
Standard ,
et en particulier nous ne savons pas quel est l'écart entre la quantité de
mémoire strictement utile pour exécuter l'application et la quantité de mémoire
qui est effectivement consommée.
Plus cet écart est grand et moins le récupérateur de mémoire a à intervenir ;
c'est donc un facteur de «confort».
Dans le système cet écart est réglable indirectement,
en particulier en fixant le maximum de mémoire qui peut être consommé.
Ainsi,
la même application peut être contrainte à s'exécuter
jusque plus de 3600 éléments en utilisant seulement 1 méga-octet.
La perte de confort n'est perceptible que pour des exécutions qui sont très
proches de la saturation.
C'est une observation que nous avons faite très souvent
et qui montre que le système peut être utilisé sur des systèmes
qui disposent d'une quantité de mémoire relativement modeste.
Le système est le plus complet et le plus performant des systèmes
proposés.
Il est la partie visible d'une recherche sur
la mise en 
uvre de Prolog,
et son développement a toujours été conduit avec l'objectif d'une
intégration maximale avec un environnement traditionnel.
Cette recherche a mis évidence le rôle des combinateurs*
et des 
-rédex*
dans la manipulation efficace des -termes,
et la possibilité de représenter par plusieurs
continuations* le contrôle de Prolog.
Elle a aussi confirmé la flexibilité de *.