Considérant les motivations pratiques de Prolog, son implémentation robuste et efficace était un objectif crucial. Les concepteurs du langage ont d'abord distribué un prototype incomplet et très inefficace, puis un interpréteur écrit en Lisp appelé *. Ce dernier était complet mais inefficace, quoique moins gravement que le prototype.
Nous avons commencé l'étude de l'implémentation de Prolog avec Pascal Brisset en 1989 [Brisset 89], et avons pu faire nos premières évaluations de performance du système * en 1991 [Brisset et Ridoux 91]. Pascal Brisset a soutenu sa thèse en 1992 [Brisset 92]. Deux années furent encore nécessaires pour consolider le système, le documenter et pouvoir le distribuer. Ce travail a fait l'objet d'une synthèse [Brisset et Ridoux 92b] qui fut à son tour résumée [Brisset et Ridoux 94]. Nous insistons sur la rapidité d'exécution de ce programme de recherche, car un projet concurrent dirigé par Gopalan Nadathur avait démarré à la même époque [Nadathur et Jayaraman 89], avec le même objectif, mais avec des méthodes complètement différentes. Ce projet n'a pas encore abouti.