HDTenEightyP/NetNews huggingface dataset:
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 18 Dec 92 14:25:23 GMT
Article-I.D.: alice.24438
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <1992Dec17.185017.17766@cs.uoregon.edu> debray@majestix.cs.uoregon.edu (Saumya K. Debray) writes:
>Fernando Pereira writes:
>> Nonetheless, the efficiency reasons that led to Prolog's
>> unification not having the check are pretty compelling, so I do not advocate
>> adding it to Prolog in all cases. 
>While I believe this statement, it would be interesting to actually see some
>numbers (preferably for programs other than nrev) showing how much more
>expensive unification becomes with the occurs check.
Let me refine and qualify my assertion. In typical programs that I have
written or read, fairly large terms are passed around. With a naive
implementation of the occurs check, each such term has to be fully examined
whenever it is passed as an actual parameter to a predicate. For instance,
append becomes O(n^2) rather than O(n). However, in many of the cases
the complex term is being unified with a variable occuring only once in
the head, with a term the variables in which occur only once in the
head, or the same situations arise involving variable instances that can be
shown by global flow analysis to be ``new'' (that is not occuring
anywhere else in the current resolvent). In any of those cases, the occurs
check is not needed. This is just scratching the surface, much more
sophisticated analyses have been published.

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, PO Box 636
Murray Hill, NJ 07974-0636
pereira@research.att.com
Newsgroups: comp.lang.prolog
From: peter@infko.uni-koblenz.de (Peter Baumgartner)
Subject: Re: Occurs check
Organization: University of Koblenz, Germany
	<1992Dec17.111142.24450@dcs.qmw.ac.uk> <24435@alice.att.com>
	<1992Dec17.185017.17766@cs.uoregon.edu>
Date: Fri, 18 Dec 1992 20:15:31 GMT

>In article <1992Dec17.185017.17766@cs.uoregon.edu> debray@majestix.cs.uoregon.edu (Saumya K. Debray) writes:
>
>Fernando Pereira writes:
>> Nonetheless, the efficiency reasons that led to Prolog's
>> unification not having the check are pretty compelling, so I do not advocate
>> adding it to Prolog in all cases. 
>
>While I believe this statement, it would be interesting to actually see some
>numbers (preferably for programs other than nrev) showing how much more
>expensive unification becomes with the occurs check. ...
>
That's a topic we are interested in, too. Often, people
working on the sound omission of the occur check write that carrying
out sound unification always is prohibited for efficiency reasons.
But has anybody investigated this systematically? 

In order to support the efficiency argument for omitting the occur
check, we carried out some small experiments with SEPIA-Prolog.
We ran the reverse-program on a list of about 1000 terms.  
The result was astonishing (at least to us): 
performance degrades only about 10-20 percent when using sound
unification. Here, it was necessary to work on (moderately) large terms in
order to note a difference at all. 

Maybe our observation is not true in general, and the result is due to
the clever implementation of SEPIA. Does someone know about 
the SEPIA-Implementation? 
Are there any better examples supporting the effciency argument?

	P. Baumgartner
--
____________________________________________________________________
Peter Baumgartner                      | peter@infko.uni-koblenz.de
Universitaet Koblenz,                  |
Institut fuer Informatik               | Voice: +49 261 9119-426
Rheinau 3-4, D-5400 Koblenz, Germany   | Fax:   +49 261 37524
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 20 Dec 92 22:53:14 GMT
Article-I.D.: alice.24458
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <TORKEL.92Dec20104928@bast.sics.se> torkel@sics.se (Torkel Franzen) writes:
>In article <24454@alice.att.com> pereira@alice.att.com (Fernando Pereira)
>   >I agree. Adding the first-order theory of rational trees to the left of the
>   >|- is precisely restricting the class of models under consideration
>   >from arbitrary first-order models to rational tree models.
>
>   This is not so, since the class of rational tree models cannot be
>characterized by any set of first order axioms, any more than the finite
>tree models.
It cannot be characterized by any *finite* set of first-order formulas.
Notice that I used *theory*, not program in my note. The term "theory"
in logic means any deductively closed set of formulas. In fact, for a finite
signature you can characterize the finite tree models by a finite set
of equality and inequality formulas -- that's precisely what the Clark
completion uses. I don't have handy the relevant papers on rational tree
models, but I believe the same is true for them (papers by Joxan Jaffar and
Michael Maher?).

