Set abstraction in functional and logic programming

This paper addresses the declarative and computational issues of incorporating set abstraction into functional and logic programming languages. The main results are the following: (i) Relative set abstraction can combine a lazy higher-order functional programming with not only first-order Horn logic, but also with a useful subset of higher-order Horn logic. Sets, as well as functions, can be treated as first-class objects. (ii) Angelic powerdomains provide the semantic foundation. These are compatible with lazy evaluation and are well-defined over elements from even non-flat (higher-order) domains. (iii) A new computation rule, more efficient than the parallel-outermost rule, is developed and shown to be a correct computation rule. (A simple left-most rule is not adequate for this language.) (iv) Optimizations incorporating ideas from narrowing and resolution greatly improve the efficiency of the interpreter, while maintaining correctness.