Implémentation de Prolog en C ou C ++

Je me demandais à quoi ressemblerait l’implémentation de Prolog en C ou C ++. Je suis principalement intéressé par sa construction en tant que bibliothèque C ou C ++, bien que l’application interprète puisse également le faire. Je suis intéressé par la lecture de ses composants internes, à savoir l’exécution des requêtes, c’est-à-dire la recherche des solutions et des types de données associés impliqués. Je serais heureux si vous me recommandiez des lectures sur le sujet ou des suggestions / conseils directs. Les lectures peuvent s’appliquer à d’autres langues POO ou à la POO générale. La plupart des matériaux épuisants résoudront la question.

Si vous voulez voir comment un système Prolog implémenté en C peut être utilisé à partir de C / C ++ en tant que bibliothèque, consultez SWI-Prolog . Il offre une interface complètement bidirectionnelle incluant le non-déterminisme pour Unix / Mac / Window – et bien plus encore. Pensez aux contraintes .

D’autre part, vous vous interrogez également sur sa mise en œuvre réelle. Il y a deux façons d’aborder cela. Vous pouvez soit commencer par le bas et travailler vous-même d’un niveau à l’autre. Ou vous pouvez commencer avec Prolog, et commencer avec les méta-interprètes qui implémentent Prolog dans Prolog. De là, vous pouvez creuser lentement dans le sang.

L’approche traditionnelle consistait à commencer par les questions fondamentales, à savoir les différentes machines abstraites. Le plus souvent cité est le WAM (Warren Abstract Machine) et il existe des alternatives au WAM à ne pas manquer. Préparez-vous au fait qu’il faudra beaucoup de temps pour que l’ implémentation ISO fonctionne correctement . Il existe de nombreuses questions qui ne sont que sommairement traitées dans la littérature, telles que le ramassage des ordures et les contraintes. Pourtant, ils sont nécessaires pour une mise en œuvre robuste.

L’autre approche consiste à apprendre d’abord Prolog, puis à étudier les méta-interprètes en détail. De cette manière, vous pourriez apprendre à voir Prolog sous un angle totalement différent. Et vous pourriez aussi acquérir des idées que vous ne pourriez pas obtenir autrement. Vous pouvez commencer avec le méta-interprète classique à trois clauses, qui réutilise une grande partie des fonctionnalités de Prolog. Selon votre intérêt, vous pourrez alors commencer à en modifier certaines parties. La bonne chose est que vous payez (en termes de taille de code) presque uniquement pour les parties que vous souhaitez creuser et réutilisez les autres parties de la langue.

Au moins dans le passé, cette approche a conduit à diverses nouvelles techniques de mise en œuvre, telles que les contraintes, Erlang , Prolog binary, existaient toutes en tant que méta-interprètes “simples”. Ensuite, après avoir compris les problèmes de langue, les mises en œuvre réelles ont été effectuées.

Il y a aussi un autre point en faveur de commencer par Prolog d’abord: que se passera-t-il si vous arrêtez vos efforts en plein milieu? Avec l’approche ascendante, vous vous retrouvez avec une collection de code obsolète. Pour la deuxième approche, vous avez appris Prolog.

Il y a quelque temps, j’ai écrit un interpréteur Prolog en C ++ (en fait, mon premier programme C ++) et suivi une approche différente du WAM (maintenant presque omniprésent). Notre enseignant de cours de langue et de construction de compilateurs a parlé d’un algorithme ABC, que j’ai implémenté (j’ai gogglé ‘l’algorithme Prolog implementation ABC’, ici un PDF que j’ai trouvé, mais que je ne connais pas encore): voici le solveur principal

//-------------------------- // 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 unsortinged 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 unsortinged 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; } 

maintenant, je ne suis pas très fier de ce code: au lieu d’ABC, j’ai fini (par un débogage plutôt pénible) en A-A1-A2 B C1-C-C2.

edit : J’ai placé les sources d’ interprétation complètes dans github.

Vous pouvez commencer par vérifier les réponses à cette question .

Vous pouvez également vérifier la source de différentes implémentations de prolog open-source (gnu prolog, swi-prolog, yap prolog, etc.) (bien que cela puisse être trop compliqué si vous voulez juste une implémentation “naïve” ou des fonctionnalités de type prolog comme le backtracking ).

Enfin, vous devriez vérifier l’ISO du prolog.

Cela dit, si vous souhaitez combiner C et Prolog, vous pouvez utiliser certaines interfaces. Je ne pense pas que la mise en place d’un prolog (efficace) soit une tâche sortingviale, surtout si l’on considère qu’il existe (de manière surprenante) de nombreuses sociétés / organisations dédiées à cette tâche.

Vous pourriez également être intéressé par une introduction à la programmation logique par Prolog de Mike Spive. Le texte complet du livre ainsi qu’une implémentation d’un prolog simplifié sont disponibles sur le lien précédent (Remarque: l’implémentation elle-même est écrite dans un dialecte pascal minimal, mais pour la compilation, elle est traduite en C. Selon l’auteur, ce dialecte de Pascal minimal est plus ou moins “l’intersection de Pascal et de C”, quoi qu’il en soit signifie que, même s’il ne satisfait pas ssortingctement aux critères, il devrait être très utile pour en savoir plus sur Prolog).

J’ai également remarqué la programmation logique et les réseaux fonctionnels d’ Alan Mycroft. En suivant ce lien, vous trouverez un interpréteur Prolog en C ++, mais je n’en sais pas beaucoup.