Programming with Binary Relations and an Associated Algebra of Programs,
Abstract
Mathematical logic is a particularly fruitful vehicle for expressing programs in a declarative style and seems well suited for artificial intelligence applications. On the other hand, Horn clause logic limited to conjunction and disjunction is somewhat primitive and low level. When programs are written as arbitrary n-ary relations, as in Prolog, hierarchically constructing more complex programs from simpler ones is often quite awkward. John Backus, in his 1977 Turing award lecture, described a well structured and expressive functional programming style along with a useful algebra of programs. However, programs as functions are less general than programs as relations. This work restricts logic programs to only binary relations and shows how to combine the backtracking of logic programming and the higher order operations of functional programming. This combination allows us to define a richer set of program forming operations that includes program inversion. We include new optimization rules and point out which FP-like rules are invalid in a relational context. As an example, we show how the algebra is used by synthesizing, from specifications, an efficient program for the N queens problem. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1985
- Accession Number
- ADP004906
Entities
People
- P. Broome
Organizations
- Ballistic Research Laboratory