我想知道 C 或 C++ 中的 Prolog 实现会是什么样子。我主要对将其构建为 C 或 C++ 库感兴趣，尽管解释器应用程序也可以。我有兴趣阅读它的内部结构，即查询执行，即找到解决方案和相关的数据类型。如果您向我推荐任何有关主题的读物或任何直接的建议/建议，我会很高兴。读数可能适用于其他 OOP 语言或一般 OOP。大多数令人筋疲力尽的材料将解决这个问题。
问问题
14004 次
4 回答
18
如果您想了解在 C/C++ 中如何将用 C 实现的 Prolog 系统用作库，请查看SWI-Prolog。它提供了一个完全双向的接口，包括 Unix/Mac/Window 的非确定性——等等。想想约束。
另一方面，您也在询问其实际实施。有两种方法可以解决这个问题。您可以从最底层开始，逐步提高自己的水平。或者你可以从 Prolog 开始，从在 Prolog 中实现 Prolog 的元解释器开始。从这里你可以慢慢挖掘到血块。
传统的方法是首先从最底层的问题开始，研究各种抽象机器。最常被引用的一种是 WAM（沃伦抽象机），然后是 您不应该错过的 WAM 的替代品。做好准备，从这到一个有效的ISO 实施将需要很长的路要走。有许多问题在文献中只是粗略地处理，例如垃圾收集和约束。然而，它们是稳健实施所必需的。
另一种方法是先学习 Prolog，然后详细研究元解释器。通过这种方式，您可能会学会从完全不同的角度看待 Prolog。而且您可能还会获得其他方式无法获得的见解。你可以从经典的三子句元解释器开始，它重用了 Prolog 的大部分功能。然后，根据您的兴趣，您可以开始具体化其中的一部分。好消息是您（就代码大小而言）几乎只为您想要挖掘的部分付费并重用该语言的其他部分。
至少在过去，这种方法导致了各种新的实现技术，例如约束、Erlang、二进制 Prolog 都首先作为“简单”元解释器存在。只有这样，在理解了语言问题之后，才完成了实际的实现。
还有一点支持先从 Prolog 开始：如果你在它中间停止努力，会发生什么？使用自下而上的方法，您最终会得到一组已失效的代码。对于第二种方法，您已经学习了 Prolog。
于 2013-01-26T10:31:36.250 回答
8
前段时间，我用 C++（真的，我的第一个 C++ 程序）编写了一个 Prolog 解释器，并采用了不同的方法，而不是（现在几乎无处不在的）WAM。我们的语言和编译器构建课程的老师谈到了一个 ABC 算法，我实现了它（我看到了“Prolog 实现 ABC 算法”，这里是我找到的 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。
编辑：我将完整的解释器源代码放在 github 中。
于 2013-01-25T20:15:37.730 回答
4
您可以从检查这个问题的答案开始。
您还可以检查各种开源 prolog 实现的来源（gnu prolog、swi-prolog、yap prolog 等）（尽管如果您只想要一个“幼稚”的实现或一些类似 prolog 的功能，例如回溯，这可能太复杂了）。
最后，您应该检查序言 ISO。
话虽如此，如果您对结合 C 和 prolog 感兴趣，可以使用一些接口；我不认为实施（有效的）序言是一项微不足道的任务，特别是如果我们考虑到（令人惊讶地）有许多公司/组织致力于它。
于 2013-01-25T18:11:10.997 回答
3
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.
于 2014-11-13T19:56:20.923 回答