Comment Prolog fonctionne-t-il techniquement ? Qu'y a-t-il sous le capot ?

Question

Je veux en savoir plus sur les aspects internes de Prolog et comprendre comment cela fonctionne.

Je sais comment l'utiliser. Mais pas comment il fonctionne en interne. Quels sont les noms des algorithmes et des concepts utilisés dans Prolog ?

Il construit probablement une sorte de structure arborescente ou de graphe d'objets dirigés, puis, lors des requêtes, il parcourt ce graphe à l'aide d'un algorithme sophistiqué. Une recherche en profondeur peut-être. Il pourrait y avoir du code source, mais ce serait bien de le lire d'abord d'un point de vue de haut niveau.

Je suis vraiment novice en matière d'IA et comprendre Prolog semble être un excellent moyen de commencer, à mon avis. Mon idée est d'essayer de reconstruire quelque chose de similaire en sautant complètement la partie analyseur. J'ai besoin de connaître les directions dans lesquelles je dois faire mes efforts de recherche.

Answer 1

Quels sont les noms des algorithmes et des concepts utilisés dans Prolog ?

• Programmation logique
• La profondeur d'abord, retour en arrière recherche
• Unification

Voir Sterling & Shapiro, L'art de Prolog (MIT Press) pour la théorie derrière Prolog.

Il construit probablement une sorte de structure arborescente ou de graphe d'objets dirigés, puis, lors des requêtes, il parcourt ce graphe à l'aide d'un algorithme sophistiqué. Une recherche en profondeur peut-être.

Il ne construit pas le graphe explicitement, ce qui ne serait même pas possible avec des espaces de recherche infinis. Consultez les premiers chapitres de Russell & Norvig pour le concept de recherche dans l'espace d'état. Oui, il fait de la recherche en profondeur avec du backtracking, mais non, ce n'est pas très sophistiqué. C'est juste très pratique et la programmation de stratégies de recherche alternatives n'est pas terriblement difficile en Prolog.

La compréhension de Prolog semble être un excellent moyen de commencer, à mon avis.

Cela dépend de ce que vous voulez faire, mais connaître Prolog ne fait certainement pas de mal. C'est une façon très différente d'aborder la programmation. La connaissance de Prolog m'a permis de comprendre très rapidement la programmation fonctionnelle.

Mon idée est d'essayer de reconstruire quelque chose de similaire en sautant complètement la partie analyseur.

Vous voulez dire sauter la syntaxe Prolog ? Si vous êtes familier avec Scheme ou Lisp, consultez le site suivant section 4.4 de Abelson & Sussman où ils expliquent comment implémenter une variante de programmation logique de Scheme, en Scheme.

Answer 2

L'IA est un vaste domaine, Prolog ne touche que l'IA symbolique. Quant à Prolog, son fonctionnement interne est trop complexe pour être expliqué ici, mais une recherche sur Google vous fournira de nombreuses ressources. Par exemple http://www.amzi.com/articles/prolog_under_the_hood.htm .

Consultez également les articles de Wikipedia pour en savoir plus sur les autres domaines de l'IA.

Answer 3

Vous pouvez également vous renseigner sur le Machine abstraite Warren
En général, le code prologue est traduit en instructions WAM, puis exécuté plus efficacement.

Answer 4

J'ajouterais :

• Langages de programmation : Une approche basée sur l'interpréteur par Samuel N. Kamin. Ce livre est épuisé, mais vous pouvez le trouver dans une bibliothèque universitaire. Il contient une implémentation de Prolog en Pascal.

• Tim Budd, "The Kamin Interpreters in C++" ( en post-scriptum )

Answer 5

La norme de base ISO pour Prolog contient également un modèle d'exécution. Le modèle d'exécution est intéressant car il donne un bon modèle des constructions de contrôle telles que cut !/0, if-then-else (->)/2, catch/3 et throw/1. Il explique également comment traiter de manière conforme les variables nues.

La présentation de la norme ISO de base n'est pas si mauvaise. Chaque construction de contrôle est décrite sous la forme d'un cas d'utilisation en prose avec une référence à une machine Prolog abstraite constituée d'une pile, etc. Il y a ensuite des images qui montrent la pile avant et après l'exécution de la construction de contrôle.

La source la moins chère est l'ANSI :
http://webstore.ansi.org/RecordDetail.aspx?sku=INCITS%2FISO%2FIEC+13211-1-1995+%28R2007%29