🚀 go-pugleaf

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

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

Thanks for the example. Indeed XOLDT can handle this one, too. Consider:
/*****************temp1.pl****************/
:- ensure_loaded('~/xoldt/xoldt_wfs.pl').
:- op(500,xfx,in).
:- table in/2.

%	out(B) = (in(B) - kill(B)) U gen(B)
X in out(B) :- X in in(B), ~ X in kill(B).
X in out(B) :- X in gen(B).

%	in (B) = U {out(P) : P in pred(B)}
X in in(B) :- X in out(P), P in pred(B).

% Example 12.11 (p. 434+) from Aho/Ullman Green Dragon
d1 in gen(b1).	d2 in gen(b1).	d3 in gen(b2).
d4 in gen(b3).	d5 in gen(b4).

d3 in kill(b1).	d4 in kill(b1).	d5 in kill(b1).	d1 in kill(b2).
d2 in kill(b3).	d5 in kill(b3).	d2 in kill(b4).	d4 in kill(b4).

b2 in pred(b1).	b1 in pred(b2).	b5 in pred(b2).	b2 in pred(b3).
b3 in pred(b4).	b3 in pred(b5).	b4 in pred(b5).	
/**********************************************/

And executing it, I 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

| ?- ['temp1.pl'].
['temp1.pl'].
% compiling file /home/u6/warren/temp1.pl
%  compiling file /u6/sr/warren/xoldt/xoldt_wfs.pl
%	...compiling msgs deleted
%  xoldt_wfs.pl compiled in module user, 4.966 sec 35,184 bytes
% temp1.pl compiled in module user, 5.217 sec 37,596 bytes

yes
| ?- X in out(B), write(X in out(B)), nl, fail.
d1 in out(b1)
d2 in out(b1)
d2 in out(b2)
d3 in out(b2)
d3 in out(b3)
d3 in out(b4)
d3 in out(b5)
d4 in out(b3)
d4 in out(b5)
d4 in out(b2)
d5 in out(b4)
d5 in out(b5)
d5 in out(b2)

no
| ?- X in in(B), write(X in in(B)),nl,fail.
d1 in in(b2)
d2 in in(b2)
d2 in in(b1)
d2 in in(b3)
d3 in in(b1)
d3 in in(b3)
d3 in in(b4)
d3 in in(b5)
d3 in in(b2)
d4 in in(b4)
d4 in in(b5)
d4 in in(b2)
d4 in in(b1)
d4 in in(b3)
d5 in in(b5)
d5 in in(b2)
d5 in in(b1)
d5 in in(b3)

no
/*************************************************************/

which agrees with the answers given by A/U on p.436.

A few comments: 

1. Again the translation to Horn clauses seems very straightforward.
The translation is meant to be close syntactically to the original.
If I were writing this directly in Prolog, I probably wouldn't use
the in/2 predicate. 

2. I'm using the xoldt_wfs version of XOLDT system (it comes with
it) because it defines ~ as negation-as-failure, and computes the
well-founded semantics. Here, of course, the program is (locally)
stratified (and safe), so a simpler treatment of negation would be
sufficient. 

3. XOLDT should work for any of these kinds of mutually recursive
definitions of finite sets of finite objects.

4. Thanks for sending me back to the GREEN Dragon book. My copy is old
and yellowed and was the book I used for the 2nd course I taught as
a professor, many moons ago. It brought back (mostly) fond memories.

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