From d5ce41f05bc322fa2fb4d0eee66080b3b3004853 Mon Sep 17 00:00:00 2001 From: Peter Mikkelsen Date: Wed, 30 Jun 2021 00:07:49 +0000 Subject: Start work on an evaluator. For now it knows how to unify but doesn't know how to handle builtin predicates or how to backtrack --- eval.c | 213 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ example.pl | 2 + fns.h | 6 +- main.c | 5 +- misc.c | 14 ++++ mkfile | 2 +- 6 files changed, 237 insertions(+), 5 deletions(-) create mode 100644 eval.c diff --git a/eval.c b/eval.c new file mode 100644 index 0000000..e04963f --- /dev/null +++ b/eval.c @@ -0,0 +1,213 @@ +#include +#include + +#include "dat.h" +#include "fns.h" + +typedef struct Binding Binding; +typedef struct Goal Goal; + +struct Binding +{ + Rune *name; + Term *value; + Binding *next; +}; + +struct Goal +{ + Term *goal; + Goal *next; +}; + +Goal *addgoals(Goal *, Term *); +Term *findclause(Term *, Term *, Binding **); +int unify(Term *, Term *, Binding **); +int equalterms(Term *, Term *); +void applybinding(Term *, Binding *); + +void +evalquery(Term *database, Term *query) +{ + Goal *goals = addgoals(nil, query); + + while(goals != nil){ + Term *goal = goals->goal; + goals = goals->next; + + if(goal == nil){ + print("Done with body\n"); + continue; + } + + print("Solving goal %S\n", prettyprint(goal)); + + /* Find a clause where the head unifies with the goal */ + Binding *bindings = nil; + Term *clause = findclause(database, goal, &bindings); + if(clause != nil){ + print("Solving it using clause %S with new bindings: ", prettyprint(clause)); + Binding *b; + for(b = bindings; b != nil; b = b->next){ + print("%S = %S ", b->name, prettyprint(b->value)); + } + print("\n"); + /* Apply bindings to all goals on the top of the stack, down to the "bodystart" goal */ + Goal *g; + for(g = goals; g != nil && g->next != nil; g = g->next) + applybinding(g->goal, bindings); + + /* Add clause body as goals, with bindings applied */ + if(clause->tag == CompoundTerm && clause->arity == 2 && runestrcmp(clause->text, L":-") == 0){ + Goal *bodystart = malloc(sizeof(Goal)); + bodystart->goal = nil; + bodystart->next = goals; + goals = bodystart; + + Term *subgoal = copyterm(clause->children->next); + applybinding(subgoal, bindings); + goals = addgoals(goals, subgoal); + } + }else{ + print("No clause unifies with the goal, backtracking...(not really yet haha)\n"); + } + } +} + +Goal * +addgoals(Goal *goals, Term *t) +{ + if(t->tag == CompoundTerm && runestrcmp(t->text, L",") == 0 && t->arity == 2){ + goals = addgoals(goals, t->children->next); + goals = addgoals(goals, t->children); + }else{ + Goal *g = malloc(sizeof(Goal)); + g->goal = t; + g->next = goals; + print("Added goal: %S\n", prettyprint(t)); + goals = g; + } + return goals; +} + +Term * +findclause(Term *database, Term *goal, Binding **bindings) +{ + Term *clause; + for(clause = database; clause != nil; clause = clause->next){ + Term *head; + if(clause->tag == CompoundTerm && runestrcmp(clause->text, L":-") == 0 && clause->arity == 2) + head = clause->children; + else + head = clause; + + if(unify(head, goal, bindings)) + return clause; + } + return nil; +} + +int +unify(Term *a, Term *b, Binding **bindings) +{ + Term *leftstack; + Term *rightstack; + Term *left; + Term *right; + + *bindings = nil; + leftstack = copyterm(a); + rightstack = copyterm(b); + + while(leftstack != nil && rightstack != nil){ + left = leftstack; + leftstack = left->next; + right = rightstack; + rightstack = right->next; + + print("Unifying:\n\t%S\n\t%S\n", prettyprint(left), prettyprint(right)); + if(equalterms(left, right)) + continue; + else if(left->tag == VariableTerm || right->tag == VariableTerm){ + if(right->tag == VariableTerm){ + Term *tmp = left; + left = right; + right = tmp; + } + Binding *b = malloc(sizeof(Binding)); + b->name = left->text; + b->value = right; + b->next = *bindings; + *bindings = b; + Term *t; + for(t = leftstack; t != nil; t = t->next) + applybinding(t, b); + for(t = rightstack; t != nil; t = t->next) + applybinding(t, b); + Binding *tmpb; + for(tmpb = *bindings; tmpb != nil; tmpb = tmpb->next) + applybinding(tmpb->value, b); + }else if(left->tag == CompoundTerm && right->tag == CompoundTerm && left->arity == right->arity && runestrcmp(left->text, right->text) == 0){ + Term *leftchild = left->children; + Term *rightchild = right->children; + while(leftchild != nil && rightchild != nil){ + Term *t1 = copyterm(leftchild); + t1->next = leftstack; + leftstack = t1; + leftchild = leftchild->next; + + Term *t2 = copyterm(rightchild); + t2->next = rightstack; + rightstack = t2; + rightchild = rightchild->next; + } + }else + return 0; /* failure */ + } + return 1; +} + +int +equalterms(Term *a, Term *b) +{ + /* Check that two non-compound terms are identical */ + if(a->tag != b->tag) + return 0; + + switch(a->tag){ + case AtomTerm: + case VariableTerm: + case StringTerm: + return !runestrcmp(a->text, b->text); + case NumberTerm: + if(a->numbertype != b->numbertype) + return 0; + if(a->numbertype == NumberInt && a->ival == b->ival) + return 1; + if(a->numbertype == NumberFloat && a->dval == b->dval) + return 1; + return 0; + default: + return 0; + } +} + +void +applybinding(Term *t, Binding *bindings) +{ + if(t->tag == VariableTerm){ + Binding *b; + for(b = bindings; b != nil; b = b->next){ + if(runestrcmp(t->text, b->name) == 0){ + Term *next = t->next; + memcpy(t, b->value, sizeof(Term)); + t->next = next; + return; + } + } + }else if(t->tag == CompoundTerm){ + Term *child; + for(child = t->children; child != nil; child = child->next) + applybinding(child, bindings); + } +} \ No newline at end of file diff --git a/example.pl b/example.pl index 8f5f0c2..bf30ba6 100644 --- a/example.pl +++ b/example.pl @@ -23,4 +23,6 @@ list2(A) :- A = [a,b|c]. curly(A) :- A = {one,two,three}. +=(A,A). + :- initialization(could_be_friends(bob, sam)). \ No newline at end of file diff --git a/fns.h b/fns.h index 81a2f08..70a1d96 100644 --- a/fns.h +++ b/fns.h @@ -5,9 +5,13 @@ Term *parse(int); Rune *prettyprint(Term *); /* misc.c */ +Term *copyterm(Term *); Term *appendterm(Term *, Term *); int termslength(Term *); Term *mkatom(Rune *); Term *mkvariable(Rune *); Term *mkcompound(Rune *, int, Term *); -Term *mknumber(int, vlong, double); \ No newline at end of file +Term *mknumber(int, vlong, double); + +/* eval.c */ +void evalquery(Term *, Term *); \ No newline at end of file diff --git a/main.c b/main.c index 10ccec9..106e6ff 100644 --- a/main.c +++ b/main.c @@ -35,9 +35,8 @@ main(int argc, char *argv[]) print("%S.\n", prettyprint(clause)); Term *goal; - for(goal = initgoals; goal != nil; goal = goal->next){ - print("Running query: %S\n", prettyprint(goal)); - } + for(goal = initgoals; goal != nil; goal = goal->next) + evalquery(prog, goal); } exits(nil); diff --git a/misc.c b/misc.c index dcd5e17..28ba45c 100644 --- a/misc.c +++ b/misc.c @@ -4,6 +4,20 @@ #include "dat.h" #include "fns.h" +Term * +copyterm(Term *orig) +{ + Term *new = malloc(sizeof(Term)); + memcpy(new, orig, sizeof(Term)); + new->next = nil; + new->children = nil; + + Term *child; + for(child = orig->children; child != nil; child = child->next) + new->children = appendterm(new->children, copyterm(child)); + return new; +} + Term * appendterm(Term *a, Term *b) { diff --git a/mkfile b/mkfile index 0e6af56..0196090 100644 --- a/mkfile +++ b/mkfile @@ -2,7 +2,7 @@ TARG=pprolog -OFILES=main.$O parser.$O prettyprint.$O misc.$O +OFILES=main.$O parser.$O eval.$O prettyprint.$O misc.$O HFILES=dat.h fns.h -- cgit v1.2.3