Anyway, this is just fine print, the main points have already been made clear:
(i) the occurs check is needed for sound deduction in pure first-order
logic; (ii) unification without the occurs check is sound for
deduction over rational tree models; (iii) Prolog unification (by this
I mean what was in Prolog originally) can construct rational terms,
but may not termfinate when unifying them; (iv) there are various
unification algorithms for rational trees, the asymptotically most efficient
of which I believe are all based on UNION-FIND (DFA equivalence). 

Fernando Pereira
pereira@research.att.com
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 19 Dec 92 00:30:12 GMT
Article-I.D.: alice.24448
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <1992Dec18.175714.3917@cs.sfu.ca> jamie@cs.sfu.ca (Jamie Andrews) writes:
>I seem to dimly remember someone having
>characterized the precise theory solved by some unification
>without occurs check.  Does anyone remember the reference?
@ARTICLE{jaffar-stuckey,
	AUTHOR = {Joxan Jaffar and Peter J. Stuckey},
	TITLE = {Semantics of Infinite Tree Logic Programming},
	JOURNAL = {Theoretical Computer Science},
	YEAR = {1986},
	VOLUME = {46},
	PAGES = {141-158}
}
>     Also, I sometimes tell people that Martelli and Montanari's
>and Paterson and Wegman's linear unification algorithms are not
>used because either (a) the constant factor is too high or (b)
>the space requirements are too high.
(a) is a problem, but the main problem is that those algorithms are linear
on the *sum* of the sizes of the two terms being unified, while
(in most practical cases) the Robinson unification algorithm without
the occurs check is linear on the size of the *smaller* term. Notice
that most such unifications in Prolog involve some arbitrarily large
constructed term and a clause head, which is tyoically small, and
of bounded size. I say above "in most practical cases" because
the Robinson algorithm without occurs check is linear on the size of
the *tree unfolding* of the smaller term, but the tree unfolding of
a term may be exponential on the size of the (graph representation of)
the term and thus on the number of variable substitution steps needed
to construct the term. In contrast, the linear unification algorithms,
as well as the most efficient algorithms for rational term unification
(all in one way or another based on some version of UNION-FIND) keep
track of which subterms they have visited and they don't revisit them.
Another source of overhead for the rational term unification algorithms
is that in general they side-effect not just the leaves (variable cells)
but also internal (complex term) nodes (at least all that I have seen
do). These side effects must be kept track of to be undone on backtracking.

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, PO Box 636
Murray Hill, NJ 07974-0636
pereira@research.att.com
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 17 Dec 92 17:10:03 GMT
Article-I.D.: alice.24435
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <1992Dec17.111142.24450@dcs.qmw.ac.uk> mmh@dcs.qmw.ac.uk (Matthew Huntbach) writes:
>I have written programs which rely on the occur-check not
>happening, since they intentionally build circular structures.
>What should be so wrong with this - after all it's a standard
>programing feature in lazy functional languages.
If you think of Prolog programs as *logic* programs where the logic is
(a fragment of) first-order logic, what is wrong it that the answers
derived without the occurs-check are in general unsound. For example,
consider the first-order question

	forall x. exists y. r(x,y) ?= exists x. r(x, x)

(where ?= means ``is the rhs a logical consequence of the lhs?''). The
answer is negative, eg. take r to be the successor relation on the natural
numbers. Now convert the question to Prolog by Skolemization. The same
question maps to the Prolog question

	r(X, f(X)) ?- r(U, U)

Without the occurs check, this succeeds! Lest you think this is an artificial
example of no practical import, let me say that I have been badly bitten
by the lack of an occurs check in several natural-language parsers and
generators. Nonetheless, the efficiency reasons that led to Prolog's
unification not having the check are pretty compelling, so I do not advocate
adding it to Prolog in all cases. A clever compiler might be able to
recognize many cases of practical importance in which the check is
not needed and only call the more expensive unification with occurs check
in the remaining cases. Alternatively, careful programmers can do some of
that analysis by hand, and put explicit calls to a sound unification
when necessary.

If you want to program with cyclic terms, you have gone outside
bare first-order logic to a system in which terms are interpreted
in a different way. The theoretical framework and practical value
of that alternative were established with the Prolog II work at Marseille,
and there's certainly a sound way of thinking about Prolog with cyclic
terms. However, as far as I know there is no free lunch. Sound and
terminating unification of cyclic terms can be more costly than
unsound Prolog unification (the reverse can also happen for acyclic terms
with a lot of reentrancy, though) and that cost is incurred at every
unification in a program.

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, PO Box 636
Murray Hill, NJ 07974-0636
pereira@research.att.com
Newsgroups: comp.lang.prolog
From: joachim@ecrc.de (Joachim Schimpf)
Subject: ECLiPSe (Was: Re: Occurs check)
Reply-To: joachim@ecrc.de
Organization: European Computer-Industry Research Centre GmbH.
Date: Wed, 16 Dec 1992 18:55:13 GMT

