Logic specifications for compiling

The essential difficulty with building and maintaining large programming systems is coping with their complexity. The primary method for dealing with such complexity is to factor the system by breaking it down into smaller parts that can be understood nearly independently. However, the most well-factored, understandable description of a problem is inherently inefficient if it is considered as a program specification to be implemented directly. In this dissertation I describe a system-building system, BC, that allows a problem to be described separately from how its solution is implemented. Producing an efficient implementation from the problem description is treated as a separate problem that is solved by BC with further specification by the system designer to make it well-defined. The factorization frees the description of the problem from responsibility for efficiency, allowing the problem description itself to be better factored. On the other hand, the description of the implementation need not preserve the factorization of the problem specification, so an efficient implementation is possible. Another side of the problem of complexity in large systems is managing detail. Much of an implementation of a problem solution consists of schemes for representing entities of the problem or solving particular types of sub-problems. Detail can be characterized as the code that follows from a well-defined scheme. The specification language for BC allows schemes to be specified in terms of an invariant and its uses. BC is capable of treating the invariant as a constraint, by producing code that maintains the invariant as well as coding the uses of the invariant. Compilation consists of using assertions to instantiate particular procedural rule schemas, each one of which corresponds to a specialized deduction, and then compiling the resulting rules to LISP. The rule language is a convenient intermediate between the logic assertion language and the implementation language in that it has both a logic interpretation and a well-defined procedural interpretation. Most of the optimization is done at the logic level. The approach is demonstrated by using it in the programming environment of the CHI Knowledge-based Programming system. Its uses include describing and implementing the database manager, the dataflow analyzer, the project management component and the system's compiler itself. It is particularly convenient for developing knowledge representation schemes, for example for such things as property inheritance and automatic maintenance of inverse property links.