Set abstraction in functional and logic programming
Frank S. K. Silbermann, Bharat Jayaraman · 1989
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.