🚀 go-pugleaf

Extract from my original posting:

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


David Warren's reply:

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

>	I have edited the details out -- BJ 


David,  

Thanks for your reply.  I was a bit sloppy in my phrasing.
You're right about memoization being enough in the XOLDT version 
of my program.  My remark was directed at memoization not being enough 
given the way that it is used in a functional language setting --- where 
all that is done is to look up a pre-computed value.  The main difference 
lies in the need to initialize the memoized call to the empty set.  As I 
alluded to in my message,  the "reach" example does not illustrate the 
full use of the "re-do" mechanism.  Here's a better example, taken from 
the "dragon book" by Aho and Ullman, page 431 (1977), to define
the set of so-called "reaching definitions" in a program flowgraph:

	out(B) = (in(B) - kill(B)) U gen(B)

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

I note your remark that you don't claim to be able to handle such 
definition.  But it would be interesting to see what XOLDT does in 
this case (you would have to refer to the dragon book for details of 
the function kill, gen and pred).

Bharat