Path: utzoo!attcan!uunet!mcvax!unido!ecrcvax!micha
From: micha@ecrcvax.UUCP (Micha Meier)
Newsgroups: comp.lang.prolog
Subject: Re: Determining order of argument unification
Message-ID: <653@ecrcvax.UUCP>
Date: 17 Nov 88 09:29:14 GMT
References: <8192@burdvax.PRC.Unisys.COM> <629@quintus.UUCP> <14359@comp.vuw.ac.nz>
Reply-To: micha@ecrcvax.UUCP (Micha Meier)
Organization: ECRC, Munich 81, West Germany
Lines: 29

In article <14359@comp.vuw.ac.nz> lindsay@comp.vuw.ac.nz (Lindsay Groves) writes:
>  - 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 basically right, you only have to precisely know why do you
	choose a specific order: if the unification succeeds, it does
	not matter in which order the arguments are unified. If it fails,
	however, we want to find it out as early as possible so that:
		
		- we didn't make too many (now redundant) operations
		  before the failure
		- the number of actions necessary to undo the failed
		  unification is minimized

	This means that first occurrences of variables should be handled
	at the end, because they cannot cause failure. 
	The order depends as well on possible mode declarations (input
	before output) and on the size or "groundness" of compound terms.
	The (unavailable :-)) compiler of Sepia makes these optimizations.


--Micha