Partial order programming (Revisited)

This paper shows the use of partial-order program clauses and lattice domains for functional and logic programming. We illustrate the paradigm using a variety of examples: graph problems, program analysis, and database querying. These applications are characterized by a need to solve circular constraints and perform aggregate operations, a capability that is very clearly and efficiently provided by partial-order clauses. We present a novel approach to their model-theoretic and operational semantics. The least Herbrand model for any function is not the intersection of all models, but the glb/lub of the respective terms defined for this function in the different models. The operational semantics combines topdown goal reduction with monotonic memo-tables. In general, when functions are defined circularly in terms of one another through monotonic functions, a memoized entry may have to monotonically updated until the least (or greatest) fixed-point is reached. This partial-order programming paradigm has been implemented and all examples shown in this paper have been tested using this implementation.