HCPRVR: An Interpreter for Logic Programs

Daniel L. ChesterAAAI 1980

Abstract

HCPRVR (Horn Clause theorem PRoVeR) is a lightweight, Lisp-based interpreter designed to integrate the declarative power of Horn clause logic programming into the Lisp environment. By representing logic as Lisp data and utilizing a specialized unification algorithm based on binding lists, HCPRVR provides a flexible and memory-efficient framework for building complex systems. This paper details the architecture of the interpreter, its support for procedural attachment, and its application in Natural Language Processing (NLP). Results indicate that HCPRVR achieves performance comparable to contemporary Prolog interpreters while maintaining the development flexibility of the Lisp ecosystem.

Introduction

In the late 1970s and early 1980s, logic programming—specifically the use of Horn clauses—emerged as an exceptionally clear and efficient paradigm for complex software development. However, the primary vehicle for this paradigm, Prolog, typically existed as a standalone environment. For researchers deeply embedded in the Lisp ecosystem, transitioning to Prolog meant sacrificing Lisp’s legendary flexibility and mature toolsets. HCPRVR was developed to bridge this gap, offering a "best of both worlds" solution: an elegant logic programming system that operates natively within Lisp, maintaining high performance for real-world applications like Natural Language Processing.

System Architecture

Logic Representation and the PROVE Function

HCPRVR represents logic programs as ordered lists of axioms (facts or rules) using Lisp-like syntax. The heart of the interpreter is the PROVE function, which operates on the problem reduction principle. Using a depth-first search strategy, PROVE manages a stack of subproblems, attempting to resolve them by matching them against the stored axiom base.

Unification via Binding Lists

To connect variables to values, HCPRVR employs a modified unification algorithm within its MATCH function. A significant innovation in HCPRVR is its avoidance of computationally expensive variable renaming or back-substitution. Instead, the system utilizes "binding lists"—essentially environments where a variable’s identity is defined by both its name and the specific list to which it belongs. This approach is significantly more memory-efficient than the "copy and rename" strategies common in earlier theorem provers.

Procedural Attachment

One of the system's most powerful features is procedural attachment. Developers can designate specific predicate names as Lisp functions. When the interpreter encounters these predicates during a proof, it executes the corresponding Lisp code directly rather than searching for a logical proof. This allows for a hybrid programming model where declarative logic handles high-level structure while procedural Lisp code manages low-level tasks such as complex arithmetic or inequality tests.

Applications and Insights

Reversible Grammars in NLP

HCPRVR was extensively used for natural language parsing. Because the system treats grammar rules as logical axioms, it supports the concept of reversible grammars. Theoretically, the same set of axioms used to parse a sentence (transforming words into semantic structures) can be used to generate a sentence (transforming semantic structures back into words). The paper demonstrates this utility through a walkthrough of parsing the sentence "THE CAT IS ON THE MAT."

Development Efficiency

A core philosophy behind HCPRVR is the prioritization of human development efficiency over raw execution speed. The author argues that the ability to write and debug code quickly within a familiar Lisp environment provides a greater net benefit to researchers than marginal gains in machine cycles. The integration of logic and functional programming allows developers to use the most appropriate tool for each specific sub-task.

Performance and Results

Despite its lightweight design, HCPRVR demonstrated impressive technical specifications:

  • Compactness: The compiled code was remarkably small, occupying only 2000 octal words of binary space.
  • Execution Speed: The system performed at speeds comparable to contemporary Prolog interpreters. A version implemented in C for the PDP11/60 ran at approximately half the speed of the compiled Lisp version on a DEC KI10.
  • Practical Validation: The system was used successfully for over a year at the University of Texas at Austin to develop research-grade NLP systems, proving its stability beyond simple theoretical exercises.

Limitations and Future Work

While effective, HCPRVR is not without limitations. Its reliance on standard depth-first search makes it susceptible to infinite loops when encountering certain recursive logical definitions—a common challenge in early logic programming. Additionally, while the system proved adequate for the NLP tasks of its time, the author noted that further optimizations in search strategies and handling of large axiom sets would be necessary for scaling to even more complex domains.

Summary updated

BibTeX
@inproceedings{chester1980hcprvr,
  author = {Daniel L. Chester},
  title = {{HCPRVR: An Interpreter for Logic Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure