Path: utzoo!attcan!uunet!snorkelwacker!usc!randvax!narain
From: narain@randvax.UUCP (Sanjai Narain)
Newsgroups: comp.lang.prolog
Subject: Compiling away bagof
Message-ID: <2567@randvax.UUCP>
Date: 31 May 90 20:09:10 GMT
Organization: Rand Corp., Santa Monica, Ca.
Lines: 88

This is in response to Richard O'Keefe's request to outline my approach
for compiling away bagof.  It has been developed in the context of DMOD
(Declarative MODeling) a technique for modeling dynamic systems.  The
optimization essentially consists of compiling away OR-parallelism when
the rules are deterministic.  A DMOD model of a dynamic system consists of
rules, roughly, of the form:

	causes(E,F) if Body.

where E and F are event templates, each of the form f(A1,..,Am,T), where T
denotes a real-valued, non-negative time instant.  Informally, the rule
means that event E causes event F provided Body. An example is:

	causes(falls(Domino,T),falls(NextDomino,T+delay)) if
		successor(Domino,NextDomino).

Event occurrences are (roughly) computed by repeatedly using the rule:

	occurs(F) if initial(F) or causes(E,F) and occurs(E).

Given, that e has occurred, an important problem is to compute the bag of
all events g such that causes(e,g). Suppose we have the following rules:

	causes(f(A1,..,Am,T),F1) if B1
	..
	..
	causes(f(A1,..,Am,T),Fk) if Bk

***where each Ai,T is a variable***.  Suppose f(a1,..,am,t) has occurred
where each ai, and t is ground.  Then, one can compute all the effects of
it using:

	bagof(F,causes(f(a1,..,am,t),F),Bag).

Given the overhead of calling bagof, and that this call must be made after
each event occurrence, and that the number of event occurrences can be
tens of thousands, this approach would be extremely slow.  We can do quite
a lot better.

Provided each of these causality rules is deterministic, i.e. produces at
most one effect for a given cause, we can collapse all of these rules into
a single one:

	brings_about(f(A1,..,Am,T),List) if
		cond(B1,F1,L1),
		..
		..
		cond(Bk,Fk,Lk),
		append_all([L1,..,Lk],List).

Here each Li is a variable.  Now brings_about returns a list of caused
events.  The ith call to cond calls Bi and if successful, binds Li to
[Fi].  Otherwise it binds Li to []. append_all appends all of these lists.
The definition of cond is:

	cond(Body,Event,List):-Body,!,List=[Event].
	cond(Body,Event,[]).

Now, to compute the list of all events caused by f(a1,..,am,t) one can
type:

	brings_about(f(a1,..,am,t),List).

No bagof is needed. For our current model, this is about 20 times faster.

LIMITATION: It is entirely possible that a causes rule be non-deterministic,
e.g. in:

	causes(falls(Domino,T),falls(NextDomino,T+delay)) if
		successor(Domino,NextDomino).

successor(A,B) could succeed more than once for a given value of A.  Then
we have to apply such a rule in all possible ways for a given causing
event.  This could be done by redefining the first rule for cond to:

	cond_1(Body,Event,List) :- bagof(Event,Body,List).

This reintroduces bagof. I am not sure how to eliminate this without an
intricate analysis of the program. Any suggestions would be greatly
appreciated.

My current solution is to have the user declare the event templates for
which all causality rules are deterministic, and then use cond for these,
and cond_1 for the rest.

Regards.

Sanjai Narain