CODEWITHSUNDEEP
prolog
SecretService - not really
SecretService - not really

Reputation: 1113

How does Prolog technically work? What's under the hood?

I want to learn more about the internals of Prolog and understand how this works.

I know how to use it. But not how it works internally. What are the names of the algorithms and concepts used in Prolog?

Probably it builds some kind of tree structure or directed object graph, and then upon queries it traveres that graph with a sophisticated algorithm. A Depth First Search maybe. There might be some source code around but it would be great to read about it from a high level perspective first.

I'm really new to AI and understanding Prolog seems to be a great way to start, imho. My idea is to try to rebuild something similar and skipping the parser part completely. I need to know the directions in which I have to do my research efforts.

Upvotes: 46

Views: 8383

Answers (8)

peter.cyc
peter.cyc

Reputation: 1813

In addition to the many good answers already posted, I add some historical facts on Prolog.

  • Wikipedia on Prolog: Prolog was created around 1972 by Alain Colmerauer with Philippe Roussel, based on Robert Kowalski's procedural interpretation of Horn clauses. Alain was a French computer scientist and professor at Aix-Marseille University from 1970 to 1995. Retired in 2006, he remained active until he died in 2017. He was named Chevalier de la Legion d’Honneur by the French government in 1986.
  • The inner works of Prolog can best be explained by its inventor in this article Prolog in 10 figures. It was published in Communications of the ACM, vol. 28, num. 12, December. 1985.

Upvotes: 3

alexkelbo
alexkelbo

Reputation: 724

Prolog uses a subset of first order predicate logic, called Horn logic. The algorithm used to derive answers is called SLD resolution.

Upvotes: 2

user502187
user502187

Reputation:

The ISO core standard for Prolog also contains an execution model. The execution model is of interest since it gives a good model of control constructs such as cut !/0, if-then-else (->)/2, catch/3 and throw/1. It also explains how to conformantly deal with naked variables.

The presentation in the ISO core standard is not that bad. Each control construct is described in a form of a prose use case with a reference to an abstract Prolog machine consisting of a stack, etc.. Then there are pictures that show the stack before and after execution of the control construct.

The cheapest source is ANSI:
http://webstore.ansi.org/RecordDetail.aspx?sku=INCITS%2FISO%2FIEC+13211-1-1995+%28R2007%29

Upvotes: 3

Jay
Jay

Reputation: 9656

The book by Sterling and Shapiro, mentioned by larsmans, actually contains an execution model of Prolog. It's quite nice and explains clearly "how Prolog works". And it's an excellent book!

There are also other sources you could try. Most notably, some Lisp books build pedagogically-oriented Prolog interpreters:

  • On Lisp by paul Graham (in Common Lisp, using -- and perhaps abusing -- macros)
  • Paradigms of Artificial Intelligence Programming by Peter Norvig (in Common Lisp)
  • Structure and Interpretation of Computer Programs by Abelson and Sussman (in Scheme).

Of these, the last one is the clearest (in my humble opinion). However, you'd need to learn some Lisp (either Common Lisp or Scheme) to understand those.

Upvotes: 3

compostus
compostus

Reputation: 1228

AI is a wide field, Prolog only touches symbolic AI. As for Prolog, the inner workings are too complex to explain here, but googling will give you plenty of resources. E.g. http://www.amzi.com/articles/prolog_under_the_hood.htm .

Check also Wikipedia articles to learn about the other areas of AI.

Upvotes: 22

adamo
adamo

Reputation: 4042

I would add:

Upvotes: 4

thanos
thanos

Reputation: 5858

You might also want to read about the Warren Abstract Machine
typically, prolog code is translated to WAM instructions and then executed more efficiently.

Upvotes: 13

Fred Foo
Fred Foo

Reputation: 363627

What are the names of the algorithms and concepts used in Prolog?

See Sterling & Shapiro, The Art of Prolog (MIT Press) for the theory behind Prolog.

Probably it builds some kind of tree structure or directed object graph, and then upon queries it traveres that graph with a sophisticated algorithm. A Depth First Search maybe.

It doesn't build the graph explicitly, that wouldn't even be possible with infinite search spaces. Check out the first chapters of Russell & Norvig for the concept of state-space search. Yes, it does depth-first search with backtracking, but no, that isn't very sophisticated. It's just very convenient and programming alternative search strategies isn't terribly hard in Prolog.

understanding Prolog seems to be a great way to start, imho.

Depends on what you want to do, but knowing Prolog certainly doesn't hurt. It's a very different way of looking at programming. Knowing Prolog helped me understand functional programming very quickly.

My idea is to try to rebuild something similar and skipping the parser part completely

You mean skipping the Prolog syntax? If you happen to be familiar with Scheme or Lisp, then check out section 4.4 of Abelson & Sussman where they explain how to implement a logic programming variant of Scheme, in Scheme.

Upvotes: 30

Related Questions