在 C 或 C++ 中实现 Prolog

I was wondering how would Prolog implementation in C or C++ look like. I am mainly interested in building it as a C or C++ library, though the interpreter app would also do. I am interested in reading about its internals, namely query execution i.e. finding the solutions and the associated datatypes involved. I would be glad if you recommended me any readings on topic or for any direct suggestions/advices. Readings might be for other OOP languages or for general OOP as well. Most exhausting material will solve the question.

解决方案

If you want to see how a Prolog system implemented in C can be used from C/C++ as a library, look at SWI-Prolog. It offers a completely bi-directional interface including non-determinism for Unix/Mac/Window — and much, much more. Think of constraints.

On the other hand, you are asking also about its actual implementation. There are two ways to approach this. You can either start from the very bottom and work yourself up level-to-level. Or you can start with Prolog, and start with meta-interpreters that implement Prolog in Prolog. From this you can slowly dig into the gore.

The traditional approach was to start with the very bottom issues first, studying the various abstract machines. The most commonly cited one is the WAM (Warren Abstract Machine) and then there are Alternatives to the WAM you should not miss. Be prepared that it will take a long way from this to a working ISO implementation. There are many issues that are only cursorily dealt with in the literature like garbage collection and constraints. Yet, they are needed for a robust implementation.

The other approach is to first learn Prolog, and then study meta-interpreters in detail. In this manner you might learn to see Prolog from an entirely different perspective. And you might also gain insights you would not get otherwise. You can start with the classical three clause meta-interpreter which reuses much of Prolog's functionality. Depending on your interest you then can start to reify parts of it. The nice thing is that you pay (in terms of code size) almost only for the parts you want to dig in and reuse the other parts of the language.

At least in the past this approach led to various new implementation techniques, e.g. constraints, Erlang, binary Prolog all existed first as a "simple" meta-interpreter. Only then, after understanding the language issues, actual implementations were done.

There is also another point in favour of starting with Prolog first: What happens, if you stop your effort right in the middle of it? With the bottom-up approach you end up with a collection of defunct code. For the second approach, you have learned Prolog.