# Accession Number:

## ADP004906

# Title:

## Programming with Binary Relations and an Associated Algebra of Programs,

# Descriptive Note:

# Corporate Author:

## ARMY BALLISTIC RESEARCH LAB ABERDEEN PROVING GROUND MD

# Personal Author(s):

# Report Date:

## 1985-02-01

# Pagination or Media Count:

## 14.0

# 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