HDTenEightyP/NetNews huggingface dataset:
From: smk@dcs.ed.ac.uk (Stefan Kahrs)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 17 Dec 92 14:00:38 GMT
Distribution: comp
Organization: University of Edinburgh, LFCS

In article <1992Dec17.111142.24450@dcs.qmw.ac.uk> mmh@dcs.qmw.ac.uk (Matthew Huntbach) writes:

MH   I have written programs which rely on the occur-check not
MH   happening, since they intentionally build circular structures.
MH   What should be so wrong with this - after all it's a standard
MH   programing feature in lazy functional languages.

If you allow cycles, you change the term universe.
A solution to a goal t=u where t and u are first order terms should be
a substitution (a mapping from variables to first-order terms) sigma,
such that sigma(t)=sigma(u).  Because sigma is a first-order
substitution, the resulting terms are first-order too.

If you are using unification without occur-check, then the
substitution might not be first-order, the substituted terms can
contain cycles. One can express this semantically by adding a fixpoint
operator to the term universe.
You are right that it is often useful to have cyclic terms;
but they live in this different term universe
and Prolog's = is an incomplete unification there, e.g. the goal
	A=f(A), B=f(B), A=B
usually fails to terminate, although it should either fail (in the
Herbrand universe) or succeed (in the extended universe).
It is possible to extend unification with a cycle check to make it
terminate even for cyclic terms (some Prologs have such a thing; I
even know a programming language which uses unification with cycle
check for type inference), but this is again less efficient than
ordinary = , probably similar in efficiency to unification with occur
check.

--
Stefan Kahrs	                   JANET:    smk@uk.ac.ed.dcs
LFCS, Dept. of Computer Science    Internet: smk@dcs.ed.ac.uk
University of Edinburgh            UUCP:     ..!mcsun!uknet!dcs!smk
Edinburgh
EH9 3JZ                            Tel:      (44)-31-650-5139
SCOTLAND                           Fax:      (44)-31-667-7209
Newsgroups: comp.lang.prolog
From: torkel@sics.se (Torkel Franzen)
Subject: Re: Occurs check
Organization: Swedish Institute of Computer Science, Kista
	<24435@alice.att.com> <TORKEL.92Dec17201903@bast.sics.se>
	<24439@alice.att.com>
Date: Fri, 18 Dec 1992 22:10:28 GMT

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

   >No, it is not too strong. I think you are confusing deduction in
   >an interpreted system (eg. Horn clauses over the domain of finite trees,
   >or of rational trees) with deduction that yields consequences true
   >in any model, that is, valid consequences.

  There is no confusion involved. It is merely a matter of "valid
consequences of what". The answers yielded by a Prolog system using
unification without occurs check are consequences in first order logic
of the clauses of the program together with the first order identity
theory of rational trees.
Newsgroups: comp.lang.prolog
From: jamie@cs.sfu.ca (Jamie Andrews)
Subject: Re: Occurs check
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
Date: Fri, 18 Dec 1992 17:57:14 GMT

In article <TORKEL.92Dec17201903@bast.sics.se> torkel@sics.se (Torkel Franzen) writes:
>  This is putting it too strongly, since such answers are perfectly
>sound relative to the interpretation of a (pure) program as the union
>of the clauses and the identities true in a suitable universe of
>rational trees.

     I was going to object to this, when I realized what Torkel
meant:  any answers that you *do* get out of systems without
occurs check are sound relative to the corresponding theory of
rational trees.

     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.  My guess
would be that applications which rely on the absence of occurs
check to construct cyclic structures would be likely to run into
these problems when comparing terms.  On the other hand I've
never written such an application so I could be wrong.

     Another point that comes out of this is that there isn't
just one "unification without occurs check"; we have to be more
precise about exactly what algorithm is being used before we can
tell how it's going to behave.  (I'm not even convinced that
*all* such straightforward unification algorithms would be sound
w.r.t. rational trees.)  I seem to dimly remember someone having
characterized the precise theory solved by some unification
without occurs check.  Does anyone remember the reference?

     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.  Can anyone point to
something comparing time *and space* requirements for

- a typical occurs-check unification
- a typical occurs-check-free unification
- Martelli and Montanari's linear unification
- Paterson and Wegman's linear unification
- Colmerauer's (or other) rational tree unification?

As I recall, M&M and P&W just proved that their algorithms were
linear.

thanks
--Jamie.
  jamie@cs.sfu.ca
