Accession Number:

ADA193647

Title:

Subset-Logic Programming: Application and Implementation,

Descriptive Note:

Corporate Author:

NORTH CAROLINA UNIV AT CHAPEL HILL DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Jayaraman, Bharat
• Nair, Anil

Report Date:

1988-02-01

Pagination or Media Count:

14.0

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

Descriptors:

• *COMPUTER PROGRAMMING
• MATCHING
• HIGH LEVEL LANGUAGES
• COMPILERS
• COMPUTER LOGIC

Subject Categories:

• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE