我想知道在C或C++中实现Prolog会是什么样子。我主要希望将其构建为C或C++库，虽然解释器应用程序也可以。我对了解其内部运作很感兴趣，尤其是查询执行，即查找解决方案和涉及的相关数据类型。如果您可以推荐有关此主题的任何阅读材料或直接建议/建议，我将不胜感激。阅读材料可能适用于其他OOP语言或一般OOP。最详尽的材料将解决问题。
在C或C++中实现Prolog
16
- yauser
4
8大多数 Prolog 实现都是用 C 或 C++ 编写的吗？ - Carl Norum
1GNU Prolog 是用 C 语言编写的 Prolog 开源实现。你可以下载源代码并查看 :-) 希望这能帮到你。 - Claudi
1我打赌你会从沃伦的抽象机：教程重建中获得很多收获，该书讨论了如何在过程式语言中实现Prolog。 - Daniel Lyons
1这并不是Prolog，但如果你倾向于最大化C++的效率，Castor似乎是一个值得检查的宝贵资源。 - CapelliC
4个回答
20
如果你想看看用C实现的Prolog系统如何作为库从C/C++中使用，那么可以看看SWI-Prolog。它提供了完全双向的接口，包括Unix/Mac/Window的非确定性等等。考虑约束。
另一方面，你也在询问它的实际实现。有两种方法来处理这个问题。你可以从底层开始，逐级向上工作。或者你可以从Prolog开始，使用实现Prolog的元解释器。从这里开始，你可以慢慢地深入了解。
传统方法是先从最基础的问题开始，研究各种抽象机。其中最常被引用的是WAM（Warren Abstract Machine），还有一些你不应该错过的WAM替代方案。请准备好，从这里到一个可工作的ISO实现还有很长的路要走。文献中只涉及到一些表面问题，比如垃圾回收和约束条件，但它们对于一个强大的实现是必需的。
另一种方法是先学习Prolog，然后详细研究元解释器。通过这种方式，您可能会完全从不同的角度看待Prolog。您也可能会获得其他方法无法获得的见解。您可以从经典的三条子句元解释器开始，该元解释器重复使用了Prolog的大部分功能。根据您的兴趣，您可以开始具体化其中的某些部分。好处是，您几乎只为您想深入挖掘和重用语言的部分付出代码大小的代价。
至少在过去，这种方法导致了各种新的实现技术，例如约束、Erlang、二进制Prolog都是首先作为“简单”的元解释器存在的。只有在理解了语言问题之后，才进行了实际的实现。
此外，还有另一个支持从Prolog开始的观点：如果你在中途停止努力会发生什么？使用自下而上的方法，你最终会得到一堆无效的代码。而对于第二种方法，你已经学会了Prolog。
另一方面，你也在询问它的实际实现。有两种方法来处理这个问题。你可以从底层开始，逐级向上工作。或者你可以从Prolog开始，使用实现Prolog的元解释器。从这里开始，你可以慢慢地深入了解。
传统方法是先从最基础的问题开始，研究各种抽象机。其中最常被引用的是WAM（Warren Abstract Machine），还有一些你不应该错过的WAM替代方案。请准备好，从这里到一个可工作的ISO实现还有很长的路要走。文献中只涉及到一些表面问题，比如垃圾回收和约束条件，但它们对于一个强大的实现是必需的。
另一种方法是先学习Prolog，然后详细研究元解释器。通过这种方式，您可能会完全从不同的角度看待Prolog。您也可能会获得其他方法无法获得的见解。您可以从经典的三条子句元解释器开始，该元解释器重复使用了Prolog的大部分功能。根据您的兴趣，您可以开始具体化其中的某些部分。好处是，您几乎只为您想深入挖掘和重用语言的部分付出代码大小的代价。
至少在过去，这种方法导致了各种新的实现技术，例如约束、Erlang、二进制Prolog都是首先作为“简单”的元解释器存在的。只有在理解了语言问题之后，才进行了实际的实现。
此外，还有另一个支持从Prolog开始的观点：如果你在中途停止努力会发生什么？使用自下而上的方法，你最终会得到一堆无效的代码。而对于第二种方法，你已经学会了Prolog。
- false
8
前段时间，我用C++编写了一个Prolog解释器（实际上是我的第一个C++程序），并采用了一种不同的方法，而不是现在几乎无处不在的WAM。我们的语言和编译器构造课程老师谈到了ABC算法，我实现了这个算法（我搜索了“Prolog implementation ABC algorithm”，这里是我找到的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;
}
现在我对那段代码并不感到自豪：通过非常痛苦的调试，我最终得到了一个A-A1-A2 B C1-C-C2的结果，而不是ABC。
编辑：我已经将完整的解释器源代码放在了GitHub上。
- CapelliC
4
2你的出现检查在哪里？ ;) - Daniel Lyons
抱歉，不可用 - 统一在单独的模块中，我希望明天能够将完整源代码放入GitHub。 - CapelliC
1那很酷，但我只是和你开玩笑。 :) - Daniel Lyons
@DanielLyons：对出现检查感兴趣吗？SWI有它，但对于（可信）少见情况它仍然没有完美的定义/实现。 - false
4
你可以先查看这个问题的答案。
你也可以查看各种开源 Prolog 实现的源代码（GNU Prolog、SWI-Prolog、YAP Prolog 等）。但如果你只想要一个“天真”的实现或一些类似于 Prolog 的功能，那可能会比较复杂。
最后，你应该查阅 Prolog 国际标准 ISO。
话虽如此，如果你有兴趣将 C 和 Prolog 结合起来，可以使用一些接口。我认为实现（高效）Prolog 并不是一项轻松的任务，特别是当我们考虑到有（惊人地）许多公司/组织专门从事这项工作时。
你也可以查看各种开源 Prolog 实现的源代码（GNU Prolog、SWI-Prolog、YAP Prolog 等）。但如果你只想要一个“天真”的实现或一些类似于 Prolog 的功能，那可能会比较复杂。
最后，你应该查阅 Prolog 国际标准 ISO。
话虽如此，如果你有兴趣将 C 和 Prolog 结合起来，可以使用一些接口。我认为实现（高效）Prolog 并不是一项轻松的任务，特别是当我们考虑到有（惊人地）许多公司/组织专门从事这项工作时。
- Thanos Tintinidis
3
你可能也会对Mike Spivey的通过Prolog入门逻辑编程感兴趣。书籍的全文以及一个简化版的Prolog实现都可以在上述链接中找到（注意：该实现本身是用一种最小的Pascal方言编写的，但为了编译它会被翻译成C。根据作者的说法，这种最小的Pascal方言更或多或少地是“Pascal和C的交集”，无论如何---不完全符合标准，但对于学习Prolog应该非常有用）。
我还注意到Alan Mycroft的逻辑编程和函数网络，点击该链接，你会发现一个用C++编写的Prolog解释器，但我不太了解它。
我还注意到Alan Mycroft的逻辑编程和函数网络，点击该链接，你会发现一个用C++编写的Prolog解释器，但我不太了解它。
- godfatherofpolka
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接