Path: utzoo!mnetor!uunet!lll-winken!lll-tis!mordor!sri-spam!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: A Suggested Additional Predicate for Prolog
Message-ID: <767@cresswell.quintus.UUCP>
Date: 14 Mar 88 05:02:58 GMT
References: <10303@shemp.CS.UCLA.EDU>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 55

In article <10303@shemp.CS.UCLA.EDU>, gast@CS.UCLA.EDU writes:
[ he wants backtrackable assert and retract, and concentrates on
  back_retract(Clause).
]
> If there were some way to temporarily
> retract a clause, but leave it's position in the database unchanged,
> programming permutations would be much easier and faster.

Eh?  Remember, N! gets *very* big, *very* fast.  What does it matter how
fast "programming permutations" is, when doing it at all is the kiss of
death to efficiency?  I hope I've misunderstood.

> By the way, assert and retract are unlike most predicates in that
> their bindings are not undone on backtracking.

Eh?  The variable _bindings_ most certainly ARE undone!  The change to
the data base is not, but then write/1 doesn't erase the screen and
read/1 doesn't reach out and shove your fingers backwards either.

> While it would be difficult to write back_retract in pure Prolog, it would
> be easy to implement it in the implementation language if that language
> is not Prolog.  A possible method assuming an ascii computer is
> to change the first character of the primary functor of the clause.

You forgot the smiley.  The only Prolog interpreter I've ever seen where
the text of the clause was stored was one done by Michael McCord in SNOBOL.
There are ways that an enabled/disabled flag could be cheaply associated
with a clause, but I strongly suspect that Mr Gast hasn't thought through
the interactions between back_retract/1 and the cut.  What is supposed to
happen if I do
	back_retract(foo), abort.
Is foo supposed to be gone, or not?

> In all of these cases back_retract 
>     1) changes an N**N problem to a N! problem.

Stirling's approximation:
	N! = sqrt(2*pi*N) * (N/e)**N * (1 + 1/12N + 1/288N**2 + O(1/N**3))
For example, (N!)/(N**N) ~=~ 9x10**-9 for N=21, which looks like a big
improvement, but 21! ~=~ 5x10**19.

Suppose an operation takes 1 microsecond, for what value of N would doing
it N! times take more than a year?  There are roughly 3.16x10**7 seconds
in a year, so for what value of N is N! > 3.16x10**13?  16! is 1.5 times
too small, 17! is 11 times too big.

Think about it:  if the basic operation costs 1 microsecond, and we do
N! of them, for N=17 it will take 11 years.  For N=14, it will take a
little over a day.

Converting an N**N algorithm to an N! one converts something which is
practically impossible to something which is only practically impossible.

-- 
Those who do not understand Prolog are
condemned to reinvent Lisp, poorly.