Is there a clear reference, with pseudo-code, on how to go about implementing a Prolog interpreter in a purely functional language? That which I have found so far seems to deal only with imperative languages, is merely a demonstration of Prolog implemented in itself, or offers no concrete algorithm to use for interpretation. I would be very appreciative of an answer.

  • 4
    $\begingroup$ The Implementation of Prolog (Princeton Series in Computer Science) by Patrice Boizumault has Lisp implementation. $\endgroup$ – Will Ness Nov 14 '12 at 8:17
  • $\begingroup$ See this answer for a relatively new approach. $\endgroup$ – false Feb 12 '17 at 23:30

Since Prolog = Syntactic Unification + Backward chaining + REPL

All three parts can be found in Artificial intelligence: structures and strategies for complex problem solving by George F. Luger. In the fourth edition of the book all three parts are implemented in LISP in Section 15.8, Logic Programming in LISP. He also puts the same code in his other books, but I don't have all of them for noting here. The code for his books can be found here.

Another source with all three parts can be found in Paradigms of artificial intelligence programming: case studies in Common Lisp by Peter Norvig. See Chapters 11, Logic Programming and 12, Compiling Logic Programs. The code for his book can be found here.

Another source is Structure and interpretation of computer programs by Hal Abelson, Jerry Sussman and Julie Sussman. See Section 4.4 Logic Programming. The site for the book is here and the code for the book is here.

It is not uncommon to find the unification algorithm with back chaining implemented in many applications if you know where to look; it is especially prevalent in type inferencing in functional compilers. Using the keywords unification or occurs helps to spot the functions. Also most implementations use unif for the name of the unification function.

For a version of Prolog, less the REPL, done in OCaml see Code and resources for "Handbook of Practical Logic and Automated Reasoning" - prolog.ml

A translation of the book code to F# can be found here. A translation of the book code to Haskell can be found here.

In terms of finding the code, the unification algorithm is easiest to find, then implementations with back chaining imbedded in applications. Finding a fully functional implementation of Prolog in a functional language with an REPL is the hardest. Most of the time the code is not in a format for direct use within PROLOG; it is heavily customized to enhance performance, so you may find the code but it will not be worth the price to tease out the parts you want. My advice would be to read Luger's book and build it up from scratch in your language of choice, even if it means installing and learning LISP and translating to do so.


Since this is a duplicate question from StackOverflow and the OP is new and in the comments says:

To give more context, I'm attempting to implement type inference, however the intricate features in the type system of my language (Dependent types, refinement types, linear typing to name a few of the less common ones) make me feel that it would be useful to base my type inference off of the algorithms driving Prolog as to obtain a very general algorithm. I will note that I'm entirely self taught, so my knowledge is lacking in large areas.

I'll expand on this here, but realize the OP should ask a new question.

For some intro stuff see implementing type inference.

The best book I know on this is Types and programming languages by Benjamin C. Pierce. The book's site is here. The resources with links to OCaml code is here. And recently started but mostly complete translation of this to F# is here.

Dependent types: pg. 462 Refinement types: pg. 207 Linear logic and type systems: pg. 109

  • 1
    $\begingroup$ Guy Coder, you sir are a gentleman and a scholar! Your assistance is most useful, and I can't thank you enough for actually taking the time to answer this question. =D - Jimster's Collaborator and Research-Weary Friend $\endgroup$ – Shenzao Nov 11 '12 at 22:26
  • $\begingroup$ I thank you again, I have already obtained these books (that is before, not as in a rapid trip to a book store). $\endgroup$ – Jimster Nov 11 '12 at 22:41
  • $\begingroup$ @Jimster Norvig's code is nice and clear, fits in a page IIRC. Don't remember though if it's pure. $\endgroup$ – Will Ness Nov 14 '12 at 8:19
  • $\begingroup$ Found another one: Lecture 26: Type Inference and Unification $\endgroup$ – Guy Coder Jan 11 '16 at 15:06
  • $\begingroup$ Of interest: unify_P3.py which is part of Assignment 2 $\endgroup$ – Guy Coder Jul 29 '16 at 17:30

See the implementation of miniprolog at my Programming languages zoo, it is the last one on the list. You can see source code online, the code is well documented.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.