🚀 go-pugleaf

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