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

This paper details the first iteration of KRL (Knowledge Representation Language), KRL-0, focusing on the design, implementation, and lessons learned from its use in various AI projects. The authors emphasize that the primary value of this cycle was in identifying problems and limitations, which directly informed the design of the next iteration, KRL-1.

TL;DR

This paper presents the first cycle of KRL, a knowledge representation language designed for building sophisticated AI systems. The authors detail the implementation of KRL-0 and its use in several experimental projects, highlighting the significant challenges and limitations encountered. These insights were crucial for guiding the development of the subsequent KRL-1.

What Problem Does This Paper Address?

The paper addresses the fundamental challenge of creating a powerful and flexible knowledge representation language (KRL) capable of supporting complex AI systems, particularly those involved in understanding language. The authors' goal was to move beyond existing approaches by organizing knowledge around conceptual entities with rich descriptions and associated procedures. They aimed to develop a system that could handle partial knowledge, represent information from multiple viewpoints, and support reasoning based on recognition and comparison with prototypes. This iterative approach, involving cycles of design, implementation, and testing, was intended to uncover the practical difficulties and limitations of their design intuitions.

Methods

KRL-0 was implemented in INTERLISP, leveraging its existing programming facilities. The design was based on several core intuitions:

  • Conceptual Entities: Knowledge organized around entities with descriptions and procedures.
  • Partial Knowledge: Descriptions accommodating multiple viewpoints and partial information.
  • Prototype-Based Reasoning: Reasoning dominated by comparing new information to stored prototypes.
  • Active Processes: Intelligent programs requiring multiple active processes with explicit scheduling.
  • Information Clustering: Knowledge clustered to reflect usage and resource constraints.
  • Flexibility: A language providing underlying tools rather than embodying specific strategies or representations.

The implementation included basic structure manipulation, a reader/printer, an agenda manager/scheduler, a procedure directory, and a rudimentary matcher. Several utilities were developed, including a data structure manipulation package (USYS) and an on-line cross-reference system (NUtils). The paper describes the use of "units" as the primary data structure, which could have various categories (Individual, Manifestation, Basic, Specialization, Abstract). Procedural attachment, triggers, and a signal table were used to control behavior and propagate information.

Datasets

Not explicitly discussed as distinct datasets. The paper describes nine small projects that served as testbeds for KRL-0. These projects involved tasks like:

  • Cryptarithmetic problem solving
  • Legal reasoning implementation
  • Concept learning (ARCH)
  • Drawing inferences about objects (COIL)
  • Simulating human memory access (FLOW)
  • Reasoning about physiological processes (PHYSIOLOGY)
  • Comparing kinship terms (KINSHIP)
  • Story analysis (SAM)
  • Medical diagnosis

These projects were used to test specific aspects of the KRL-0 language and system.

Key Insights and Ideas

  • The Value of Failure: The authors emphasize that the most significant lessons learned came from the difficulties and disappointments encountered, rather than successes. This iterative process of identifying problems was key to refining the language.
  • Limitations of Fixed Categories: The initial categorization of units (Individual, Manifestation, Basic, Specialization, Abstract) proved too limiting in practice, especially for specialized domains like medicine.
  • Viewpoints are Crucial but Clumsy: The need to "chunk" knowledge into relevant units and associate context (viewpoints) with descriptions was recognized, but KRL-0's mechanisms for this (attaching features to descriptors, embedding in contingencies) were found to be clumsy and ad hoc.
  • Prototype vs. Instance Complexity: Representing the complex relationship between prototypes and instances (e.g., a disease being both an instance of "Disease" and a prototype for specific cases) posed challenges.
  • Inheritance is Tricky: The basic inheritance mechanism in KRL-0 did not automatically handle slot inheritance, making it awkward to program cases where slots should be inherited. A "further specification" mechanism was proposed but not fully implemented.
  • Context-Dependent Descriptions are Hard to Factor: Combining object-factored databases with context-dependent descriptions led to difficulties in factoring information across different "worlds" or hypothetical scenarios.
  • Data Structure Manipulation is Low-Level: KRL-0 was not fully declaratively recursive, requiring direct LISP manipulation of data structures for certain operations, leading to ad hoc solutions and complexity.
  • Deletion is an Unnatural Act: The language's bias towards additive descriptions made deleting or replacing structures difficult without resorting to LISP, causing issues with time-dependent values and efficiency.
  • Matcher Flexibility vs. Detail: While the KRL-0 matcher offered great flexibility in defining strategies, the low level of control made it difficult to write general strategies, leading to ad hoc solutions and potential issues with semantic equivalence.
  • Bindings and Circularity: Extracting bindings from matches and controlling circular reasoning were significant problems, often requiring special, ad hoc mechanisms.
  • Interface Between KRL and LISP: The reliance on LISP for procedures created awkward constructs and highlighted the need for a more integrated procedural language.
  • Underdeveloped Facilities: Key areas like sets, sequences, indexing, and scheduling were provided as primitives, requiring users to build more complex functionalities themselves, leading to duplicated effort.
  • Address Space Limitations: The embedding of KRL-0 within INTERLISP severely limited available address space, forcing compromises in project scope and driving the need for more efficient memory management in KRL-1.

