我想知道Prolog在C或C++中的实现方式如何.我主要感兴趣的是将它构建为C或C++库,尽管解释器应用程序也可以.我有兴趣阅读它的内部,即查询执行,即查找解决方案和相关的数据类型.如果您向我推荐任何有关主题的阅读材料或任何直接建议/建议,我将很高兴.读数可能适用于其他OOP语言或一般OOP.最耗尽的材料将解决这个问题.
fal*_*lse 12
如果您想了解如何在C/C++中使用C语言实现的Prolog系统作为库,请查看SWI-Prolog.它提供了一个完全双向的界面,包括Unix/Mac/Window的非确定性 - 以及更多.想一想约束.
另一方面,您也在询问其实际实施情况.有两种方法可以解决这个问题.你可以从最底层开始,从一个级别到另一个级别自己动手.或者你可以从Prolog开始,然后从在Prolog中实现Prolog的元解释器开始.从这里你可以慢慢挖掘血腥.
传统的方法是首先从最底层的问题开始,研究各种抽象机器.最常被引用的是WAM(Warren抽象机器),然后有 WAM的替代品, 你不应该错过.做好准备,从这需要很长的路要走,才能实现ISO的实施.在垃圾收集和约束等文献中,有许多问题只能被轻易处理.然而,它们是强大实施所必需的.
另一种方法是首先学习Prolog,然后详细研究元解释器.通过这种方式,您可以从完全不同的角度学习Prolog.而且你也可能获得你不会得到的见解.您可以从经典的三句子元解释器开始,它重复使用Prolog的大部分功能.根据您的兴趣,您可以开始重新部分它.好处是你支付(代码大小)几乎只为你想要挖掘的部分和重用语言的其他部分.
至少在过去,这种方法导致了各种新的实现技术,例如约束,Erlang,二元Prolog都首先作为"简单"的元解释器存在.只有这样,在理解了语言问题之后,才进行了实际的实施.
另外还有一点赞成首先从Prolog开始:如果你在中间停止努力,会发生什么？使用自下而上的方法,您最终会得到一组已失效的代码.对于第二种方法,您已经学习了Prolog.
前段时间我用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中.
| 归档时间： |
|
| 查看次数： |
11700 次 |
| 最近记录： |