Subset-Logic Programming: Application and Implementation,
NORTH CAROLINA UNIV AT CHAPEL HILL DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Subset-logic programming is a paradigm of programming with subset and equality assertions. We propose this paradigm as a logical basis for programming with sets. We present a language called SEL to illustrate the approach. The terms of SEL are the usual first-order terms of Prolog, augmented with one associative-commutative a-c constructor, U, for defining sets. Computationally, we treat assertions as one-way rewrite rules, where the matching used is a restricted form of associative-commutative matching. Unlike Prologs unification, a-c matching could produce multiple matching substitutions, which can effectively serve to iterate over the elements of sets, thus permitting many useful set operations to be stated non-recursively. We also describe the implementation of SEL. We show how WAM-like instructions can be used to compile SEL programs. Because matching rather than unification is used, the read and write modes of get instructions can be identified at compile-time. Two forms of backtracking occur in addition to backtracking upon failure, the implementation also backtracks upon success in order to collect all elements of a set. An important property of a SEL function is whether or not it distributes over nondeterminism in a particular argument. If it does, we can avoid checking for duplicates in this argument, and also avoid constructing the set corresponding to this argument.
- Computer Programming and Software