Key Results

  • Successful Implementation of KRL-0: Despite its limitations, KRL-0 was implemented and used in nine distinct projects, demonstrating the feasibility of the core design ideas.
  • Identification of Key Problems: The primary "result" was the comprehensive identification of KRL-0's shortcomings, which provided a clear roadmap for KRL-1. These included issues with representation, matching, procedural attachment, and system facilities.
  • Demonstration of Iterative Design: The paper serves as a case study for the iterative development of AI languages, showing how practical experience with an initial version directly informs the next.
  • Insights into AI System Building: The projects highlighted the practical challenges of building complex AI systems, including memory limitations, the need for robust error handling, and the difficulty of managing large, evolving codebases.

Limitations and Future Work

Limitations Acknowledged:

  • Basic Representation Problems: Difficulties in expressing semantic/logical structures, manipulating descriptions, matcher shortcomings, and an awkward KRL-LISP interface.
  • Shortcomings in Facilities: Lack of standardized packages, infelicitous syntax, and cramped address space.
  • Ad Hoc Solutions: Many projects resorted to "patches" or LISP-level manipulations to overcome KRL-0's limitations.
  • Incomplete Documentation: The KRL-0 manual quickly became obsolete, forcing reliance on source code and discussions.
  • Memory Constraints: The limited address space of the INTERLISP environment was a major bottleneck.

Future Work (KRL-1):

  • Semantic Regularity: A substantial shift towards semantic regularity and a formal understanding of reasoning processes.
  • Uniform Meta-Description: A unified approach to meta-description covering features, traps, triggers, and index terms.
  • Structured Interpreter: An interpreter operating on the meaning of forms, not just their details, for a more uniform framework.
  • Data Compaction: Mechanisms to represent internal structures as full-fledged descriptions for manipulation.
  • Compiler: A compiler for Match, Seek, and Describe expressions to reduce overhead.
  • Uniform System Events: A more general notion of system events for procedural attachment.
  • Simplified Syntax: Indentation-based syntax, "footnotes" for meta-descriptions, and simplified set/sequence notations.
  • Simplified Categories and Agendas: Avoiding specific commitments made in KRL-0.
  • Expanded Facilities: Enhanced support for sets, sequences, scheduling, time-dependent values, category hierarchies, matching, and multiple worlds.
  • Addressing Address Space: Exploring solutions like swapping mechanisms, though seen as a temporary fix.
  • Larger Systems: Focusing on fewer, larger projects for KRL-1 testing to explore emergent problems of scale.
  • Comprehensive Documentation: Plans for more extensive documentation than for KRL-0.
  • Procedural Formalism: Postponing the design of a comprehensive programming formalism as part of KRL-1, but recognizing its importance for future versions.

Summary updated

BibTeX
@inproceedings{1977experience,
  title = {{Experience with KRL-0: One Cycle of a Knowledge Representation Language}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}

Loading related content...

Figure