Path: utzoo!utgpu!water!watmath!clyde!bellcore!rutgers!cmcl2!nrl-cmf!ames!pasteur!agate!labrea!decwrl!sun!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Probabilistic 'or'?
Message-ID: <272@quintus.UUCP>
Date: 10 Aug 88 22:11:57 GMT
References: <613@etive.ed.ac.uk> <257@quintus.UUCP> <628@etive.ed.ac.uk>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 53

In article <628@etive.ed.ac.uk> jha@lfcs.ed.ac.uk (Jamie Andrews) writes:
>In article <257@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>>Um, "a random instance" doesn't mean a lot.  What DISTRIBUTION do you
>>want?  Are mazes with 500,000 cells to be as likely as ones with 5?
>
>     This is essentially what I meant by wanting a weighting on
>the probability of picking a clause.

I see that I did not express myself plainly.
The point is that
 -- simple distributions defined on clause selection may yield complicated
    or unintuitive distributions on *results*
 -- simple distributions on *results* may require complicated distributions
    on clause selection
 -- therefore obtaining the distribution one wants on results may
    require at least as much ``programming'' to specify the elementary
    choice probabilities as calling library routines would have involved.

To try to make this clearer, let's consider just about the simplest
possible example.  Let's have a version of member/2 which tries its
clauses in a randomly chosen order so that each element has an equal
chance of being chosen first.  (To keep things simple, assume that
the list argument is ground and the element argument unbound.)

membof(L, X) :<prob1>- L = [X|_].
membof(L, X) :<prob2>- L = [_|T], membof(T, X).

where the idea is that with probability prob1 we try the first clause,
then the second clause, or with probability prob2=1-prob1 we try the
second clause, then the first clause.

THERE IS NO FIXED NUMBER prob1 WHICH WILL YIELD THE DESIRED RESULT.

We have to *compute* prob1 from the arguments.  Specifically,
prob1=1/length(L).  Now, if we just plug that formula in, and write

membof(L, X) :< 1/length(L) >- L = [X|_].
membof(L, X) :<1-1/length(L)>- L = [_|T], membof(T, X).

then we're doing a huge amount of extra work.  It would be a VERY
clever compiler (able to prove theorems in probability theory) which
could optimise this.  We could do it ourselves, producing

membof(L, X) :-
	length(L, N),
	N > 0,
	membof(L, N, X).

membof(L, N, X) :< 1/N >, L = [X|_].
membof(L, N, X) :<1-1/N>, L = [_|T], M is N-1, membof(T, M, X).

By the time you have done this much programming, you find that the
built-in randomising has helped you very little.