Path: utzoo!utgpu!watserv1!watmath!att!pacbell!pacbell.com!ames!uhccux!munnari.oz.au!bruce!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Compiling away bagof
Message-ID: <3129@goanna.cs.rmit.oz.au>
Date: 2 Jun 90 07:46:28 GMT
References: <2567@randvax.UUCP>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 106

In article <2567@randvax.UUCP>, narain@randvax.UUCP (Sanjai Narain) writes:
> This is in response to Richard O'Keefe's request to outline my approach
> for compiling away bagof.

Whew!  Had me worried for a minute there, but it _is_ in the book!

> Given, that E has occurred, an important problem is to compute the bag of
> all events G such that causes(E, G).

It isn't clear to me why bagof/3 is being used here.  What is the
significance of the rule ordering?  If we have
	causes(ying, tong) :- true.
	...
	causes(ying, iddle) :- true.
why does it _matter_ that the bag look like [...,tong,...,iddle,...]
rather than [...,iddle,...,tong,...]?  Again, suppose we have
	causes(kill(X,Y), dies(Y)) :- true.
	causes(kill(X,Y), dies(X)) :- good_police, death_penalty.
and the event kill(john,john) occurs.  (We are to suppose that john
succeeds in killing himself, and that he is caught, convicted, and
sentenced to death for murder.)  Why is it important to have dies(john)
appear twice in the bag rather than just once?

Absent any reason for recording multiple references to the same event,
it would appear to be appropriate to use setof/3 rather than bagof/3.
Indeed, it is almost _always_ appropriate to use setof/3 rather than
bagof/3, both for theoretical reasons and for practical reasons.
Theoretical reasons:  see Chapter 4 "Why Duplicate Rows are Prohibited"
of C.J.Date's "Relational Database writings 1985--1989".
Practical reasons:  if you want to combine the results of an all-
solutions predicate with other such collections, it is much more
efficient to use set operations based on merging, which need the result
to be sorted anyway, so you might as well let setof/3 do it.

> Suppose we have the following rules:
> 	causes(f(A1,..,Am,T), F1) :- B1.
> 	..
> 	..
> 	causes(f(A1,..,Am,T), Fk) :- 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).

> 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) :-
> 		cond(B1, F1, L1),
> 		..
> 		..
> 		cond(Bk, Fk, Lk),
> 		append_all([L1,..,Lk], List).

(1) We don't need the restriction to A1,...,Am,T being variables in
    the original rules.  We _do_ need the restriction to the call
    having ground arguments a1,...,am,t.
(2) We don't need append_all/2 (called append/2 in library(lists)).

	brings_about(f(A1_0,...,Am_0,T_0), L_1) :-
		(   A1_1 = A1_0, ..., Am_1 = Am_0, T_1 = T_0, B1 ->
		    L_1 = [F_1|L_2]
		;   L_1 = L_2
		),
		...
		(   A1_k = A1_0, ..., Am_k = Am_0, T_k = T_k, Bk ->
		    L_k = [F_k]
		;   L_k = []
		).

    Each L_{i}\L_{i+1} is a list difference pair.  Assuming a Prolog
    compiler that open-codes if->then;else (as they all should...) this
    also avoids the overhead of building a copy of each B_i and passing
    through call/1.

> LIMITATION: It is entirely possible that a causes rule be non-deterministic,
> e.g. in:
> 
> 	causes(falls(Domino,T), falls(NextDomino,T+delay)) :-
> 		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).	/* MISTAKE */

Er, if you have a DEC-10-compatible implementation of bagof/3, this isn't
going to do what you think it's going to do.  If the Body has any variables
which are strictly local to the Body (i.e. in the original
	causes(Cause, Effect) :- Body
if there are any variables in the Body which appear neither in Cause nor
Effect) then bagof/3 is going to say "ah hah, these are free variables,
the caller wants to know their bindings, I shall enumerate bindings for
these free variables and for each binding list only the Events that
corresond to that binding."  In fact, what you want here, if indeed you
want bagof-like behaviour at all, is findall/3.  There's another obvious
problem which is avoided by using findall/3.

	cond_1(Body, Template, Events) :-
		findall(Template, Body, Events).	/* CORRECTED */

-- 
"A 7th class of programs, correct in every way, is believed to exist by a
few computer scientists.  However, no example could be found to include here."