Реализация Пролога в C или переполнение стека
Мне было интересно, как будет выглядеть реализация Prolog в C или C ++. Я в основном заинтересован в том, чтобы создать ее как библиотеку C или C ++, хотя приложение-интерпретатор тоже подойдет. Я заинтересован в чтении его внутренних компонентов, а именно выполнения запросов, то есть поиска решений и соответствующих типов данных. Я был бы рад, если бы вы порекомендовали мне какие-либо чтения по теме или любые прямые предложения / советы. Показания могут быть для других языков ООП или для общего ООП, а также. Самый утомительный материал решит вопрос.
Решение
Если вы хотите увидеть, как систему Prolog, реализованную на C, можно использовать из C / C ++ в качестве библиотеки, посмотрите на SWI-Prolog. Он предлагает полностью двунаправленный интерфейс, включая недетерминированность для Unix / Mac / Window — и многое, многое другое. Думать о ограничения.
С другой стороны, вы спрашиваете также о его фактической реализации. Есть два способа приблизиться к этому. Вы можете начать с самого низа и повышать свой уровень до уровня. Или вы можете начать с Пролога и начать с мета-интерпретаторов, которые реализуют Пролог в Прологе. От этого вы можете медленно копаться в крови.
Традиционный подход состоял в том, чтобы сначала начать с самых нижних вопросов, изучая различные абстрактные машины. Наиболее часто упоминается WAM (абстрактная машина Уоррена), а затем есть
Альтернативы WAM
Вы не должны пропустить. Будьте готовы, что это займет долгий путь от этого до работы Внедрение ISO. Есть много вопросов, которые только кратко рассматриваются в литературе, такие как сборка мусора и ограничения. Тем не менее, они необходимы для надежной реализации.
Другой подход — сначала изучить Пролог, а затем подробно изучить мета-интерпретаторы. Таким образом, вы можете научиться видеть Пролог с совершенно другой точки зрения. И вы также можете получить понимание, которое вы не получите иначе. Вы можете начать с классического мета-интерпретатора из трех пунктов, который использует большую часть функций Пролога. В зависимости от вашего интереса, вы можете начать реализацию его частей. Приятно то, что вы платите (с точки зрения размера кода) почти только за те части, которые хотите копать, и повторно используете другие части языка.
По крайней мере, в прошлом этот подход привел к различным новым методам реализации, например, ограничения, Erlang, Бинарный Пролог все существовал сначала как «простой» мета-интерпретатор. Только тогда, после понимания языковых проблем, фактические реализации были сделаны.
Есть также еще один момент в пользу начала с Пролога в первую очередь: что произойдет, если вы остановите свои усилия прямо в середине? При подходе «снизу вверх» вы получаете набор несуществующего кода. Для второго подхода вы выучили пролог.
Другие решения
Некоторое время назад я написал интерпретатор Prolog на C ++ (на самом деле, моя первая программа на C ++) и следовал другому подходу вместо (теперь почти повсеместного) WAM. Наш учитель на курсе построения языков и компиляторов говорил об алгоритме ABC, и я реализовал его (я поглядел на «алгоритм 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.
Вы можете начать с проверки ответов на этот вопрос.
Вы также можете проверить источник различных реализаций пролога с открытым исходным кодом (пролог gnu, swi-prolog, пролог yap и т. Д.) (Хотя это может быть слишком сложно, если вы просто хотите «наивную» реализацию или некоторые прологоподобные функции, такие как обратное отслеживание) ).
Наконец, вы должны проверить пролог ISO.
Сказав это, если вы заинтересованы в сочетании C и пролога, есть несколько интерфейсов, которые вы можете использовать; Я не думаю, что внедрение (эффективного) пролога является тривиальной задачей, особенно если учесть, что (удивительно) много компаний / организаций, посвященных этому.
Вам также может быть интересно посмотреть на Майка Спиви Введение в логическое программирование через пролог. Как полный текст книги, так и реализация упрощенного Пролога доступны по предыдущей ссылке (Примечание: сама реализация написана на минимальном диалекте Паскаля, но для компиляции это переводится на C. По словам автора, этот минимальный диалект Паскаля является более или менее «пересечением Паскаля и С», во всяком случае — что бы это ни значило, поэтому, хотя оно и не строго удовлетворяет критериям, оно должно быть весьма полезно для изучения Пролога).
Я также заметил Алана Майкрофта Логическое программирование и функциональные сети, перейдя по этой ссылке, вы найдете интерпретатор Prolog в C ++, но я не знаю много об этом.