Implementing Prolog in C or C++ [closed]

Question

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.

Answer 1

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.

Answer 2

Some time ago I wrote a Prolog interpreter in C++ (really, my first C++ program), and followed a different approach instead of the (now nearly ubiquitous) WAM. Our teacher at course of languages and compilers construction talked about an ABC algorithm, and I implemented that (I goggled 'Prolog implementation ABC algorithm', here a PDF that I found, but I don't know - yet) : here the core solver

//--------------------------
// evaluation core of query
//  use algorithm ABC
//
int IntlogExec::query(const Clause *q)
{
    unsigned nc = 0;

    ProofStack::Env *pcn, *pfn;
    stkpos cn, fn;
#define PCN (pcn = ps->get(cn))
#define PFN (pfn = ps->get(fn))

    UnifyStack us(vs, ts);

    if (!q)
        goto C;

    fn = ps->push(STKNULL);
    PFN->vspos = vs->reserve(q->get_nvars());
    pfn->trail = ts->curr_dim();
    pfn->dbpos = 0;
    pfn->call = 0;

    // current query is empty?
A:  if (!q->get_body()) {

        // search untried calls
A1:     //fn = ps->curr_dim() - 1;
        fn = cn;

        ProofStack::Env *e = ps->get(fn);
        while (e->father != STKNULL) {
            if (tr && e->call && tr->exit(fn, e->call))
                return -1;
            if (e->call && !e->call->is_last())
                break;
            e = ps->get(fn = e->father);
        }
        if (e->father == STKNULL)
            return 1;

        // set call to next untried brother
        cn = ps->push(PFN->father);
        PCN->call = pfn->call->next();
        pcn->vspos = pfn->vspos;
        fn = pfn->father;

    } else {
        cn = ps->push(fn);
        PCN->call = q->get_body();
    }

A2: PFN;
    pcn->dbpos = 0;
    cc = pcn->call;

    if (nc++ == ncycle)
    {
        nc = 0;
        sighandler();
    }

    // trace the call
    if (tr && tr->call(cn, cc))
        return -1;

    switch (cc->get_type()) {

    case CallData::BUILTIN: {
        BuiltIn *btp = cc->get_builtin();

        pcn->trail = ts->curr_dim();
        pcn->vspos = pfn->vspos;

        // if evaluate OK
        if (btp->eval(cc->args(), this, 0)) {

            //          if (tr && tr->exit(cn, cc))
            //              return -1;

            //          if (btp->retry || pcn->call->last())
            //              goto A1;

            //          pcn->call = pcn->call->next();
            //          goto A2;
            goto A1;
        }

        PCN;

        if (tr && tr->fail(cn, pcn->call))
            return -1;

        unbind(pcn->trail);
    }
    goto C1;

    case CallData::CUT: {
        stkpos gf = PFN->father;
        if (    gf != STKNULL &&
                pfn->call->is_last() &&
                pfn->call == pcn->call->next()) {
            // tail recursion optimization
            ProofStack::Env *pgf = ps->get(gf);
            pgf->vspos = pfn->vspos;

            ASSERT(!pcn->call->is_last());

            slist_iter s(tmpt);
            ElemTmp *t;
            while ((t = (ElemTmp*)s.next()) != 0 && t->spos > fn)
                t->spos = fn;

            CallData *cproc = pcn->call;
            cn = ps->pop(cn - fn) - 1;
            PCN->call = cproc->next();
            fn = pcn->father;

            goto A2;
        }

        pcn->trail = ts->curr_dim();
        pcn->vspos = pfn->vspos;
    }
    goto A1;

    case CallData::DISJUNCT:            // replace with catenated try
        pcn->vspos = pfn->vspos;
        pcn->trail = ts->curr_dim();
        cn = ps->push(fn);
        PCN->call = cc->next();         // left side
        goto A2;

    case CallData::DBPRED:

        // initialize DB search
        pcn->dbpos = db->StartProc(cc->get_dbe());

        // DB matching & unification
B:  if (pcn->dbpos && (q = pcn->dbpos->get()) != 0) {

            unsigned nvars = q->get_nvars();
            pcn->vspos = vs->reserve(nvars);
            pcn->trail = ts->curr_dim();

            /*
   if (!unify(  pfn->vspos, cc->args(),
      pcn->vspos, q->h_args(), q->h_arity()))
   */
            if (q->h_arity() > 0) {
                TermArgs pa1 = cc->args(),
                        pa2 = q->h_args();

                us.clear();
                for (int i = q->h_arity() - 1; i > 0; i--) {
                    UnifyStack::termPair *tp = us.push();
                    tp->t1 = pa1.getarg(i);
                    tp->i1 = pfn->vspos;
                    tp->t2 = pa2.getarg(i);
                    tp->i2 = pcn->vspos;
                }
                us.check_overflow();

                if (!us.work(   pa1.getarg(0), pfn->vspos,
                                pa2.getarg(0), pcn->vspos))
                {
                    // undo changes
                    unbind(pcn->trail);
                    vs->pop(nvars);

                    // try next match
                    pcn->dbpos = pcn->dbpos->succ(db);
                    goto B;
                }
            }

            fn = cn;
            goto A;
        }
        break;

    default:
        ASSERT(0);
    }

    if (tr && PCN->call && tr->fail(cn, cc))
        return -1;

    // backtracking
C1: query_fail(ps->curr_dim() - cn);

    // resume top query
C:  cn = ps->curr_dim() - 1;
    unbind(PCN->trail);

C2: if ((fn = pcn->father) == STKNULL)
        return 0;

    if ((cc = pcn->call) == 0)
        goto C1;

    switch (cc->get_type()) {

    case CallData::CUT:  {      // change satisfaction path up to father
        stkpos fvp = PFN->vspos;
        query_fail(cn - fn + 1);
        if ((cn = ps->curr_dim() - 1) != STKNULL) {
            unbind(PCN->trail);
            vs->pop(vs->curr_dim() - fvp);
            goto C2;
        }
        return 0;
    }

    case CallData::BUILTIN: {   // check builtins retry
        BuiltIn *btp = cc->get_builtin();

        if (btp->args & BuiltIn::retry) {

            if (tr && tr->redo(cn, cc))
                return -1;

            // could be resatisfied
            pcn->trail = ts->curr_dim();
            pcn->vspos = PFN->vspos;

            // if evaluate OK
            if (btp->eval(cc->args(), this, 1))
                goto A1;
        }

        // failed
        goto C1;
    }

    case CallData::DISJUNCT:    // evaluate right side
        if (tr && tr->redo(cn, cc))
            return -1;

        pcn->call = cc->get_orelse();
        goto A2;

    case CallData::DBPRED:      // a DB query node to retry
        if (tr) {   // display REDOs (TBD)
            if (pcn->dbpos && pcn->dbpos->succ(db) && tr->redo(cn, cc))
                return -1;
        }
        vs->pop(vs->curr_dim() - pcn->vspos);
        pcn->dbpos = pcn->dbpos->succ(db);
        PFN;
        goto B;

    default:
        ASSERT(0);
    }

    return -1;
}

now I'm not very proud of that code: instead of ABC I ended up (by means of rather painful debugging) to an A-A1-A2 B C1-C-C2.

edit: I placed the complete interpreter sources in github.

Answer 3

You can start by checking the answers to this question.

You can also check the source of various open-source prolog implementations (gnu prolog, swi-prolog, yap prolog and more) (although this might be too complicated if you just want a "naive" implementation or some prolog-like features like backtracking).

Finally you should check the prolog ISO.

Having said that, if you are interested in combining C and prolog there are some interfaces you can use; I don't think that implementing an (efficient) prolog is a trivial task, especially if we consider that there are (surprisingly) many companies/organizations dedicated to it.

Answer 4

You might also be interested in looking at Mike Spivey's An Introduction to Logic Programming through Prolog. Both the full text of the book as well as an implementation of a simplified Prolog are available at the previous link (Note: the implementation itself is written in a minimal Pascal dialect, but for compilation this is translated into C. According to the author, this minimal Pascal dialect is more or less the "intersection of Pascal and C", anyway---whatever that means, so while not strictly satisfying the criteria, it should be quite useful for learning about Prolog).

I also noticed Alan Mycroft's Logic Programming and Functional Nets, following this link you will find a Prolog interpreter in C++, but I don't know much about it.