Introduction
In the early 1980s, knowledge-based systems faced a significant architectural challenge: the divide between high-level knowledge representation (KR) and efficient execution. Typically, a knowledge base (KB) was written in a specialized language that required runtime interpretation, leading to performance bottlenecks and maintenance complexities. This paper, presented at AAAI in 1984, introduces BC, a "very-high-level" programming system designed to bridge this gap by compiling logic assertions directly into optimized Lisp code.
System Architecture
The core innovation of BC is its treatment of KR features as high-level specifications rather than static data structures. The system employs a multi-stage compilation pipeline to transform abstract logic into procedural code.
As shown in the figure above, the pipeline consists of several key components:
- VLogic: A specification language based on first-order predicate logic.
- Logic Assertion Compiler (LAC): This component processes VLogic assertions alongside user-provided "meta-annotations" to produce an intermediate representation in VRL (a rule language).
- Rule Compiler (RC): Utilizing stepwise refinement, the RC transforms abstract rules into low-level, executable Lisp.
Meta-Annotations and Program Synthesis
A critical aspect of the BC system is the use of meta-assertions or annotations. Rather than relying on the compiler to infer the most efficient implementation, the developer provides explicit instructions on how specific logic should be utilized.
These annotations allow for various compilation strategies, such as compile-in-line to bake logic directly into functions or compile-transform to convert forms into equivalent procedural code. Other tags mentioned in the system include triggered-by for forward-chaining demons and computes for backward-chaining functions. By factoring the problem into a logical description and an implementation strategy, BC enables the synthesis of "tangled," highly efficient code from clean, declarative specifications.
Key Insights
The paper shifts the paradigm of knowledge bases from static repositories to active components of a program specification. Key insights include:
- Logic as a Synthesis Tool: Logic is used for program synthesis at compile-time rather than just inference at runtime.
- Uniformity: Using VLogic for both the KB and program logic simplifies system reasoning.
- The Knowledge Compiler: The concept of a "knowledge compiler" allows for the pre-processing of KR features, ensuring that production systems remain performant.
Results and Applications
The BC system demonstrated its utility through several practical applications:
- Self-Hosting: The system was largely written in its own languages; a version of the Rule Compiler was used to compile its own specification, replacing an earlier hand-written Lisp version.
- KR Feature Implementation: The authors successfully implemented complex features like inverse link maintenance (e.g., automatically updating reciprocal relationships) and property inheritance (e.g., deducing attributes of instances from class-level logic) without requiring explicit storage for every instance.
- Integration: BC was integrated into the CHI knowledge-based programming environment, aiding in data structure selection and algorithmic design.
Limitations and Future Work
While promising, the system faced challenges. At the time of publication, the Logic Assertion Compiler (LAC) was still under development. Furthermore, expressing certain KR schemes—such as inheritance from "prototypical" elements—proved difficult in pure logic because the relationships are less direct than standard set quantification. The mapping of abstract relations to non-uniform implementations remains a complex task requiring careful developer guidance through meta-annotations.
Summary updated