C または C++ での Prolog の実装はどのようになるのだろうと思っていました。私は主に、C または C++ ライブラリとしてビルドすることに関心がありますが、インタープリター アプリでもビルドできます。その内部、つまりクエリの実行、つまりソリューションと関連するデータ型を見つけることに興味があります。トピックに関する読み物や直接的な提案/アドバイスをお勧めしていただければ幸いです. 読み取りは、他の OOP 言語または一般的な OOP の場合もあります。ほとんどの消耗品は、質問を解決します。
14004 次
4 に答える
18
C で実装された Prolog システムを C/C++ からライブラリとして使用する方法を知りたい場合は、SWI-Prologを参照してください。Unix/Mac/Windows の非決定性を含む完全に双方向のインターフェイスを提供します。制約について考えてみましょう。
一方で、その実際の実装についても質問しています。これには 2 つの方法があります。一番下から始めて、レベルを上げていくことができます。または、Prolog から始めて、Prolog に Prolog を実装するメタインタープリターから始めることもできます。ここから、ゆっくりとマチを掘り下げることができます。
伝統的なアプローチは、さまざまな抽象的な機械を研究して、最初に一番下の問題から始めることでした。最も一般的に引用されるのは WAM (Warren Abstract Machine) であり、 見逃せないWAM の代替手段があります。これからISO の実装が機能するまでには長い道のりがかかることを覚悟しておいてください。ガベージ コレクションや制約など、文献ではざっとしか扱われていない問題がたくさんあります。それでも、堅牢な実装には必要です。
もう 1 つのアプローチは、最初に Prolog を学習し、次にメタインタープリターを詳細に学習することです。このようにして、Prolog をまったく異なる視点から見ることを学ぶことができます。また、他の方法では得られない洞察を得ることができます。Prolog の機能の多くを再利用する従来の 3 節メタインタープリターから始めることができます。興味に応じて、その一部を具体化することができます。良い点は、言語の他の部分を掘り下げて再利用したい部分に対してのみ (コードサイズに関して) 料金を支払うことです。
少なくとも過去には、このアプローチはさまざまな新しい実装技術につながりました。たとえば、制約、Erlang、バイナリ Prolog はすべて、最初は「単純な」メタインタープリターとして存在していました。その後、言語の問題を理解した後、実際の実装が行われました。
最初に Prolog から始めることを支持するもう 1 つのポイントもあります。途中で努力をやめるとどうなりますか? ボトムアップ アプローチでは、機能していないコードのコレクションができあがります。2 番目のアプローチでは、Prolog を学習しました。
于 2013-01-26T10:31:36.250 に答える
8
しばらく前に、私は C++ で Prolog インタープリターを作成し (実際、私の最初の C++ プログラムです)、(今ではほとんどどこにでもある) 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
この質問に対する回答を確認することから始めることができます。
また、さまざまなオープンソースのプロローグ実装 (gnu プロローグ、swi-prolog、yap プロローグなど) のソースを確認することもできます (ただし、「素朴な」実装やバックトラッキングなどのプロローグのような機能が必要な場合は、これは複雑すぎる可能性があります。 ）。
最後に、prolog ISO を確認する必要があります。
そうは言っても、C と Prolog の組み合わせに興味がある場合は、使用できるインターフェイスがいくつかあります。(効率的な) プロローグを実装することは、特に (驚くほど) 多くの企業/組織がそれに専念していることを考えると、簡単な作業ではないと思います。
于 2013-01-25T18:11:10.997 に答える
3
また、Mike Spivey のAn Introduction to Logic Programming through Prologにも興味があるかもしれません。本の全文と簡略化された Prolog の実装の両方が、前のリンクで入手できます (注: 実装自体は最小限の Pascal 方言で書かれていますが、コンパイルのために C に翻訳されています。著者によると、とにかく、この最小限の Pascal の方言は多かれ少なかれ「Pascal と C の共通部分」です --- それが何を意味するにせよ、そのため、基準を厳密に満たすわけではありませんが、Prolog について学ぶのに非常に役立つはずです)。
また、Alan Mycroft のLogic Programming and Functional Netsにも気付きました。このリンクをたどると、C++ で Prolog インタープリターが見つかりますが、それについてはあまり知りません。
于 2014-11-13T19:56:20.923 に答える