Внедрение Prolog в C или С++

Ответ 1

Если вы хотите увидеть, как система Prolog, реализованная на C, может быть использована из C/С++ в качестве библиотеки, посмотрите SWI-Prolog. Он предлагает полностью двунаправленный интерфейс, включая недетерминизм для Unix/Mac/Window — и многое, многое другое. Подумайте о ограничениях.

С другой стороны, вы также спрашиваете о его фактической реализации. Есть два способа приблизиться к этому. Вы можете начать с самого дна и самостоятельно работать на уровне уровня. Или вы можете начать с Prolog и начать с мета-интерпретаторов, которые реализуют Prolog в Prolog. Из этого вы можете медленно копаться в крови.

Традиционный подход состоял в том, чтобы начать сначала с самых нижних проблем, изучая различные абстрактные машины. Наиболее часто упоминается WAM (Warren Abstract Machine), а затем есть Альтернативы WAM вы не должны пропустить. Будьте готовы к тому, что это займет много времени от рабочей работы ISO. В литературе есть много вопросов, которые в литературе можно использовать только в том виде, как сбор мусора и ограничения. Тем не менее, они необходимы для надежной реализации.

Другой подход - сначала изучить Prolog, а затем детально изучить мета-интерпретаторы. Таким образом, вы можете научиться видеть Prolog с совершенно другой точки зрения. И вы также можете получить информацию о том, что вы не получите иначе. Вы можете начать с мета-интерпретатора классического трехпозиционного предложения, который повторно использует многие функции Prolog. В зависимости от вашего интереса вы можете начать его повторять. Самое приятное, что вы платите (с точки зрения размера кода) почти только для частей, которые хотите копать и повторно использовать другие части языка.

По крайней мере, в прошлом этот подход привел к различным новым методам внедрения, например. ограничения Erlang, двоичный пролог все существовал сначала как "простой" мета-интерпретатор. Только после понимания языковых проблем были выполнены фактические реализации.

Есть еще один момент в пользу начинать с Prolog в первую очередь: что происходит, если вы остановите свое усилие прямо посередине? При подходе снизу вверх вы получаете коллекцию несуществующего кода. Для второго подхода вы узнали Prolog.

Ответ 2

Некоторое время назад я написал интерпретатор Prolog в С++ (на самом деле, свою первую программу на С++) и использовал другой подход вместо (теперь почти вездесущего) WAM. Наш преподаватель по курсу развития языков и компиляторов рассказал об алгоритме ABC, и я реализовал это (я изучил "алгоритм ABC реализации ABL", здесь в PDF, который я нашел, но пока не знаю): вот главный решатель

//--------------------------
// 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;
}

теперь я не очень горжусь этим кодом: вместо ABC я закончил (посредством довольно болезненной отладки) A-A1-A2 B C1-C-C2.

edit: я поместил полный интерпретатор sources в github.

Ответ 3

Вы можете начать с проверки ответов на этот вопрос.

Вы также можете проверить источник различных реализаций пролога open-source (gnu prolog, swi-prolog, yap prolog и т.д.) (хотя это может быть слишком сложно, если вам просто нужна "наивная" реализация или какой-то пролог-подобный такие как backtracking).

Наконец, вы должны проверить пролог ISO.

Сказав это, если вы заинтересованы в объединении C и пролога, вы можете использовать некоторые интерфейсы; Я не думаю, что реализация (эффективного) пролога - тривиальная задача, особенно если учесть, что есть (удивительно) многие компании/организации, посвященные этому.

Ответ 4

Вам также может быть интересно посмотреть на Майка Спайви Введение в программирование логики через Prolog. Как полный текст книги, так и реализация упрощенного Prolog доступны по предыдущей ссылке (Примечание: сама реализация написана на минимальном диалекте Паскаля, но для компиляции это переводится на C. Согласно автору, этот минимальный диалект Паскаля является более или менее "пересечением Паскаля и С", в любом случае - независимо от того, что это означает, поэтому, не строго соблюдая критерии, он должен быть весьма полезен для изучения Пролога).

Я также заметил, что Alan Mycroft Логическое программирование и функциональные сети, следуя этой ссылке, вы найдете интерпретатор Prolog на С++, но я не Знайте об этом много.