"The Tao's net encompasses the whole universe."  - tao te ching
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 20 Dec 92 02:05:36 GMT
Article-I.D.: alice.24454
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <TORKEL.92Dec18231028@lludd.sics.se> torkel@sics.se (Torkel Franzen) writes:
>In article <24439@alice.att.com> pereira@alice.att.com (Fernando Pereira)
> writes:
>   >No, it is not too strong. I think you are confusing deduction in
>   >an interpreted system (eg. Horn clauses over the domain of finite trees,
>   >or of rational trees) with deduction that yields consequences true
>   >in any model, that is, valid consequences.
>  There is no confusion involved. It is merely a matter of "valid
>consequences of what". The answers yielded by a Prolog system using
>unification without occurs check are consequences in first order logic
>of the clauses of the program together with the first order identity
>theory of rational trees.
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. For some
applications this is fine, but as I pointed out earlier for many others
it is not. In any case, one needs to be *very* clear about what one
is assuming to the left of the |-. 

Fernando Pereira
pereira@research.att.com
From: rss@seg.npl.co.uk (Roger Scowen)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 16 Dec 92 11:45:24 GMT
Organization: National Physical Laboratory, UK


Jussi.Rintanen@hut.fi
(Message-ID: <1992Dec13.173016.8849@nntp.hut.fi>) asks:

> Question 1: What implementations of Prolog implement the occurs check?
> (Our university has both Sicstus and NU-Prolog.)
 
The current draft International Standard for Prolog provides built-in
predicates 

1)  unify_with_occurs_check/2

   For any arguments unify_with_occurs_check(X, Y) always 
   succeeds or fails, and never generates an error or 
   gives an undefined result.  

2)   =/2 (unifies) 

   When unification involves infinite trees either as arguments 
   or as a partial result of some top-down unification algorithm,
   the behaviour is undefined.  A standard-conforming processor 
   might consistently succeed or fail for a unification that is 
   formally undefined.  This predicate can be implemented 
   much more efficiently than unify_with_occurs_check/2.

For more information, see 
    R S Scowen, "An overview of Prolog standardization 
    --- progress, problems and solutions", pp922-936 
    of "Logic programming --- proceedings of the eighth 
    international conference" (K Furukawa: Editor,  MIT Press, 
    Cambridge, Massachusetts, 1991. ISBN 0-262-56058-5.)

Roger Scowen (ISO/IEC JTC1 SC22 WG17 Prolog convener),
DITC/93, National Physical Laboratory,
Teddington, Middlesex, Great Britain   TW11 0LW
Telephone: +44 81 943 6956
E-Mail: rss@seg.npl.co.uk         Fax: +44 81 977 7091
18 December 1992
From: awinterb@diana.cair.du.edu (Art Winterbauer)
Newsgroups: comp.lang.prolog
Subject: next_to code question
Date: 17 Dec 92 20:49:18 GMT
Organization: University of Denver, Denver, Colorado

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
-- 
Art Winterbauer  N0OQS
Internet:  awinterb@du.edu OR awinterb@diana.cair.du.edu
Packet:    n0oqs @ w0gvt.#neco.co.usa
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Occurs check
Date: 18 Dec 92 15:03:17 GMT
Article-I.D.: alice.24439
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <TORKEL.92Dec17201903@bast.sics.se> torkel@sics.se (Torkel Franzen) writes:
>In article <24435@alice.att.com> pereira@alice.att.com (Fernando Pereira)
> 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.
>  This is putting it too strongly, since such answers are perfectly
>sound relative to the interpretation of a (pure) program as the union
>of the clauses and the identities true in a suitable universe of
>rational trees. The logic involved is still first order logic, it's
>just that we have a somewhat stronger interpretation of programs.
No, it is not too strong. I think you are confusing deduction in
an interpreted system (eg. Horn clauses over the domain of finite trees,
or of rational trees) with deduction that yields consequences true
in any model, that is, valid consequences. If I use resolution to
show that P |- exists x. Q (by deriving the empty clause from
P /\ forall x. not Q) I have shown P |= exists x. Q, that is, for *any*
model M such that M |= P there is an assignment a for x such that
P, a |= Q. In particular (going back to my example) if I conclude
by resolution that P |- exists x. r(x,x) then in every model of P
there is an element that stands in the r relation with itself. With
P = forall u. r(u, f(u)), from which exists x. r(x,x) follows by resolution
without the occurs check, the model in which r is the successor relation
on |N and f the successor function refutes exists x. r(x, x). Thus
resolution without the occurs check is unsound as a method for deriving
valid consequences in (uninterpreted) first-order logic. It could
still be sound as a method for deriving true conseuqnces over some class of
models, eg. rational trees. But that is a *very* different thing. When
using logic for knowledge representation, we often do not know what
models to consider, but rather we are interested in characterizing
logically the class on models of interest. Thus we need to work with
valid consequence, not just true consequence in particular models.
On the other hand, if we are interested in using logic to define
relations over particular structures, eg. rational trees, resolution
modulo a particular equational theory can be the right way to go.
Still, it is important not to confuse those two alternatives.

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: lhe@sics.se (Lars-Henrik Eriksson)
Subject: Re: Array implementations?
Organization: Swedish Institute of Computer Science, Kista
	<1992Dec14.185540.2981@cs.sfu.ca>
