HDTenEightyP/NetNews huggingface dataset:
Newsgroups: comp.lang.prolog

/ hpbbrd:comp.lang.prolog / ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) /  5:35 am  Apr  9, 1992 /

> Nope, not at all.  The PD implementation is based on assert/retract,
> and most "bubble-in-the-heap" findall/3 implementations I've heard of
> will introduce new variables too.  What you need is something that collects
> solutions just like findall/3 then walks along them putting back the
> original variables whenever it is possible to do so.

Can somebody point me to a description of the `bubble-in-the-heap' technique ?

	Thanks in advance,

		Jens Kilian.

--
Internet: jensk@hpbbn.bbn.hp.com      HPDESK : JENS_KILIAN%XU@HP1200
MausNet:  Jens Kilian @ BB                     KILIAN_JENS/HP1200_XU@hpbbi4
Phone: (0|+49)7031-14-1726            TELNET : 778-1726
Fax  : (0|+49)7031-14-2049
-------------------------------------------------------------------------------
As the air to a bird, or the sea to a fish, so is contempt to the contemptible.
From: kean@cs.ubc.ca (Alex Kean)
Newsgroups: comp.lang.prolog
Subject: Re: To J.W. Lloyd (Foundations of Logic Programming)
Date: 14 Apr 92 20:13:03 GMT
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada

I have a similar problem in 

        "Updating Knowledge Base", 
         New Generation Computing (8) 1990.
         
pp 77-78:

    P2 =     r(X) <- p(X)
             r(X) <- p(X) ^ q(X)

     comp(P2) |= forall (x) p(X) <- q(X)

I presume comp(P2) is program completion (which I know nothing about), then

   r(X) equiv ( p(X) v (p(X)^q(X)) )  |=  forall (x) p(X) <- q(X).

I couldn't figure it out how the above entailment is true.
Maybe I am missing something about program completion, or maybe
something very simple. Please advise.

Thanks,
Best Regards,

Alex Kean <kean@cs.ubc.ca>

Department of Computer Science           
University of British Columbia
6356 Agricultural Road,
Vancouver, British Columbia
Canada V6T 1Z2

Tel: +1 (604)-822-4912
Fax: +1 (604)-822-5485
Newsgroups: comp.lang.prolog
From: fbahg@nuscc.nus.sg (Himawan Gunadhi)
Subject: Help needed with sbprolog -- can't run
Organization: National University of Singapore
Date: Wed, 15 Apr 1992 10:03:03 GMT


I have just installed sbprolog on a DECstation 5000/120, running Ultrix
4.2. I get something like the following when I try to start it up:

sbprolog/sim > sbprolog ../modlib/\$readloop
sbprolog/sim > Fixed up unaligned data access for pid 3971 (sbprolog) at pc 0x40416c

this message is repeated endlessly until I abort. What went wrong?
Thanks for any help I can get.
-- 
Himawan Gunadhi                  	INTERNET: fbahg@nuscc.nus.sg
Dept of Decision Sciences      	 	BITNET  : fbahg@nusvm
National University of Singapore
From: bharat@acsu.buffalo.edu (Bharat Jayaraman)
Newsgroups: comp.lang.prolog
Subject: Re: memoization
Date: 10 Apr 92 03:02:27 GMT
Organization: State University of New York at Buffalo/Comp Sci

In message <1992Apr8.161318.17505@sbcs.sunysb.edu>, David has translated 
the program

       out(B) = (in(B) - kill(B)) U gen(B)
       in (B) = U {out(P) : P in pred(B)}

as follows (glad to hear that this brings back fond memories (8-)).

	X in out(B) :- X in in(B), ~ X in kill(B).
	X in out(B) :- X in gen(B).
	X in in(B)  :- X in out(P), P in pred(B).

It appears from this example and the previous one ("reach") that XOLDT avoids 
working with the actual set, but simply return the elements one at a time 
at the top-level.  There are problems where there seems to be a need to 
form the resulting set at an intermediate stage of the computation, perform 
some operation on it, and proceed until convergence is reached.  To be
more concrete, here's a formulation of shortest distance between a 
vertex-pair in a graph (in the SEL notation) illustrating this need.

	closure costs/2, costs2/2.	%closure = memo + redo

	short(X,Y) = if X=Y then 0 else min(costs(X,Y)). 
		% min returns smallest number in a set; it returns 
		% some large number ("infinity") if the set is empty.

	costs(X,Y) = costs2(edgesfrom(X),Y).

	costs2({to(X,D)\_},Y)  contains if X=Y then {D} else {D+short(X,Y)}.

	edgesfrom(a) = {to(b,10), to(c,16), to(d,8)}.  % to(vertex,distance)
	edgesfrom(b) = {to(a,20), to(c,2), to(e,4)}.
		etc.

	% use a different representation for the graph if you prefer.

Bharat
From: feldman@cs.tulane.edu (Damon Feldman)
Newsgroups: comp.lang.prolog
Subject: Purpose of Prolog Semantics
Date: 8 Apr 92 00:46:04 GMT
Article-I.D.: cs.10805
Organization: Computer Science Dept., Tulane University, New Orleans, LA

What are the advantages to the formal semantics of (pure) Prolog?
In particular what are the individual advantages of the fixpoint
semantics and the least model semantics?

My feeling is that the model-theoretic semantics (declaritive) is by
far more important than the others, because it allows the programmer
to think in the predicate calc. rather than mentally model the actions
of the interpretor.  The fixpoint semantics is then little more than a
link to the least model semantics.  I'd like to hear what other people
think about this.

Damon

-- 
Damon Feldman                  feldman@rex.cs.tulane.edu
Computer Science Dept.         Tulane University, New Orleans LA, USA
From: abreu@ionie.inria.fr (Salvador Abreu)
Newsgroups: comp.lang.prolog
Subject: Re: Modules for Prolog
Date: 6 Apr 92 16:46:39 GMT
Organization: INRIA - Rocquencourt, France
In-reply-to: bp@dcs.ed.ac.uk's message of 2 Apr 92 18:36:55 GMT

See also the stuff on Contextual Logic Programming:

	@InProceedings{MonteiroP89,
	    author={Monteiro, L. and Porto, A},
	    title={Contextual Logic Programming},
	    pages={284--299},
	    crossref={ICLP89}
	}

	@InProceedings{LammaMN89,
	    author={Lamma, E. and Mello, P. and A. Natali},
	    title={The Design of an Abstract Machine for Efficient
		   Implementation of Contexts in Logic Programming},
	    pages={303--317},
	    crossref={ICLP89}
	}

	@Proceedings{ICLP89,
	  title =       {Proceedings of the Sixth International Conference on
			 Logic Programming},
	  year =        {1989},
	  editor =      {Levi, Giorgio and Martelli, Maurizio},
	  publisher =   {MIT Press},
	  address =     {Cambridge, Massachusetts London, England},
	}
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: term-encoding sets so that unify = intersect
Date: 13 Apr 92 06:04:03 GMT
Organization: Comp Sci, RMIT, Melbourne, Australia

In article <2521@keele.keele.ac.uk>, csa09@seq1.keele.ac.uk (P. Singleton) writes:
about the trick of representing subsets of 1..N as 0, N-1 variables, 1:

> No doubt this is in "The Craft of Prolog", which I _still_ haven't
> bought, or even read much of, but can anyone cite an original or early
> appearance of this trick?

In the Quintus library, library(vsets) contains the text:
    Richard A. O'Keefe got this trick from
    Fernando C. N. Pereira who figured it out after
    Alain Colmerauer told him it could be done.

The fundmamental idea here is the use of variables as switches.  It doesn't
matter how the switches are distributed, the important thing is that
unifying two variables = closing a switch, and
having two distinct values at the ends of a chain of switches =
    "blowing a fuse" if all the switches are closed

For example, you can use this trick to implement "one out of N" constraints
in Prolog, where you can say, in effect:  X in 1..N, X ~= i.  (The neat
trick here is setting up a network of switches so that once N-1 values
have been ruled out, X is automatically bound to the remaining one.)

> I have generalised it to domains which may grow after some
> subsets have already been denoted: one way is to leave each list
> somewhat unbound at its tail, and a more ambitious variation uses
> sparse binary trees which should be more efficient for small subsets
> of large domains.  Dare I claim originality for these in my thesis?

Lists are not the important point.  library(vsets), for example, uses
compound terms (which makes fast "X ~= i" statements possible).
I have recently been trying to come up with a good representation for
intervals, and it looked as though sets would be no harder.  My current
idea is to use something would could fairly be called a sparse binary tree.
I wonder whether we have the same idea?  It sounds as though you're
further along.

-- 
I am writing a book on debugging aimed at 1st & 2nd year CS students using
C/Modula/Pascal-like languages.  Please send suggestions (other than "you
_must_ cite "C Traps and Pitfalls") to ok@goanna.cs.rmit.oz.au
From: bharat@acsu.buffalo.edu (Bharat Jayaraman)
Newsgroups: comp.lang.prolog
Subject: Re: memoization
Date: 13 Apr 92 00:11:43 GMT
Organization: State University of New York at Buffalo/Comp Sci

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

> In article <1992Apr12.172448.21191@acsu.buffalo.edu> bharat@acsu.buffalo.edu:
>>Regarding 4), may I ask what is a "dynamic-programming solution", i.e.,
>>would you not entertain a top-down solution with memoization?   If not, 
>>why not?  This is a crucial question,  as it has serious implications for all 
>>WAM-based implementations.

> Many thanks for the references. As for "dynamic programming" solutions,
> I was concerned more specifically with the ability to imitate the best
> dynamic programming solutions for problems such as shortest path, not just
> with the ability to store intermediate results (which may not be enough).

You're welcome --- my basic point was that those optimizations with sets 
can be arranged very nicely in a functional-language setting under 
a top-down regime.  And thanks for mentioning the work by R and S 
on distributing min over sets.  

Regarding dynamic programming and memoization,  I have always thought 
that memoization yields the same order of performance as dynamic 
programming, faring better or worse (to within a constant factor) 
depending upon the problem at hand.  But I would think that, for
problems "such as shortest path", memoization would fare better
than dynamic programming because one doesn't have to solve all possible 
subproblems (as one would if one imitates dynamic prog. strictly), 
e.g.,  there might be unreachable segments of the graph that have no 
bearing on the shortest path for a given vertex pair, and a top-down 
scheme with memoization would naturally avoid them.  On the down-side, 
accessing those memo-tables efficiently is not a trivial matter (the
constant-factor problem), but work is in progress on that front ...

Bharat Jayaraman
bharat@cs.buffalo.edu
Newsgroups: comp.lang.prolog
From: enrico@cs.uh.edu
Subject: Re: To all who posted supposedly solutions of J.W. Lloyds example
Organization: University of Houston
Date: Wed, 15 Apr 1992 15:29:58 GMT

In article <3729@tuegate.tue.nl> wsbusup4@rwa.urc.tue.nl (Jan Stout) writes:
> 
> You all assume that :- means logical equivalence, i.e. <->, but I was taught
> that it means logical consequence, i.e. <-.
> 
> Surely the :- looks more like an <- than like a <->. I was even told that
> the :- was designed to look like the --in most charactersets absent--
> \leftarrow symbol.
> 
> 							Jan Stout.

Yes, you are correct saying that :- means <-, but you must remember
that by definition when you construct the completion of a program P 
(Comp(P)) you transform the implications in logical equivalences; that
is if you have a definition for a predicate p

	p :- q1
	...
	p :- qn

then in Comp(P) you will have

	p <-> (q1 v ... v qn)

(modulo the usual quantifications....)

				Ciao
					Enrico

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

Pontelli Enrico
University of Houston
Dept. Computer Science
Newsgroups: comp.lang.prolog
From: warren@sbwarren.cs.sunysb.edu (David Scott Warren)
Subject: Re: Memoization
Organization: State University of New York at Stony Brook
Date: Tue, 7 Apr 1992 18:12:06 GMT

In article <1992Apr7.151903.28393@acsu.buffalo.edu> bharat@acsu.buffalo.edu (Bharat Jayaraman) writes:

>....  To 
>motivate a related but perhaps more general use of memoization,  consider 
>the following natural program for the set of reachable nodes of a graph,
>represented as a set of ordered pairs edge(a,b): 
>
>reach(V, G)    = {V}  U  {Y : X in adjacent(V, G),  Y in reach(X, G)}
>
>adjacent(V, G) = {A : edge(V,A) in G}	  
>
>This program would loop if graph G is cyclic, but wouldn't under memoization.
>However, memoization alone is not enough to compute the desired answer!  

I don't understand this claim. I think that memoization (as I
understand it, as OLDT) DOES compute the desired answer. Consider
the following Prolog translation of Bharat's program:

/************temp.pl***************************************/
:- ensure_loaded('~/xoldt/xoldt.pl').
:- op(700,xfx,in).
:- table in/2.

%reach(V, G)    = {V}  U  {Y : X in adjacent(V, G),  Y in reach(X, G)}
V in reach(V,_G).
Y in reach(V,G) :- X in adjacent(V,G), Y in reach(X,G).

%adjacent(V, G) = {A : edge(V,A) in G}	  
A in adjacent(V,G) :- edge(V,A) in G.

% example cyclic graph
edge(a,b) in g1.
edge(a,c) in g1.
edge(b,d) in g1.
edge(d,b) in g1.
/**********************************************/

I'm making no claim about being able always to translate programs in
Bharat's langauges into Prolog so directly, but this does seem to be
a relatively straightforward translation. The (:- table in/2.)
directive is to tell my memoing subsystem to memo the in/2 predicate.
Executing this with my XOLDT system (Plug: see an earlier message on
how to obtain it), I get: 

%%%%%%%%%%%%%%%%%%%%%%%%%%%
warren% qp3
qp3
Quintus Prolog Release 3.0 (Sun-4, SunOS 4.1)
Copyright (C) 1990, Quintus Computer Systems, Inc. All rights reserved.
1310 Villa Street, Mountain View, California U.S.A. (415) 965-7700

| ?- ['temp.pl'].
['temp.pl'].
% compiling file /home/u6/warren/temp.pl
% compiling file /u6/sr/warren/xoldt/xoldt.pl
% ...loading comments deleted
% xoldt.pl compiled in module user, 4.700 sec 30,056 bytes
% temp.pl compiled in module user, 4.850 sec 32,428 bytes

yes
| ?- X in reach(a,g1).
X = a ;

X = b ;

X = d ;

X = c ;

no
| ?- X in reach(b,g1).

X = b ;

X = d ;

no
| ?- a in reach(X,g1).

X = a ;

no
| ?- 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This does seem to me to be the desired answers. Am I ``desiring''
the wrong thing? Note that a correct implementation of memoing does
indeed compute a least-fixed-point. 

-David S. Warren
 <warren@cs.sunysb.edu>
From: lipton@saul.cis.upenn.edu (Jim Lipton)
Newsgroups: comp.lang.prolog
Subject: prolog for mac
Date: 12 Apr 92 02:04:29 GMT

What prologs are avilable for the MAC (Powerbook, Classic). Are any public domain versions
available? 

Please respond directly to my e-mail address. Thanks.

Dept. of Mathematics                   1610 Rodman st.
4C17 Rittenhouse Lab,                  Philadelphia, PA 19146
University of Pennsylvania             home phone:  (215) 731-0139
Philadelphia, PA  19104                Office phone: (215)-898 5196

           E-MAIL: lipton@saul.cis.upenn.edu
    FAX: (215) 898-2010 (specify J. Lipton, c/o Math Dept.)

    

Newsgroups: comp.lang.prolog
From: ad@munta.cs.mu.OZ.AU (Andrew Davison)
Subject: LP Newsletter Call
Originator: ad@munta.cs.mu.OZ.AU
Organization: Department of Computer Sci, University of Melbourne
Date: Thu, 9 Apr 1992 09:43:12 GMT


Logic Programming Newsletter - SUBMISSIONS 
------------------------------------------

Issue 5/2 of the Newsletter is at the printers
and if you're a member of the Association of Logic Programming
(ALP) you should be receiving a copy in the next couple of weeks.

Never one to take a rest, I'm starting to gather contributions
for the next issue.

We'll print almost anything relevant to LP. For instance,
news on new products, abstracts, short notes on 
research (1-2 pages), your views on some aspect of LP,
trip reports, announcements of workshops,
conferences, meetings, etc.


The submission deadline is June 5th
                           --------

Contributions are welcome by email, floppy disk (MAC or PC - please
include an ASCII version) or by mail for shorter contributions.
By ASCII, I mean plain text files - not LaTex please. 

Preference is STRONGLY given to material received via email or 
on disc - it saves a lot of retyping.

My address is :

	Andrew Davison,
	Dept. of Computer Science,
	University of Melbourne,
        Parkville,
        Melbourne, Victoria 3052,
        AUSTRALIA

Email:   ad@cs.mu.oz.au
Fax:	+61 3 348 1184
Phone:	+61 3 344 7207 / 5230
Telex:   AA 35185


Thanks,
    Andrew


P.S.
I've received a number of messages asking about the ALP, and how
to join. The best person to contact about these matters is :

        Cheryl Anderson,
        ALP Administrative Secretary,
        Dept. of Computing,
        Imperial College,
        180 Queen's Gate,
        London, SW7 2BZ, UK

Email:   csa@doc.ic.ac.uk
Fax:    +44 71 589 1552
Phone:  +44 71 589 5111 x5011
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: term-encoding sets so that unify = intersect
Date: 12 Apr 92 20:34:48 GMT
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <2521@keele.keele.ac.uk> csa09@seq1.keele.ac.uk (P. Singleton) writes:
>
>Chris Mellish told me of a trick attributed, in Prolog folklore, to
>Colmerauer, whereby a subset of N values is denoted by a list of N+1
>variables, each adjacent pair corresponding to one possible element.
>Iff a pair share, that element is not in the subset.
> [...] can anyone cite an original or early
>appearance of this trick?

I believe Chris heard of the trick and the attribution from me.
When I visited Marseille in 1977, Alain Colmerauer gave me as a puzzle
the question of representing subsets of a finite
set so that non-empty intersection is represented by unification.
I spent a long evening working on it, and came up with some encoding,
but not as elegant as what you describe, which is the solution that
Alain showed me the next morning. I don't think the trick was ever described
in print by him.
>I have generalised it to domains which may grow after some
>subsets have already been denoted. [...]
> Dare I claim originality for these in my thesis?
As far as I know, that is new.

Fernando Pereira
AT&T Bell Laboratories, Murray Hill, NJ
pereira@research.att.com
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: ?: Efficient implementation of HASHING in PROLOG
Keywords: Prolog, Hashing
Date: 15 Apr 92 04:44:16 GMT
Organization: Comp Sci, RMIT, Melbourne, Australia

In article <1992Apr14.181452.6752@quintus.com>, ludemann@quintus.com (Peter Ludemann) writes:
> And in some Prologs, the hashing function is available to programmers,
> so that complex terms can be hashed.  So, for example, you can do:
> 
> foo(X,Y,Z) :- hash_term(X-Y,Hash), foo2(Hash,X,Y,Z).
> 
> add_foo(X,Y,Z) :- hash_term(X-Y,Hash), assertz(foo2(Hash,X,Y,Z)).

Note that the predicate SHOULD be called term_hash(Term, Hash);
with the name hash_term/2 one expects the hash argument to precede
the term argument.

-- 
I am writing a book on debugging aimed at 1st & 2nd year CS students using
C/Modula/Pascal-like languages.  Please send suggestions (other than "you
_must_ cite "C Traps and Pitfalls") to ok@goanna.cs.rmit.oz.au
From: gmartin@mcs213f.cs.umr.edu (Greg Martin )
Newsgroups: comp.lang.prolog
Subject: Help needed with DCG.
Date: 16 Apr 92 15:20:32 GMT
Organization: University of Missouri - Rolla

Hi, everyone.  I'm in an introductory AI class this semester,
and we've been dealing with DCG's of late.  We're supposed
to write a query language that will be used to construct
Prolog queries to 5 databases.  My problem is not with
the DCG per se, but rather with handling 'variables', that
is variables in the query.
An example of a query would be:

retrieve country where Population > 1000.  

Note: that's thousands of thousands.  Anyway, I'm having
trouble figuring out how to handle Population and other
'variables'.  They're coming through as quoted atoms, as
expected.  Any ideas on how to turn this into a variable,
after determining the meaning?  Or am I taking the wrong
tack here?  This may be a really trivial problem, but I'm
fairly new to prolog, and I've been puzzling over this for
about 2 weeks.

Thanks,
Greg


""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"  O softly singing lute, / See with my tears thou time do keep.           "
"  Yet softly, gentle strings, / Agree with love that cannot sleep.        "
"  Sorrow hyst whenas it sings. / When tears do fall then sighs arise.     "
"  So grief oft shines in most sad eyes, / Yea love through heart it dies. " 
"         -Francis Pilkington, 1624                                        "
"  Greg Martin  gmartin@cs.umr.edu          What disclaimer???             "
From: wsbusup4@rwa.urc.tue.nl (Jan Stout)
Newsgroups: comp.lang.prolog
Subject: To all who posted supposedly solutions of J.W. Lloyds example
Date: 15 Apr 92 10:12:15 GMT
Reply-To: wsbusup4@urc.tue.nl
Organization: Eindhoven University of Technology, The Netherlands


You all assume that :- means logical equivalence, i.e. <->, but I was taught
that it means logical consequence, i.e. <-.

Surely the :- looks more like an <- than like a <->. I was even told that
the :- was designed to look like the --in most charactersets absent--
\leftarrow symbol.

							Jan Stout.
From: pereira@alice.att.com (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: memoization
Date: 11 Apr 92 17:26:22 GMT
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs

In article <1992Apr10.211118.18102@sbcs.sunysb.edu> warren@sbwarren.cs.sunysb.edu (David Scott Warren) writes:
>In article <1992Apr10.030227.7679@acsu.buffalo.edu> bharat@acsu.buffalo.edu (Bharat Jayaraman) writes:
>>
>>[...] There are problems where there seems to be a need to 
>>form the resulting set at an intermediate stage of the computation, perform 
>>some operation on it, and proceed until convergence is reached. To be
>>more concrete, here's a formulation of shortest distance between a 
>>vertex-pair in a graph [...]
> [...]
>And as David H.D. Warren pointed out in his seminal paper in 82 on
>``Higher-order extension to Prolog...'', there are times we need
>something like setof/3, to ``extensionalize'' a predicate. The
>natural translation of your program to ``Prolog'' would require a
>setof-like operation, it seems to me.
> [...]
>3. This is not a particularly good way computationally to solve this
>problem. The loop checking is the kind you get in Prolog's top-down
>strategy, which can end up doing a lot of redundant computation. 

An interesting alternative is the treatment of aggregates in bottom-up
execution of logic programs developed by Sudarshan and Ramakrishnan, which
yields an efficient dynamic-programming algorithm for examples like
shortest path. The problem with explicit set comprehensions for problems
of this kind is that the inference system cannot take advantage of the
distributivity of the aggregation operator, say min, over set construction.
S. and R. provide a method for specifying such properties and a program
transformation algorithm that uses the specification to eliminate the
need for explicit set construction.

More generally, one could ask the question: given a set of recursion
equations over sets over a signature Sigma of set functions (eg. union,
set difference, selection of extremal elements according to some order, etc.),
under what conditions on Sigma and the allowed expressions on the rhs
of the equations do we have

	1) fixpoints
	2) least fixpoints reachable in at most omega steps
	3) equivalent logic programs, replacing each set A by an
	appropriate membership predicate (aggregations allowed)
	4) efficient dynamic-programming solutions

1) and 2) seem clearly related to LP semantics via something like 3), but
I haven't seen (or had yet the time to investigate) an exact connection.
Anyone know of papers on those issues?

Fernando Pereira
AT&T Bell Laboratories, Murray Hill
pereira@research.att.com