In article 7918@cucs5.cs.cuhk.hk, jlee@cs.cuhk.hk (Jimmy Ho Man Lee) writes:
>joachim@ecrc.de (Joachim Schimpf) writes:
>
>>Our Prolog system ECLiPSe, which is the successor of SEPIA, has an option
>
>How is ECLiPSe different from SEPIA?

ECLiPSe is the integration of ECRC's Sepia and MegaLog systems. It is fully
compatible with Sepia and includes all of MegaLog's knowledge base functionality.
We can distribute the system under similar conditions as Sepia was distributed,
i.e. as object code and to academic/non-commercial research sites only.

A more detailed announcement will follow soon.

---------------------------------------------------------------------------
 Joachim Schimpf                                 Email   joachim@ecrc.de 
 European Computer-Industry Research Centre      Phone   +49 89 92699 111
 Arabellastrasse 17, D-8000 Munich 81, Germany   Fax     +49 89 92699 170
From: milan@bcsaic.boeing.com (Milan Richter)
Newsgroups: comp.lang.prolog
Subject: Re: Trilogy vendor in UK or Europe?
Date: 15 Dec 92 00:32:40 GMT
Organization: Boeing Computer Services

In article <XX4mVB2w165w@lcraft.ersys.edmonton.ab.ca> cduguay@lcraft.ersys.edmonton.ab.ca (Claude Duguay) writes:
>fred@opal.cs.tu-berlin.de (Reinhard Arlt) writes:
>
>>Who markets Trilogy in the UK?  Or in Europe?  I rang the "Complete Logic
>>Systems" USA number listed in the resource guide, but got no reply.
>>I just want to play around with constraint solving, and can't afford CHIP.
>
>I can't tell you what their address is but Trilogy was developed by a
>Canadian company based in Vancouver, BC. You migth be able to get the
>number from directory assistance and information about distributors directly
>through them.

To my knowledge, the company is presently defunct. The author of Trilogy,
dr. Paul Voda, is moving to Europe to continue development of a new version,
without constraints, though. I don't have a connection with him.

-- Milan Richter, Seattle


Newsgroups: comp.lang.prolog
From: scip2012@nusunix1.nus.sg (WU JIANHUA)
Subject: WANTED: RULE SET OF SMALL EXPERT SYSTEM
Organization: National University of Singapore
X-Newsreader: TIN [version 1.1 PL6]
Date: Mon, 14 Dec 1992 08:44:53 GMT

[ Article crossposted from comp.ai.shells ]
[ Author was  ]
[ Posted on Mon, 14 Dec 1992 08:32:15 GMT ]

Hi,

I am looking for a set of rules for expert systems. It should be
consistent and associate with some uncertain information.

Can anyone give some hints? Many thanks in advance!


Cheers,
********************************************************************************
        **   **            Wu, Jianhua
       **   ** **  **   ** Dept. of Infomation Systems & Computer Science
      **   *** ** ** * **  National University of Singapore 
 **  **   **  ** ** * **   Singapore 0511
**  **   **  ** *******    E-Mail: WuJianHu@ISCS.NUS.SG, Scip2012@NUSUNIX.NUS.SG
****   ***  **  ** **      Phone : +65 7726136       Fax: +65 7794580
From: mmh@dcs.qmw.ac.uk (Matthew Huntbach)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 18 Dec 92 09:30:45 GMT
Organization: Computer Science Dept, QMW, University of London, UK.

In article <24435@alice.att.com> pereira@alice.UUCP () writes:
>If you think of Prolog programs as *logic* programs where the logic is
>(a fragment of) first-order logic, what is wrong it that the answers
>derived without the occurs-check are in general unsound. For example,
>consider the first-order question
>
Well, yes, I'm aware of this, but Prolog is such a compromised
form of logic that I wonder if it matters. In any case, I
generally program in Strand where since there isn't full
unification, the problems of unifying cyclic terms don't occur.

Matthew Huntbach
From: cduguay@lcraft.ersys.edmonton.ab.ca (Claude Duguay)
Newsgroups: comp.lang.prolog
Subject: Re: next_to code question
Date: Sun, 20 Dec 92 07:13:52 MST
Organization: LogiCraft Corp, Edmonton, AB, Canada

