StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Some time ago I wrote a Prolog interpreter in C++ (really, my first C++ program), and followed a different approach instead of the (now nearly ubiquitous) WAM. Our teacher at course of languages and compilers construction talked about an ABC algorithm, and I implemented that (I goggled 'Prolog implementation ABC algorithm', <a href="https://cs.uwaterloo.ca/research/tr/1984/CS-84-47.pdf">here</a> a PDF that I found, but I don't know - yet) : here the core solver</p> <pre><code>//-------------------------- // 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; } </code></pre> <p>now I'm not very proud of that code: instead of ABC I ended up (by means of rather painful debugging) to an A-A1-A2 B C1-C-C2.</p> <p><em>edit</em>: I placed the complete interpreter <a href="https://github.com/CapelliC/IL">sources</a> in github. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload