Efficiency Considerations on Built-in Taxonomic Reasoning in PROLOG

1. Time overhead due to the taxonomy mechanism

In the first series of tests the programs do not make use of taxonomic reasoning at all. Note that Taxlog is an extension of Prolog, thus we could use the very same source programs in our experiments for both the interpreters.

We took the test programs from Warren (15) :

nreverse, which inverts the terms of a list, applied to list30, a 30 element list;

• qsort, a version of the quicksort algorithm, applied to the Warren list50 list;
• deriv, a program for computing symbolic derivatives, applied on four different arithmetic expressions, named times10, divide10, log10, and ops8;
• serialise, which translates a given string into a list of numbers which represent the character

**In the dbquery example, the system gives five answers. We reported in the table, respectively, the time for the first answer and the time for the refutation.

codes, applied to the string palin25;

• . dbquery, which represents a simple query application on a little geographic database.

Table 1 summarizes the resu1 ts of this series of tests. For the Warren's examples, the overhead falls into the interval between 1.80% and 5.06% of the total execution time.

The overhead does not depend on the total execution time. It is due exclusively to the higher complexity involved in the unification, because Taxlog considers the case of restricted variables even if in these examples they do not appear.

2. Time advantages in using taxonomies

In this second series of tests we measured the improvement which derives from an extensive use of the taxonomic reasoning capability. The testing program represents a simple query on a database. Some properties in the database are defined by using objects and classes declared in a taxonomy. In the query some variables are restricted.

Two different versions have been built for each test program. In the standard Prolog version, no restricted variable appears, while the Taxlog version contains a description of the taxonomy in terms of the primitives we introduced. A number of difficulties has been faced in order to make significant the comparison between the two systems. First, even though the two systems interpret the same example, they give a different number of answers, because Prolog instantiates variables to the constants which satisfy the goal, but Taxlog generalizes answers as far as possible to categories. In order to have comparable results two kinds of measures have been taken: the first­ answer time, that is the time the system takes in order to find the first solution for the goal, and the refutation time, i.e. the time the interpreter takes to generate all solutions and then answer

"no".

Second, first-answer times in a Prolog interpreter are greatly dependent on the clause ordering: in a choice point the interpreter examines directly the correct branch only if it is the first in the database. First-answer times were taken with the database ordered in the most favou­ rable way. Note that the Taxlog interpreter is very little sensitive to the order of the various parts of a taxonomy. Thus, the first-answer time is the most favourable measure for Prolog. On the contra­ ry, the refutation time is fully independent from the clause ordering in the database for both sys­ tems, provided that no extra-logical feature, such as cut, assert, etc., appears. In general, Taxlog capabilities are exploited for refutation problems.

Third, two different kinds of query have been taken into consideration. In the first case there is a two-variable query: the interpreter satisfies the goal by finding a suitable combination of values for the two variables. In the second case two constants appear instead of the variables: the interpreter proves that the query is satisfied by the two constants. Two-variable queries have been measured, for Taxlog, in two different ways: in the first, an answer is given in terms of restricted variables, in the second way the answer is made uniform to standard Prolog by filtering it through the current atom primitive.

Fourth, the test programs for the two systems are not equal: it is therefore possible that different implementation techniques for the same program require different answer times. With respect to standard Prolog, the two solutions, top-down and bottom-up, have been considered for the problem of searching through a taxonomy. Note that for first-answer times with optimal ordering of clauses top-down and bottom-up are almost equivalent, because no true search is required. Thus, only results for top-down are reported. The difference between the two approaches may be better appreciated for refutation times.

Finally, first-answer times for random clause ordering range from the first-answer time for optimal clause ordering (including it) to the refutation time (excluding it). Thus the comparison of the two measures gives an idea of the answer times for increasingly more non-deterministic problems.

In Appendix 3 we report the test program for each version.

First-answer times

The test has been repeated for increasingly deeper taxonomies: the results (see Table 2) show that first-order times linearly depend on the taxonomy depth. As the rate is much higher for Prolog than for Taxlog, we have proved that a single complex unification step is far more efficient than a taxonomic deduction with a simple unification algorithm. Note that Taxlog results for two-variable queries do not depend on the taxonomy size, because only one clause is used, and taxon­ omic information is not required (see Appendix 3).