awinterb@diana.cair.du.edu (Art Winterbauer) writes:
> Here's some code I don't understand.
> 
> append([],L,L) :- !.
> append([X|L1],L2,[X|L3]) :- append(L1,L2,L3). 
> 
> next_to(El1,El2,List) :- append(_,[El1,El2|_], List).
> 
> In the second edition of Clocksin and Mellish, p. 150, they state that the
> above definition of "next_to" is an example of relational programming.  By
> typing:
> 
> next_to(a,b,[c,d,a,b,q]).
> 
> for example, you'll get a true response.  I don't know why it works,
> probably because I never could quite understand how append works.  Since
> I'm missing an important concept here, could someone explain to me (and the
> net) why it works?  The debugger in the Prolog interpreter (Amziod) I have
> doesn't seem to go into enough detail to show me exactly what's happening.
> 
> Thanks,
> 
> Art

This is easier to understand if you try to explain it declaratively. Firstly,
the append predicate is nondeterministic and will provide all possible
solutions to List1 + List2 = List3.  The next_to predicate says, in plain
English, that any two elements are in sequence if they are the first two
elements of any back portion for the given list. The append predicate will
return any valid combination and the syntax [El1,El2|_] tests the first two
elements for each list returned (in the second parameter of append).

To play around with it, try using append like:

   append(Front,Back,[a,b,c,d,e,f])
   
to see what values Back returns. Another way to write next_to would be:

   next_to(El1,El2,[El1,El2|_]).
   next_to(El1,El2,[_|Tail]) :- next_to(El1,El2,Tail).

This version says, in English, that the elements are next to each other if
they are in sequence as the first two elements of the list OR if they are
next to each other in the Tail of the list.

Hope this helps a little...

Claude Duguay              cduguay@lcraft.ersys.edmonton.ab.ca 
Newsgroups: comp.lang.prolog
From: hoppet@opal.cs.tu-berlin.de (Thomas Hoppe)
Subject: Looking for code to index clauses or n-ary trees
Keywords: Indexing, predicate symbols, clauses, n-ary trees, Quintus indexer
Organization: Techn. University of Berlin, Germany
Date: Fri, 18 Dec 1992 23:33:12 GMT

Dear net'ers

for the purpose of explicit and fast storage of proof-trees, I'm
looking for some sophisticated indexing mechanism on Prolog clauses.
Clauses asserted in the Prolog DB are implicitly indexed on the
predicate symbol contained in the clause head as primary key and
usually explicitly on the first argument as secondary key. For the
purpose of a fast access to clauses over some predicate symbol
contained in the body of a clause, I need now some indexing mechanism.
I.e.\ if a clause p :- q, r. is given, I like to retrieve this clause
directly from the Prolog DB and from a given goal r without inspecting
every asserted clause and its body. 

Since a clause p :- q, r. can be regarded as tree of depth one with
root p and sons q and r, such an indexing mechanism could also be used
to index trees with an arbitrary number of sons per node.  Such an
indexing mechanism is also useful for implementing forward chaining
inference systems, thus I thought that it is maybe a good idea to ask
the Prolog community out there whether someone has implemented already
such a mechanism. 

Although the Quintus libraries contain some package called 'indexer',
which realizes an advanced indexing mechanism on arbitrary arguments
(and thus extends the secondary explicite indexing mechanism above), I
haven't found yet any library package realizing an extended indexing
mechanism of the implicite, primary type. Clearly, indexing on the
arguments of a predicate is much easier (since their number of
arguments is fixed) than indexing over an arbitrary long list of body
predicates. 

Although a Prolog clause is a term structure of nested binary symbols
(usually :- , and ;) and literals as leaves, the first idea is to
regard a clause as binary tree. On this way 'indexer' can be easily
extended for indexing binary tree's, since the number of subtree's is
fixed. But that's a level to low for my purpose: first, this has the
consequence that a large number of (:- , and ;) entries exists in the
DB, and second, for finding the clause head an algorithm would need to
'crawl up' the tree.  If instead the indexing mechanism indexes n-ary
tree's, a quicker look-up is possible. 

If you have implemented such a thing or if you know a reference for
some code, I would appreciate it. If of interest, I summarize the
responses I receive.

ADVthanxANCE, 

	Thomas Hoppe

--
Thomas Hoppe  Projekt KIT-BACK		email: hoppet@cs.tu-berlin.de
Technische Universitaet Berlin		phone: 030-314-25494
Franklinstr. 28/29			fax  : 030-314-24929
1000 Berlin 10	Germany			priv.: 030-3236564
From: torkel@sics.se (Torkel Franzen)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 21 Dec 92 05:47:35 GMT
	<24435@alice.att.com> <TORKEL.92Dec17201903@bast.sics.se>
	<24439@alice.att.com> <TORKEL.92Dec18231028@lludd.sics.se>
	<24454@alice.att.com> <TORKEL.92Dec20104928@bast.sics.se>
	<