Date: Wed, 16 Dec 1992 11:23:22 GMT

In article <1992Dec14.185540.2981@cs.sfu.ca> gregory@cs.sfu.ca (Gregory Sidebottom) writes:

   Yes, *access* is in constant time, *update* is not.  The only way to
   way to change a value in an array in Prolog implemented using
   structures is to copy it except put the new element where the old one
   was.  This takes linear time and space.  With trees, it takes log time
   and space on average, since you only have to traverse and copy one
   path in the tree.

   Now you may be able to hack constant time access and update arrays
   into Prolog using assert/retract or by linking with some C code and
   using assignment, but that wouldn't be very Prolog like.  You would
   lose most of the advantages of Prolog and might as well use a
   procedural language.  

   There is some research in the functional programming language
   community into providing logical versions of arrays with constant time
   access and update for the way arrays are usually used.  The idea is
   that if you change a value in an array by making a new copy, usually,
   you don't need to look at the old copy ever again.  If the compilers
   can recognize this 'single threaded' use of arrays, it safely
   implement the array operations using destructive assignment.  An
   approach for non-single threaded uses is to keep the original array
   and each reference to the array is associated with a set of changes
   that have taken place.  This can also can give close time constant
   time and space performance in many applications.  

This idea was described (and implemented) for logic programming at
least as early as 1984.

  Eriksson and Rayner: Incorporating Mutable Arrays into Logic Programming,
  Proceedings of the Second International Logic Programming Conference,
  Uppsala University, Sweden, 1984.

