"untiless"
UNLP meta-interpreters
Miguel Calejo
Technical note draft, DI/UNL, 23 January
1989
Introduction
This note shows how to build UNLP [Porto Pereira
Trindade 87] meta-interpreters. Previous interpreters made use
of until
or unless
primitives, not defined in "pure" UNLP themselves. These
primitives have been added to UNLP essentially to implement pure
UNLP interpreters. The new interpreters to be presented avoid
the need for them by:
a,b) using different representations for predicate
definitions;
c,d) in a more tortuous way, using all
and lazy all
metapredicates.
We start by recalling the traditional interpreter,
and then move on to an interpreter in two versions, using two
different new predicate definition representations. Then we restart
with the old interpreter, and instead reimplement until
(and hence unless)
in two different ways, using the standard (eager) all
and a lazy all.
The traditional UNLP interpreter, T
For your convenience, next is a "traditional"
minimal interpreter, due to Porto and Trindade. We're not considering
the extensions to accomodate Prolog clauses with arbitrary cuts
(i.e, the "conditional and" and "conditional or"
body goals), inspired by Luís Moniz Pereira, or system
predicates. The interested reader can check the cited reference.
(1) ti(true) !.(2) ti((G1,G2))
<-> ti(G1), ti(G2).(3) ti(G) <-> (rule(G,B), ti_cond(B,NB))
until iff_body(B), ti(NB).
(4) ti_cond(iff(C,B),B) <-> ti(C).(5) ti_cond(if(B),B) !.
(6) iff_body(iff(_,_)) !.
Clauses are accessed through the meta-predicate rule(Head,B).
If the clause has an exclusive implication then B
will be iff(Condition,Body),
otherwise if(Body).
until provides
the magic of cuts within disjunctions. The Prolog definitions
for until and unless follow:G
until C :- G, (C, !; true).G unless C :- G, (C, !, fail; true).
The interpreter A
until in clause
(3) is used to avoid producing more solutions to its conjunction
goal argument when a committment occurs. Although UNLP forces
committments to be explicit in the clause structure, the above
interpreter does not detach the fetching of that information from
the nondeterminism of the rule
call. Consequently, the "committment character" of the
current object clause used can not be explicit at the level of
clause (3), and a "dynamic " committment must be used
instead.
Instead of rule/2
we use predicate_definition/2.
For each predicate P in the program there is a fact
predicate_definition(P,Rule_sequence)
where Rule_sequence encodes the sequence of clauses
constituting the predicate definition for P, and P is a most general
instance of the predicate literal sharing no variables with the
Rule_sequence term.
We can now rewrite clauses (3-6) above, obtaining
the new (meta) interpreter:
(3') i(G) <-> predicate_definition(G,Rules),
i_body(Rules,G).
(4') i_body([rule(G,iff(C,B))|_],G) <-> i(B) <= i(C).(5')
i_body([rule(G,if(B))|_],G) <- i(B).(6') i_body([_|Rules],G)
<-> i_body(Rules,G).
Having explicitly separated the fetching of clauses
from their use in the meta-interpreter, object level committments
can now correspond directly to ordinary meta-level committments
(clauses 4' and 5'). Shallow backtracking at the object level
maps into shallow backtracking and recursion at the meta-level.
The interpreter B
Another possibility is using a "next_clause"
primitive, in the vein of [Parker88]. Let's consider that we have
3 primitives for accessing rules in a predicate definition:
first_ref(G,Ref)
returns a reference for the first rule in the definition
for the predicate of goal G. Does not produce bindings
in G. instance(Rule,Ref)
returns the "rule" term for the rule referenced
by Ref. next_ref(Ref1,Ref2)
returns the reference Ref2 for the next rule after
the one with reference Ref1. Of course, this primitive could have
the goal as an extra argument, in order to take advantage of indexing.
The interpreter now becomes:
(3") i(G) <-> first_ref(G,R1),
instance(Rule,R1), i_body(Rule,G,R1).(4") i_body(rule(G,iff(C,B)),G,_)
<-> i(B) <= i(C).(5") i_body(rule(G,if(B)),G,_)
<- i(B).(6") i_body(_,G,R1) <- next_ref(R1,R2), instance(Rule,R2),
i_body(Rule,G,R2).
Implementationwise: T vs A vs B
Using "predicate_definition"
instead of "rule"
(A) is inherently worse, at least in a structure-copying implementation,
since all rules have to be fetched even if they're not needed.
It is also worse than the interpreter B using the "next_clause"
primitives, as these are based on cheap pointer chasing and the
interpreter fetches one rule at a time.
The winner in efficiency will possibly be the older
interpreter T, since interpreter B unifies the goal G with the
rule head only after it fetches it. This seems worse because a
unification that fails will do so a posteriori, on the next iteration
of i_body:
the unification is being made explicitly (in clauses (4",5")),
while the older interpreter T makes it implicitly in the rule
call. The interpreter B should cause a full "rule" term
to be built in the Prolog heap, while interpreter T can benefit
from the interleaving of that construction with the unification
of the goal with the rule head. This is hardly surprising: the
extra expressivity available (making unification explicit) comes
with a price.
Spacewise, both interpreter A and interpreter B required
an additional recursion for each clause fetched. Therefore, A
does not recover space on backtracking as in T, and for B to recover
it a Prolog implementation with garbage collection is needed.
As stated above, the next_ref
implementation might take indexing into account by having G as
an extra argument, but it can't be allowed to bind its variables
if it is to be used explicitly in the interpreter.
Both of the new interpreters above can be obviously
improved by using first argument indexing in themselves, but that
shouldn't affect the previous comparisons.
The interpreter C
Another possibility for making interpreters without
until/unless
is obviously to get rid of these in general. Following
a suggestion by António Porto, we now present new definitions
of the primitives until
and unless
which use an all
solutions metapredicate, instead of resorting to Prolog cuts within
disjunctions (cf. with the previous definitions). With these new
definitions we can use the good old interpreter T (and call the
combination "interpreter C").
G until C <-> all(S,G,Solutions),
until(Solutions,G,C).
until([G|_],G,C) ! <= C.until([G|_],G,_).until([_|Solutions],G,C)
<-> until(Solutions,G,C).
G unless C <-> all(GG,G,Solutions), unless(Solutions,G,C).
unless([G|_],G,C) # <= C.unless([G|_],G,_).unless([_|Solutions],G,C)
<-> unless(Solutions,G,C).
In the interpreters above, getting all the clauses
in a predicate definition at once (A) or while iterating forward
(B) allowed us to replace the until
call at the interpreter level by an UNLP if-then-else. To implement
until/unless
in the general case as above we collect all solutions to G and
test the condition C afterwards, needing only UNLP's if-then-elses
as well. Like in the A interpreter case this implementation is
inherently less efficient, since all solutions need to be computed
a priori.
The interpreter D
On the other hand, using a lazy all
primitive (for example, [M.Pereira Nasr 84]) would have the benefits
the "next_clause"
primitives brought to the B interpreter.
Consider the primitives:
first_solution(G,S,R)
Computes the first solution S for G, without producing
bindings in G and returning a reference R denoting the state of
that computation (after S is computed)
next_solution(R1,S,R2)
Takes the state of an ongoing computation
of some top goal G, denoted by reference R1, and computes the
next solution S to G, obtaining a new state of that computation,
denoted by reference R2. Fails if there are no more solutions
to G.
The implementation of these primitives must rely
on some sort of parallel computation, with its own backtracking,
such as a coroutine or a remote process, for example.
until can now
be defined as follows (the reader may check that unless
can be implemented similarly):
G until C <-> first_solution(G,S,R),
until(G,S,C,R).
until(G,G,C,_) ! <= C.until(G,G,_,_).until(G,S,C,R1) <->
next_solution(R1,S,R2), until(G,S,C,R2).
We call "D" to the interpreter T using
this until
definition.
Conclusion
All this seems to be rather academic, as the new
interpreters are either slightly or much more inefficient than
the traditional one. The extra control gained in interpreter B
seems hardly useful at all. Implementing until/unless
with lazy all
seems a curious and useless enterprise, given the implicit implementation
costs…
The motivation has been instead to "purify"
UNLP a little further, attempting to make it independent of Prolog
cuts.
References
António Porto, L.M.Pereira and Luís
Trindade, "UNLP reference manual", UNL ALPES report
1987
D. Stott Parker, Thomas W.Page, Jr. and Richard Muntz,
"Improving Clause Access in Prolog",, UCLA CS Dept.,
1988
Luís Moniz Pereira and Roger Nasr, "Delta-Prolog"
(??), Proceedings of the Conference on Fifth Generation Computer
Systems 1984, ICOT, Tokyo.
Acknowledgements
To António Porto, Luís Moniz Pereira
and Luís Trindade for relevant suggestions and criticisms.
|
Declarativa