Accession Number : ADA193647

Title :   Subset-Logic Programming: Application and Implementation,

Corporate Author : NORTH CAROLINA UNIV AT CHAPEL HILL DEPT OF COMPUTER SCIENCE

Personal Author(s) : Jayaraman, Bharat ; Nair, Anil

PDF Url : ADA193647

Report Date : Feb 1988

Pagination or Media Count : 14

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.

Descriptors :   *COMPUTER PROGRAMMING, MATCHING, HIGH LEVEL LANGUAGES, COMPILERS, COMPUTER LOGIC

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE