Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ucbvax!decwrl!labrea!sri-unix!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Probabilistic 'or'?
Message-ID: <257@quintus.UUCP>
Date: 6 Aug 88 04:24:17 GMT
References: <613@etive.ed.ac.uk>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 30

In article <613@etive.ed.ac.uk> jha@lfcs.ed.ac.uk (Jamie Andrews) writes:
>
>generate all of them.  With the probablistic 'or', you could just
>specify what something has to be to be a maze, and let the system
>give you a random instance.
>
>     I guess it would be easy enough to write a predicate with
>clause/1 and some system random call, but this would make the code
>more messy, and (if we care about such things today) would raise
>logical problems.

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?
Take a simpler example: a random graph with vertices 1..N for given fixed N.
Just what _is_ a "random graph"?  Are all arcs equally likely?  HOW likely?
What distribution of out-degrees?  Just think about this:
if I write a random predicate
	random_list([]) <*- true.
	random_list([_|L]) <*- random_list(L).
and ask
	| ?* random_list(L).
_any_ length is permitted:  if your random LP system goes off for a million
years computing a list of 10**30 elements, it has a perfect right to.  I
wouldn't even be entitled to object if it did this nearly every time.  By
the time you've specified the distribution (what if it is input-dependent?)
you've written as much code as if you'd called library routines.

Having thought about it a bit, I believe that it would raise far worse
logical problems to try to build randomness into the language; pseudo-random
number generators can after all be specified with pure predicates--they're
just ordinary arithmetic functions.