Refutation times

Three groups of tests have been done, in order to measure the refutation time rate resulting in increasing (uniformly):

the number of objects per class,

the number of subclasses per class,

the depth of the taxonomy.

All experiments for each group of tests make use of balanced taxonomies with a uniform number of objects per bottom-level class. Table 3 shows the

results for these tests.

Increasing the depth of the taxonomy.

B. Memory requirements

Some considerations arise when the space requirements for the two systems, Prolog and Taxlog, are compared. We can distinguish between static and dynamic space requirements.

1. Static space requirements

Actually, Tax log imposes a space overhead of two words per atom, in order to store the two ad­ ditional pointers (see Section III). This overhead must be payed for each atom in the system, thus included all atoms which are members of no class.

In order to store taxonomic relations, we need some space for classes, and for s s and is a arcs. Table 4 summarizes space requirem~nts for-Taxlog, and for the two approaches, top-down and bottom-up, in Prolog. In these measures we do not consider the space for storing atoms. Classes are represented in Taxlog by entities in the category area, while in Prolog they are represented as unary functors. The bottom-up approach, moreover, requires some space for storing a clause for each category entry. In Prolog more space is needed in order to store s s and is_ a arcs than in Tax log because the arcs are represented as normal clauses, representation for head, tail, information must be provided. and thus a and control

Clauses not involving restricted variables need the very same space for both systems. When restricted variables appear, instead, the space difference between Prolog and Taxlog depends on two parameters: T, that is the number of taxonomic restrictions in a clause (and their equivalent representation as predicates in standard Prolog), and V, that is the number of global variables in the Taxlog clause. For our implementation, a formula gives the difference in number of words:

(Prolog_space - Taxlog_space) = 5 * T - v

Note that an intensive use of taxonomic restrictions favours Taxlog, because Prolog requires space in order to store the predicate form of the taxonomic restriction and the comma separator, while Taxlog stores directly the restriction as a pointer to the category area in the initial environment. But restricted variables are considered global, and, actually, the initial environment contains a word for each global variable. This fact explains why the corrective factor appears in the formula.

2. Dynamic space requirements

It is worth noting that Taxlog requires the very same dynamic space as Prolog, if the taxonomy mechanism is not used. The only stack space waste that Taxlog imposes, respect with Pro log, is in trail management, because the old variable ~estrictions must be stored together with the variable addresses, during the unification. But the careful trail management algorithm we used saves are this space when unrestricted variables instantiated.

Surprisingly, even if taxonomies are used, much dynamic space is gained, as the data in Table 5 confirm, because many stack records, that Prolog pushes on the local stack for handling the clauses describing the taxonomy, are simply not used (and thus not stored) by Taxlog. Consequently, more space is gained in the trail stack, because there is no need of saving the addresses of the taxonomic clauses; moreover, less variables exist in the system. The increase in the global stack size is due to the fact that restricted variables are classified as global, and thus are stored in the global stack instead of the local stack.

Table 5 refers to the same examples used for first-answer time queries with two variables. Data are relative to the smallest taxonomy (depth = 2). Bigger taxonomies give the same results for Taxlog, but a higher space usage for Prolog, due to the stack records for the taxonomy clauses.

VI CONCLUSIONS

The efficiency of a prototype of the Taxlog interpreter has been valued with respect to standard Prolog by means of a series of measurements. The maximum overhead, due to the higher degree of complexity of the extended interpreter, is about 5% of the execution times, and is fully independent from the size of the test problem. An intensive use of taxonomies involves considerable improvements in terms of execution times. The taxonomic reasoning model employed in Taxlog is quite general: this system feels a good candidate for many practical applications (3).

ACKNOWLEDGEMENTS

Most work on the model has been accomplished by the author and Cristina Bena, whose contribution is invaluable. Useful suggestions came to this work from Franco Sirovich, Gianfranco Rossi and Alberto Martelli at the Comp. Science Dept. of University of Turin. The author wishes to thank his colleagues at Laboratorio di Intelligenza Artificiale for their support and helpful discussions.

APPENDIX 1 - USER-FRIENDLY SYNTAX FOR DEFINING TAXONOMIES