--
Lars-Henrik Eriksson                            Internet: lhe@sics.se
Swedish Institute of Computer Science           Phone (intn'l): +46 8 752 15 09
Box 1263                                        Telefon (nat'l): 08 - 752 15 09
S-164 28  KISTA, SWEDEN                         Fax: +46 8 751 72 30
Newsgroups: comp.lang.prolog
From: gregory@cs.sfu.ca (Gregory Sidebottom)
Subject: Re: Trilogy vendor in UK or Europe?
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
Date: Mon, 14 Dec 1992 18:26:59 GMT

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.

   Claude Duguay              cduguay@lcraft.ersys.edmonton.ab.ca 

I've been wondering what's going on with Trilogy myself, so I tried to
phone them up.  They still have a number listed with directory
assistance, but it is not in service and they don't have any
information about a new number.

I suspect that the company what developed Trilogy (Complete Logic
Systems) folded recently.  I did hear a couple of years ago that Paul
Voda (the original developer of Trilogy) sold the company and went
back to his home country in eastern Europe (the former Czechoslovakia,
I think) for business opportunities resulting from the fall of
Communism.

Does anybody know what is going on with Trilogy and Complete Logic
Systems?  

Greg
-- 
Greg Sidebottom,                                      | There's not a word that
Expert Systems Laboratory, Centre for Systems Science | goes here that rhymes
Simon Fraser University, Burnaby BC V5A 1S6, Canada   | with anything. -CVB
Newsgroups: comp.lang.prolog
From: dave@quintus.com (David Bowen)
Subject: Prolog job at Quintus
Organization: Quintus Corporation, Palo Alto, CA
Date: Tue, 15 Dec 1992 04:26:04 GMT


I know that this newsgroup is not supposed to be used for advertising,
but (unfortunately) there aren't too many jobs where Prolog expertise 
is a requirement, so readers may be interested to know that there is 
one currently open at Quintus.  We are looking for an experienced Prolog
programmer to join our Application Products Group and work on our WorkPro 
line of products.  Below is the job advertisement which has gone out to misc.jobs.offered as well as to the San Jose Mercury News.  Please 
address any enquiries to jobs@quintus.com.

- Dave Bowen
  VP, Product Engineering

-------------------------------------------------------------------------

Quintus Corporation, with its Quintus WorkPro product line, is
pioneering the rapidly emerging market for "customer information
solutions".  Our first product in this product line, CustomerQ, is an
information management tool which supports call tracking, solution
searching, and product defect tracking.  Key features include a
powerful graphical user interface, multi-table query-by-example
searching, solution matching, point-and-click construction of ad-hoc
reports, automatic notification and escalation, email and fax
integration, and extensive data modeling and customization
capabilities.

Quintus is currently seeking a talented software engineer to join its
Application Products Group which:

  - designs and implements extensions to the Quintus WorkPro
    technology
  - builds products based on that technology

The position requires:

  - a M.S. degree in Computer Science, or equivalent experience
  - very strong programming skills
  - experience of programming in Prolog
  - experience of programming in C

Also very useful would be knowledge of any of the following:

  - Unix system calls and libraries
  - relational databases
  - object-oriented programming
  - X Windows and Motif
  - Microsoft Windows and DOS

Please address resumes to:

    Human Resources Dept - Ref APG-SE
    Quintus Corporation
    2100 Geng Road
    Palo Alto
    CA 94303

Or send email to:

    jobs@quintus.com

Quintus Corporation is an Intergraph company.
Newsgroups: comp.lang.prolog
From: juwang@icaen.uiowa.edu (Juite Wang)
Subject: Looking Prolog-written nonlinear planner
Date: Sun, 13 Dec 1992 06:38:23 GMT
Organization: Iowa Computer Aided Engineering Network, University of Iowa
Keywords: Planning, Prolog
  Does anybody know any Prolog-written nonlinear planner?  I am new in AI planning.  I am looking for a start point to understand how it functions.  I will appreciate if somebody can help me.
			
                       Juite Wang
     Email: juwang@icaen.uiowa.edu
From: cduguay@lcraft.ersys.edmonton.ab.ca (Claude Duguay)
Newsgroups: comp.lang.prolog
Subject: Re: Turbo Prolog question
Date: Fri, 11 Dec 92 15:45:04 MST
Organization: LogiCraft Corp, Edmonton, AB, Canada

J.Cowan@cs.ucl.ac.uk writes:

> Does anyone know how an external database REF in
> Turbo Prolog is represented in C.
> 
> James Cowan

The external database Ref is a long (unsigned I think) in C. You have to
be careful with these because they combine two word parts that let the
system know where the data is located. If you're just using them as handles
(the way they should be used) then the long datatype is what you're looking
for. PDC/Turbo Prolog has a Professional User's Guide that details using
the external database with C but they point out that some of the predicates
can cause problems (presumably the nondeterministic ones, especially).

Claude Duguay              cduguay@lcraft.ersys.edmonton.ab.ca 
Newsgroups: comp.lang.prolog
From: joachim@ecrc.de (Joachim Schimpf)
Subject: Re: Occurs check
Reply-To: joachim@ecrc.de
Organization: European Computer-Industry Research Centre GmbH.
Date: Mon, 14 Dec 1992 10:38:13 GMT

Our Prolog system ECLiPSe, which is the successor of SEPIA, has an option
to enable the occurs check. ECLiPSe is available for academic sites for
a nominal fee. Please send email if you are interested.

---------------------------------------------------------------------------
 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

Newsgroups: comp.lang.prolog
From: ludemann@quintus.com (Peter Ludemann)
Subject: Re: Occurs check
Organization: Quintus Corporation, Palo Alto, CA
Date: Fri, 18 Dec 1992 19:07:11 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) ...

An extreme example is "append" for difference lists (no flames on the
terminology, please!).  Without the occurs check, the cost is O(1);
with the occurs check, the cost is O(n) on the size of the terms (in 
other words, it gets the same cost as regular append).  Normally, the
programmer knows that the occurs check isn't needed, so this is a big win.

Without the occurs check, "infinite" or "rational" terms can be produced.
I've seen one practical use for them, for representing the fixpoint
of a recursive program as a term.  No doubt, there are other uses.

-----

Peter Ludemann
From: rbs@uk.ac.ed.aisb (Robert Scott)
Newsgroups: comp.lang.prolog
Subject: What is a reduction?
Date: 14 Dec 92 14:10:31 GMT
Reply-To: rbs@aisb.ed.ac.uk
Distribution: comp
Organization: Dept AI, Edinburgh University, Scotland


Is there a standard definition of what constitutes a reduction
in a logic programming language?
In particular:

  - are system goal reductions counted?
  - are attempted goals in failed clauses also counted as reducitons?
  - are guard goals in committed-choice languages counted?
  - are output unifications in the body of a clause in committed-choice
    languages counted?

Also, is the a difference between a reduction and a logical inference?

I'd like to know the definitions of these terms so that I can
compare the speeds of various logic language implementations.




--
Rob Scott
---
Department of AI              email: rbs@aisb.ed.ac.uk
University of Edinburgh         Tel: 031-650-2718
EDINBURGH, EH1 1HN