Path: utzoo!attcan!uunet!munnari!vuwcomp!lindsay
From: lindsay@comp.vuw.ac.nz (Lindsay Groves)
Newsgroups: comp.lang.prolog
Subject: Re: Determining order of argument unification
Message-ID: <14359@comp.vuw.ac.nz>
Date: 10 Nov 88 21:44:40 GMT
References: <8192@burdvax.PRC.Unisys.COM> <629@quintus.UUCP>
Reply-To: lindsay@comp.vuw.ac.nz (Lindsay Groves)
Organization: Comp Sci, Victoria Univ, Wellington, New Zealand
Lines: 33

In article <629@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>...  So f(X,Y+Z,W) might have its arguments
>processed in a different order from f(X,W,Y+Z).

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:
  - check constant arguments first; these are easy checks to perform, and if
    one fails, that saves a lot of other work.
  - next check functors on compound terms; same reason as above, but it takes 
    a bit more work to do.
  - next handle first occurrences of variables; these only require bindings to
    be created.
  - finally handle second and subsequent occurrences of variables; this is the
    only place that the full unification algorithm needs to be invoked, so it
    shoulb de put off as long as possible.

This is bit simplified; e.g. it overlooks the question of when to process 
arguments of compound terms (that may depend on the representation used, and
how much effort is required to get at components), but I think the general
idea is clear enough.

Has anyone investigated this kind of thing?  What kind of improvement can be
expected?

Do any of the available (or unavailable, for that matter) Prolog compilers do
this?

-- 

	Lindsay Groves

	Logic programmers' theme song: "The first cut is the deepest"