🚀 go-pugleaf

In article <1992Apr10.030227.7679@acsu.buffalo.edu> bharat@acsu.buffalo.edu (Bharat Jayaraman) writes:
>
>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.
>

/*
Ahhh Bharat, now it gets interesting. Indeed you have pointed out a
truth. In order to understand what OLDT can do, you have only to
understand what ``Datalog'' programs can do. I scare-quote the
``Datalog'' because you _can_ use function symbols, just not to build
recursive data structures. So in our example: 
	X in out(B) :- X in in(B), ~ X in kill(B).
is ``Datalog'', since this could be written as:
	in_out(X,B) :- in_in(X,B), ~ in_kill(X,B).
which is Datalog. (The restriction to Datalog is only to guarantee
termination. For general programs with function symbols, we may get
nontermination, as in Prolog, but we are guaranteed to be at least
as ``terminating'' as Prolog with all-solutions.)

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. Now the XOLDT _system_ does
support such an operation: findall/3. (Please, no flames from the
other thread on how horrible findall/3 is, and how wonderful/horrible
setof/bagof/.. are. I agree with everything anybody ever said on
that topic. (A foolish consistency is the hobgoblin...:-)) I point
out that findall/3 is part of the _system_, like setof/3 is part of a
Prolog _system_, not that there is a simple, coherent theory for it.

So with findall/3, let's see what could be done with this problem.
*/
:- ensure_loaded('~/et/xoldt.pl').
:- op(500,xfx,in).
:- table in/2.

%	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.
0 in short(X,X).
D in short(X,Y) :- X \== Y, findall(D1,(D1 in costs(X,Y)),Ds), Ds \== [], 
	min_list(Ds,1000000,D).

%	costs(X,Y) = costs2(edgesfrom(X),Y).
D in costs(X,Y) :- D in costs2(edgesfrom(X),Y).

%	costs2({to(X,D)\_},Y)  contains if X=Y then {D} else {D+short(X,Y)}.
D in costs2(Edges,X) :- to(X,D) in Edges.
D in costs2(Edges,Y) :- 
	to(X,D1) in Edges, D2 in short(X,Y), D is D1+D2.

%	my own simpler graph
to(b,2) in edgesfrom(a).
to(d,6) in edgesfrom(b).	to(c,3) in edgesfrom(b).
to(a,1) in edgesfrom(c).	to(d,2) in edgesfrom(c).

min_list([],D,D).
min_list([X|L],D0,D) :- X < D0 -> min_list(L,X,D) ; min_list(L,D0,D).

/*********************************************

Due to limitations in findall/3, D in short(X,Y) must be called with 
X and Y bound. So we get:

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

| ?- ['temparticle.pl'].
% compiling file /home/u6/warren/temparticle.pl
%  compiling file /u6/sr/warren/et/xoldt.pl
%   ... more stuff
%  xoldt.pl compiled in module user, 4.800 sec 29,596 bytes
% temparticle.pl compiled in module user, 5.016 sec 32,524 bytes

yes
| ?- member(X,[a,b,c,d]),member(Y,[a,b,c,d]),D in short(X,Y),
	write(c(X,Y,D)),nl,fail.
c(a,a,0)
c(a,b,2)
c(a,c,5)
c(a,d,7)
c(b,a,4)
c(b,b,0)
c(b,c,3)
c(b,d,5)
c(c,a,1)
c(c,b,3)
c(c,c,0)
c(c,d,2)
c(d,d,0)

no
| ?-

A number of caveats:

1. This works because the XOLDT system incorporates a loop-check
through recursive calls to findall/3. This allows the cycles to be
terminated. (It is used to implement the well-founded semantics.)

2. The version of XOLDT I distributed will NOT execute this program
correctly. (Contact me if you care why.)

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. 

4. Another, computationally better, way to do this is to use the
constraint subsystem in XOLDT, which allows you to process the cost
as a ``constraint''. So XOLDT with constraints would solve this
problem in a better way. But that, too, requires an extension of the
simple OLDT Prolog system. The example of a possibilistic program
meta-interpreter that comes with the XOLDT system does essentially
this computation. 

So, Bharat, this IS an example of a program that your set language
can handle naturally, that Prolog under XOLDT cannot (without some 
``higher-order extension''.)

-David S. Warren
 <warren@cs.sunysb.edu>
**********/