A simple, user-friendly syntax has been defined for helping the programmer to introduce taxonomies into the Taxlog system. A BNF description of the grammar is given, together with a Pro log description of its semantics and an example. BNF description:

Taxonomy_declaration ::=declare Tree.

Tree : := Atom

I Atom := List of elements

I Tree -> Tree- { : Tree l

List_of'_elements · : := [Atom L Atom D

Note: {I · are the usual and indicate zero or more Prolog interpretation: Kleene closure operators, occurrences of a pattern.

?- op(2SS,f'x,declare),

op(2S4,xfy, '->'), ·

op(200,xf'x,':=').

declare Tree :- declare(Tree,lOOOOOO, ).

declare((A-)B),N,Top) :- !, declare(A,N,Top),

NmlO is N - 10,

declaress(Top,B,NmlO).

declare((A := L),N,A) :- !, mkcateg(A,N), mkisa(L,A).

declare(A,N,A) :- mkcateg(A,N).

declaress(T,(B,C),N) :- !, declare(B,N,TopB),

mkss(TopB,T),

declaress(T,C,N).

declaress(T,B,N) :- declare(B,N,TopB), mkss(TopB,T).

Example:

?-declare european-> italian :=[me],

french, german, english.

?- declare nationality .- [italian, french,

german, english].

APPENDIX 2 - READING AND WRITING TAXLOG TERMS

From the syntax point of view, the Taxlog interpreter accepts exactly the Prolog constructs. The read primitive first builds the deep structure of the input expression, considering the special ' : ' symbol as a normal syntactic operator*, then interprets it and considers its second argument as a succession of restrictions to be applied to the variables appearing in the first argument. The read primitive makes therefore the symbol · · · and the syntactical structure of the restrictions transparent to the rest of the system. For example if the goal:

*Note that in the bootstrapping phase the operators are currently defined as follows:

?- op(2SS,xfx,·:·), op(2S4,xfx,·:-'), op(2S3,xf'y,','), etc.

?- read(A), functor(A,F,Arity).

is given the input sequence:

structure ( Var1, Var2, Var3) : Var1 isa catl. the Taxlog answer is the following:

A = structure(_1,_2,_3) F = structure Arity = 3

while the goal:

?- read(A), arg(1,A,V).

with the same input structure as before produces the following answer:

A = structure(_1,_2,_3) : 1 isa cat1

V 1 : 1 isa cat1

The write primitive writes its argument with the same syntax as the answers: if in its argument any restricted variable appears, the write primitive .prints the argument denoting each variable with a symbol. Then the special ':' operator is printed, followed by the restrictions on the variables in the format:

<variable) iss <class)

The symmetry between read and write has been maintained: structures written on a file by Taxlog are in the format accepted by the read primitive.

APPENDIX 3 - TEST PROGRAMS

Here follows an example of the test programs and taxonomies for time measurement.

Taxlog ?- mkcateg(zero,100), mkcateg([a,b],90), mkss([a,b],zero), mkisa(oa,a), mkisa(ob,b). relation(A,B) : A isa a, B isa b. Prolog, top-down zero(A) :- a( A). a(oa). relation(A,B) :- a(A), b(B). Prolog, bottom-up zero (zero) · a(a). zero(A) b(ob). b(b). - b(A). a(A) :- zero(A). oa(A) :- a(A). b(A) :- zero(A). ob(A) :- b(A). relation(A,B) - isa(A,a), isa(B,b). isa(O,C) :- I = ·· [ O,C] , I. Measurements for first-answer times measure :- cpu_time(T1), relation(A,B), cpu_ time(T2), Tdiff is T2 - T1, write(Tdiff). /* (1) */ For two-constant queries, instead of (1) use: relation(oa,ob), For Taxlog two-variable queries with current_atom, instead of (1) use:

re1ation(A,B), current_atom(A), current_atom(B),

1 isa cat1

Measurements for refutation times

measure :- cpu_time(T), refute(T).

refute(_) :- re1ation(A,B), fail. /* (2) */ refute(T1) :- cpu_time(T2), Tdiff is T2- T1, write(Tdiff).

For two-constant queries, instead of (2) use :

refute(_) :- relation(oa,ob), fail.

For Taxlog two-variable queries with current_atom,

instead of (2) use:

refute( ) - relation(A,B), current_atom(A), current_atom(B), fail.