Organization: Swedish Institute of Computer Science, Kista

In article <24458@alice.att.com> pereira@alice.att.com (Fernando Pereira)
 writes:

   >It cannot be characterized by any *finite* set of first-order formulas.

  Finiteness is not relevant here. It is a matter of what can be
expressed in first order logic. By compactness, any set of first order
formulas which has a model with the Herbrand universe
{0,s(0),s(s(0)),..} as its domain will have countable models
containing elements different from (the interpretations of) the terms
0,s(0), ec. Therefore it is not correct to say that adding the
(complete) first order identity theory of finite trees to the left of
|- is precisely restricting the class of models under consideration
from arbitrary first order models to finite tree models.  Similarly
for rational trees. Such a restriction cannot be achieved in first
order logic.
Newsgroups: comp.lang.prolog
From: rolandi@hssc.scarolina.edu (Walter Rolandi)
Subject: Quintus
Organization: USC  Department of Computer Science
Date:  7 Dec 92 15:28:23 GMT


I tried to call Quintus the other day with, I admit, a phone number
that's not been used in almost two years.  I got a message that the
number was disconnected.

Can anyone tell me where Quintus now is and what their phone number
is?

Thanks.


--

  WALTER G. ROLANDI
  USENET: rolandi@andy.hssc.scarolina.edu
INTERNET: rolandi@hsscls.hssc.scarolina.edu
Newsgroups: comp.lang.prolog
From: torkel@sics.se (Torkel Franzen)
Subject: Re: Occurs check
Organization: Swedish Institute of Computer Science, Kista
	<TORKEL.92Dec17201903@bast.sics.se> <1992Dec18.175714.3917@cs.sfu.ca>
Date: Sat, 19 Dec 1992 11:19:14 GMT

In article <1992Dec18.175714.3917@cs.sfu.ca> jamie@cs.sfu.ca (Jamie Andrews)
 writes:

   >However, there are still completeness problems, with cases
   >like
   >  x=f(x), y=f(y), x=y
   >where such systems typically loop instead of succeeding, and
   >even cases like
   >  x=f(x,g(x)), y=f(y,h(y)), x=y
   >where such systems may loop where they should fail.

  Yes, and "unification without occur check" is of course a poor way of
dealing with rational trees. Sicstus supports unification of rational
trees, and thus treats the above cases correctly. However, the argument
I criticized might as well have been applied to a proper implementation
of rational trees.
From: slzw0@cc.usu.edu
Newsgroups: comp.lang.prolog
Subject: Help! FTP-site for dos-prolog
Date: 13 Dec 92 17:03:50 MDT
Organization: Utah State University


Are there anyone out there who knows ftp site where I can get prolog
interpreter for dos machine?

Thanks

Newsgroups: comp.lang.prolog
From: peter@infko.uni-koblenz.de (Peter Baumgartner)
Subject: Re: Occurs check
Organization: University of Koblenz, Germany
Date: Mon, 14 Dec 1992 19:50:50 GMT

In article <1992Dec13.173016.8849@nntp.hut.fi> jur@robin.cs.hut.fi (Jussi Rintanen) writes:

>   Question 1: What implementations of Prolog implement the occurs check?
>   (Our university has both Sicstus and NU-Prolog.)
>


Try SEPIA-Prolog  from  ECRC  in munich/Germany.  It   has   some nice
features, including the  possibility  for sound unification.  It  also
includes "iterative deepening", so you need not program it explicitly.
Sepia is cheap and pretty fast. Contact sepia_request@ecrc.de (i'm not
quite sure about this adress)

As an alternative you could "linearize" the heads of your rules, i.e.
eliminate multiple occurences of variables in the head. For example, 
your rule

	axiom(impl(A,impl(B,A)),k).

then becomes

	axiom(impl(A,impl(B,A1)),k) :- unify(A,A1).

where unify/2 is a sound unification procedure, as can be found e.g. 
in the quintus library. This works sufficiently well for many
programs. However, the first alternative, a Prolog with built-in sound
unification, is superior (wrt. efficiency).

	Peter
--
____________________________________________________________________
Peter Baumgartner                      | peter@infko.uni-koblenz.de
Universitaet Koblenz,                  |
Institut fuer Informatik               | Voice: +49 261 9119-426
Rheinau 3-4, D-5400 Koblenz, Germany   | Fax:   +49 261 37524