Subset-Logic Programming: Application and Implementation,
Abstract
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 Prolog's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1988
- Accession Number
- ADA193647
Entities
People
- Anil P. Nair
- Bharat Jayaraman
Organizations
- University of North Carolina at Chapel Hill