Efficient Prolog A Practical Guide.pdf

Research Report AI-1989-08

Ecient Prolog: A Practical Guide

Michael A. Covington

Artiﬁcial Intelligence Programs

The University of Georgia

Athens, Georgia 30602

August 16, 1989

Abstract

Abstract: Properly used, Prolog is as fast as any language with com-

parable power. This paper presents guidelines for using Prolog e-

ciently. Some of these guidelines rely on implementation- dependent

features such as indexing and tail recursion optimization; others are

matters of pure algorithmic complexity.

Many people think Prolog is inecient. This is partly because of the poor

performance of early experimental implementations, but another problem is

that some programmers use Prolog ineciently.

Properly used, Prolog performs automated reasoning as fast as any other

language with comparable power. It is certainly as fast as Lisp, if not faster.

There are still those who rewrite Prolog programs in C “for speed,” but this

is tantamount to boasting, “I can implement the core of Prolog better than

a professional Prolog implementor.”

This paper will present some practical guidelines for using Prolog eciently.

The points made here are general and go well beyond the implementation-

speciﬁc advice normally given in manuals.

1 Think procedurally as well as declaratively.

Prolog is usually described as a declarative or non-procedural language. This

is a half-truth. It would be better to say that most Prolog clauses can be

read two ways: as declarative statements of information and as procedures

for using that information. For instance,

in(X,usa) :- in(X,georgia).

means both “X is in the U.S.A. if X is in Georgia” and “To prove that X is

in the U.S.A., prove that X is in Georgia.”

Prolog is not alone in this regard. The Fortran statement

X=Y+Z

can be read both declaratively as the equation x = y + z and procedurally as

the instructions LOAD Y, ADD Z, STORE X. Of course declarative readings

pervade Prolog to a far greater extent than Fortran.

Sometimes the declarative and procedural readings conﬂict. For example,

Fortran lets you utter the mathematical absurdity X=X+1. More subtly,

the Fortran statements

A = (B+C)+D

A = B+(C+D)

look mathematically equivalent, but they give profoundly diﬀerent results

when B=10000000, C=-10000000, and D=0.0000012345.

Analogous things happen in Prolog. To take a familiar example, the clause

ancestor(A,C) :-

ancestor(A,B), ancestor(B,C).

is part of a logically correct deﬁnition of “ancestor,” but it can cause an

endless loop when Prolog interprets it procedurally.

The loop arises because, when B and C are both unknown, the goal ancestor(A,B)

on the right is no diﬀerent from ancestor(A,C) ontheleft. Theclausesimply

calls itself with essentially the same arguments, making no progress toward

a proof. But if the clause is rewritten as

ancestor(A,C) :-

parent(A,B), ancestor(B,C).

there is no loop because ancestor cannot call itself with the same arguments.

The moral is that to use Prolog eﬀectively, one must understand not only the

declarative reading of the program but also the procedures that the computer

will follow when executing it. The limitations of Prolog’s built-in proof pro-

cedures are not ﬂaws in the implementation; they are deliberate compromises

between logical thoroughness and ecient search.

2 Narrow the search.

Searching takes time, and an ecient program must search eciently. In a

knowledge base that lists 1000 gray objects but only 10 horses, the query

?- horse(X), gray(X).

can be 100 times as fast as the alternative

?- gray(X), horse(X).

because it narrows the range of possibilities earlier.

Many opportunities to narrow the search space are much more subtle. Con-

sider the problem of determining whether two lists are set-equivalent — that

is, whether they have exactly the same elements, though not necessarily in

thesameorder.

Two lists are set-equivalent if and only if one of them is a permutation of the

other. One strategy, then, is to generate all the permutations of the ﬁrst list

and compare them to the second list:

set_equivalent(L1,L2) :-

permute(L1,L2).

The trouble is that an N-element list has N! permutations; testing the set-

equivalence of two 20-element lists can require 2.4

10 18 comparisons. I

have actually seen someone attempt this in a Prolog program.

It is much faster to sort both lists and compare the results:

set_equivalent(L1,L2) :-

sort(L1,L3), sort(L2,L3).

An N -element list can be sorted in about N log 2 N steps — i. e., about 86

steps per 20-element list — and each “step” involves considerably less work

than generating a new permutation. So this technique is faster than the ﬁrst

one by a factor of more than 10 16 .

Let uniﬁcation do the work.

As a classroom exercise I ask my students to write a predicate that accepts a

list and succeeds if that list has exactly three elements. Some of the weaker

answers that I get look like this:

has_three_elements(X) :-

length(X,N),

N=3.

Slightly better are those that say

has_three_elements(X) :-

length(X,3).

thereby letting the built-in pattern-matcher test whether length returns 3.

But the best students cut the Gordian knot by writing:

has_three_elements([_,_,_]).

The point is that [_,_,_] matches any three-element list and nothing else.

Uniﬁcation does all the work.

Uniﬁcation can even rearrange the elements of a data structure. Here is a

predicate that accepts a list and generates, from it, a similar list with the

ﬁrst two elements swapped:

swap_first_two([A,B|Rest],[B,A|Rest]).

Again, uniﬁcation does all the work. More precisely, the data structures

[A,B|Rest] and [B,A|Rest] , or templates for them, are created when the

program is compiled, and uniﬁcation gives values to the variables at run time.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: