🚀 go-pugleaf

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>