Path: utzoo!utgpu!watmath!clyde!att!rutgers!mit-eddie!bu-cs!purdue!decwrl!sun!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Search strategies in PROLOG
Message-ID: <699@quintus.UUCP>
Date: 18 Nov 88 03:51:15 GMT
References: <8811171657.AA18741@decwrl.dec.com>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 48

In article <8811171657.AA18741@decwrl.dec.com> vantreeck@curie.dec.com writes:
>>Path: decwrl!sun!pitstop!sundc!seismo!uunet!munnari!vuwcomp!lindsay
>>Subject: Re: Determining order of argument unification
> 
>>I have often wondered about this.  It would seem to be a fairly simple 
>>optimisation in a Prolog compiler to look at the arguments in a call and
>>process them in an order that does the easiest things first.  For example:
>>	Lindsay Groves

Wayne Citrin wrote a paper at UC Berkeley in Spring 1985:
	A Comparison of Indexing and Term Reordering:
	Two Methods for Speeding Up the Execution of Prolog Programs.
For the things he looked at, term reordering over and above what the WAM
does rarely paid off.

The normal WAM order is to work from left to right in a term, handling
constants and variables as you find them, but postponing compound terms.
The exception to this is that if the last argument of a term is compound,
it is processed straight away, before any preceding compound arguments.

E.g.	f(g(X),a,h(X),Y,g(Y))
does	a, Y, g(Y), g(X), h(X) in that order.

>These implementations have added indexing on the first
>argument in the head of a clause as an after thought to address real-world
>programs, where searching is generally the dominant time consumer. 

No, first-argument indexing is NOT an afterthought.  It is a vital part
of the basic machinery, analogous to CASE statements in Pascal.
Indexing tells you two things:  these clauses are relevant (reducing search)
and these are the ONLY relevant clauses (determinacy).

>I've spent some time looking at ways to build DFID search efficiently into
>PROLOG. The primary problem is that PROLOG programs have side-effects which
>aren't reversible on backtracking (e.g., keyboard input). DFID does a lot more
>backtracking where "normal" PROLOG would be deterministic. 

I'm afraid I've not seen anything by Van Treeck on this.  I got the idea from
Mark Stickel, who has implemented it as part of his "Prolog Technology
Theorem Prover".  Stickel points out that you need three things:
    (1)	Sound unification (easy to add to the WAM)
    (2) A fair searching strategy (iterative deepening is dead simple to add)
    (3) Resolution against opposite sign ancestors to handle negation

One of the handouts in our "advanced Prolog course" is a tiny little
term_expansion/2 definition which provides iterative deepening by source-
to-source transformation.  That seems to be efficient enough for most
purposes.