A Prolog Program for Bottom-up Evaluation
David S. Warren · 2025
Read A Prolog Program for Bottom-up Evaluation by David S. Warren (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09223.txt.
Introduction
Warren offers a short 2025 paper on a small Prolog program with an odd charm. The program reads logic rules and works out their meaning from the bottom up. It turns the rules into meta-rules, then uses them to build the full model step by step. The result works like the classic semi-naive method used in database logic.
Warren calls the piece a programming pearl, a small program worth study for its craft. He singles out its use of one Prolog feature that adds facts as it runs. In most programs he finds that feature murky, but here he calls it the clearest and best way to write the method. The paper is brief and written for logic programmers.
Catalog record
| CREATOR | David S. Warren |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-09223
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Prolog Program for Bottom-up Evaluation David S. Warren Abstract This short paper describes a simple and intuitive Prolog program, a metainterpreter, that computes the bottom up meaning of a simple positive Horn clause definition. It involves a simple transformation of the object program rules into metarules, which are then used by a metainterpreter to compute bottom up the model of the original program. The resulting algorithm is a form of semi-naive bottom-up evaluation. We discuss various reasons why this Prolog program is particularly interesting. In particular, this is perhaps the only Prolog program for which I find the use of Prolog’s assert/1 to be intrinsic, easily understood, and the best, most perspicuous, way to program an algorithm. This short paper might be best characterized as a Prolog programming pearl. 1 Introduction A positive Prolog program is an inductive definition of a set of relations over terms. There are two well-known basic ways to compute elements of relations that are defined in this way [ 3 ] , [ 6 ] : top-down [ 5 ] and bottom-up [ 2 ] . Top-down evaluation starts with a query to a defined relation that asks for members of the defined relation that are instances of the query. It is query driven, since at each step a set of subqueries is posed that drive the search for an answer. Bottom-up evaluation starts with the facts, the data, and uses existing facts to iteratively infer new facts to ultimately compute all members of the defined relations. Prolog uses SLD resolution, a top-down, query-driven evaluation strategy using highly optimized compilation techniques. Datalog systems use a bottom-up, data-driven evaluation strategy with engines optimized for that execution. Some problems are more efficiently solved top down and some bottom up. Thus there are some problems for which a Prolog programmer would like to use the Prolog built-in top-down strategy to perform bottom-up evaluation. Several Prolog systems now support a hybrid evaluation strategy called tabled evaluation (e.g., [ 9 ] , [ 8 ] , [ 10 ] , [ 4 ] ), which allows those Prolog systems to use aspects of bottom-up evaluation within the Prolog top-down framework. Tabling normally can provide all the bottom-up processing needed by a Prolog programmer. But some Prolog systems do not have tabling, and tabling is not precisely bottom-up evaluation in any case. Another use for bottom-up processing in Prolog is for teaching and debugging purposes. Students can learn more about what their Prolog definitions mean by exploring how they would evaluate bottom up. And experienced programmers may be able to find why Prolog does not compute an expected result by exploring the bottom-up computation. For all these reasons a good, simple, customizable implementation of bottom-up evaluation within a Prolog environment is desirable. Prolog is well-known for the elegance of the metainterpreters that it supports, and a bottom-up evaluator requires a metainterpreter. But Prolog metainterpreters normally inherit a top-down strategy from the Prolog evaluator. A metainterpreter that interprets object programs bottom up is not so obvious. This short paper describes a metainterpreter written in (standard ISO) Prolog that evaluates pure, positive Prolog programs bottom up. 2 The Algorithm The first step of the algorithm is to transform the object program into a new set of rules, rules that define a new binary predicate we call implies/2 . The implies rules are generated from the object program as follows: For each object rule: H\mbox{ :- }B_{1},B_{2},...,B_{n}. generate n implies/2 rules, one for each B_{i} . Specifically, for each B_{i} generate \mbox{implies}(B_{i},H)\mbox{ :- }B_{1},B_{2},...,B_{i-1},B_{i+1},...B_{n}. And for each object fact of the form H. generate an implies/2 fact of the form \mbox{implies}(\mbox{true},H). The metainterpreter uses these generated implies/2 rules to evaluate the original object program bottom up. The main metainterpreter predicate bu(Schedule,SchedEnd) takes a difference list that contains all the facts that have been derived but have not yet been used, along with the rules and other known facts, to derive new facts. The Prolog code for the metainterpreter bu/2 is: bu([],[]). % finished bu([Fact|Sched],SchedEnd) :- nonvar(Fact), % another derived fact to process findall(Hd,implies(Fact,Hd),Inferred), % get newly inferred facts assert_and_sched_inferred(Inferred,SchedEnd,NewSchedEnd), bu(Sched,NewSchedEnd). The first clause terminates when there are no more derived facts whose inferences are to be propagated. The second clause is the workhorse: it takes the next fact from the schedule, calls implies/2 on that fact and collects together the heads of all object rules now satisfied using that fact, i.e. facts that can now be inferred. It then uses assert_and_sched_inferred to process all those facts: for each that is not already in the database, it adds it to the database and adds it to the end of the schedule. And iterates. The supporting predicates are: assert_and_sched_inferred([],Sched,Sched). assert_and_sched_inferred([Fact|Inferred],Sched,SchedEnd) :- (subsuming_fact(Fact) -> assert_and_sched_inferred(Inferred,Sched,SchedEnd) ; assert(Fact), Sched = [Fact|SchedTail], assert_and_sched_inferred(Inferred,SchedTail,SchedEnd) ). subsuming_fact(Hd) :- term_variables(Hd,Variables), call(Hd), is_most_general_term(Variables). % all still variables and distinct The initial call to generate the least fixpoint is: ?- bu([true|End],End). Consider the meaning of a generated rule for implies/2 in bu/2 . Atom implies(A,H) is true if there is a rule in the object program that has head H and a body literal A and all the other body literals of the rule are true in the database. I.e., A implies H if the remaining body literals are true. This is clearly a consequence of the original object program rule. These rules are applied starting with the empty database, finding facts implied by the database facts and these rules, updating the database with the newly inferred facts, and iterating until no new facts can be inferred. 3 Transitive Closure Example Consider the Prolog rules for transitive closure of a simple graph: tc(X,Y) :- edge(X,Y). tc(X,Y) :- edge(X,Z), tc(Z,Y). edge(a,b). edge(b,c). edge(c,b). We note that since the graph in edge/2 is a cyclic graph, Prolog will go into an infinite loop when asked the query :- tc(A,B). But bottom-up evaluation will terminate as we shall see. The implies/2 rules generated from these object rules and facts are: implies(edge(X,Y),tc(X,Y)). implies(edge(X,Z),tc(X,Y)) :- tc(Z,Y)) implies(tc(Z,Y),tc(X,Y)) :- edge(X,Z)) implies(true,edge(a,b)). implies(true,edge(b,c)). implies(true,edge(c,b)). Each iteration of the main loop takes a fact from the schedule and produces a list of newly derived facts. that trace is: true adds [edge(a,b),edge(b,c),edge(c,b)] edge(a,b) adds [tc(a,b)] edge(b,c) adds [tc(b,c)] edge(c,b) adds [tc(c,b),tc(c,c)] tc(a,b) adds [] tc(b,c) adds [tc(a,c)] tc(c,b) adds [tc(b,b)] tc(c,c), tc(a,c), and tc(b,b) each adds [] finished This evaluator also handles unsafe programs, i.e., those with variables in answers. For example: append([],L,L). append([X|L1],L2,[X|L3]) :- append(L1,L2,L3). which generates the implies/2 facts: implies(true,append([],A,A). implies(append(A,B,C),append([D|A],B,[D|C]). and its trace: true adds [append([],A,A)] append([],A,A) adds [append([B],C,[B|C])] append([B],C,[B|C]) adds [append([D,E],F,[D,E|F])] append([D,E],F,[D,E|F]) adds [append([G,H,I],J,[G,H,I|J])] and it continues... Clearly if a Prolog program has infinitely many answers, its bottom-up evaluation will not terminate. But it can be useful to see the first several answers, as we’ve done here for append/3 . We can modify our bottom-up evaluator to return nondeterministically each fact and the new facts it generates. This allows the user to see the facts as they are iteratively generated and either stop the generation or to ask for another. The following modification of bu/2 is such a program: bu([Fact|Sched],SchedEnd,Fact1,NewFacts) :- nonvar(Fact), % done if a variable. findall(Hd,implies(Fact,Hd),Inferred), assert_and_sched_new(Inferred,SchedEnd,NewSchedEnd), (NewSchedEnd = [], SchedEnd \== [], % something added