🚀 go-pugleaf

In message <22547@alice.att.com> dtd. 11 Apr 92 17:26:22 GMT, Fernando writes:

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

I'm not sure exactly which "inference system" is alluded to above, but the 
above optimization works very nicely in the setting of a functional language.
(The functional languages of interest to me are "logic languages" whose
declarative semantics is set of the logical consequences of equations, and 
whose operational semantics or "inference" is term-rewriting.)  
David Plaisted noted the need to avoid forming explicit sets in our 
1987 FPCA paper, and this idea was given more concrete form in our 
1988 SLP/ICLP paper. The SEL compilers (versions 1 and 2) take programmer-
supplied mode annotations, e.g. mode foo(yes,no,yes,no), indicating precisely
in which argument positions a function distributes over union, and it 
generates WAM-like code so that intermediate set formation and checking
of duplicates are by-passed in these arguments.  (The SEL compilers do not 
support this annotation for arbitrary (i.e. non-set-valued) functions, 
e.g., min, but the basic idea is the same and can be extended to this
case as well.)  So, I think the efficiency benefits referred to by 
Fernando are not the exclusive virtue of bottom-up procedures.  

In <22547@alice.att.com> dtd. 11 Apr 92 17:26:22 GMT, Fernando continues:

> 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
> haven't seen (or had yet the time to investigate) an exact connection.
> Anyone know of papers on those issues?

Regarding 1) and 2), in the paper "Programming with Equations, Subsets, 
and Relations", NACLP 89, Plaisted and I mention a sufficient (but I
believe crucial) condition ---subset-monotonicity--- on allowed expressions 
on the rhs of equations/subset assertions so that a lfp semantics can be 
given.  That paper covers such a wide ground that we did not have space to 
address any one topic in much detail; and we didn't discuss fixed-point 
semantics explicitly, although it was very much in our considerations.
I should add that we have considerably improved upon the ideas in
that paper in the meantime.

Regarding 4), may I ask what is a "dynamic-programming solution", i.e.,
would you not entertain a top-down solution with memoization?   If not, 
why not?  This is a crucial question,  as it has serious implications for all 
WAM-based implementations.

Bharat Jayaraman
bharat@cs.buffalo.edu