Experience with KRL-0: One Cycle of a Knowledge Representation Language

Daniel G. Bobrow, Terry Winograd

Introduction

In 1977, the field of Artificial Intelligence was undergoing a significant shift. Researchers were moving away from purely logic-based systems toward representation schemes capable of handling the ambiguity, context, and "common sense" inherent in human thought. This paper provides a candid "post-mortem" of KRL-0, the first experimental iteration of the Knowledge Representation Language (KRL). Developed by a team from Xerox PARC and Stanford, including AI pioneers Daniel Bobrow and Terry Winograd, KRL-0 represented an ambitious attempt to bridge the gap between theoretical intuitions and the practical realities of implementation.

Architectural Foundations of KRL-0

KRL-0 was implemented in INTERLISP and centered around several novel architectural choices designed to support sophisticated language understanding. The core philosophy treated reasoning as a process of matching new information against stored prototypes.

Units and Slots

Knowledge was organized into "Units," representing conceptual entities, which contained "Slots" for specific attributes. Unlike strict definitions in formal logic, KRL-0 utilized Prototypes. Reasoning involved comparing a new instance to a known prototype and noting the differences, allowing the system to handle partial information and multiple viewpoints (e.g., viewing a heart as both a mechanical pump and an anatomical organ).

Procedural Attachment and Control

To move beyond static data structures, KRL-0 employed "procedural attachment." Mechanisms known as "triggers" and "traps" allowed LISP code to execute automatically when information was added to or requested from a slot. To manage the resulting complexity, the authors implemented a multi-level Agenda—a scheduler that prioritized tasks ranging from immediate data propagation to "last-ditch" brute-force searches.

Hypothetical Worlds

The system supported "hypothetical worlds," enabling the testing of assumptions and the exploration of "what-if" scenarios without permanently altering the primary knowledge base. This was crucial for handling contingent information and maintaining consistency across different contexts.

Experimental Domains

Rather than using the massive corpora common in modern AI, the authors evaluated KRL-0 through nine distinct "mini-projects" that tested the language's versatility:

  • Story Understanding (SAM): A reproduction of the Yale "Script Applier Mechanism" for analyzing short stories about restaurant visits.
  • Medical Diagnosis: An implementation of a model for diagnosing kidney disease.
  • Problem Solving: A solver for cryptarithmetic puzzles (e.g., SEND + MORE = MONEY).
  • Domain Modeling: Legal reasoning, kinship terms in English and Sherpa, and human memory simulation.

Key Insights and Qualitative Results

The researchers successfully demonstrated that KRL-0 could replicate the functionality of several specialized AI systems within a single, unified framework. However, the most valuable outcomes were the qualitative insights gained from the system's failures.

Reasoning as Recognition

The experiments confirmed that a significant component of intelligence is recognition—identifying that a new situation "looks like" a stored prototype. This validated the frame-based approach but also highlighted the "clumsiness" of rigid categorization. KRL-0 forced every unit into specific categories (like Individual or Abstract), which proved too restrictive for the fluid nature of real-world knowledge.

The Need for Meta-Description

A critical realization was the necessity for the language to describe itself. The authors identified a need for meta-description—a way for one description to describe another—to handle complex concepts like viewpoints and perspectives more elegantly.

The LISP Interface Gap

Because KRL-0 was embedded in INTERLISP, programmers frequently bypassed the language's declarative limitations by writing raw LISP code. While this improved efficiency, it defeated the purpose of a high-level representation language and created a "gap" between the intended model and the actual implementation.

Limitations and the Path to KRL-1

The "post-mortem" revealed several practical bottlenecks:

  • Performance: The general-purpose "Matcher" engine was often too slow, leading programmers to write manual shortcuts.
  • Syntax: The use of nested brackets ((), {}, <>) resulted in cumbersome, unreadable code.
  • Memory Constraints: The 18-bit address space of the PDP-10 computers imposed a hard ceiling on model complexity, forcing researchers to spend significant effort optimizing code for memory.
  • Inheritance: The lack of automatic attribute inheritance made programming tedious compared to modern object-oriented paradigms.

These lessons directly informed the design of KRL-1, which aimed for a more uniform meta-description system, a simplified syntax (reminiscent of modern indentation-based languages), and a compiler to optimize the matching process. KRL-0 thus served its purpose as a vital "first cycle" in the iterative development of knowledge representation systems.

Summary updated

BibTeX
@inproceedings{bobrow1977experience,
  author = {Daniel G. Bobrow and Terry Winograd},
  title = {{Experience with KRL-0: One Cycle of a Knowledge Representation Language}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure