Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!usc!samsung!think!ames!uhccux!munnari.oz.au!djk
From: djk@cs.mu.OZ.AU (David Keegel)
Newsgroups: comp.lang.prolog
Subject: Re: Fun. vs. Logic
Message-ID: <DJK.89Nov23184835@munginya.cs.mu.OZ.AU>
Date: 23 Nov 89 07:48:35 GMT
References: <11500018@hpldola.HP.COM> <11500019@hpldola.HP.COM>
Sender: news@cs.mu.oz.au
Reply-To: djk@cs.mu.Oz.AU
Organization: Computer Science Dept, The University of Melbourne, Australia
Lines: 108
In-reply-to: patch@hpldola.HP.COM's message of 22 Nov 89 07:27:54 GMT
Cc: djk@murtoa

I'll just respond to a couple of points in this (LONG) article.

In article <11500019@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes:

] the danger of NON-TERMINATION is constantly rearing its ugly head.

] I can either document these dangers in comments, mode declarations, or some
] other "bag" on the side of the language, or I can rewrite my predicate to be
] robust.  I, a self-styled purist, usually opt for the latter.

Or you can use a co-routining system like NU-Prolog which can often
delay evaluation of a predicate which would cause infinite loops.

]     object([]).
]     object([C|X]) :-
]	   object(X),
]	   construct(C, X).

I don't understand why you don't have "construct(C, X), object(X)" as
the body of the second clause, so you can use tail recursion. Never mind.

] By the way, I'll bet that a lot of predicates which SEEM to have infinitely
] many solutions in some directions can be recast so that they don't.  The
] problem is:  it's a major pain in the ass.

Your example doesn't have show infinite _solutions_, but infinite
_computation_. This is a horse of a different colour. (Except we all
know that there is only one colour of horses :-)

] Here's an example.  Let's write a predicate which defines "sequences of
] natural numbers" in a straightforward way.
]
]     sequence([]).
]     sequence([N|Ns]) :-
]         natural(N),
]         sequence(Ns).
] 
]     natural([]).
]     natural(s(N)) :-
]         natural(N).
] 
]     card([], []).
]     card([_|Ns], s(N)) :-
]         card(Ns, N).
] 
] Now we look for sequences of cardinality 2 (s(s([]))):

(I thought s(s(....(s(0))...)) was the standard notation, but never mind.)

]     sequence(Ns), card(Ns, s(s([]))).

] We get one solution Ns=[[],[]], and on backtracking we fly off into the
] weeds.

This problem is easy to solve in NU-Prolog. By writing
	?- sequence(List) when List.
NU-Prolog will delay when List is a variable. This means your call to
sequence/1 will initially delay (intuitively: ``call me when you know
what the sequence is''), and card/2 will start computing. Now instead of
testing Ns, card/2 is _generating_ Ns.

As it instantiates Ns, sequence/1 can wake up and test that each
element is a natural number (in fact it generates the numbers). Since
card instantiates Ns to [_1, _2], sequence can't "fly off into the
weeds". Natural/1 still generates infinite solutions, but this is the
intended behaviour -- you asked for all sequences of two natural
numbers. (_This_ is what Richard was talking about, I presume.)


] In order to make things more efficient, I'll have to start
] using more ad-hoc data structures.  For example, I could represent "sets" as
] trees and get O(logN) access time.  But I'd have to give up my so-called
] "constructive" ideal:  I doubt that it's possible to write omni-directional
] predicates for manipulating trees, since they're doubly-recursive.

I don't understand. What is the problem with double recursion? Why do
you call trees "ad-hoc"?

] Besides, what is "first-order logic" other than Horn clauses?  (That's not a
] rhetorical question.)

First-order logic includes negation (you have heard of that, haven't
you? :-), as well as implication and quantifiers.

] I'd like to see NU Prolog working on this database:

]     person(pat).
]     person(diana).

] with this query:

]     ?- not person(X).

] I'm guessing that either X remains an unbound variable which is constrained
] to not be a person, or the query freezes on X.  What DOES happen?

Your query fails immediately, because X only occurs once. A query

	?- not person(X), X = _.

will delay (freeze) the not, and "flounder" because nothing instantiates X.
(Uniquely occurring variables have existential quantification where
they occur; in this case _inside_ the not. Or something like that.)

--
                        David Keegel    (djk@cs.mu.OZ.AU)

   "Flattery will get you nowhere, unless someone else does it to you"